summaryrefslogtreecommitdiff
path: root/library/qdawg.cpp
Unidiff
Diffstat (limited to 'library/qdawg.cpp') (more/less context) (ignore whitespace changes)
-rw-r--r--library/qdawg.cpp2
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,119 +1,117 @@
1/********************************************************************** 1/**********************************************************************
2** Copyright (C) 2000-2002 Trolltech AS. All rights reserved. 2** Copyright (C) 2000-2002 Trolltech AS. All rights reserved.
3** 3**
4** This file is part of the 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
7** GNU General Public License version 2 as published by the Free Software 7** GNU General Public License version 2 as published by the Free Software
8** Foundation and appearing in the file LICENSE.GPL included in the 8** Foundation and appearing in the file LICENSE.GPL included in the
9** packaging of this file. 9** packaging of this file.
10** 10**
11** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE 11** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
12** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 12** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
13** 13**
14** See http://www.trolltech.com/gpl/ for GPL licensing information. 14** See http://www.trolltech.com/gpl/ for GPL licensing information.
15** 15**
16** Contact info@trolltech.com if any conditions of this licensing are 16** Contact info@trolltech.com if any conditions of this licensing are
17** not clear to you. 17** not clear to you.
18** 18**
19**********************************************************************/ 19**********************************************************************/
20#include "qdawg.h" 20#include "qdawg.h"
21#include <qintdict.h> 21#include <qintdict.h>
22#include <qvaluelist.h>
23#include <qtextstream.h>
24#include <qfile.h> 22#include <qfile.h>
25#include <qtl.h> 23#include <qtl.h>
26 24
27#include <limits.h> 25#include <limits.h>
28#include <stdio.h> 26#include <stdio.h>
29 27
30// for mmap 28// for mmap
31#include <sys/types.h> 29#include <sys/types.h>
32#include <sys/stat.h> 30#include <sys/stat.h>
33#include <sys/mman.h> 31#include <sys/mman.h>
34#include <fcntl.h> 32#include <fcntl.h>
35#include <errno.h> 33#include <errno.h>
36#include <unistd.h> 34#include <unistd.h>
37 35
38class QDawgPrivate; 36class QDawgPrivate;
39class QTrie; 37class QTrie;
40 38
41typedef QValueList<QTrie*> TrieClub; 39typedef QValueList<QTrie*> TrieClub;
42typedef QIntDict<TrieClub> TrieClubDirectory; 40typedef QIntDict<TrieClub> TrieClubDirectory;
43 41
44class TriePtr { 42class TriePtr {
45public: 43public:
46 QChar letter; 44 QChar letter;
47 QTrie* p; 45 QTrie* p;
48 int operator <(const TriePtr& o) const; 46 int operator <(const TriePtr& o) const;
49 int operator >(const TriePtr& o) const; 47 int operator >(const TriePtr& o) const;
50 int operator <=(const TriePtr& o) const; 48 int operator <=(const TriePtr& o) const;
51}; 49};
52 50
53class TrieList : public QValueList<TriePtr> { 51class TrieList : public QValueList<TriePtr> {
54 bool sorted; 52 bool sorted;
55public: 53public:
56 TrieList() 54 TrieList()
57 { 55 {
58 sorted=TRUE; 56 sorted=TRUE;
59 } 57 }
60 58
61 QTrie* findAdd(QChar c); 59 QTrie* findAdd(QChar c);
62 bool equal(TrieList& l); 60 bool equal(TrieList& l);
63 61
64 void sort() 62 void sort()
65 { 63 {
66 if ( !sorted ) { 64 if ( !sorted ) {
67 qHeapSort(*this); 65 qHeapSort(*this);
68 sorted = TRUE; 66 sorted = TRUE;
69 } 67 }
70 } 68 }
71}; 69};
72 70
73// A fast but memory-wasting temporary class. The Dawg is the goal. 71// A fast but memory-wasting temporary class. The Dawg is the goal.
74class QTrie { 72class QTrie {
75public: 73public:
76 QTrie(); 74 QTrie();
77 ~QTrie(); 75 ~QTrie();
78 76
79 void insertWord(const QString& s, uint index=0); 77 void insertWord(const QString& s, uint index=0);
80 bool equal(QTrie* o); 78 bool equal(QTrie* o);
81 void dump(int indent=0); 79 void dump(int indent=0);
82 80
83private: 81private:
84 TrieList children; 82 TrieList children;
85 bool isword; 83 bool isword;
86 84
87 friend class QDawgPrivate; 85 friend class QDawgPrivate;
88 int maxdepth; 86 int maxdepth;
89 int decendants; 87 int decendants;
90 int key; 88 int key;
91 void distributeKeys(TrieClubDirectory& directory); 89 void distributeKeys(TrieClubDirectory& directory);
92 QTrie* clubLeader(TrieClubDirectory& directory); 90 QTrie* clubLeader(TrieClubDirectory& directory);
93 int collectKeys(); 91 int collectKeys();
94 friend class TriePtr; 92 friend class TriePtr;
95 friend class TrieList; 93 friend class TrieList;
96}; 94};
97 95
98QTrie::QTrie() 96QTrie::QTrie()
99{ 97{
100 key = 0; 98 key = 0;
101 isword = FALSE; 99 isword = FALSE;
102} 100}
103 101
104QTrie::~QTrie() 102QTrie::~QTrie()
105{ 103{
106 // NOTE: we do not delete the children - after conversion to DAWG 104 // NOTE: we do not delete the children - after conversion to DAWG
107 // it's too difficult. The QTrie's are deleted via the directory. 105 // it's too difficult. The QTrie's are deleted via the directory.
108} 106}
109 107
110void QTrie::insertWord(const QString& s, uint index) 108void QTrie::insertWord(const QString& s, uint index)
111{ 109{
112 if ( index == s.length() ) { 110 if ( index == s.length() ) {
113 isword = TRUE; 111 isword = TRUE;
114 } else { 112 } else {
115 QTrie* t = children.findAdd(s[index]); 113 QTrie* t = children.findAdd(s[index]);
116 t->insertWord(s,index+1); 114 t->insertWord(s,index+1);
117 } 115 }
118} 116}
119 117