xml-tree-inc.hpp

   1 #ifndef XML_TREE_INTERNAL__
   2 #error "xml-tree-inc.hpp should not be included directly"
   3 #endif
   4
   5 #ifndef XML_TREE_INC_HPP_
   6 #define XML_TREE_INC_HPP_
   7
   8 #include <cstdio>
   9
  10 inline uint32_t xml_tree::size() const
  11 {
  12   return tag_seq_len / 2;
  13 }
  14
  15 inline uint32_t xml_tree::num_tags() const
  16 {
  17   return tag_names->size();
  18 }
  19
  20 inline uint32_t xml_tree::subtree_size(xml_tree::node_t x) const
  21 {
  22   return x == root() ? this->par->n/2 : bp_subtree_size(this->par, x);
  23 }
  24
  25 inline uint32_t
  26 xml_tree::subtree_tags(xml_tree::node_t x, xml_tree::tag_t label) const
  27 {
  28   xml_tree::node_t y = bp_find_close(this->par, x);
  29   if (y - x < 10) {
  30     uint32_t count = 0;
  31     for(xml_tree::node_t i = x; i < y; i++)
  32       count += (tag(i) == label);
  33     return count;
  34   } else {
  35     return tags[label]->rank(y) - tags[label]->rank(x);
  36   };
  37 }
  38
  39 inline uint32_t xml_tree::subtree_elements(xml_tree::node_t x,
  40                                            xml_tree::tag_t *atts) const
  41 {
  42
  43   int32_t size = bp_subtree_size(par, x) - 1;
  44   if (size <= 0) return 0;
  45   size -= subtree_tags(x, xml_tree::PCDATA_OPEN_TAG_ID);
  46   if (size < 3) return (uint32_t) size;
  47   for(; *atts != xml_tree::NIL_TAG_ID; atts++)
  48     size -= subtree_tags(x, *atts);
  49   return (uint32_t) size;
  50
  51 }
  52
  53 inline bool xml_tree::is_leaf(xml_tree::node_t x) const
  54 {
  55   return !bp_inspect(this->par, x+1);
  56 }
  57
  58 inline bool xml_tree::is_open(xml_tree::node_t x) const
  59 {
  60   return bp_inspect(this->par, x);
  61 }
  62
  63 inline bool xml_tree::is_ancestor(xml_tree::node_t x,
  64                                   xml_tree::node_t y) const
  65 {
  66   return bp_is_ancestor(this->par, x, y);
  67 }
  68
  69 inline bool
  70 xml_tree::is_right_descendant(xml_tree::node_t x,
  71                               xml_tree::node_t y) const
  72 {
  73   return
  74     (x > root())
  75     && (y <= bp_parent_close(this->par, x))
  76     && (y >= bp_find_close(this->par, x));
  77 }
  78
  79 inline bool xml_tree::is_first_child(xml_tree::node_t x) const
  80 {
  81   return (x <= this->root()) || (bp_inspect(this->par, x - 1));
  82 }
  83
  84 inline bool xml_tree::is_nil(xml_tree::node_t x) const
  85 {
  86   return (x == xml_tree::NIL);
  87 }
  88
  89 inline xml_tree::tag_t xml_tree::tag(xml_tree::node_t x) const
  90 {
  91   if (bits_per_tag == 8)
  92     return  (xml_tree::tag_t) (((unsigned char*) tag_seq)[x]);
  93   else
  94     return get_field(tag_seq, bits_per_tag, x);
  95 }
  96
  97 inline xml_tree::node_t xml_tree::root() const
  98 {
  99   return xml_tree::ROOT;
 100 }
 101
 102
 103 inline xml_tree::node_t xml_tree::parent(xml_tree::node_t x) const
 104 {
 105   return bp_parent(this->par, x);
 106 }
 107
 108 inline xml_tree::node_t xml_tree::first_child(node_t x) const
 109 {
 110   xml_tree::node_t result = bp_first_child(this->par, x);
 111   return result;
 112 }
 113
 114 inline xml_tree::node_t xml_tree::last_child(xml_tree::node_t x) const
 115 {
 116   if (is_leaf(x))
 117     return  xml_tree::NIL;
 118   else
 119     return bp_find_open(this->par, bp_find_close(this->par, x) - 1);
 120 }
 121
 122 inline xml_tree::node_t xml_tree::next_sibling(xml_tree::node_t x) const
 123 {
 124   xml_tree::node_t result = bp_next_sibling(this->par, x);
 125   return result;
 126 }
 127
 128 inline xml_tree::node_t xml_tree::prev_sibling(xml_tree::node_t x) const
 129 {
 130   return bp_prev_sibling(this->par, x);
 131 }
 132
 133 inline xml_tree::node_t xml_tree::first_element(xml_tree::node_t x) const
 134 {
 135   xml_tree::node_t n = first_child(x);
 136   if (is_nil(n)) return xml_tree::NIL;
 137   switch (tag(n)) {
 138   case xml_tree::ATTRIBUTE_OPEN_TAG_ID:
 139     n = next_sibling(n);
 140     if (is_nil(n) || tag(n) != xml_tree::PCDATA_OPEN_TAG_ID) return n;
 141     //Fallthrough
 142   case PCDATA_OPEN_TAG_ID:
 143     n = n + 2;
 144     return bp_inspect(this->par, n) ? n : xml_tree::NIL;
 145   default:
 146     return n;
 147   };
 148 }
 149
 150 inline xml_tree::node_t xml_tree::next_element(xml_tree::node_t x) const
 151 {
 152   x = next_sibling(x);
 153   if (is_nil(x)) return x;
 154   if (tag(x) == xml_tree::PCDATA_OPEN_TAG_ID){
 155     xml_tree::node_t y = x + 2;
 156     return bp_inspect(this->par, y) ? y : xml_tree::NIL;
 157   } else
 158     return x;
 159 }
 160
 161
 162 inline xml_tree::node_t xml_tree::tagged_next_close(xml_tree::node_t x,
 163                                               xml_tree::tag_t label) const
 164 {
 165   xml_tree::node_t i=x;
 166   for(xml_tree::node_t i = x+1; i < std::min(x+100, this->par->n); i++)
 167     if (tag(i) == label)
 168       return i;
 169
 170   return tags[label]->select_next(i);
 171 }
 172
 173 inline xml_tree::node_t xml_tree::tagged_next(xml_tree::node_t x,
 174                                               xml_tree::tag_t label) const
 175 {
 176   return tags[label]->select_next(x);
 177 }
 178
 179 inline xml_tree::node_t
 180 xml_tree::tagged_descendant(xml_tree::node_t x,
 181                             xml_tree::tag_t tag) const
 182 {
 183   xml_tree::node_t y = tagged_next(x, tag);
 184   return is_nil(y) || !is_ancestor(x, y) ? xml_tree::NIL : y;
 185 }
 186
 187 inline xml_tree::node_t
 188 xml_tree::tagged_following_before(xml_tree::node_t x,
 189                                   xml_tree::tag_t tag,
 190                                   xml_tree::node_t limit) const
 191 {
 192   xml_tree::node_t close = bp_find_close(this->par, x);
 193   xml_tree::node_t s = tagged_next(close, tag);
 194   return (s < limit) ? s : xml_tree::NIL;
 195 }
 196
 197
 198 inline xml_tree::node_t xml_tree::tagged_child(xml_tree::node_t x,
 199                                                xml_tree::tag_t t) const
 200 {
 201   xml_tree::node_t c = first_child(x);
 202   xml_tree::node_t result;
 203   if (is_nil(c) || tag(c) == t)
 204     return c;
 205   else
 206     return tagged_sibling(c, t);
 207 }
 208
 209 inline xml_tree::node_t xml_tree::tagged_sibling(xml_tree::node_t x,
 210                                                  xml_tree::tag_t t) const
 211 {
 212   xml_tree::node_t sibling = next_sibling(x);
 213   xml_tree::tag_t stag;
 214   while (sibling  != xml_tree::NIL) {
 215     stag = tag(sibling);
 216     if (stag == t)
 217       return  sibling;
 218     sibling = next_sibling(sibling);
 219   };
 220   return sibling;
 221 }
 222
 223 inline xml_tree::node_t
 224 xml_tree::select_descendant(xml_tree::node_t x, xml_tree::tag_t *tags) const
 225 {
 226   if (is_leaf(x)) return xml_tree::NIL;
 227   auto min = xml_tree::NIL;
 228   auto aux = xml_tree::NIL;
 229   for(; *tags != xml_tree::NIL_TAG_ID; ++tags){
 230     aux = tagged_next(x, *tags);
 231     if ((unsigned int) aux < (unsigned int) min) min = aux;
 232   };
 233   return (min == xml_tree::NIL || is_ancestor(x, min)) ? min : xml_tree::NIL;
 234 }
 235
 236
 237 inline xml_tree::node_t
 238 xml_tree::select_following_before(xml_tree::node_t x, xml_tree::tag_t *tags,
 239                                   xml_tree::node_t limit) const
 240 {
 241   auto min = xml_tree::NIL;
 242   auto aux = xml_tree::NIL;
 243   auto close = bp_find_close(this->par, x);
 244
 245   for(; *tags != xml_tree::NIL_TAG_ID; ++tags){
 246     aux = tagged_next(close, *tags);
 247     if ((unsigned int) aux < (unsigned int) min) min = aux;
 248   }
 249
 250   return (min == xml_tree::NIL || min < limit) ? min : xml_tree::NIL;
 251 }
 252
 253
 254 xml_tree::node_t xml_tree::closing(xml_tree::node_t x) const
 255 {
 256   return bp_find_close(this->par, x);
 257 }
 258
 259
 260 inline SXSI::TextCollection *xml_tree::get_text_collection() const
 261 {
 262   return text_collection;
 263 }
 264
 265 inline xml_tree::node_t xml_tree::parent_node(int32_t d) const
 266 {
 267   xml_tree::node_t res = text_positions->select1(d+1);
 268   return (xml_tree::node_t) res;
 269 }
 270
 271 inline SXSI::TextCollection::document_result
 272 xml_tree::prefix(uchar const *s) const
 273 {
 274   return text_collection->Prefix(s);
 275 }
 276
 277 inline SXSI::TextCollection::document_result
 278 xml_tree::suffix(uchar const *s) const
 279 {
 280   return text_collection->Suffix(s);
 281 }
 282
 283 inline SXSI::TextCollection::document_result
 284 xml_tree::equals(uchar const *s) const
 285 {
 286   return text_collection->Equal(s);
 287 }
 288
 289 inline SXSI::TextCollection::document_result
 290 xml_tree::contains(uchar const *s) const
 291 {
 292   return text_collection->Contains(s);
 293 }
 294
 295 inline SXSI::TextCollection::document_result
 296 xml_tree::less_than(uchar const *s) const
 297 {
 298   return text_collection->LessThan(s);
 299 }
 300
 301
 302 #endif //XML_TREE_INC_HPP_