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
00070
00071
00072
00073
00074
00075 #ifndef __TREE__
00076 #define __TREE__
00077
00078 #include "symbol.hh"
00079 #include "node.hh"
00080 #include <vector>
00081 #include <map>
00082 #include <assert.h>
00083
00084
00085
00086 class CTree;
00087 typedef CTree* Tree;
00088
00089 typedef map<Tree, Tree> plist;
00090 typedef vector<Tree> tvec;
00091
00109 class CTree
00110 {
00111 private:
00112 static const int kHashTableSize = 510511;
00113 static Tree gHashTable[kHashTableSize];
00114
00115 public:
00116 static bool gDetails;
00117
00118 private:
00119
00120 Tree fNext;
00121 Node fNode;
00122 void* fType;
00123 plist fProperties;
00124 unsigned int fHashKey;
00125 int fAperture;
00126 tvec fBranch;
00127
00128 CTree (unsigned int hk, const Node& n, const tvec& br);
00129
00130 bool equiv (const Node& n, const tvec& br) const;
00131 static unsigned int calcTreeHash (const Node& n, const tvec& br);
00132 static int calcTreeAperture (const Node& n, const tvec& br);
00133
00134 public:
00135 ~CTree ();
00136
00137 static Tree make (const Node& n, int ar, Tree br[]);
00138 static Tree make(const Node& n, const tvec& br);
00139
00140
00141 const Node& node() const { return fNode; }
00142 int arity() const { return fBranch.size();}
00143 Tree branch(int i) const { return fBranch[i]; }
00144 unsigned int hashkey() const { return fHashKey; }
00145 int aperture() const { return fAperture; }
00146 void setAperture(int a) { fAperture=a; }
00147
00148
00149
00150 ostream& print (ostream& fout) const;
00151 static void control ();
00152
00153
00154 void setType(void* t) { fType = t; }
00155 void* getType() { return fType; }
00156
00157
00158 void setProperty(Tree key, Tree value) { fProperties[key] = value; }
00159 void clearProperty(Tree key) { fProperties.erase(key); }
00160 Tree getProperty(Tree key) {
00161 plist::iterator i = fProperties.find(key);
00162 if (i==fProperties.end()) {
00163 return 0;
00164 } else {
00165 return i->second;
00166 }
00167 }
00168 };
00169
00170
00171
00172
00173 inline Tree tree (const Node& n) { Tree br[1]; return CTree::make(n, 0, br); }
00174 inline Tree tree (const Node& n, const Tree& a) { Tree br[]= {a}; return CTree::make(n, 1, br); }
00175 inline Tree tree (const Node& n, const Tree& a, const Tree& b) { Tree br[]= {a,b}; return CTree::make(n, 2, br); }
00176 inline Tree tree (const Node& n, const Tree& a, const Tree& b, const Tree& c) { Tree br[]= {a,b,c}; return CTree::make(n, 3, br); }
00177 inline Tree tree (const Node& n, const Tree& a, const Tree& b, const Tree& c, const Tree& d) { Tree br[]= {a,b,c,d}; return CTree::make(n, 4, br); }
00178
00179 inline Tree tree (const Node& n, const Tree& a, const Tree& b, const Tree& c, const Tree& d, const Tree& e) { Tree br[]= {a,b,c,d,e}; return CTree::make(n, 5, br); }
00180
00181
00182 int tree2int (Tree t);
00183 float tree2float (Tree t);
00184 const char* tree2str (Tree t);
00185 void* tree2ptr (Tree t);
00186 void* getUserData(Tree t);
00187
00188
00189 bool isTree (const Tree& t, const Node& n);
00190 bool isTree (const Tree& t, const Node& n, Tree& a);
00191 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b);
00192 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c);
00193 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d);
00194 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d, Tree& e);
00195
00196
00197 inline ostream& operator << (ostream& s, const CTree& t) { return t.print(s); }
00198
00199
00200
00201
00202
00203
00204
00205
00206 Tree rec(Tree body);
00207 Tree rec(Tree id, Tree body);
00208
00209 bool isRec(Tree t, Tree& body);
00210 bool isRec(Tree t, Tree& id, Tree& body);
00211
00212
00213
00214 Tree ref(int level);
00215 Tree ref(Tree id);
00216
00217 bool isRef(Tree t, int& level);
00218 bool isRef(Tree t, Tree& id);
00219
00220
00221
00222
00223 inline bool isOpen(Tree t) { return t->aperture() > 0; }
00224 inline bool isClosed(Tree t) { return t->aperture() <= 0;}
00225
00226
00227
00228 Tree lift(Tree t);
00229
00230 Tree deBruijn2Sym (Tree t);
00231 void updateAperture (Tree t);
00232
00233
00234
00235 class Tabber
00236 {
00237 int fIndent;
00238 int fReserve;
00239 public:
00240 Tabber(int n=0) { fIndent = n; }
00241 Tabber& operator++() { fIndent++; return *this;}
00242 Tabber& operator--() { assert(fIndent > 0); fIndent--; return *this; }
00243
00244 ostream& print (ostream& fout)
00245 { fIndent += fReserve; fReserve = 0; for (int i=0; i<fIndent; i++) fout << '\t'; return fout; }
00246 };
00247
00248
00249 inline ostream& operator << (ostream& s, Tabber& t) { return t.print(s); }
00250
00251 extern Tabber TABBER;
00252
00253
00254 #endif