#!/usr/bin/env python
# encoding: utf-8

"""
Algorithmique et structures de données (L2 année 2010/2011)
Correction du partiel 2009/2010
"""

# Exercice 1: Fonctions récursives

def somme(l):
	if vide(l):
		return 0
	else:
		return tete(l) + somme(queue(l))

def ordre(l):
	if vide(l) or vide(queue(l)):
		return True
	elif tete(l) > tete(queue(l)):
		return False
	else:
		return ordre(queue(l))

def apparait(x, n, l):
	if n <= 0:
		return True
	elif vide(l):
		return False
	elif tete(l) == x:
		return apparait(x, n-1, queue(l))
	else:
		return apparait(x, n, queue(l))

def double(x, l):
	if vide(l):
		return liste()
	elif tete(l) == x:
		return cons(x, cons(x, double(x, queue(l))))
	else:
		return cons(tete(l), double(queue(x, l)))

# Exercice 2: Listes pointées

# I. Listes chaînées simples

class Noeud:
	pass
def noeud(x):
	n = Noeud()
	n.valeur = x
	n.suivant = None
	return n

class Liste:
	pass
def liste(x):
	l = Liste()
	n = noeud(x)
	l.premier = n
	l.curseur = n
	return l

def lire(l):
	return l.curseur.valeur

def deplacer_droite(l):
	l.curseur = l.curseur.suivant

def debut(l):
	return l.curseur == l.premier

def fin(l):
	return l.curseur.suivant == None

def ajouter_droite(x, l):
	n = noeud(x)
	n.suivant = l.curseur.suivant
	l.curseur.suivant = n

# Les fonctions deplacer_droite, debut, fin et ajouter_droite font un nombre constant d'opérations, indépendamment du nombre d'éléments dans la liste.

def deplacer_gauche(l):
	n = l.premier
	while n.suivant != l.curseur:
		n = n.suivant
	l.curseur = n

def ajouter_gauche(x, l):
	if debut(l):
		n = noeud(x)
		n.suivant = l.premier
		l.premier = n
	else:
		p = l.premier
		while p.suivant != l.curseur
			p = n.suivant
		n = noeud(x)
		n.suivant = l.curseur
		p.suivant = n

# Sur une liste de longueur n, les fonctions ajouter_gauche et deplacer_gauche peuvent effectuer de l'ordre de n opérations (il faut parcourir la liste pour trouver le noeud qui se trouve juste avant le curseur).

# II. Listes doublement chaînées

class Noeud:
	pass
def noeud(x):
	n = Noeud()
	n.valeur = x
	n.precedent = None
	n.suivant = None
	return n
	
class Liste:
	pass
def liste(x):
	l = Liste()
	n = noeud(x)
	l.premier = n
	l.dernier = n
	l.curseur = n
	return l

def deplacer_gauche(l):
	l.curseur = l.curseur.precedent

def ajouter_gauche(x, l):
	n = noeud(x)
	if l.curseur == l.premier:
		l.premier = n
	else:
		l.curseur.precedent.suivant = n
		n.precedent = l.curseur.precedent
	n.suivant = l.curseur
	l.curseur.precedent = n

# Les fonctions deplacer_gauche et ajouter_gauche ont maintenant une complexité constante.

# III. Piles

class Noeud:
	pass
def noeud(x):
	n.valeur = x
	n.suivant = None
	return n

class Liste:
	pass
def liste(x):
	l = Liste()
	n = noeud(x)
	l.gauche = n
	l.droite = None
	return l

def deplacer_gauche(l):
	n = l.gauche
	l.gauche = n.suivant
	n.suivant = l.droite
	l.droite = n

def deplacer_droite(l):
	n = l.droite
	l.droite = n.suivant
	n.suivant = l.gauche
	l.gauche = n

def ajouter_droite(x, l):
	n = noeud(x)
	n.suivant = l.droite
	l.droite = n

def ajouter_gauche(x, l):
	n = noeud(x)
	n.suivant = l.gauche.suivant
	l.gauche.suivant = n

def debut(l):
	return l.gauche.suivant == None

def fin(l):
	return l.droite == None

# Toutes ces fonctions ont une complexité constante.

# IV. Tableaux

MAX = 1000

class Liste:
	pass
def liste(x):
	l = Liste()
	l.tableau = [None]*MAX
	l.tableau[0] = x
	l.longueur = 1
	l.curseur = 0

# Les fonctions de déplacement se font en temps constant (on change la valeur de l.curseur). Les insertions à droite et à gauche sont en temps linéaire (il faut décaler les valeurs dans le tableau qui sont à droite de la position où l'on insère la nouvelle valeur).