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