# -*- coding: utf-8 -*-
#
#Modulo Array
#
#Author: Emilio U. Giuffrida & Students
#Date: 17/10/2018
#
#
#TODO:
#
#1- add comments
#2- add shell sort,insertion sort, quicksort and merge sort

from array import *
import os
import random
import sys


def creaArrayIntStatico(n_Elementi):
	newArray=array("i", [])

	for i in range(0, n_Elementi):
		newArray.append(sys.maxint)

	return newArray


def creaArrayIntDinamico():
	return array("i", [])


def creaArrayFloatStatico(n_Elementi):
	newArray=array("f", [])

	for i in range(0, n_Elementi):
		newArray.append(-1.0)

	return newArray

def creaArrayFloatDinamico():
	return array("f", [])


def stampaArray(myVector):

	state = isEmpty_v2_0(myVector)

	if (state == True):
		print ("L'array e' vuoto!")

		return -1
	else:
		lenght = len (myVector)
		for i in range (0, lenght):
			print myVector[i],

		print ""

		return 0


def riempiArrayDinamico(n_Elementi, myVector):

	for i in range(0, n_Elementi):
		nuovoElemento=random.randint(1,500)
		myVector.append(nuovoElemento)

	return 0


def riempiArrayStatico(myVector):
	state = isEmpty_v2_0(myVector)

	if (state == True):
		print ("L'array e' vuoto!")

		return
	else:
		lenght = len (myVector)
		for i in range (0, lenght):
			nuovoElemento=random.randint(1,500)
			myVector[i]=nuovoElemento
			print "Elemento inserito in posizione", i,":",myVector[i]

		print ""

		return

#Genera un IndexError: array index out of range
def svuotaArray_conErrore(n_Elementi, myVector):

	for i in range(0, n_Elementi):
		elementToRemove=myVector[i]
		myVector.remove(elementToRemove)

		print("Vettore aggiornato", myVector)

	return


def svuotaArrayDinamico_con_errore(n_Elementi, myVector):

	nElementiDecrementata = n_Elementi

	while(nElementiDecrementata>0):
		headElement=myVector[0]
		myVector.remove(headElement)
		nElementiDecrementata = nElementiDecrementata -1

		print("Vettore aggiornato", myVector)

	return



def svuotaArrayDinamico(myVector):

	state=is_Empty_v2_0(myVector)

	if (state==True):
		print ("Errore! il vettore è già vuoto!")
	else:
		nElementiDecrementata = len(myVector)

		while(nElementiDecrementata>0):
			headElement=myVector[0]
			myVector.remove(headElement)
			nElementiDecrementata = nElementiDecrementata -1

			print("Vettore aggiornato", myVector)

	return



def svuotaArrayStatico(myVector):
	state = isEmpty_v2_0(myVector)

	if (state == True):
		print ("L'array e' vuoto!")

		return False
	else:
		lenght = len (myVector)
		for i in range (0, lenght):
			myVector[i]=sys.maxint

	return True


def clonaArray_conIterator(myVector):
	clonato=array('i',[])

	for elemento in myVector:
		clonato.append(elemento)

	return clonato


def clonaArray_conIndice(myVector):
	clonato=array('i',[])

	lunghezza=len(myVector)
	for i in range (0, lunghezza-1):
		elemento=myVector[i]
		clonato.append(elemento)

	return clonato


def eliminaUguali(myVector):
	newVector=array('i',[])

	for elemento in myVector:
		if elemento not in newVector:
			newVector.append(elemento)

	return newVector


def isEmpty_v1_0(myVector):
	lunghezza=len(myVector)

	if (lunghezza==0) :
		return 1
	else:
		return 0

def isEmpty_v1_1(myVector):
	lunghezza=myVector.count

	if (lunghezza==0) :
		return 1
	else:
		return 0

def isEmpty_v2_0(myVector):
	trueOrFalse = ( len(myVector) == 0 )

	return trueOrFalse

def isEmpty_v2_1(myVector):
	trueOrFalse = ( myVector.count == 0 )

	return trueOrFalse

def isEmpty_v3_0(myVector):
	return ( len(myVector) == 0 )


def isEmpty_v3_1(myVector):
	return ( myVector.count == 0 )


def isFull(myVector):
	for index in range (0,len(myVector)):
		if (myVector[index]!= sys.maxint):
			continue
		else:
			return 0

def isFull_v2_0(myVector):
	for i in myVector:
		if (i != -1 and -1.0):
			a=True
		else:
			a=False
			break
	return a


def isFull_v2_1(myVector):
	for i in myVector:
		if (i== -1 and -1.0):
			return False
	return True


def separaElementi(myVector):

	arrayPari=array("i",[])
	arrayDispari=array("i",[])

	contaElementiPari=0
	contaElementiDispari=0

	for element in myVector:

	if ((element%2) == 0):
		arrayPari.append(element)
	else:
		arrayDispari.append(element)

	return


def scambiaOrdine(myVector):

	lunghezza=len(myVector)

	halfLenght=lunghezza/2

	for i in range (0, halfLenght-1):

		aux=myVector[i]
		myVector[i]=myVector[(lunghezza-1)-i]
		myVector[(lunghezza-1)-i]=aux

	print "L'array invertito e': ", myVector

	return



