00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 #include <sstream>
00019 #include <vector>
00020
00021 #include "Sym.h"
00022
00023 using namespace std;
00024
00025 typedef UniqueNodeStats* (*NodeStatFunc)(Sym&);
00026
00027 UniqueNodeStats* (*Sym::factory)(const Sym&) = 0;
00028
00029 SymMap Sym::dag(100000);
00030 std::vector<unsigned> Sym::token_count;
00031
00032
00033 size_t get_size(const SymVec& vec) {
00034 size_t sz = 0;
00035 for (unsigned i = 0; i < vec.size(); ++i) {
00036 sz += vec[i].size();
00037 }
00038 return sz;
00039 }
00040
00041 size_t get_depth(const SymVec& vec) {
00042 size_t dp = 1;
00043 for (unsigned i = 0; i < vec.size(); ++i) {
00044 dp = std::max(dp, vec[i].depth());
00045 }
00046 return dp;
00047 }
00048
00049 Sym::Sym(token_t tok, const SymVec& args_) : node(dag.end())
00050 {
00051 detail::SymKey key(tok, detail::SymArgs(args_));
00052 detail::SymValue val;
00053
00054 node = dag.insert(pair<const detail::SymKey, detail::SymValue>(key, val)).first;
00055
00056 if (__unchecked_refcount() == 0) {
00057 node->second.size = 1 + get_size(args_);
00058 node->second.depth = 1 + get_depth(args_);
00059
00060
00061 if (tok >= token_count.size()) {
00062 token_count.resize(tok+1);
00063 }
00064
00065 incref();
00066 node->first.fixate();
00067
00068 if (factory) node->second.uniqueNodeStats = factory(*this);
00069
00070 }
00071 else incref();
00072 }
00073
00074 Sym::Sym(token_t tok, const Sym& a) : node(dag.end()) {
00075 SymVec args_; args_.push_back(a);
00076 detail::SymKey key(tok, detail::SymArgs(args_));
00077 detail::SymValue val;
00078
00079 node = dag.insert(pair<const detail::SymKey, detail::SymValue>(key, val)).first;
00080
00081 if (__unchecked_refcount() == 0) {
00082 node->second.size = 1 + get_size(args_);
00083 node->second.depth = 1 + get_depth(args_);
00084
00085
00086 if (tok >= token_count.size()) {
00087 token_count.resize(tok+1);
00088 }
00089
00090 incref();
00091 node->first.fixate();
00092
00093 if (factory) node->second.uniqueNodeStats = factory(*this);
00094 }
00095 else incref();
00096 }
00097
00098 Sym::Sym(token_t tok) : node(dag.end()) {
00099 detail::SymKey key(tok);
00100 detail::SymValue val;
00101 node = dag.insert(pair<const detail::SymKey, detail::SymValue>(key, val)).first;
00102
00103 if (__unchecked_refcount() == 0) {
00104 node->second.size = 1;
00105 node->second.depth = 1;
00106
00107
00108 if (tok >= token_count.size()) {
00109 token_count.resize(tok+1);
00110 }
00111
00112 incref();
00113
00114
00115 if (factory) node->second.uniqueNodeStats = factory(*this);
00116
00117 }
00118 else incref();
00119 }
00120
00121 std::pair<Sym,bool> insert_subtree_impl(const Sym& cur, size_t w, const Sym& nw) {
00122 if (w-- == 0) return make_pair(nw, !(nw == cur));
00123
00124 const SymVec& vec = cur.args();
00125 std::pair<Sym,bool> result;
00126 unsigned i;
00127
00128 for (i = 0; i < vec.size(); ++i) {
00129 if (w < vec[i].size()) {
00130 result = insert_subtree_impl(vec[i], w, nw);
00131 if (result.second == false) return std::make_pair(cur, false);
00132 break;
00133 }
00134 w -= vec[i].size();
00135 }
00136 SymVec newvec = cur.args();
00137 newvec[i] = result.first;
00138 return make_pair(Sym(cur.token(), newvec), true);
00139 }
00140
00141 Sym insert_subtree(const Sym& cur, size_t w, const Sym& nw) {
00142 return insert_subtree_impl(cur,w,nw).first;
00143 }
00144 Sym get_subtree(const Sym& cur, size_t w) {
00145 if (w-- == 0) return cur;
00146
00147 const SymVec& vec = cur.args();
00148 for (unsigned i = 0; i < vec.size(); ++i) {
00149 if (w < vec[i].size()) return get_subtree(vec[i], w);
00150 w-=vec[i].size();
00151 }
00152 return cur;
00153 }
00154
00155