| -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,279 +1,277 @@ /********************************************************************** ** 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 ) maxdepth = s->maxdepth+1; } if ( decendants ) { key += decendants + maxdepth*256 + children.count() * 65536; if ( !key ) key++; // unlikely } TrieClub* c = directory[key]; if ( !c ) directory.insert(key, (c = new TrieClub) ); c->prepend(this); } QTrie* QTrie::clubLeader(TrieClubDirectory& directory) { if ( !key ) return directory[0]->first(); for (TrieList::Iterator it=children.begin(); it!=children.end(); ++it) { QTrie* t= (*it).p->clubLeader(directory); (*it).p = t; } TrieClub *club = directory[key]; for (TrieClub::Iterator it = club->begin(); it != club->end(); ++it) { QTrie* o = *it; if ( o->equal(this) ) return o; } return this; } int QTrie::collectKeys() { int n=0; if ( key ) key=0,n+=children.count(); for (TrieList::Iterator it=children.begin(); it!=children.end(); ++it) n += (*it).p->collectKeys(); return n; } int TriePtr::operator <(const TriePtr& o) const { return letter < o.letter; } int TriePtr::operator >(const TriePtr& o) const { return letter > o.letter; } 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(); 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; } QTrie* TrieList::findAdd(QChar c) { for (Iterator it=begin(); it!=end(); ++it) { if ( (*it).letter == c ) return (*it).p; } TriePtr p; p.p = new QTrie; p.letter = c; prepend(p); sorted=FALSE; sort(); return p.p; } static const char* dawg_sig = "QDAWG100"; class QDawgPrivate { public: QDawgPrivate(QIODevice* dev) { QDataStream ds(dev); char sig[8]; ds.readRawBytes(sig,8); if ( !strncmp(dawg_sig,sig,8) ) { uint n; char* nn; ds.readBytes(nn,n); // #### endianness problem ignored. node = (QDawg::Node*)nn; nodes = n / sizeof(QDawg::Node); } else { node = 0; } } bool ok() const { return node; } QDawgPrivate(uchar* mem) { if ( !strncmp(dawg_sig,(char*)mem,8) ) { mem += 8; int n = ((mem[0]*256+mem[1])*256+mem[2])*256+mem[3]; mem += 4; // #### endianness problem ignored. node = (QDawg::Node*)((char*)mem); nodes = n / sizeof(QDawg::Node); } } QDawgPrivate(QTrie* t) // destroys the QTrie. { TrieClubDirectory directory(9973); t->distributeKeys(directory); QTrie* l = t->clubLeader(directory); ASSERT(l==t); generateArray(t); TrieClub *club; for (QIntDictIterator<TrieClub> dit(directory); (club=dit); ++dit) { for (TrieClub::Iterator it = club->begin(); it != club->end(); ++it) { delete *it; } delete club; } } bool write(QIODevice* dev) { |