1 #ifndef XML_TREE_INTERNAL__
2 #error "xml-tree-inc.hpp should not be included directly"
5 #ifndef XML_TREE_INC_HPP_
6 #define XML_TREE_INC_HPP_
10 inline uint32_t xml_tree::size() const
12 return tag_seq_len / 2;
15 inline uint32_t xml_tree::num_tags() const
17 return tag_names->size();
20 inline uint32_t xml_tree::subtree_size(xml_tree::node_t x) const
22 return x == root() ? this->par->n/2 : bp_subtree_size(this->par, x);
26 xml_tree::subtree_tags(xml_tree::node_t x, xml_tree::tag_t label) const
28 xml_tree::node_t y = bp_find_close(this->par, x);
31 for (xml_tree::node_t i = x; i <= y; ++i)
32 count += (tag(i) == label);
35 return tags[label]->rank(y) - tags[label]->rank(x);
39 inline uint32_t xml_tree::subtree_elements(xml_tree::node_t x) const
42 int32_t size = bp_subtree_size(par, x) - 1;
43 if (size <= 0) return 0;
44 size -= subtree_tags(x, xml_tree::PCDATA_OPEN_TAG_ID);
45 size -= subtree_tags(x, xml_tree::ATTRIBUTE_OPEN_TAG_ID);
46 size -= subtree_tags(x, xml_tree::ATTRIBUTE_DATA_OPEN_TAG_ID);
47 if (size < 3) return (uint32_t) size;
48 std::unordered_set<xml_tree::tag_t>::iterator it;
49 for(it = this->attribute_ids->begin();
50 it != this->attribute_ids->end();
52 size -= subtree_tags(x, *it);
53 return (uint32_t) size;
57 inline bool xml_tree::is_leaf(xml_tree::node_t x) const
59 return !bp_inspect(this->par, x+1);
62 inline bool xml_tree::is_open(xml_tree::node_t x) const
64 return bp_inspect(this->par, x);
67 inline bool xml_tree::is_ancestor(xml_tree::node_t x,
68 xml_tree::node_t y) const
70 return bp_is_ancestor(this->par, x, y);
74 xml_tree::is_right_descendant(xml_tree::node_t x,
75 xml_tree::node_t y) const
79 && (y <= bp_parent_close(this->par, x))
80 && (y >= bp_find_close(this->par, x));
83 inline bool xml_tree::is_first_child(xml_tree::node_t x) const
85 return (x <= this->root()) || (bp_inspect(this->par, x - 1));
88 inline bool xml_tree::is_nil(xml_tree::node_t x) const
90 return (x == xml_tree::NIL);
93 inline xml_tree::tag_t xml_tree::tag(xml_tree::node_t x) const
95 if (bits_per_tag == 8)
96 return (xml_tree::tag_t) (((unsigned char*) tag_seq)[x]);
98 return get_field(tag_seq, bits_per_tag, x);
101 inline xml_tree::node_t xml_tree::root() const
103 return xml_tree::ROOT;
107 inline xml_tree::node_t xml_tree::parent(xml_tree::node_t x) const
109 return bp_parent(this->par, x);
112 inline xml_tree::node_t xml_tree::first_child(node_t x) const
114 xml_tree::node_t result = bp_first_child(this->par, x);
118 inline xml_tree::node_t xml_tree::last_child(xml_tree::node_t x) const
121 return xml_tree::NIL;
123 return bp_find_open(this->par, bp_find_close(this->par, x) - 1);
126 inline xml_tree::node_t xml_tree::next_sibling(xml_tree::node_t x) const
128 xml_tree::node_t result = bp_next_sibling(this->par, x);
132 inline xml_tree::node_t xml_tree::prev_sibling(xml_tree::node_t x) const
134 return bp_prev_sibling(this->par, x);
137 inline xml_tree::node_t xml_tree::first_element(xml_tree::node_t x) const
139 xml_tree::node_t n = first_child(x);
140 if (is_nil(n)) return xml_tree::NIL;
142 case xml_tree::ATTRIBUTE_OPEN_TAG_ID:
144 if (is_nil(n) || tag(n) != xml_tree::PCDATA_OPEN_TAG_ID) return n;
146 case PCDATA_OPEN_TAG_ID:
148 return bp_inspect(this->par, n) ? n : xml_tree::NIL;
154 inline xml_tree::node_t xml_tree::next_element(xml_tree::node_t x) const
157 if (is_nil(x)) return x;
158 if (tag(x) == xml_tree::PCDATA_OPEN_TAG_ID){
159 xml_tree::node_t y = x + 2;
160 return bp_inspect(this->par, y) ? y : xml_tree::NIL;
166 inline xml_tree::node_t xml_tree::tagged_next_close(xml_tree::node_t x,
167 xml_tree::tag_t label) const
169 xml_tree::node_t i=x;
170 for(i = x+1; i < std::min(x+100, this->par->n); i++)
174 return tags[label]->select_next(i);
177 inline xml_tree::node_t xml_tree::tagged_next(xml_tree::node_t x,
178 xml_tree::tag_t label) const
180 return tags[label]->select_next(x);
183 inline xml_tree::node_t
184 xml_tree::tagged_descendant(xml_tree::node_t x,
185 xml_tree::tag_t tag) const
187 xml_tree::node_t y = tagged_next(x, tag);
188 return is_nil(y) || !is_ancestor(x, y) ? xml_tree::NIL : y;
191 inline xml_tree::node_t
192 xml_tree::tagged_following_before(xml_tree::node_t x,
194 xml_tree::node_t limit) const
196 xml_tree::node_t close = bp_find_close(this->par, x);
197 xml_tree::node_t s = tagged_next(close, tag);
198 return (s < limit) ? s : xml_tree::NIL;
202 inline xml_tree::node_t xml_tree::tagged_child(xml_tree::node_t x,
203 xml_tree::tag_t t) const
205 xml_tree::node_t c = first_child(x);
206 xml_tree::node_t result;
207 if (is_nil(c) || tag(c) == t)
210 return tagged_sibling(c, t);
213 inline xml_tree::node_t xml_tree::tagged_sibling(xml_tree::node_t x,
214 xml_tree::tag_t t) const
216 xml_tree::node_t sibling = next_sibling(x);
217 xml_tree::tag_t stag;
218 while (sibling != xml_tree::NIL) {
222 sibling = next_sibling(sibling);
227 inline xml_tree::node_t
228 xml_tree::select_descendant(xml_tree::node_t x, xml_tree::tag_t *tags) const
230 if (is_leaf(x)) return xml_tree::NIL;
231 auto min = xml_tree::NIL;
232 auto aux = xml_tree::NIL;
233 for(; *tags != xml_tree::NIL_TAG_ID; ++tags){
234 aux = tagged_next(x, *tags);
235 if ((unsigned int) aux < (unsigned int) min) min = aux;
237 return (min == xml_tree::NIL || is_ancestor(x, min)) ? min : xml_tree::NIL;
241 inline xml_tree::node_t
242 xml_tree::select_following_before(xml_tree::node_t x, xml_tree::tag_t *tags,
243 xml_tree::node_t limit) const
245 auto min = xml_tree::NIL;
246 auto aux = xml_tree::NIL;
247 auto close = bp_find_close(this->par, x);
249 for(; *tags != xml_tree::NIL_TAG_ID; ++tags){
250 aux = tagged_next(close, *tags);
251 if ((unsigned int) aux < (unsigned int) min) min = aux;
254 return (min == xml_tree::NIL || min < limit) ? min : xml_tree::NIL;
258 xml_tree::node_t xml_tree::closing(xml_tree::node_t x) const
260 return bp_find_close(this->par, x);
264 inline SXSI::TextCollection *xml_tree::get_text_collection() const
266 return text_collection;
269 inline xml_tree::node_t xml_tree::parent_node(int32_t d) const
271 xml_tree::node_t res = text_positions->select1(d+1);
272 return (xml_tree::node_t) res;
275 inline SXSI::TextCollection::document_result
276 xml_tree::prefix(uchar const *s) const
278 return text_collection->Prefix(s);
281 inline SXSI::TextCollection::document_result
282 xml_tree::suffix(uchar const *s) const
284 return text_collection->Suffix(s);
287 inline SXSI::TextCollection::document_result
288 xml_tree::equals(uchar const *s) const
290 return text_collection->Equal(s);
293 inline SXSI::TextCollection::document_result
294 xml_tree::contains(uchar const *s) const
296 return text_collection->Contains(s);
299 inline SXSI::TextCollection::document_result
300 xml_tree::less_than(uchar const *s) const
302 return text_collection->LessThan(s);
306 #endif //XML_TREE_INC_HPP_