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