00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 #ifndef DJC_COROPA_LIBALGEBRA_LIEBASISH_SEEN
00019 #define DJC_COROPA_LIBALGEBRA_LIEBASISH_SEEN
00020
00022
00095 class hall_basis
00096 {
00097 public:
00099 typedef DEG KEY;
00101 typedef std::pair<KEY, KEY> PARENT;
00102 protected:
00104 std::vector<PARENT> hall_set;
00106 std::map<PARENT, KEY> reverse_map;
00108 std::vector<DEG> degrees;
00110 std::string letters;
00112 std::map<LET, KEY> ltk;
00114 DEG curr_degree;
00115 public:
00117 hall_basis(DEG n_letters)
00118 : curr_degree(0)
00119 {
00120
00121 degrees.push_back(0);
00122 PARENT p(0,0);
00123 hall_set.push_back(p);
00124
00125 for (LET c = 1; c <= n_letters; ++c)
00126 letters += (char) c;
00127
00128
00129 std::string::size_type i;
00130 for (i = 1; i <= letters.size(); ++i)
00131 {
00132 PARENT parents(0,i);
00133 hall_set.push_back(parents);
00134 degrees.push_back(1);
00135 ltk[letters[i - 1]] = (LET) i;
00136 }
00137 curr_degree = 1;
00138
00139 }
00141
00144 inline void growup(DEG desired_degree)
00145 {
00146 for (DEG d = curr_degree + 1; d <= desired_degree; ++d)
00147 {
00148 KEY bound = (KEY)hall_set.size();
00149 for (KEY i = 1; i <= bound; ++i)
00150 for (KEY j = i + 1; j <= bound; ++j)
00151 if ((degrees[i] + degrees[j] == d) && (hall_set[j].first <= i))
00152 {
00153 PARENT parents(i, j);
00154 hall_set.push_back(parents);
00155 degrees.push_back(d);
00156 reverse_map[parents] = (KEY) hall_set.size() - 1;
00157 }
00158 ++curr_degree;
00159 }
00160 }
00162 inline DEG degree(const KEY& k) const
00163 {
00164 return degrees[k];
00165 }
00167 inline KEY keyofletter(LET letter) const
00168 {
00169 return ltk.find(letter)->second;
00170 }
00172 inline KEY lparent(const KEY& k) const
00173 {
00174 return hall_set[k].first;
00175 }
00177 inline KEY rparent(const KEY& k) const
00178 {
00179 return hall_set[k].second;
00180 }
00182 inline bool letter(const KEY& k) const
00183 {
00184 return ((k > 0) && (k <= letters.size()));
00185 }
00187 inline LET getletter(const KEY& k) const
00188 {
00189 return letters[k - 1];
00190 }
00192 inline KEY begin(void) const
00193 {
00194 return 1;
00195 }
00197 inline KEY end(void) const
00198 {
00199 return 0;
00200 }
00202 inline KEY nextkey(const KEY& k) const
00203 {
00204 if (k < (hall_set.size() - 1))
00205 return (k + 1);
00206 else
00207 return 0;
00208 }
00210 inline DEG keypos(const KEY& k) const
00211 {
00212 return k;
00213 }
00215 inline DEG size(void) const
00216 {
00217 return ( (KEY) hall_set.size() - 1);
00218 }
00220 inline friend std::ostream& operator<<(std::ostream& os, hall_basis& b)
00221 {
00222 for (KEY k = b.begin(); k != b.end(); k = b.nextkey(k))
00223 os << b.key2string(k) << ' ';
00224 return os;
00225 }
00226
00227
00229 inline const std::string& key2string(const KEY& k) const
00230 {
00231 static boost::recursive_mutex table_access;
00232
00233 boost::lock_guard<boost::recursive_mutex> lock(table_access);
00234
00235 static std::vector<std::string> table;
00236
00237 if (k > table.size())
00238 {
00239 for (KEY i = (KEY) table.size() + 1; i <= k; ++i)
00240 table.push_back(_key2string(i));
00241 }
00242 return table[k - 1];
00243 }
00244 private:
00246 std::string _key2string(const KEY& k) const
00247 {
00248 std::ostringstream oss;
00249 if (k > 0)
00250 {
00251 if (letter(k))
00252 oss << getletter(k);
00253 else
00254 {
00255 oss << '[';
00256 oss << key2string(lparent(k));
00257 oss << ',';
00258 oss << key2string(rparent(k));
00259 oss << ']';
00260 }
00261 }
00262 return oss.str();
00263 }
00264 };
00265
00267
00273 template<typename SCA, typename RAT, DEG n_letters, DEG max_degree>
00274 class lie_basis : public hall_basis,
00275 public basis_traits<With_Degree, n_letters, max_degree>
00276 {
00277 public:
00279 typedef hall_basis::KEY KEY;
00281 typedef std::map<KEY, SCA> MAP;
00283 typedef lie<SCA, RAT, n_letters, max_degree> LIE;
00285 typedef RAT RATIONAL;
00286 public:
00288 lie_basis(void)
00289 : hall_basis(n_letters) {}
00291
00298 inline const LIE& prod(const KEY& k1, const KEY& k2)
00299 {
00300 static boost::recursive_mutex table_access;
00301
00302 boost::lock_guard<boost::recursive_mutex> lock(table_access);
00303
00304 static std::map<PARENT, LIE> table;
00305 static typename std::map<PARENT, LIE>::iterator it;
00306 PARENT p(k1, k2);
00307 it = table.find(p);
00308 if (it == table.end())
00309 return table[p] = _prod(k1, k2);
00310 else
00311 return it->second;
00312 }
00314
00319 LIE replace(const KEY& k, const std::vector<LET>& s, const std::vector<LIE*>& v, std::map<KEY, LIE>& table)
00320 {
00321 typename std::map<KEY, LIE>::iterator it;
00322 it = table.find(k);
00323 if (it != table.end())
00324 return it->second;
00325 else
00326 {
00327 if (letter(k))
00328 {
00329 typename std::vector<LET>::size_type i;
00330 for (i = 0; i < s.size(); ++i)
00331 if (s[i] == getletter(k))
00332 return table[k] = *(v[i]);
00333 return (table[k] = (LIE)k);
00334 }
00335 else
00336 return (table[k]
00337 = replace(lparent(k), s, v, table)
00338 * replace(rparent(k), s, v, table));
00339 }
00340 }
00341 private:
00343 LIE _prod(const KEY& k1, const KEY& k2)
00344 {
00345 static LIE empty;
00346
00347 if (k1 == k2)
00348 return empty;
00349
00350 if (k1 > k2)
00351 return -prod(k2, k1);
00352
00353 DEG target_degree = degrees[k1] + degrees[k2];
00354 if ((max_degree > 0) && (target_degree > max_degree))
00355 return empty;
00356
00357 growup(target_degree);
00358
00359 PARENT parents(k1, k2);
00360 typename std::map<PARENT, KEY>::const_iterator it;
00361 it = reverse_map.find(parents);
00362 if (it != reverse_map.end())
00363 {
00364
00365 LIE result(it->second);
00366 return result;
00367 }
00368 else
00369
00370 {
00371
00372
00373
00374 KEY k3(lparent (k2));
00375 KEY k4(rparent (k2));
00376 LIE result(prod(k1, k3) * (LIE)k4);
00377 return result.sub_mul(prod(k1, k4), (LIE)k3);
00378 }
00379 }
00381 inline friend std::ostream& operator<<(std::ostream& os, const std::pair<lie_basis*, KEY>& t)
00382 {
00383 return os << t.first->key2string(t.second);
00384 }
00385 };
00386
00387
00388
00389 #endif // DJC_COROPA_LIBALGEBRA_LIEBASISH_SEEN
00390
00391