lde_alunos_26092019

# Lista Duplamente Encadeada com uso de Sentinelas

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

    def __str__(self):
        return str(self.dado)

class LDE:
    def __init__(self):
        self.header = Dnodo()   # <<< Sentinela Cabeça
        self.trailer = Dnodo()  # <<< Sentinela Cauda
        self.tam = 0            # qtde de itens na lista

    def is_empty(self):
        if self.header.proximo is None and self.trailer.anterior is None:
            return True
        return False

    def __inserir(self, novo):
        self.header.proximo = novo    # header -> novo
        novo.anterior = self.header   # header <- novo
        novo.proximo = self.trailer   # novo -> trailer
        self.trailer.anterior = novo  # novo <- trailer

    def inserirInicio(self, novo):
        if self.is_empty():
            self.__inserir(novo)
        else:
            atual_primeiro = self.header.proximo #para saber quem eh o primeiro
            novo.proximo = atual_primeiro   # atual <- novo
            atual_primeiro.anterior = novo  # atual -> novo
            self.header.proximo = novo      # header -> novo
            novo.anterior = self.header     # header <- novo

        self.tam += 1

    def inserirFim(self, novo):
        if self.is_empty():
            self.__inserir(novo)
        else:
            atual_ultimo = self.trailer.anterior
            novo.anterior = atual_ultimo
            novo.proximo = self.trailer
            atual_ultimo.proximo = novo
            self.trailer.anterior = novo

        self.tam += 1

    def __remover(self): # chamado quando temos apenas 1 elemento na LDE
        removido = self.header.proximo
        removido.proximo = None
        removido.anterior = None
        self.header.proximo = None
        self.trailer.anterior = None
        return removido

    def removerInicio(self):
        if self.is_empty():
            print('Lista Vazia!')
            return

        if self.tam == 1:
            removido = self.__remover()
        else:
            # lista possui + de 1 item
            removido = self.header.proximo
            novo_head = removido.proximo
            self.header.proximo = novo_head
            removido.proximo = None
            removido.anterior = None

        self.tam -= 1
        return removido

    def removerFim(self):
        if self.is_empty():
            print('Lista Vazia!')
            return

        if self.tam == 1:
            removido = self.__remover()
        else:
            # descobrir quem eh o ultimo
            removido = self.trailer.anterior
            novo_ultimo = removido.anterior
            novo_ultimo.proximo = self.trailer
            self.trailer.anterior = novo_ultimo
            removido.proximo = None
            removido.anterior = None

        self.tam -= 1
        return removido

    def imprimir(self, reverso=False):
        if self.is_empty():
            print('Lista Vazia')
            return

        if not reverso: # mesmo que if (reverso == True)
            item = self.header.proximo # devolve o 1o da lista
            while (item.proximo is not None):
                print(item)
                item = item.proximo
        else:
            item = self.trailer.anterior # devolve o ultimo da lista
            while (item.anterior is not None):
                print(item)
                item = item.anterior

    def removerAntes(self, alvo):
        # header <-> [] <-> [] <-> trailer

        nodo_atual = self.buscar(alvo)
        nodo_anterior = nodo_atual.anterior

        if (nodo_anterior != self.header):
            aux = nodo_anterior.anterior
            aux.proximo = nodo_atual
            nodo_atual.anterior = aux

            nodo_anterior.anterior = None
            nodo_anterior.proximo = None

        self.tam -= 1

    def removerApos(self, alvo): ## remover nodo apos o alvo passado
        ## alvo eh um Dnodo
        if alvo.proximo == self.trailer: # se o alvo for o ultimo, entao nao faz nada
            return None

        remover = alvo.proximo
        alvo.proximo = remover.proximo
        remover.proximo.anterior = alvo

        remover.proximo = None
        remover.anterior = None


    def get(self, indice): # (indice: int) retorna nodo
        if self.is_empty():
            print('Lista Vazia')
            return

        cont = 0
        item = self.header.proximo

        while (item.proximo is not None):
            if indice == cont:
                return item

            item = item.proximo
            cont += 1

        return None

    def buscar(self, alvo): # (alvo: string) retorna a 1a ocorrencia do novo
        if self.is_empty():
            print('Lista Vazia')
            return

        item = self.header.proximo

        while (item.proximo is not None):
            if alvo == item.dado:
                return item

            item = item.proximo

        return None

    def substituir(self, alvo, valor): # (alvo: Dnodo) | (valor: string)
        if self.is_empty():
            print('Lista Vazia')
            return

        alvo.dado = valor

    def buscarTodos(self, alvo): # retorna uma list com resultados
        if self.is_empty():
            print('Lista Vazia')
            return

        resultado = []

        item = self.header.proximo

        while (item.proximo is not None):
            if alvo == item.dado:
                resultado.append(item)

            item = item.proximo

        return resultado

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

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

    def merge(self, outra_lista):
        ## CONCATENANDO AS REFERENCIAS
        '''
        ultimo = self.trailer.anterior
        primeiro_outra = outra_lista.header.proximo

        ultimo.proximo = primeiro_outra
        primeiro_outra.anterior = ultimo

        self.trailer.anterior = outra_lista.trailer.anterior
        outra_lista.trailer.anterior.proximo = self.trailer
        '''

        ## CONCATENANDO INSERINDO OS VALORES DA SEGUNDA LISTA
        item = outra_lista.header.proximo # devolve o 1o da lista
        while (item.proximo is not None):
             self.inserirFim(Dnodo(item.dado))
             item = item.proximo


    def __len__(self):
        return self.tam

## TESTES ##
'''
lista = LDE()
lista.inserirInicio(Dnodo('abc'))
lista.inserirInicio(Dnodo('001'))
lista.inserirInicio(Dnodo('xyz'))
lista.inserirFim(Dnodo('zzz'))
lista.removerInicio()
lista.removerFim()

lista.imprimir(True)
'''
'''
l = LDE()
l.inserirFim(Dnodo('X'))
l.inserirFim(Dnodo('Y'))

l2 = LDE()
l2.inserirFim(Dnodo('A'))
l2.inserirFim(Dnodo('B'))

l.merge(l2)

l.imprimir()
'''

lista = LDE()
lista.inserirFim(Dnodo('1'))
lista.inserirFim(Dnodo('2'))
lista.inserirFim(Dnodo('3'))

nodo = lista.buscar('2')
lista.removerApos(nodo)

lista.imprimir() ## deve retornar [1] [2]