summaryrefslogtreecommitdiff
path: root/library/qdawg.cpp
Side-by-side diff
Diffstat (limited to 'library/qdawg.cpp') (more/less context) (ignore whitespace changes)
-rw-r--r--library/qdawg.cpp123
1 files changed, 120 insertions, 3 deletions
diff --git a/library/qdawg.cpp b/library/qdawg.cpp
index 3615693..af5dc82 100644
--- a/library/qdawg.cpp
+++ b/library/qdawg.cpp
@@ -1,10 +1,10 @@
/**********************************************************************
-** 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.
**
** This file may be distributed and/or modified under the terms of the
** GNU General Public License version 2 as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL included in the
** packaging of this file.
**
@@ -193,13 +193,13 @@ int TriePtr::operator <=(const TriePtr& o) const
{ return letter <= o.letter; }
bool TrieList::equal(TrieList& l)
{
if ( count() != l.count() )
return FALSE;
- sort(); l.sort();
+ sort(); l.sort();
ConstIterator it2 = begin();
ConstIterator it = l.begin();
for( ; it != l.end(); ++it, ++it2 )
if ( (*it).letter != (*it2).letter || ! (*it).p->equal((*it2).p) )
return FALSE;
return TRUE;
@@ -397,23 +397,71 @@ private:
private:
int nodes;
QDawg::Node *node;
};
+/*!
+ \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()
{
d = 0;
}
+/*!
+ Deletes the DAWG.
+*/
QDawg::~QDawg()
{
delete d;
}
+/*!
+ \overload
+ Replaces all the DAWG's words with words read from \a dev.
+*/
bool QDawg::createFromWords(QIODevice* dev)
{
delete d;
QTextStream i(dev);
QTrie* trie = new QTrie;
@@ -426,12 +474,15 @@ bool QDawg::createFromWords(QIODevice* dev)
d = new QDawgPrivate(trie);
else
d = 0;
return TRUE;
}
+/*!
+ Replaces all the DAWG's words with the words in the \a list.
+*/
void QDawg::createFromWords(const QStringList& list)
{
delete d;
if ( list.count() ) {
QTrie* trie = new QTrie;
@@ -441,20 +492,29 @@ void QDawg::createFromWords(const QStringList& list)
d = new QDawgPrivate(trie);
} else {
d = 0;
}
}
+/*!
+ Returns a list of all the words in the DAWG.
+*/
QStringList QDawg::allWords() const
{
QStringList result;
if ( d ) d->appendAllWords(result);
return result;
}
+/*!
+ Replaces the DAWG with the DAWG in \a filename.
+ The file is memory-mapped.
+
+ \sa write()
+*/
bool QDawg::readFile(const QString& filename)
{
delete d;
d = 0;
int f = ::open( QFile::encodeName(filename), O_RDONLY );
if ( f < 0 )
@@ -469,42 +529,99 @@ bool QDawg::readFile(const QString& filename)
d = new QDawgPrivate((uchar*)tmp);
}
::close( f );
return d;
}
+/*!
+ Replaces the DAWG with the DAWG in \a dev.
+ The file is memory-mapped.
+
+ \sa write()
+*/
bool QDawg::read(QIODevice* dev)
{
delete d;
d = new QDawgPrivate(dev);
if ( d->ok() )
return TRUE;
delete d;
d = 0;
return FALSE;
}
+/*!
+ Writes the DAWG to \a dev, in a custom QDAWG format.
+*/
bool QDawg::write(QIODevice* dev) const
{
return d ? d->write(dev) : TRUE;
}
+/*!
+ Returns the number of words in the DAWG.
+*/
int QDawg::countWords() const
{
return d ? d->countWords() : 0;
}
+/*!
+ Returns the root \link qdawg-node.html Node\endlink of the DAWG.
+*/
const QDawg::Node* QDawg::root() const
{
return d ? d->root() : 0;
}
+/*!
+ Returns TRUE if the DAWG contains the word \a s; otherwise returns
+ FALSE.
+*/
bool QDawg::contains(const QString& s) const
{
return d ? d->contains(s) : FALSE;
}
+/*!
+ \internal
+
+ For debugging: prints out the DAWG contents.
+*/
void QDawg::dump() const
{
if ( d ) d->dump();
}
+/*!
+ \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.
+*/