// "Copyright [2015] <Ricardo Sell>"
template<typename T>
class Lista {
private:
    int tamanholista;
    int ultimo;
    int valor;
    T dados;
public:
    Lista() {  // construtor da classe lista
        int posicao;  // variável para percorrer a lista
        int valor;
        int tamanholista = 100;
        dados = new T[tamanholista];
        ultimo = -1;
    }
    explicit Lista(int tam) {
        ultimo = -1;
        tamanholista = tam;
        dados = new T[tamanholista];
    }
    void adiciona(T dado) {
        if (listaCheia()) {
            throw 1;
        } else {
            ultimo++;
            dados[ultimo] = dado;
        }
    }
    void adicionaNoInicio(T dado) {
        if (listaCheia()) {
            throw 1;
        } else {
            ultimo++;
            posicao = ultimo;
            while (posicao > 0) {
                dados[posicao] = dados[posicao - 1];
            }
            dados[0] = dado;
        }
    }
    void adicionaNaPosicao(T dado, int destino) {
        if (listaCheia()) {
            throw 1;
        } else {
            if (destino > ultimo + 1 || destino < 0) {
                throw 1;
            }
            ultimo++;
            posicao = ultimo;
            while (posicao > destino) {
                dados[posicao] = dados[posicao - 1];
                posicao--;
            }
            dados[destino] = dado;
        }
    }
    void adicionaEmOrdem(T dado) {
        posicao = 0;
        if (listaCheia()) {
            throw 1;
        } else {
            while (posicao <= ulitmo && dado > (dados[posicao])) {
                posicao++;
            }
        }
        return (adicionaNaPosicao(dado, posicao));
    }
    T retira() {
        if (listaVazia()) {
            throw 1;
        } else {
            ultimo--;
        }
        return dados[ultimo + 1];
    }
    T retiraDoInicio() {
        if (listaVazia()) {
            throw 1;
        } else {
            ultimo--;
            valor = dados[0];
            posicao = 0;
            while (posicao <= ultimo) {
                dados[posicao] = dados[posicao + 1];
                posicao++;
            }
        }
        return valor;
    }
    T retiraDaPosicao(int fonte) {
        if (fonte > ultimo || fonte < 0) {
            throw 1;
        } else {
            if (listaVazia()) {
                throw 1;
            } else {
                ultimo--;
                valor = dados[fonte];
                posicao = fonte;
                while (posicao <= ultimo) {
                    dados[posicao] = dados[posicao + 1];
                    posicao++;
                }
            }
        }
        return valor;
    }
    T retiraEspecifico(T dado) {
        if (listaVazia()) {
            throw 1;
        } else {
            posicao = posicao[dado];
            if (posicao < 0) {
                throw 1;
            }
        }
        return (retiraDaPosicao(posicao));
    }
    int posicao(T dado) {
        ultimo = -1;
        posicao = 0;
        while (posicao <= ulitmo && !(igual(dado, dados[posicao] {
                                    posicao++;
                                }
                                if (posicao > ultimo) {
                                    throw 1;
                                }
                                return posicao;
                            }
                            bool contem(T dado) {
                                posicao = 0;
                                if (listaVazia()) {
                                    throw 1;
                                } else {
                                    while (posicao <= tamanholista) {
                                        if (dados[posicao] != dado) {
                                            posicao++;
                                        } else {
                                            break;
                                        }
                                    }
                                }
                                return dado;
                            }
                            bool igual(T dado1, T dado2) {
                                return (dado1 == dado2);
                            }
                            bool maior(T dado1, T dado2) {
                                return (dado1 > dado2);
                            }
                            bool menor(T dado1, T dado2) {
                                return dado1 < dado2;
                            }
                            bool listaCheia() {
                                return (ultimo == tamanholista - 1);
                            }
                            bool listaVazia() {
                                return (ultimo == -1);
                            }
                            void destroiLista() {
                                ultimo = -1;
                            }
                        };