自家製の Trie を実装する必要があり、Iterator の部分で行き詰まっています。トライのインクリメント方法がわかりません。
誰かが私が物事を片付けるのを手伝ってくれることを願っています.
イテレータのコードは次のとおりです。
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;
};
そして、ここに私のトライがあります:
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);
};