## Lista Duplamente Encadeada Circular

class DNodo:
    def __init__(self, dado = None):
        self.dado = dado
        self.proximo = None
        self.anterior = None

    def __str__(self):
        return self.dado

class LDECircular:
    def __init__(self):
        self.sentinela = DNodo()
        self.sentinela.proximo = self.sentinela
        self.sentinela.anterior = self.sentinela
        self.tam = 0

    def is_empty(self): ## verifica se lista é vazia
        if (self.sentinela.proximo == self.sentinela and
            self.sentinela.anterior == self.sentinela) or self.tam == 0:
            return True
        else:
            return False

    def primeiro(self):
        if self.is_empty():
            print('Lista Vazia')
            return
        else:
            return self.sentinela.proximo

    def ultimo(self):
        if self.is_empty():
            print('Lista Vazia')
            return
        else:
            return self.sentinela.anterior

    def inserir(self, novo): # inserirFim (append)
        if isinstance(novo, DNodo): # se for um DNodo
            
            ## nao eh necessario testar vazio
            ultimo = self.sentinela.anterior
            
            ultimo.proximo = novo
            novo.anterior = ultimo
            novo.proximo = self.sentinela
            self.sentinela.anterior = novo
        else:
            raise Exception("Método inserir espera um DNodo")
            
        self.tam += 1

    def inserir_inicio(self):
        if isinstance(novo, DNodo): # se for um DNodo
            pass
        else:
            raise Exception("Método inserirInicio espera um DNodo")
        
        self.tam += 1
    
    def remover(self): # remover_inicio
        removido = self.sentinela.proximo
        self.sentinela.proximo = removido.proximo
        removido.proximo.anterior = self.sentinela
        
        self.tam -= 1
        return removido

    def remover_fim(self): # removerFim
        removido = self.sentinela.anterior
        removido.anterior.proximo = self.sentinela
        self.sentinela.anterior = removido.anterior

        self.tam -= 1
        return removido

    def get(self, index): # obter item em determinada posicao
        if not self.is_empty():
            i = 0
            item = self.sentinela.proximo                
            while (item != self.sentinela):
                if (i == index):
                    return item
                
                item = item.proximo
                i += 1

    def buscar(self, dado): # buscar comparando o dado do DNodo
        if not self.is_empty():
            item = self.sentinela.proximo                
            while (item != self.sentinela):                
                if item.dado == dado:
                    return item
                item = item.proximo
        
    def imprimir(self, direcao = None):
        if not self.is_empty():
            if (direcao == 'frente' or direcao is None): # forward (padrao)
                item = self.sentinela.proximo                
                while (item != self.sentinela):
                    print(item)
                    item = item.proximo
                    
            elif (direcao == 'tras'): # backward
                item = self.sentinela.anterior
                while (item != self.sentinela):
                    print(item)
                    item = item.anterior
            else:
                raise Exception("Direção inválida, use: frente ou tras")

lista = LDECircular()
lista.inserir(DNodo('A'))
lista.inserir(DNodo('B'))
lista.inserir(DNodo('C'))
lista.imprimir() ## ira imprimir B e C
#lista.imprimir('tras')
print('Procurando por \'C\'')
achou = lista.buscar('C')
print('Encontrado: {}'.format(achou))
#lista.remover()
#lista.remover_fim()
print('Item na posicao 1: {}'.format(lista.get(1)))
lista.imprimir()