1 /* Hapy is a public domain software. See Hapy README file for the details. */
2
3 #include <Hapy/Assert.h>
4 #include <Hapy/PreeFarm.h>
5 #include <Hapy/IoStream.h>
6 #include <Hapy/Pree.h>
7
8 #include <functional>
9 #include <algorithm>
10
11
Pree()12 Hapy::Pree::Pree(): up(0), down(0), left(0), right(0), kidCount(0),
13 idata(0), minSize(0), implicit(false), leaf(false) {
14 left = right = this;
15 }
16
17 // parent and nextFramed are not copied
Pree(const Pree & p)18 Hapy::Pree::Pree(const Pree &p): up(0), down(0), left(0), right(0), kidCount(0),
19 idata(p.idata), minSize(p.minSize),
20 implicit(p.implicit), leaf(p.leaf), theRid(p.theRid) {
21 left = right = this;
22 copyKids(p);
23 }
24
~Pree()25 Hapy::Pree::~Pree() {
26 clearKids();
27 }
28
clear()29 void Hapy::Pree::clear() {
30 match.clear();
31
32 up = 0;
33 clearKids();
34 // these should already be correct; we are just trying to be robust here
35 left = right = this;
36 down = 0;
37 kidCount = 0;
38
39 idata = 0;
40 minSize = 0;
41 implicit = leaf = false;
42 theRid.clear();
43 }
44
operator =(const Pree & p)45 Hapy::Pree &Hapy::Pree::operator =(const Pree &p) {
46 if (this != &p) {
47 kidlessAssign(p);
48 clearKids();
49 copyKids(p);
50 }
51 return *this;
52 }
53
clearKids()54 void Hapy::Pree::clearKids() {
55 // we can only put well-formed trees and down may not be well-formed
56 if (down)
57 PreeFarm::Put(popSubTree());
58 }
59
copyKids(const Pree & p)60 void Hapy::Pree::copyKids(const Pree &p) {
61 Assert(!down);
62 for (const_iterator i = p.rawBegin(); i != p.rawEnd(); ++i)
63 newChild() = *i;
64 }
65
coreNode() const66 const Hapy::Pree &Hapy::Pree::coreNode() const {
67 if (implicit) {
68 Should(!leaf);
69 const_iterator i = rawBegin();
70 Assert(i != rawEnd());
71 if (!i->implicit)
72 return *i;
73 ++i;
74 Assert(i != rawEnd());
75 return i->coreNode();
76 }
77 return *this;
78 }
79
deeplyImplicit() const80 bool Hapy::Pree::deeplyImplicit() const {
81 if (!implicit)
82 return false;
83 for (const_iterator i = rawBegin(); i != rawEnd(); ++i) {
84 if (!i->deeplyImplicit())
85 return false;
86 }
87 return true;
88 }
89
rid() const90 const Hapy::RuleId &Hapy::Pree::rid() const {
91 return coreNode().theRid;
92 }
93
count() const94 Hapy::Pree::size_type Hapy::Pree::count() const {
95 const Pree &c = coreNode();
96 return (leaf || c.leaf) ? 0 : c.rawCount();
97 }
98
begin() const99 Hapy::Pree::const_iterator Hapy::Pree::begin() const {
100 const Pree &c = coreNode();
101 return (leaf || c.leaf) ? c.rawEnd() : c.rawBegin();
102 }
103
end() const104 Hapy::Pree::const_iterator Hapy::Pree::end() const {
105 const Pree &c = coreNode();
106 return c.rawEnd();
107 }
108
operator [](size_type idx) const109 const Hapy::Pree &Hapy::Pree::operator [](size_type idx) const {
110 const Pree &c = coreNode();
111 Assert(!leaf && !c.leaf);
112 return c.rawChild(idx);
113 }
114
find(const RuleId & id) const115 const Hapy::Pree &Hapy::Pree::find(const RuleId &id) const {
116 for (const_iterator i = begin(); i != end(); ++i) {
117 if (i->rid() == id)
118 return *i;
119 }
120 Assert(false);
121 return *begin();
122 }
123
image() const124 const Hapy::string &Hapy::Pree::image() const {
125 return coreNode().rawImage();
126 }
127
rawImage() const128 const Hapy::string &Hapy::Pree::rawImage() const {
129 return match.image(); // expensive
130 }
131
132
rawRid() const133 const Hapy::RuleId &Hapy::Pree::rawRid() const {
134 return theRid;
135 }
136
rawRid(const RuleId & aRid)137 void Hapy::Pree::rawRid(const RuleId &aRid) {
138 theRid = aRid;
139 }
140
rawCount() const141 Hapy::Pree::size_type Hapy::Pree::rawCount() const {
142 return kidCount;
143 }
144
rawDeepCount() const145 Hapy::Pree::size_type Hapy::Pree::rawDeepCount() const {
146 Hapy::Pree::size_type count = rawCount();
147 for (const_iterator i = rawBegin(); i != rawEnd(); ++i)
148 count += i->rawDeepCount();
149 return count;
150 }
151
rawBegin() const152 Hapy::Pree::const_iterator Hapy::Pree::rawBegin() const {
153 return const_iterator(down, 0);
154 }
155
rawEnd() const156 Hapy::Pree::const_iterator Hapy::Pree::rawEnd() const {
157 return const_iterator(down, kidCount);
158 }
159
rawChild(size_type idx) const160 const Hapy::Pree &Hapy::Pree::rawChild(size_type idx) const {
161 // should we cache the last lookup, trading space for speed?
162 Assert(down);
163 Assert(0 <= idx && idx < kidCount);
164 const Pree *res = down;
165 if (idx <= kidCount/2) {
166 for (; idx > 0; --idx)
167 res = res->right;
168 } else {
169 for (idx = kidCount - idx; idx > 0; --idx)
170 res = res->left;
171 }
172 Assert(res);
173 return *res;
174 }
175
top() const176 const Hapy::Pree &Hapy::Pree::top() const {
177 return up ? up->top() : *this;
178 }
179
backChild() const180 const Hapy::Pree &Hapy::Pree::backChild() const {
181 Assert(down);
182 return *down->left;
183 }
184
backChild()185 Hapy::Pree &Hapy::Pree::backChild() {
186 Assert(down);
187 return *down->left;
188 }
189
newChild()190 Hapy::Pree &Hapy::Pree::newChild() {
191 Pree *p = PreeFarm::Get();
192 pushChild(p);
193 return *p;
194 }
195
popChild()196 void Hapy::Pree::popChild() {
197 Pree *kid = down->left;
198 rawPopChild(kid);
199 PreeFarm::Put(kid);
200 }
201
rawPopChild(Pree * kid)202 void Hapy::Pree::rawPopChild(Pree *kid) {
203 Assert(kid && kid != this && kid->up == this);
204 Assert(down);
205 Assert(kidCount > 0);
206 if (--kidCount <= 0) {
207 Should(down == kid);
208 down = 0;
209 } else {
210 if (down == kid)
211 down = kid->right;
212 InsertAfter(kid->left, kid->right);
213 kid->left = kid->right = kid;
214 }
215 }
216
217 // extracts this->down and shapes it as a tree
popSubTree()218 Hapy::Pree *Hapy::Pree::popSubTree() {
219 Assert(down);
220
221 // reshape kids list into a tree if we have more than one kid
222 Pree *top = down;
223 if (top->left != top) { // not a well-formed tree
224 Should(kidCount > 1);
225 Pree *kids = down->left;
226 HalfConnect(down->left, down->right); // closed kids loop
227 top->left = top->right = top; // made an isolated top
228 // note that kids "ups" are wrong now, but Farm does not care
229 if (top->down) {
230 top->kidCount += (kidCount - 1);
231 InsertAfter(top->down->left, kids);
232 } else {
233 top->kidCount = (kidCount - 1);
234 top->down = kids;
235 }
236 }
237
238 down = 0;
239 kidCount = 0;
240
241 return top;
242 }
243
pushChild(Pree * p)244 void Hapy::Pree::pushChild(Pree *p) {
245 Assert(p->left == p); // or we would be pushing more than one kid
246 if (down)
247 InsertAfter(down->left, p);
248 else
249 down = p;
250 p->up = this;
251 ++kidCount;
252 }
253
emptyHorizontalLoop() const254 bool Hapy::Pree::emptyHorizontalLoop() const {
255 if (rawCount() <= 1)
256 return false;
257 const Pree &last = backChild();
258 // emulate reverse_iterator
259 for (const Pree *i = down->left->left; i; i = i->left) {
260 if (i->match.start() < last.match.start()) // progress made
261 return false;
262 if (i->sameState(last))
263 return true;
264 if (i == down)
265 break;
266 }
267 return false;
268 }
269
emptyVerticalLoop() const270 bool Hapy::Pree::emptyVerticalLoop() const {
271 for (const Pree *i = up; i; i = i->up) {
272 if (i->minSize > 0) // accumulated debt (a form of progress)
273 return false;
274 if (i->match.start() < this->match.start()) // parsed something
275 return false;
276 if (i->rawRid() == rawRid()) // same rule, no progress
277 return true;
278 }
279 return false;
280 }
281
expectedMinSize() const282 Hapy::Pree::size_type Hapy::Pree::expectedMinSize() const {
283 return minSize + (up ? up->expectedMinSize() : 0);
284 }
285
sameState(const Pree & n) const286 bool Hapy::Pree::sameState(const Pree &n) const {
287 return n.rawRid() == rawRid() &&
288 n.match.start() == match.start() && n.idata == idata;
289 }
290
sameSegment(const Pree * them,bool & exhausted) const291 bool Hapy::Pree::sameSegment(const Pree *them, bool &exhausted) const {
292 exhausted = false;
293 const Pree *us = up;
294 while (us && them) {
295 if (!us->sameState(*them))
296 return false; // found different path component
297 if (us->sameState(*this))
298 return true; // both reached the end of the segment
299 us = us->up;
300 them = them->up;
301 }
302 exhausted = true;
303 return false; // one segment is shorter or both too short
304 }
305
306 // optimization: remove empty trimming and unwanted kids
commit()307 void Hapy::Pree::commit() {
308 // best optimization possible: remove unwanted kids
309 if (leaf) {
310 clearKids();
311 return;
312 }
313
314 // commit kids and remove empty implicit kids
315 for (Pree *kid = down, *next = 0; kid; kid = next) {
316 next = kid->right;
317 if (next == down)
318 next = 0;
319 if (kid->match.size() == 0 && kid->deeplyImplicit()) {
320 rawPopChild(kid);
321 PreeFarm::Put(kid);
322 } else {
323 kid->commit(); // assume that commit does not change match.size
324 }
325 }
326
327 // if an implicit node has only core kid left, replace it with the kid
328 while (implicit && rawCount() == 1) {
329 Pree *c = down;
330 Assert(!(c->down == 0 && c->kidCount > 0));
331 // be careful to move (not to copy) c and not destroy c's kids
332 Should(match == c->match);
333 kidlessAssign(*c);
334 kidCount = c->kidCount;
335 c->kidCount = 0;
336 down = c->down; // raw
337 c->down = 0; // raw
338 // XXX: c kids' "up" points to c, is that bad? should caller s/this/c/?
339 PreeFarm::Put(c);
340 }
341 }
342
343 // assign everything but leave kids alone
kidlessAssign(const Pree & p)344 void Hapy::Pree::kidlessAssign(const Pree &p) {
345 // up, down, and kidCount
346 match = p.match;
347 idata = p.idata;
348 minSize = p.minSize;
349 implicit = p.implicit;
350 leaf = p.leaf;
351 theRid = p.theRid;
352 }
353
rawImage(const string & anImage)354 void Hapy::Pree::rawImage(const string &anImage) {
355 aboutToModify();
356 match.image(anImage);
357 }
358
print(ostream & os) const359 Hapy::ostream &Hapy::Pree::print(ostream &os) const {
360 return coreNode().print(os, "");
361 }
362
print(ostream & os,const string & pfx) const363 Hapy::ostream &Hapy::Pree::print(ostream &os, const string &pfx) const {
364 size_type c = count();
365 os << pfx << rid();
366 if (c > 0)
367 os << '(' << c << ')';
368 os << ": " << coreNode().match << endl;
369 if (c > 0) {
370 const string p = pfx + " ";
371 for (const_iterator i = begin(); i != end(); ++i)
372 i->print(os, p);
373 }
374 return os;
375 }
376
rawPrint(ostream & os,const string & pfx) const377 Hapy::ostream &Hapy::Pree::rawPrint(ostream &os, const string &pfx) const {
378 os << pfx << rawRid() << " (" << rawCount() << "): '" << match << "'" <<
379 " at " << match.start();
380 if (minSize > 0)
381 os << " msize: " << minSize;
382 if (implicit)
383 os << " implicit";
384 if (leaf)
385 os << " leaf";
386 os << endl;
387 if (rawCount()) {
388 const string p = pfx + " ";
389 for (const_iterator i = rawBegin(); i != rawEnd(); ++i)
390 i->rawPrint(os, p);
391 }
392 return os;
393 }
394