author | zecke <zecke> | 2002-09-10 12:09:49 (UTC) |
---|---|---|
committer | zecke <zecke> | 2002-09-10 12:09:49 (UTC) |
commit | 6b77a1cdb9536b1c135eb86d53a6b2c22c19b0a4 (patch) (unidiff) | |
tree | 6ebc93c6432f4ed9d00ef1448b6a047ef522a79a /library/qdawg.cpp | |
parent | d10cddb3c9ce75bc90b14add14bc133737fe35aa (diff) | |
download | opie-6b77a1cdb9536b1c135eb86d53a6b2c22c19b0a4.zip opie-6b77a1cdb9536b1c135eb86d53a6b2c22c19b0a4.tar.gz opie-6b77a1cdb9536b1c135eb86d53a6b2c22c19b0a4.tar.bz2 |
Qtopia1-6 merge
still to test
bic changes to be resolved
more changes to be made?
-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 @@ | |||
1 | /********************************************************************** | 1 | /********************************************************************** |
2 | ** Copyright (C) 2000 Trolltech AS. All rights reserved. | 2 | ** Copyright (C) 2000-2002 Trolltech AS. All rights reserved. |
3 | ** | 3 | ** |
4 | ** This file is part of Qtopia Environment. | 4 | ** This file is part of the Qtopia Environment. |
5 | ** | 5 | ** |
@@ -402,3 +402,44 @@ private: | |||
402 | 402 | ||
403 | /*! | ||
404 | \class QDawg qdawg.h | ||
405 | \brief The QDawg class provides an implementation of a Directed Acyclic Word Graph. | ||
403 | 406 | ||
407 | A DAWG provides very fast look-up of words in a word list. | ||
408 | |||
409 | The word list is created using readFile(), read() or | ||
410 | createFromWords(). A list of all the DAWG's words is returned by | ||
411 | allWords(), and the total number of words is returned by | ||
412 | countWords(). Use contains() to see if a particular word is in the | ||
413 | DAWG. The root \link qdawg-node.html node\endlink is returned by root(). | ||
414 | |||
415 | A global DAWG is maintained for the current locale. See the | ||
416 | \l Global class for details. | ||
417 | |||
418 | The structure of a DAWG is a graph of \link qdawg-node.html | ||
419 | Nodes\endlink. There are no cycles in the graph (since there are no | ||
420 | inifinitely repeating words). Each \link qdawg-node.html | ||
421 | Node\endlink is a member of a list of \link qdawg-node.html | ||
422 | Nodes\endlink called a child list. Each \link qdawg-node.html | ||
423 | Node\endlink in the child list has a \e letter, an \e isWord flag, | ||
424 | at most one \e jump arc, and at most one arc to the next child in | ||
425 | the list. | ||
426 | |||
427 | If you traverse the \link qdawg-node.html Nodes\endlink in a DAWG, | ||
428 | starting from the root(), and you concatenate all the letters from | ||
429 | the single child in each child list that you visit, at every \link | ||
430 | qdawg-node.html Node\endlink which has the isWord flag set your | ||
431 | concatenation will be a word in the list represented by the DAWG. | ||
432 | |||
433 | For example, the DAWG below represents the word list: | ||
434 | ban, band, can, cane, cans, pan, pane, pans. | ||
435 | |||
436 | This structuring not only provides O(1) lookup of words in the word list, | ||
437 | but also produces a smaller storage file than a plain text file word list. | ||
438 | |||
439 | \img qdawg.png | ||
440 | */ | ||
441 | |||
442 | /*! | ||
443 | Constructs a new empty DAWG. | ||
444 | */ | ||
404 | QDawg::QDawg() | 445 | QDawg::QDawg() |
@@ -408,2 +449,5 @@ QDawg::QDawg() | |||
408 | 449 | ||
450 | /*! | ||
451 | Deletes the DAWG. | ||
452 | */ | ||
409 | QDawg::~QDawg() | 453 | QDawg::~QDawg() |
@@ -413,2 +457,6 @@ QDawg::~QDawg() | |||
413 | 457 | ||
458 | /*! | ||
459 | \overload | ||
460 | Replaces all the DAWG's words with words read from \a dev. | ||
461 | */ | ||
414 | bool QDawg::createFromWords(QIODevice* dev) | 462 | bool QDawg::createFromWords(QIODevice* dev) |
@@ -431,2 +479,5 @@ bool QDawg::createFromWords(QIODevice* dev) | |||
431 | 479 | ||
480 | /*! | ||
481 | Replaces all the DAWG's words with the words in the \a list. | ||
482 | */ | ||
432 | void QDawg::createFromWords(const QStringList& list) | 483 | void QDawg::createFromWords(const QStringList& list) |
@@ -446,2 +497,5 @@ void QDawg::createFromWords(const QStringList& list) | |||
446 | 497 | ||
498 | /*! | ||
499 | Returns a list of all the words in the DAWG. | ||
500 | */ | ||
447 | QStringList QDawg::allWords() const | 501 | QStringList QDawg::allWords() const |
@@ -454,2 +508,8 @@ QStringList QDawg::allWords() const | |||
454 | 508 | ||
509 | /*! | ||
510 | Replaces the DAWG with the DAWG in \a filename. | ||
511 | The file is memory-mapped. | ||
512 | |||
513 | \sa write() | ||
514 | */ | ||
455 | bool QDawg::readFile(const QString& filename) | 515 | bool QDawg::readFile(const QString& filename) |
@@ -474,2 +534,8 @@ bool QDawg::readFile(const QString& filename) | |||
474 | 534 | ||
535 | /*! | ||
536 | Replaces the DAWG with the DAWG in \a dev. | ||
537 | The file is memory-mapped. | ||
538 | |||
539 | \sa write() | ||
540 | */ | ||
475 | bool QDawg::read(QIODevice* dev) | 541 | bool QDawg::read(QIODevice* dev) |
@@ -485,2 +551,5 @@ bool QDawg::read(QIODevice* dev) | |||
485 | 551 | ||
552 | /*! | ||
553 | Writes the DAWG to \a dev, in a custom QDAWG format. | ||
554 | */ | ||
486 | bool QDawg::write(QIODevice* dev) const | 555 | bool QDawg::write(QIODevice* dev) const |
@@ -490,2 +559,5 @@ bool QDawg::write(QIODevice* dev) const | |||
490 | 559 | ||
560 | /*! | ||
561 | Returns the number of words in the DAWG. | ||
562 | */ | ||
491 | int QDawg::countWords() const | 563 | int QDawg::countWords() const |
@@ -495,2 +567,5 @@ int QDawg::countWords() const | |||
495 | 567 | ||
568 | /*! | ||
569 | Returns the root \link qdawg-node.html Node\endlink of the DAWG. | ||
570 | */ | ||
496 | const QDawg::Node* QDawg::root() const | 571 | const QDawg::Node* QDawg::root() const |
@@ -500,2 +575,6 @@ const QDawg::Node* QDawg::root() const | |||
500 | 575 | ||
576 | /*! | ||
577 | Returns TRUE if the DAWG contains the word \a s; otherwise returns | ||
578 | FALSE. | ||
579 | */ | ||
501 | bool QDawg::contains(const QString& s) const | 580 | bool QDawg::contains(const QString& s) const |
@@ -505,2 +584,7 @@ bool QDawg::contains(const QString& s) const | |||
505 | 584 | ||
585 | /*! | ||
586 | \internal | ||
587 | |||
588 | For debugging: prints out the DAWG contents. | ||
589 | */ | ||
506 | void QDawg::dump() const | 590 | void QDawg::dump() const |
@@ -510 +594,34 @@ void QDawg::dump() const | |||
510 | 594 | ||
595 | /*! | ||
596 | \class QDawg::Node qdawg.h | ||
597 | \brief The QDawg::Node class represents one node of a QDawg. | ||
598 | */ | ||
599 | |||
600 | /*! | ||
601 | \fn QChar QDawg::Node::letter() const | ||
602 | |||
603 | Returns this Node's letter. | ||
604 | */ | ||
605 | /*! | ||
606 | \fn bool QDawg::Node::isWord() const | ||
607 | |||
608 | Returns TRUE if this Node is the end of a word; otherwise returns | ||
609 | FALSE. | ||
610 | */ | ||
611 | /*! | ||
612 | \fn bool QDawg::Node::isLast() const | ||
613 | |||
614 | Returns TRUE if this Node is the last in the child list; otherwise | ||
615 | returns FALSE. | ||
616 | */ | ||
617 | /*! | ||
618 | \fn const Node* QDawg::Node::next() const | ||
619 | |||
620 | Returns the next child Node in the child list or 0 if the current | ||
621 | Node isLast(). | ||
622 | */ | ||
623 | /*! | ||
624 | \fn const Node* QDawg::Node::jump() const | ||
625 | |||
626 | Returns the node connected to this Node. | ||
627 | */ | ||