QDawg Class Reference

The QDawg class provides an implementation of a Directed Acyclic Word Graph. More...

#include </home/clem/local/src/opie/library/qdawg.h>

Collaboration diagram for QDawg:

[legend]List of all members.

Public Member Functions
	QDawg ()
	~QDawg ()
bool	readFile (const QString &)
bool	read (QIODevice *dev)
bool	write (QIODevice *dev) const
bool	createFromWords (QIODevice *dev)
void	createFromWords (const QStringList &)
QStringList	allWords () const
bool	contains (const QString &) const
int	countWords () const
const Node *	root () const
void	dump () const
Static Public Attributes
static const int	nodebits = 18
Private Attributes
QDawgPrivate *	d
Friends
class	QDawgPrivate
Classes
class	Node
	The QDawg::Node class represents one node of a QDawg. More...

---

Detailed Description

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 node is returned by root().

A global DAWG is maintained for the current locale. See the Global class for details.

The structure of a DAWG is a graph of Nodes. There are no cycles in the graph (since there are no inifinitely repeating words). Each Node is a member of a list of Nodes called a child list. Each Node in the child list has a letter, an isWord flag, at most one jump arc, and at most one arc to the next child in the list.

If you traverse the Nodes 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 Node 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.

qdawg.png

Definition at line 28 of file qdawg.h.

---

Constructor & Destructor Documentation

QDawg::QDawg (   )

Constructs a new empty DAWG. Definition at line 443 of file qdawg.cpp. References d.

QDawg::~QDawg (   )

Deletes the DAWG. Definition at line 451 of file qdawg.cpp. References d.

---

Member Function Documentation

QStringList QDawg::allWords (   )  const

Returns a list of all the words in the DAWG. Definition at line 499 of file qdawg.cpp. References QDawgPrivate::appendAllWords(), and d. Referenced by Global::addWords().

bool QDawg::contains (  const QString &  s  )  const

Returns TRUE if the DAWG contains the word s; otherwise returns FALSE. Definition at line 578 of file qdawg.cpp. References QDawgPrivate::contains(), d, and FALSE.

int QDawg::countWords (   )  const

Returns the number of words in the DAWG. Definition at line 561 of file qdawg.cpp. References QDawgPrivate::countWords(), and d.

void QDawg::createFromWords (  const QStringList &  list  )

Replaces all the DAWG's words with the words in the list. Definition at line 481 of file qdawg.cpp. References QValueList< T >::begin(), QValueList< T >::count(), d, QValueList< T >::end(), QTrie::insertWord(), and QDawgPrivate.

bool QDawg::createFromWords (  QIODevice *  dev  )

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts. Replaces all the DAWG's words with words read from dev. Definition at line 460 of file qdawg.cpp. References QTextStream::atEnd(), d, QString::fromUtf8(), i, QTrie::insertWord(), QDawgPrivate, QTextStream::readLine(), and TRUE. Referenced by Global::addWords(), and Global::fixedDawg().

void QDawg::dump (   )  const

For internal use only. For debugging: prints out the DAWG contents. Definition at line 588 of file qdawg.cpp. References d, and QDawgPrivate::dump().

bool QDawg::read (  QIODevice *  dev  )

Replaces the DAWG with the DAWG in dev. The file is memory-mapped. See also: write() Definition at line 539 of file qdawg.cpp. References d, FALSE, QDawgPrivate::ok(), QDawgPrivate, and TRUE.

bool QDawg::readFile (  const QString &  filename  )

Replaces the DAWG with the DAWG in filename. The file is memory-mapped. See also: write() Definition at line 513 of file qdawg.cpp. References d, QFile::encodeName(), f, FALSE, and QDawgPrivate. Referenced by Global::dawg(), and Global::fixedDawg().

const QDawg::Node * QDawg::root (   )  const

Returns the root Node of the DAWG. Definition at line 569 of file qdawg.cpp. References d, and QDawgPrivate::root().

bool QDawg::write (  QIODevice *  dev  )  const

Writes the DAWG to dev, in a custom QDAWG format. Definition at line 553 of file qdawg.cpp. References d, TRUE, and QDawgPrivate::write(). Referenced by Global::addWords(), and Global::fixedDawg().

---

Friends And Related Function Documentation

friend class QDawgPrivate [friend]

Definition at line 66 of file qdawg.h. Referenced by createFromWords(), read(), and readFile().

---

Member Data Documentation

QDawgPrivate* QDawg::d [private]

Definition at line 67 of file qdawg.h. Referenced by allWords(), contains(), countWords(), createFromWords(), dump(), QDawg(), read(), readFile(), root(), write(), and ~QDawg().

const int QDawg::nodebits = 18 [static]

Definition at line 44 of file qdawg.h.

---

The documentation for this class was generated from the following files:

• library/qdawg.h
• library/qdawg.cpp

---