-rw-r--r-- | library/qdawg.cpp | 2 |
1 files changed, 0 insertions, 2 deletions
diff --git a/library/qdawg.cpp b/library/qdawg.cpp index af5dc82..2ea5734 100644 --- a/library/qdawg.cpp +++ b/library/qdawg.cpp @@ -1,151 +1,149 @@ /********************************************************************** ** Copyright (C) 2000-2002 Trolltech AS. All rights reserved. ** ** 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. ** ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. ** ** See http://www.trolltech.com/gpl/ for GPL licensing information. ** ** Contact info@trolltech.com if any conditions of this licensing are ** not clear to you. ** **********************************************************************/ #include "qdawg.h" #include <qintdict.h> -#include <qvaluelist.h> -#include <qtextstream.h> #include <qfile.h> #include <qtl.h> #include <limits.h> #include <stdio.h> // for mmap #include <sys/types.h> #include <sys/stat.h> #include <sys/mman.h> #include <fcntl.h> #include <errno.h> #include <unistd.h> class QDawgPrivate; class QTrie; typedef QValueList<QTrie*> TrieClub; typedef QIntDict<TrieClub> TrieClubDirectory; class TriePtr { public: QChar letter; QTrie* p; int operator <(const TriePtr& o) const; int operator >(const TriePtr& o) const; int operator <=(const TriePtr& o) const; }; class TrieList : public QValueList<TriePtr> { bool sorted; public: TrieList() { sorted=TRUE; } QTrie* findAdd(QChar c); bool equal(TrieList& l); void sort() { if ( !sorted ) { qHeapSort(*this); sorted = TRUE; } } }; // A fast but memory-wasting temporary class. The Dawg is the goal. class QTrie { public: QTrie(); ~QTrie(); void insertWord(const QString& s, uint index=0); bool equal(QTrie* o); void dump(int indent=0); private: TrieList children; bool isword; friend class QDawgPrivate; int maxdepth; int decendants; int key; void distributeKeys(TrieClubDirectory& directory); QTrie* clubLeader(TrieClubDirectory& directory); int collectKeys(); friend class TriePtr; friend class TrieList; }; QTrie::QTrie() { key = 0; isword = FALSE; } QTrie::~QTrie() { // NOTE: we do not delete the children - after conversion to DAWG // it's too difficult. The QTrie's are deleted via the directory. } void QTrie::insertWord(const QString& s, uint index) { if ( index == s.length() ) { isword = TRUE; } else { QTrie* t = children.findAdd(s[index]); t->insertWord(s,index+1); } } bool QTrie::equal(QTrie* o) { if ( o == this ) return TRUE; if ( isword != o->isword ) return FALSE; return children.equal(o->children); } void QTrie::dump(int indent) { for (TrieList::Iterator it=children.begin(); it!=children.end(); ++it) { QTrie* s = (*it).p; for (int in=0; in<indent; in++) fputc(' ',stderr); fprintf(stderr," %c %d %s %p\n",(*it).letter.unicode(), s->key,s->isword?"word":"",s); s->dump(indent+2); } } void QTrie::distributeKeys(TrieClubDirectory& directory) { maxdepth = INT_MIN; decendants = children.count(); key = 0; for (TrieList::Iterator it=children.begin(); it!=children.end(); ++it) { QTrie* s = (*it).p; QChar l = (*it).letter; s->distributeKeys(directory); key = key*64+l.unicode()+s->key*5; decendants += s->decendants; if ( s->maxdepth+1 > maxdepth ) |