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 | 123 |
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,6 +1,6 @@ | |||
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 | ** |
6 | ** This file may be distributed and/or modified under the terms of the | 6 | ** This file may be distributed and/or modified under the terms of the |
@@ -197,5 +197,5 @@ bool TrieList::equal(TrieList& l) | |||
197 | if ( count() != l.count() ) | 197 | if ( count() != l.count() ) |
198 | return FALSE; | 198 | return FALSE; |
199 | sort(); l.sort(); | 199 | sort(); l.sort(); |
200 | ConstIterator it2 = begin(); | 200 | ConstIterator it2 = begin(); |
201 | ConstIterator it = l.begin(); | 201 | ConstIterator it = l.begin(); |
@@ -401,5 +401,46 @@ private: | |||
401 | }; | 401 | }; |
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() |
405 | { | 446 | { |
@@ -407,4 +448,7 @@ QDawg::QDawg() | |||
407 | } | 448 | } |
408 | 449 | ||
450 | /*! | ||
451 | Deletes the DAWG. | ||
452 | */ | ||
409 | QDawg::~QDawg() | 453 | QDawg::~QDawg() |
410 | { | 454 | { |
@@ -412,4 +456,8 @@ QDawg::~QDawg() | |||
412 | } | 456 | } |
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) |
415 | { | 463 | { |
@@ -430,4 +478,7 @@ bool QDawg::createFromWords(QIODevice* dev) | |||
430 | } | 478 | } |
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) |
433 | { | 484 | { |
@@ -445,4 +496,7 @@ void QDawg::createFromWords(const QStringList& list) | |||
445 | } | 496 | } |
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 |
448 | { | 502 | { |
@@ -453,4 +507,10 @@ QStringList QDawg::allWords() const | |||
453 | 507 | ||
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) |
456 | { | 516 | { |
@@ -473,4 +533,10 @@ bool QDawg::readFile(const QString& filename) | |||
473 | } | 533 | } |
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) |
476 | { | 542 | { |
@@ -484,4 +550,7 @@ bool QDawg::read(QIODevice* dev) | |||
484 | } | 550 | } |
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 |
487 | { | 556 | { |
@@ -489,4 +558,7 @@ bool QDawg::write(QIODevice* dev) const | |||
489 | } | 558 | } |
490 | 559 | ||
560 | /*! | ||
561 | Returns the number of words in the DAWG. | ||
562 | */ | ||
491 | int QDawg::countWords() const | 563 | int QDawg::countWords() const |
492 | { | 564 | { |
@@ -494,4 +566,7 @@ int QDawg::countWords() const | |||
494 | } | 566 | } |
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 |
497 | { | 572 | { |
@@ -499,4 +574,8 @@ const QDawg::Node* QDawg::root() const | |||
499 | } | 574 | } |
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 |
502 | { | 581 | { |
@@ -504,4 +583,9 @@ bool QDawg::contains(const QString& s) const | |||
504 | } | 583 | } |
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 |
507 | { | 591 | { |
@@ -509,2 +593,35 @@ void QDawg::dump() const | |||
509 | } | 593 | } |
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 | */ | ||