00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029 #ifndef TST_H
00030 #define TST_H
00031
00032 #include "ft_allocator.h"
00033
00034
00035
00036
00037
00038 class TST;
00039 class PTST;
00040 class TSTNode;
00041
00043 class TSTNode {
00044 public:
00045 void * data;
00046
00047 TSTNode(char c, TSTNode * u);
00048
00049 TSTNode * next() const;
00050 TSTNode * prev() const;
00051
00052 TSTNode * upper_bound(char s) const;
00053 TSTNode * lower_bound(char s) const;
00054
00055 void print(int level = 0) const;
00056 bool is_eos() const;
00057
00058 private:
00059 char c;
00060 TSTNode * up;
00061 TSTNode * left;
00062 TSTNode * middle;
00063 TSTNode * right;
00064
00065 TSTNode * backtrack_prev() const;
00066 TSTNode * backtrack_next() const;
00067
00068 friend class TST;
00069 friend class PTST;
00070 };
00071
00077 class TST {
00078 public:
00079 TST();
00080
00081 TSTNode * insert(const char * s, FTAllocator & a);
00082 const TSTNode * find(const char * s) const;
00083
00084 TSTNode * first() const;
00085 TSTNode * last() const;
00086 void print() const;
00087 void clear();
00088
00089 protected:
00090 TSTNode * root;
00091 };
00092
00093 enum PartialResult {
00094 Found_Partial,
00095 Found_Complete,
00096 Not_Found
00097 };
00098
00102 class PTST : public TST {
00103 public:
00104 PartialResult find_partial(const TSTNode ** pp,
00105 const char ** s) const;
00106 TSTNode * insert_partial(const char * s, FTAllocator & a);
00107 };
00108
00109 #ifdef HAVE_INLINE
00110 #include "tst.icc"
00111 #endif
00112
00113 #endif