def shift_sinistra(myVector):
	headElement=myVector[0]
	myVector.remove(headElement)
	myVector.append(headElement)

	print ("Vettore dopo lo shift a sinistra:", myVector)
	return 0

def shift_destra(myVector):
	numeroElementi=len(myVector)

	tailElement=myVector[numeroElementi-1]
	myVector.remove(tailElement)
	myVector.insert(0,tailElement)

	print ("Vettore dopo lo shift a destra:", myVector)
	return 0


def rotazione_sx(myVector):
	for  n_Elementi in myVector:
		shift_sinistra (myVector)

	return 0


def rotazione_dx(myVector):
	for  n_Elementi in myVector:
		shift_destra (myVector)

	return 0


def shiftASinistra_C (myVector):
	l= len(myVector)
	headElement=myVector[0]

	for i in range(0, l-1):
		myVector[i]=myVector[i+1]

	myVector[l-1]=headElement

	print ("Vettore shiftato a sx:", myVector)

	return 0


def shiftADestra_C(myVector):
	l= len(myVector)
	tailElement = myVector[l-1]

	#Per scandire l'array in ordine inverso
	for i in xrange(l - 1, -1, -1):
		if (i<=l-1) :
			myVector[i]=myVector[i-1]

	myVector[0]=tailElement

	print ("Vettore shiftato a dx: ", myVector)

	return 0



def selectionSort(myVector):

	i=0
	j=0
	comodo=0


	n=len(myVector)
	for i in range(i, n-i):
		j=i+1

		for j in range(j, n):

			if(myVector[i]>myVector[j]):
				comodo=myVector[i]
				myVector[i]=myVector[j]
				myVector[j]=comodo


	return


def bubbleSort(myVector):

	N=len(myVector)
	Continua=True

	while(Continua):

		Continua=False
		for i in range(0, N-1):
			if(myVector[i]>myVector[i+1]):
				comodo=myVector[i]
				myVector[i]=myVector[i+1]
				myVector[i+1]=comodo
				Continua=True


	return


def shakerSort(myVector):

	numeroElementi= len(myVector)
	continua=True
	while continua==True:
		superiore=numeroElementi
		continua=False
		for i in range(0, superiore-1):
			if(myVector[i]>myVector[i+1]):
				aiuto=myVector[i]
				myVector[i]=myVector[i+1]
				myVector[i+1]=aiuto

				continua=True
				superiore=i

		for i in range(superiore-1, 0):
			if(myVector[i]>myVector[i-1]):
				aiuto=myVector[i]
				myVector[i]=myVector[i-1]
				myVector[i-1]=aiuto

				continua=True
				superiore=i
		print myVector
	return


def insertionSort(alist):
   for index in range(1,len(alist)):

     currentvalue = alist[index]
     position = index

     while position>0 and alist[position-1]>currentvalue:
         alist[position]=alist[position-1]
         position = position-1

     alist[position]=currentvalue

def shellSort(alist):
    sublistcount = len(alist)//2
    while sublistcount > 0:

      for startposition in range(sublistcount):
        gapInsertionSort(alist,startposition,sublistcount)

      sublistcount = sublistcount // 2

def gapInsertionSort(alist,start,gap):
    for i in range(start+gap,len(alist),gap):

        currentvalue = alist[i]
        position = i

        while position>=gap and alist[position-gap]>currentvalue:
            alist[position]=alist[position-gap]
            position = position-gap

        alist[position]=currentvalue

def RicercaBinaria(vettore, x):

	n=len(vettore)
	primo = 0
	ultimo = n-1
	trovato = False
	indice=0

	while (primo <= ultimo) and (not trovato):
		centro = (primo + ultimo) / 2

		if (vettore[centro] == x):
			trovato = True
			indice=centro

			print "L'elemento ricercato e' in posizione ", indice

		elif (vettore[centro] < x):
				primo = centro + 1

		else:
			ultimo = centro - 1

	return trovato



#------------
#Main program
#------------
def main():
	#Pulisce lo schermo
	os.system('clear')

	numeroElementi=input("Inserisci il numero di elementi: ")
	staticVector = creaArrayIntStatico(numeroElementi)

	#print ("Array di interi statico vuoto: ", staticVector)
	stampaArray(staticVector)

	#dynamicVector = creaArrayIntDinamico()

	#print ("Array di interi dinamico vuoto: ", dynamicVector)
	#riempiArrayDinamico(numeroElementi, vector)

	riempiArrayStatico(staticVector)
	stampaArray(staticVector)
	#print ("Array riempito: ", staticVector)

	#arrayClonato1= clonaArray_conIterator(vector)
	#print ("Array clonato con iteratore", arrayClonato1)

	#arrayClonato2= clonaArray_conIndice(vector)
	#print ("Array clonato con indice", arrayClonato2)

	#svuotaArray_conErrore(numeroElementi, vector)
	#svuotaArray(numeroElementi, vector)

	#print ("Array svuotato: ", vector)


if (__name__=="__main__"):
	main()