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 = 2000000;
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 void clearProperties() { fProperties = plist(); }
00161
00162 void exportProperties(vector<Tree>& keys, vector<Tree>& values);
00163
00164 Tree getProperty(Tree key) {
00165 plist::iterator i = fProperties.find(key);
00166 if (i==fProperties.end()) {
00167 return 0;
00168 } else {
00169 return i->second;
00170 }
00171 }
00172 };
00173
00174
00175
00176
00177 inline Tree tree (const Node& n) { Tree br[1]; return CTree::make(n, 0, br); }
00178 inline Tree tree (const Node& n, const Tree& a) { Tree br[]= {a}; return CTree::make(n, 1, br); }
00179 inline Tree tree (const Node& n, const Tree& a, const Tree& b) { Tree br[]= {a,b}; return CTree::make(n, 2, br); }
00180 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); }
00181 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); }
00182
00183 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); }
00184
00185
00186 int tree2int (Tree t);
00187 double tree2float (Tree t);
00188 double tree2double (Tree t);
00189 const char* tree2str (Tree t);
00190 void* tree2ptr (Tree t);
00191 void* getUserData(Tree t);
00192
00193
00194 bool isTree (const Tree& t, const Node& n);
00195 bool isTree (const Tree& t, const Node& n, Tree& a);
00196 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b);
00197 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c);
00198 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d);
00199 bool isTree (const Tree& t, const Node& n, Tree& a, Tree& b, Tree& c, Tree& d, Tree& e);
00200
00201
00202 inline ostream& operator << (ostream& s, const CTree& t) { return t.print(s); }
00203
00204
00205
00206
00207
00208
00209
00210
00211 Tree rec(Tree body);
00212 Tree rec(Tree id, Tree body);
00213
00214 bool isRec(Tree t, Tree& body);
00215 bool isRec(Tree t, Tree& id, Tree& body);
00216
00217
00218
00219 Tree ref(int level);
00220 Tree ref(Tree id);
00221
00222 bool isRef(Tree t, int& level);
00223 bool isRef(Tree t, Tree& id);
00224
00225
00226
00227
00228 inline bool isOpen(Tree t) { return t->aperture() > 0; }
00229 inline bool isClosed(Tree t) { return t->aperture() <= 0;}
00230
00231
00232
00233 Tree lift(Tree t);
00234
00235 Tree deBruijn2Sym (Tree t);
00236 void updateAperture (Tree t);
00237
00238
00239
00240 class Tabber
00241 {
00242 int fIndent;
00243 public:
00244 Tabber(int n=0) : fIndent(n) {}
00245 Tabber& operator++() { fIndent++; return *this;}
00246 Tabber& operator--() { assert(fIndent > 0); fIndent--; return *this; }
00247
00248 ostream& print (ostream& fout)
00249 { for (int i=0; i<fIndent; i++) fout << '\t'; return fout; }
00250 };
00251
00252
00253 inline ostream& operator << (ostream& s, Tabber& t) { return t.print(s); }
00254
00255 extern Tabber TABBER;
00256
00257
00258 #endif