34 #include "DataTable.hpp" 35 #include "../util/MyVector.hpp" 40 class NodeTableEntity:
public DataTable<Node<ARITY> > {
41 mutable MyVector<MyVector<int> > higherLevelTable;
42 mutable MyVector<MyVector<int> > lowerLevelTable;
49 NodeTableEntity(
int n = 1)
50 : DataTable<Node<ARITY> >(n) {
61 DataTable<Node<ARITY> >::init(n);
68 void initTerminals() {
69 MyVector<Node<ARITY> >& t = (*this)[0];
71 for (
int j = 0; j < 2; ++j) {
72 t[j] = Node<ARITY>(j, j);
100 size_t size()
const {
101 return this->totalSize() - (*this)[0].size();
108 int numVars()
const {
109 return this->numRows() - 1;
117 void stretchBottom(
int n) {
122 this->setNumRows(n + 1);
124 for (
int i = n0; i > 0; --i) {
125 size_t m = (*this)[i].size();
126 this->initRow(i + d, m);
128 for (
size_t j = 0; j < m; ++j) {
129 for (
int b = 0; b < ARITY; ++b) {
130 NodeId ff = child(i, j, b);
133 (ii == 0) ? ff : NodeId(ii + d, ff.col());
141 for (
int i = 1 - d; i <= n0; ++i) {
142 size_t m = (*this)[i].size();
143 this->initRow(i + d, m);
145 for (
size_t j = 0; j < m; ++j) {
146 for (
int b = 0; b < ARITY; ++b) {
147 NodeId ff = child(i, j, b);
151 (ii + d <= 0) ? 1 : NodeId(ii + d, ff.col());
158 this->setNumRows(n + 1);
167 Node<ARITY>
const& node(NodeId f)
const {
168 return (*
this)[f.row()][f.col()];
176 Node<ARITY>& node(NodeId f) {
177 return (*
this)[f.row()][f.col()];
186 NodeId child(NodeId f,
int b)
const {
187 return child(f.row(), f.col(), b);
196 NodeId& child(NodeId f,
int b) {
197 return child(f.row(), f.col(), b);
207 NodeId child(
int i,
size_t j,
int b)
const {
208 assert(0 <= b && b < ARITY);
209 return (*
this)[i][j].branch[b];
219 NodeId& child(
int i,
size_t j,
int b) {
220 assert(0 <= b && b < ARITY);
221 return (*
this)[i][j].branch[b];
230 NodeId getZeroDescendant(NodeId f,
int stopLevel)
const {
231 assert(0 <= stopLevel);
232 if (stopLevel == 0 && f.hasEmpty())
return 1;
233 while (f.row() > stopLevel) {
243 higherLevelTable.clear();
244 lowerLevelTable.clear();
251 void makeIndex(
bool useMP =
false)
const {
252 int const n = this->numRows() - 1;
253 higherLevelTable.clear();
254 higherLevelTable.resize(n + 1);
255 lowerLevelTable.clear();
256 lowerLevelTable.resize(n + 1);
257 MyVector<bool> lowerMark(n + 1);
259 for (
int i = n; i >= 1; --i) {
260 MyVector<Node<ARITY> >
const& node = (*this)[i];
261 size_t const m = node.size();
263 MyVector<bool> myLower(n + 1);
267 #pragma omp parallel for schedule(static) 268 for (intmax_t j = 0; j < intmax_t(m); ++j) {
269 for (
int b = 0; b < ARITY; ++b) {
270 int const ii = node[j].branch[b].row();
271 if (ii == 0)
continue;
274 if (ii < lowest) lowest = ii;
276 if (!lowerMark[ii]) {
278 lowerMark[ii] =
true;
285 for (
size_t j = 0; j < m; ++j) {
286 for (
int b = 0; b < ARITY; ++b) {
287 int const ii = node[j].branch[b].row();
288 if (ii == 0)
continue;
289 if (ii < lowest) lowest = ii;
290 if (!lowerMark[ii]) {
292 lowerMark[ii] =
true;
297 higherLevelTable[lowest].push_back(i);
298 MyVector<int>& lower = lowerLevelTable[i];
299 for (
int ii = lowest; ii < i; ++ii) {
300 if (myLower[ii]) lower.push_back(ii);
310 MyVector<int>
const& higherLevels(
int level)
const {
311 if (higherLevelTable.empty()) makeIndex();
312 return higherLevelTable[level];
321 MyVector<int>
const& lowerLevels(
int level)
const {
322 if (lowerLevelTable.empty()) makeIndex();
323 return lowerLevelTable[level];
331 void dumpDot(std::ostream& os, std::string title =
"")
const {
332 os <<
"digraph \"" << title <<
"\" {\n";
333 for (
int i = this->numRows() - 1; i >= 1; --i) {
334 os <<
" " << i <<
" [shape=none];\n";
336 for (
int i = this->numRows() - 2; i >= 1; --i) {
337 os <<
" " << (i + 1) <<
" -> " << i <<
" [style=invis];\n";
340 if (!title.empty()) {
341 os <<
" labelloc=\"t\";\n";
342 os <<
" label=\"" << title <<
"\";\n";
345 bool terminal1 =
false;
347 for (
int i = this->numRows() - 1; i > 0; --i) {
348 size_t m = (*this)[i].size();
350 for (
size_t j = 0; j < m; ++j) {
351 NodeId f = NodeId(i, j);
352 os <<
" \"" << f <<
"\";\n";
354 for (
int b = 0; b < ARITY; ++b) {
355 NodeId ff = child(i, j, b);
356 bool aa = ff.getAttr();
357 if (ff == 0)
continue;
361 os <<
" \"" << f <<
"\" -> \"$\"";
365 os <<
" \"" << f <<
"\" -> \"" << ff <<
"\"";
376 << ((b == 1) ?
"blue" :
377 (b == 2) ?
"red" :
"green");
380 if (aa) os <<
",arrowtail=dot";
386 os <<
" \"$\" [shape=square,label=\"⊤\"];\n";
389 os <<
" {rank=same; " << i;
390 for (
size_t j = 0; j < m; ++j) {
391 os <<
"; \"" << NodeId(i, j) <<
"\"";
402 class NodeTableHandler {
405 NodeTableEntity<ARITY> entity;
408 : refCount(1), entity(n) {
411 Object(NodeTableEntity<ARITY>
const& entity)
412 : refCount(1), entity(entity) {
417 if (refCount == 0)
throw std::runtime_error(
"Too many references");
422 if (refCount == 0)
delete this;
429 NodeTableHandler(
int n = 1)
430 : pointer(new Object(n)) {
433 NodeTableHandler(NodeTableHandler
const& o)
434 : pointer(o.pointer) {
438 NodeTableHandler& operator=(NodeTableHandler
const& o) {
445 ~NodeTableHandler() {
449 NodeTableEntity<ARITY>
const& operator*()
const {
450 return pointer->entity;
453 NodeTableEntity<ARITY>
const* operator->()
const {
454 return &pointer->entity;
461 NodeTableEntity<ARITY>& privateEntity() {
462 if (pointer->refCount >= 2) {
464 pointer =
new Object(pointer->entity);
466 return pointer->entity;
474 NodeTableEntity<ARITY>& init(
int n = 1) {
475 if (pointer->refCount == 1) {
476 pointer->entity.init(n);
480 pointer =
new Object(n);
482 return pointer->entity;
489 void derefLevel(
int i) {
490 if (pointer->refCount == 1) pointer->entity[i].clear();