summaryrefslogtreecommitdiffstats
path: root/src/suffixtree.h
blob: 28d2a6cadb65e07ccb8dccc75f955a16f7180620 (plain)
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
/******************************************************************************
 *
 * 
 *
 * Copyright (C) 1997-2003 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.
 *
 * Documents produced by Doxygen are derivative works derived from the
 * input used in their production; they are not affected by this license.
 *
 */

#ifndef SUFFIXTREE_H
#define SUFFIXTREE_H

#include "qtbc.h"
#include <qlist.h>
#include <qarray.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 };

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;
    QCString 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 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