1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
/******************************************************************************
*
* $Id$
*
* Copyright (C) 1997-1999 by Dimitri van Heesch.
*
* Permission to use, copy, modify, and distribute this software and its
* documentation under the terms of the GNU General Public License is hereby
* granted. No representations are made about the suitability of this software
* for any purpose. It is provided "as is" without express or implied warranty.
* See the GNU General Public License for more details.
*
* All output generated with Doxygen is not covered by this license.
*
*/
#ifndef SUFFIXTREE_H
#define SUFFIXTREE_H
#include <qlist.h>
#include <qarray.h>
#include <qstring.h>
#include <qfile.h>
class SuffixNodeList;
class IndexTree;
enum WordRefMasks { WORDINNAME_MASK=4, INNAME_MASK=2, FULLWORD_MASK=1 };
enum WordRefBits { WORDINNAME_BIT=2, INNAME_BIT=1, FULLWORD_BIT=0 };
// bool inName;
// bool fullWord;
// bool wordInName;
struct WordRef
{
int id;
short freq;
char flags;
};
class SuffixNode
{
friend class SuffixTree;
friend class IndexNode;
friend class SuffixNodeList;
public:
SuffixNode(const char *);
~SuffixNode();
int insert(const char *word,int refId,int inName,int full);
void addReference(int refId,int inName,int fullWord);
void dump(int,const char *);
void resolveForwardReferences(int &offset);
int size(); // return the size of the tree whose root is this node
bool write(QFile &f);
private:
SuffixNodeList *children;
QArray<WordRef> references;
QString label;
int branchOffset;
int totalFreq;
};
class SuffixNodeList : public QList<SuffixNode>
{
public:
SuffixNodeList() : QList<SuffixNode>() {}
~SuffixNodeList() {}
int compareItems(GCI item1,GCI item2);
};
class SuffixTree
{
friend class SuffixNode;
public:
SuffixTree();
~SuffixTree();
void insertWord(const char *word,int index,bool inName);
//void buildIndex();
void resolveForwardReferences();
void dump();
int size(); // return the size of the (flat) tree in bytes
bool write(QFile &f);
int numberOfNodes() { return nodes; }
private:
int nodes;
SuffixNode *root;
};
extern bool writeNumber(QFile &f,int);
extern bool writeString(QFile &f,const char *s);
#endif
|
