| -rw-r--r-- | library/qdawg.cpp | 121 |
1 files changed, 119 insertions, 2 deletions
diff --git a/library/qdawg.cpp b/library/qdawg.cpp index 3615693..af5dc82 100644 --- a/library/qdawg.cpp +++ b/library/qdawg.cpp @@ -1,5 +1,5 @@ /********************************************************************** -** Copyright (C) 2000 Trolltech AS. All rights reserved. +** Copyright (C) 2000-2002 Trolltech AS. All rights reserved. ** -** This file is part of Qtopia Environment. +** This file is part of the Qtopia Environment. ** @@ -402,3 +402,44 @@ private: +/*! + \class QDawg qdawg.h + \brief The QDawg class provides an implementation of a Directed Acyclic Word Graph. + A DAWG provides very fast look-up of words in a word list. + + The word list is created using readFile(), read() or + createFromWords(). A list of all the DAWG's words is returned by + allWords(), and the total number of words is returned by + countWords(). Use contains() to see if a particular word is in the + DAWG. The root \link qdawg-node.html node\endlink is returned by root(). + + A global DAWG is maintained for the current locale. See the + \l Global class for details. + + The structure of a DAWG is a graph of \link qdawg-node.html + Nodes\endlink. There are no cycles in the graph (since there are no + inifinitely repeating words). Each \link qdawg-node.html + Node\endlink is a member of a list of \link qdawg-node.html + Nodes\endlink called a child list. Each \link qdawg-node.html + Node\endlink in the child list has a \e letter, an \e isWord flag, + at most one \e jump arc, and at most one arc to the next child in + the list. + + If you traverse the \link qdawg-node.html Nodes\endlink in a DAWG, + starting from the root(), and you concatenate all the letters from + the single child in each child list that you visit, at every \link + qdawg-node.html Node\endlink which has the isWord flag set your + concatenation will be a word in the list represented by the DAWG. + + For example, the DAWG below represents the word list: + ban, band, can, cane, cans, pan, pane, pans. + + This structuring not only provides O(1) lookup of words in the word list, + but also produces a smaller storage file than a plain text file word list. + + \img qdawg.png +*/ + +/*! + Constructs a new empty DAWG. +*/ QDawg::QDawg() @@ -408,2 +449,5 @@ QDawg::QDawg() +/*! + Deletes the DAWG. +*/ QDawg::~QDawg() @@ -413,2 +457,6 @@ QDawg::~QDawg() +/*! + \overload + Replaces all the DAWG's words with words read from \a dev. +*/ bool QDawg::createFromWords(QIODevice* dev) @@ -431,2 +479,5 @@ bool QDawg::createFromWords(QIODevice* dev) +/*! + Replaces all the DAWG's words with the words in the \a list. +*/ void QDawg::createFromWords(const QStringList& list) @@ -446,2 +497,5 @@ void QDawg::createFromWords(const QStringList& list) +/*! + Returns a list of all the words in the DAWG. +*/ QStringList QDawg::allWords() const @@ -454,2 +508,8 @@ QStringList QDawg::allWords() const +/*! + Replaces the DAWG with the DAWG in \a filename. + The file is memory-mapped. + + \sa write() +*/ bool QDawg::readFile(const QString& filename) @@ -474,2 +534,8 @@ bool QDawg::readFile(const QString& filename) +/*! + Replaces the DAWG with the DAWG in \a dev. + The file is memory-mapped. + + \sa write() +*/ bool QDawg::read(QIODevice* dev) @@ -485,2 +551,5 @@ bool QDawg::read(QIODevice* dev) +/*! + Writes the DAWG to \a dev, in a custom QDAWG format. +*/ bool QDawg::write(QIODevice* dev) const @@ -490,2 +559,5 @@ bool QDawg::write(QIODevice* dev) const +/*! + Returns the number of words in the DAWG. +*/ int QDawg::countWords() const @@ -495,2 +567,5 @@ int QDawg::countWords() const +/*! + Returns the root \link qdawg-node.html Node\endlink of the DAWG. +*/ const QDawg::Node* QDawg::root() const @@ -500,2 +575,6 @@ const QDawg::Node* QDawg::root() const +/*! + Returns TRUE if the DAWG contains the word \a s; otherwise returns + FALSE. +*/ bool QDawg::contains(const QString& s) const @@ -505,2 +584,7 @@ bool QDawg::contains(const QString& s) const +/*! + \internal + + For debugging: prints out the DAWG contents. +*/ void QDawg::dump() const @@ -510 +594,34 @@ void QDawg::dump() const +/*! + \class QDawg::Node qdawg.h + \brief The QDawg::Node class represents one node of a QDawg. +*/ + +/*! + \fn QChar QDawg::Node::letter() const + + Returns this Node's letter. +*/ +/*! + \fn bool QDawg::Node::isWord() const + + Returns TRUE if this Node is the end of a word; otherwise returns + FALSE. +*/ +/*! + \fn bool QDawg::Node::isLast() const + + Returns TRUE if this Node is the last in the child list; otherwise + returns FALSE. +*/ +/*! + \fn const Node* QDawg::Node::next() const + + Returns the next child Node in the child list or 0 if the current + Node isLast(). +*/ +/*! + \fn const Node* QDawg::Node::jump() const + + Returns the node connected to this Node. +*/ |