| -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,407 +1,405 @@ /********************************************************************** ** 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) { QDataStream ds(dev); ds.writeRawBytes(dawg_sig,8); // #### endianness problem ignored. ds.writeBytes((char*)node,sizeof(QDawg::Node)*nodes); return dev->state() == IO_Ok; } void dumpWords(int nid=0, int index=0) { static char word[256]; // ick latin1 int i=0; do { QDawg::Node& n = node[nid+i]; word[index] = n.let; if ( n.isword ) fprintf(stderr,"%.*s\n",index+1,word); if ( n.offset ) dumpWords(n.offset+nid+i,index+1); } while (!node[nid+i++].islast); } void dump(int nid=0, int indent=0) { int i=0; do { QDawg::Node& n = node[nid+i]; fprintf(stderr,"%d: ",nid+i); for (int in=0; in<indent; in++) fputc(' ',stderr); fprintf(stderr," %c %d %d %d\n",n.let, n.isword,n.islast,n.offset); if ( n.offset ) dump(n.offset+nid+i,indent+2); } while (!node[nid+i++].islast); } int countWords(int nid=0) { int t=0; int i=0; do { QDawg::Node& n = node[nid+i]; if ( n.isword ) t++; if ( n.offset ) t+=countWords(n.offset+nid+i); } while (!node[nid+i++].islast); return t; } bool contains(const QString& s, int nid=0, int index=0) const { int i=0; do { QDawg::Node& n = node[nid+i]; if ( s[index] == QChar((ushort)n.let) ) { if ( n.isword && index == (int)s.length()-1 ) return TRUE; if ( n.offset ) return contains(s,n.offset+nid+i,index+1); } } while (!node[nid+i++].islast); return FALSE; } void appendAllWords(QStringList& list, int nid=0, QString s="") const { int i=0; int next = s.length(); do { QDawg::Node& n = node[nid+i]; s[next] = QChar((ushort)n.let); if ( n.isword ) list.append(s); if ( n.offset ) appendAllWords(list, n.offset+nid+i, s); } while (!node[nid+i++].islast); } const QDawg::Node* root() { return node; } private: void generateArray(QTrie* t) { nodes = 0; int n = t->collectKeys(); node = new QDawg::Node[n]; appendToArray(t); ASSERT(n == nodes); } int appendToArray(QTrie* t) { if ( !t->key ) { if ( !t->children.count() ) return 0; t->key = nodes; nodes += t->children.count(); QDawg::Node* n = &node[t->key-1]; int here = t->key; for (TrieList::Iterator it=t->children.begin(); it!=t->children.end(); ++it) { QTrie* s = (*it).p; ++n; n->let = (*it).letter.unicode(); n->isword = s->isword; n->islast = 0; n->offset = appendToArray(s); if ( n->offset ) { int t = n->offset-here; n->offset=t; if ( n->offset != t ) qWarning("Overflow: too many words"); } here++; } n->islast = 1; } return t->key; } private: int nodes; QDawg::Node *node; }; /*! \class QDawg qdawg.h \brief 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. |