#include <cstdio>
-#if 0
-#define ASSERT_NODE(orig, res) do { \
- if (res < -1 || res >= par->n|| (res != -1 && res < orig)) \
- fprintf(stderr, \
- "Assertion failure: original node %i, result %i, line %i\n", \
- orig, res, __LINE__); \
- } while (0)
-#else
-#define ASSERT_NODE(orig, res)
-#endif
-
inline uint32_t xml_tree::size() const
{
return tag_seq_len / 2;
inline uint32_t xml_tree::subtree_size(xml_tree::node_t x) const
{
- return bp_subtree_size(this->par, x);
+ return x == root() ? this->par->n/2 : bp_subtree_size(this->par, x);
}
inline uint32_t
xml_tree::node_t y = bp_find_close(this->par, x);
if (y - x < 10) {
uint32_t count = 0;
- for(xml_tree::node_t i = x; i < y; i++)
+ for (xml_tree::node_t i = x; i <= y; ++i)
count += (tag(i) == label);
return count;
} else {
- return tags->rank(label, y) - tags->rank(label, x);
- };
+ return tags[label]->rank(y) - tags[label]->rank(x);
+ }
+}
+
+inline uint32_t xml_tree::subtree_elements(xml_tree::node_t x,
+ xml_tree::tag_t *atts) const
+{
+
+ int32_t size = bp_subtree_size(par, x) - 1;
+ if (size <= 0) return 0;
+ size -= subtree_tags(x, xml_tree::PCDATA_OPEN_TAG_ID);
+ if (size < 3) return (uint32_t) size;
+ for(; *atts != xml_tree::NIL_TAG_ID; atts++)
+ size -= subtree_tags(x, *atts);
+ return (uint32_t) size;
+
}
inline bool xml_tree::is_leaf(xml_tree::node_t x) const
return !bp_inspect(this->par, x+1);
}
+inline bool xml_tree::is_open(xml_tree::node_t x) const
+{
+ return bp_inspect(this->par, x);
+}
+
inline bool xml_tree::is_ancestor(xml_tree::node_t x,
xml_tree::node_t y) const
{
inline xml_tree::node_t xml_tree::first_child(node_t x) const
{
xml_tree::node_t result = bp_first_child(this->par, x);
- ASSERT_NODE(x, result);
return result;
}
inline xml_tree::node_t xml_tree::next_sibling(xml_tree::node_t x) const
{
xml_tree::node_t result = bp_next_sibling(this->par, x);
- ASSERT_NODE(x, result);
return result;
}
return x;
}
-inline xml_tree::node_t xml_tree::tagged_next(node_t x, tag_t tag) const
+
+inline xml_tree::node_t xml_tree::tagged_next_close(xml_tree::node_t x,
+ xml_tree::tag_t label) const
+{
+ xml_tree::node_t i=x;
+ for(xml_tree::node_t i = x+1; i < std::min(x+100, this->par->n); i++)
+ if (tag(i) == label)
+ return i;
+
+ return tags[label]->select_next(i);
+}
+
+inline xml_tree::node_t xml_tree::tagged_next(xml_tree::node_t x,
+ xml_tree::tag_t label) const
{
- return this->tags->select_next(tag, x);
+ return tags[label]->select_next(x);
}
inline xml_tree::node_t
inline xml_tree::node_t
xml_tree::tagged_following_before(xml_tree::node_t x,
xml_tree::tag_t tag,
- xml_tree::node_t limit) const
+ xml_tree::node_t limit) const
{
xml_tree::node_t close = bp_find_close(this->par, x);
xml_tree::node_t s = tagged_next(close, tag);
return c;
else
return tagged_sibling(c, t);
- /* ASSERT_NODE(x, result);
- return result;*/
}
inline xml_tree::node_t xml_tree::tagged_sibling(xml_tree::node_t x,
xml_tree::tag_t stag;
while (sibling != xml_tree::NIL) {
stag = tag(sibling);
- if (stag == t) {
- ASSERT_NODE(x, sibling);
+ if (stag == t)
return sibling;
- }
sibling = next_sibling(sibling);
};
- ASSERT_NODE(x, sibling);
return sibling;
}
+inline xml_tree::node_t
+xml_tree::select_descendant(xml_tree::node_t x, xml_tree::tag_t *tags) const
+{
+ if (is_leaf(x)) return xml_tree::NIL;
+ auto min = xml_tree::NIL;
+ auto aux = xml_tree::NIL;
+ for(; *tags != xml_tree::NIL_TAG_ID; ++tags){
+ aux = tagged_next(x, *tags);
+ if ((unsigned int) aux < (unsigned int) min) min = aux;
+ };
+ return (min == xml_tree::NIL || is_ancestor(x, min)) ? min : xml_tree::NIL;
+}
+
+
+inline xml_tree::node_t
+xml_tree::select_following_before(xml_tree::node_t x, xml_tree::tag_t *tags,
+ xml_tree::node_t limit) const
+{
+ auto min = xml_tree::NIL;
+ auto aux = xml_tree::NIL;
+ auto close = bp_find_close(this->par, x);
+
+ for(; *tags != xml_tree::NIL_TAG_ID; ++tags){
+ aux = tagged_next(close, *tags);
+ if ((unsigned int) aux < (unsigned int) min) min = aux;
+ }
+
+ return (min == xml_tree::NIL || min < limit) ? min : xml_tree::NIL;
+}
+
+
xml_tree::node_t xml_tree::closing(xml_tree::node_t x) const
{
return bp_find_close(this->par, x);
inline xml_tree::node_t xml_tree::parent_node(int32_t d) const
{
- return (xml_tree::node_t) text_positions->select1(d + 1);
+ xml_tree::node_t res = text_positions->select1(d+1);
+ return (xml_tree::node_t) res;
}
inline SXSI::TextCollection::document_result