c++ - Atrapado en una implementación de iterador de un Trie

iterator

Question

Tengo que implementar una Trie casera y estoy atascado en la parte Iterator. No puedo entender el método de incremento para el trie.

Espero que alguien me ayude a aclarar las cosas.

Aquí está el código para el iterador:

template <typename T> class Trie<T>::IteratorPrefixe{
friend class Trie<T>;
public:
    IteratorPrefixe() : tree(NULL), currentNode(NULL), currentKey("") {};
    pair<string, T*> operator*() {return make_pair(currentKey, currentNode -> element);} ;
    IteratorPrefixe operator++()throw(runtime_error);
    void operator=(IteratorPrefixe iter) {tree = iter.tree; currentNode = iter.currentNode; currentKey = iter.currentKey;};
    bool operator==(IteratorPrefixe iter) {return tree == iter.tree && currentNode == iter.currentNode;};
    bool operator!=(IteratorPrefixe iter) {return tree != iter.tree || currentNode != iter.currentNode;};
private:
    Trie<T> * tree;
    Trie<T> * currentNode;
    string currentKey;
};

Y aquí está mi Trie:

template <typename T> class Trie {
friend class IteratorPrefixe;
public:
    // Create a Trie<T> from the alphabet of nbletters, where nbletters must be
    // between 1 and NBLETTERSMAX inclusively
    Trie(unsigned nbletters) throw(runtime_error);

    // Add a key element of which is given in the first argument and content second argument
    // The content must be defined (different from NULL pointer)
    // The key is to be composed of valid letters (the letters between A + inclusive and exclusive nbletters
    //      Eg  if nblettres is 3, a, b and c are the only characters permitted;
    //          If nblettres is 15, only the letters between a and o inclusive are allowed.
    // Returns true if the insertion was achieved, returns false otherwise.
    bool addElement(string, T*) throw(runtime_error);
    // Deletes a key element of which is given as an argument and returns the contents of the node removed
    // The key is to be composed of letters valid (see above)
    // Can also delete at the same time the reference of the ancestors, if these ancestors are no longer used.
    // Returns NULL if the item has no delete
    T* removeElement(string cle) throw(runtime_error);
    // Find a key element of which is given as an argument and returns the associated content
    // The key is to be composed of letters valid (see above)
    // Returns NULL if the key does not exist
    T* searchElement(string cle) throw();
    // Iterator class to browse the Trie <T> in preorder mode
    class IteratorPrefixe;
    // Returns an iterator pointing to the first element
    IteratorPrefixe pbegin() throw(runtime_error);
    // Returns an iterator pointing beyond the last item
    IteratorPrefixe pend() throw();

private:
    unsigned nbLetters;
    T* element;
    vector<Trie<T> *> childs;
    Trie<T> * parent;

    // This function removes a node and its ancestors if became unnecessary. It is essentially the same work
    // as deleteElement that is how to designate remove a node that is changing. Moreover, unlike
    // deleteElement, it does not return any information on the node removed.
    void remove(Trie<T> * node) throw();

    // This function is seeking a node based on a given key. It is essentially the same work
    // searchElement but that returns a reference to the node found (or null if the node does not exist)
    // The key is to be composed of letters valid (see above)
    Trie<T>* search(string key) throw(runtime_error);
};

Answer 1

Es posible que desee ver mis implementaciones de trie modificadas en:

• trie de jdkoftinoff

Específicamente, puede encontrar la discusión que tuve en comp.lang.c ++ moderada sobre la implementación de iteradores para trie de una manera compatible con STL, que es un problema ya que desafortunadamente todos los contenedores stl están forzados a usar std :: pair <>, y el el iterador debe contener el valor en lugar de solo una referencia al nodo individual en el trie.

Answer 2

Por un lado, el código que se muestra en realidad no describe un trie. Por el contrario, parece ser un árbol que contiene un par de elementos en cada nodo ( T* y unsigned ). Puede por disciplina usar un árbol de tuplas como un trie, pero es solo por convención, no por cumplimiento. Esto es parte de por qué está teniendo dificultades para implementar el operator++ .

Lo que debe hacer es hacer que cada Trie contenga un ADT disjunto izquierda-derecha, en lugar de solo los elementos brutos. Es una capa de abstracción que se encuentra más comúnmente en los lenguajes funcionales (por ejemplo, Scala''s Either ). Desafortunadamente, el sistema de tipos de C ++ no es lo suficientemente potente como para hacer algo tan elegante. Sin embargo, no hay nada que te impida hacer esto:

template <class L, class R>
class Either
{
public:

    Either(L *l) : left(l), right(0)
    {}

    Either(R *r) : left(0), right(r)
    {}

    L *get_left() const
    {
        return left;
    }

    R *get_right() const
    {
        return right;
    }

    bool is_left() const
    {
        return left != 0;
    }

    bool is_right() const
    {
        return right != 0;
    }

private:
    L *left;
    R *right;
};

Entonces los miembros de datos de Trie se definirían de la siguiente manera:

private:
    Either<unsigned, T*> disjoint;

    vector<Trie<T> *> children;    // english pluralization
    Trie<T> * parent;

Estoy jugando rápido con tus punteros, pero entiendes lo que estoy diciendo. El bit más importante es que ningún nodo dado puede contener tanto un unsigned como un T* .

Pruebe esto y vea si eso ayuda. Creo que encontrará que ser capaz de determinar fácilmente si está en una hoja o una rama le ayudará enormemente en su intento de iterar.

Answer 3

Me alegra ver que aún se enseñan los Tries, son una estructura de datos importante que a menudo se descuida.

Puede haber un problema de diseño en su código ya que probablemente debería tener una clase Trie y una clase Node. La forma en que lo escribió parece que cada nodo en su Trie es su propio trie, lo que puede funcionar, pero complicará algunas cosas.

En realidad, no está claro por su pregunta qué es lo que está teniendo el problema: calcular el orden o calcular el código real.

A partir del nombre del iterador, parece que debería funcionar en orden de prefijo. Como su trie almacena palabras y sus nodos secundarios están organizados por letras, se espera que revise todas las palabras en orden alfabético. Cada incremento te llevará a la siguiente palabra.

Lo invariante sobre su iterador es que en cualquier punto (siempre que sea válido), debe apuntar a un nodo con un "carácter terminador" para una palabra válida. Calcular esa palabra simplemente implica escanear hacia arriba a lo largo de la cadena principal hasta encontrar toda la cadena. Pasar a la siguiente palabra significa hacer una búsqueda DFS: subir una vez, buscar enlaces en los "hermanos" posteriores, ver si encuentras una palabra, si no subir recursivamente, etc.