xml-tree.hpp

   1 #ifndef XML_TREE_HPP_
   2 #define XML_TREE_HPP_
   3
   4
   5 #include <cstdint>
   6 #include <unordered_set>
   7 #include <unordered_map>
   8 #include <libbp/bp.h>
   9 #include <libbp/bp-darray.h>
  10 #include <libcds/includes/basics.h>
  11 #include <libcds/includes/static_bitsequence.h>
  12 #include <libcds/includes/alphabet_mapper.h>
  13 #include <libcds/includes/static_sequence.h>
  14 #include "bit-vector.hpp"
  15
  16 #undef W
  17 #undef Wminusone
  18 #undef WW
  19
  20 #include <TextCollection/TextCollection.h>
  21 #include <TextCollection/TextCollectionBuilder.h>
  22
  23 class xml_tree_builder;
  24
  25 class xml_tree {
  26 public:
  27   typedef int32_t node_t;
  28   typedef int32_t tag_t;
  29
  30   static const node_t NIL = -1;
  31   static const node_t ROOT = 0;
  32
  33   static const char* NIL_TAG;
  34   static const tag_t NIL_TAG_ID = -1;
  35   static const char* DOCUMENT_OPEN_TAG;
  36   static const tag_t DOCUMENT_OPEN_TAG_ID = 0;
  37   static const char* ATTRIBUTE_OPEN_TAG;
  38   static const tag_t ATTRIBUTE_OPEN_TAG_ID = 1;
  39   static const char* PCDATA_OPEN_TAG;
  40   static const tag_t PCDATA_OPEN_TAG_ID = 2;
  41   static const char* ATTRIBUTE_DATA_OPEN_TAG;
  42   static const tag_t ATTRIBUTE_DATA_OPEN_TAG_ID = 3;
  43   static const char* CLOSE_TAG;
  44   static const tag_t CLOSE_TAG_ID = 4;
  45
  46
  47   ~xml_tree();
  48
  49   //Counting functions
  50   /**
  51    * [size()] returns the size of the tree (number of nodes)
  52    * Runs in O(1)
  53    */
  54   inline uint32_t size() const;
  55
  56   /**
  57    * [num_tags()] returns the number of distinct tags.
  58    * Runs in O(1)
  59    */
  60   inline uint32_t num_tags() const;
  61
  62   /**
  63    * [subtree_size(n)] returns the size of the subtree (number of nodes)
  64    * rooted at n.
  65    * Runs in O(1)
  66    */
  67   inline uint32_t subtree_size(node_t) const;
  68
  69   /**
  70    * [subtree_tags(n, t)] returns the number of occurences of tag [t] in the
  71    * subtree rooted at [n]
  72    * Runs in O(1)
  73    */
  74   inline uint32_t subtree_tags(node_t, tag_t) const;
  75
  76   /**
  77    * [subtree_elements(n)] returns the number of element nodes below [n]
  78    * Runs in O(1)
  79    */
  80   inline uint32_t subtree_elements(node_t) const;
  81
  82   /**
  83    * [num_children(n)] returns the number of child nodes of [n]
  84    * (both text and elements, and including a fake <@> node if
  85    * present).
  86    * Runs in O(1) (?)
  87    */
  88   uint32_t num_children(node_t) const;
  89
  90   /**
  91    * [child_pos(n)] returns the position of [n] amongst its siblings
  92    * Runs in O(1) (?)
  93    */
  94   uint32_t child_pos(node_t) const;
  95
  96
  97   //Node_T tests
  98   /**
  99    * [is_leaf(n)] returns true if [n] is a leaf (i.e. if [num_children(n)]
 100    * returns 0
 101    * Runs in O(1)
 102    */
 103   inline bool is_leaf(node_t) const;
 104
 105   /**
 106    * [is_ancestor(n, m)] returns true if [n] is an ancestor of [m], false
 107    * otherwise
 108    * Runs in O(1)
 109    */
 110   inline bool is_ancestor(node_t, node_t) const;
 111
 112   /**
 113    * [is_right_descendant(n, m)] returns true if [m] is a descendant-or-self of
 114    * a following-sibling of [n], false otherwise
 115    * Runs in O(1)
 116    */
 117   inline bool is_right_descendant(node_t, node_t) const;
 118
 119   /**
 120    * [is_child(n, m)] returns true if [m] is a child of [n]
 121    * Runs in O(1)
 122    */
 123   bool is_child(node_t, node_t) const;
 124
 125   /**
 126    * [is_first_child(n, m)] returns true if [m] is the first child of [n]
 127    * Runs in O(1)
 128    */
 129   inline bool is_first_child(node_t) const;
 130
 131   /**
 132    * [is_nil(n)] returns true if [n] is equal to xml_tree::NIL
 133    * Runs in O(1)
 134    */
 135   inline bool is_nil(node_t) const;
 136
 137   /**
 138    * [is_open(n)] returns true if [n], seen as an index in the
 139    * underlying BP representation corresponds to an opening parenthesis.
 140    * Runs in O(1)
 141    */
 142   inline bool is_open(node_t) const;
 143
 144   //Numbering functions
 145   /**
 146    * [depth(n)] returns the depths of node [n]. The root has depth 1.
 147    * Runs in O(1)
 148    */
 149   uint32_t depth(node_t) const;
 150
 151   /**
 152    * [preorder(n)] returns the preorder of node [n]. Equivalent to calling
 153    * rank on the underlying BP representation.
 154    * Runs in O(1)
 155    */
 156   uint32_t preorder(node_t) const;
 157
 158   /**
 159    * [preorder(n)] returns the postorder of node [n].
 160    * Runs in O(1)
 161    */
 162   uint32_t postorder(node_t) const;
 163
 164   //Tag functions
 165   /**
 166    * [tag(n)] returns the tag of node [n] which must be a valid node identifier
 167    * (in particular not NIL)
 168    * Runs in O(1)
 169    */
 170   inline tag_t tag(node_t) const;
 171
 172   /**
 173    * [get_tag_name_by_ref(t)] returns the string representation of tag [t]
 174    * For elements, the string representation is the tag name itself
 175    * Returns <!INVALID!> if [t] is not a proper tag identifier.
 176    * Runs in O(1)
 177    */
 178   const char* get_tag_name_by_ref(tag_t) const;
 179
 180   /**
 181    * [register_tag(s)] returns the tag identifier for the tag represented
 182    * by the string [s]. If no such tag exists in the document, return a
 183    * fresh tag identifier [i]. Subsequent calls with the same [s] will return
 184    * the same identifier.
 185    * Runs in O(1)
 186    */
 187   tag_t register_tag(char *s);
 188
 189   //Navigation functions
 190
 191   /**
 192    * [root()] returns the root node of the tree.
 193    * Runs in O(1)
 194    */
 195   inline node_t root () const;
 196
 197   /**
 198    * [child(n, i)] returns the [i]th child of [n]
 199    * Runs in O(i) (?)
 200    */
 201   node_t child(node_t, uint32_t) const;
 202
 203   /**
 204    * [parent(n)] returns the parent node of [n]. Returns
 205    * xml_tree::NIL if [n] is the root of the tree.
 206    * Runs in O(1)
 207    */
 208   inline node_t parent(node_t) const;
 209
 210   /**
 211    * [first_child(n)] returns the first child of [n]. Returns
 212    * xml_tree::NIL if [n] is a leaf.
 213    * Runs in O(1)
 214    */
 215   inline node_t first_child(node_t) const;
 216
 217   /**
 218    * [last_child(n)] returns the last child of [n]. Returns
 219    * xml_tree::NIL if [n] is a leaf.
 220    * Runs in O(1)
 221    */
 222   inline node_t last_child(node_t) const;
 223
 224   /**
 225    * [next_sibling(n)] returns the following sibling of  [n].
 226    * Returns xml_tree::NIL if [n] is the last of its siblings.
 227    * Runs in O(1)
 228    */
 229   inline node_t next_sibling(node_t) const;
 230
 231   /**
 232    * [prev_sibling(n)] returns the preceding sibling of  [n].
 233    * Returns xml_tree::NIL if [n] is the first of its siblings.
 234    * Runs in O(1)
 235    */
 236   inline node_t prev_sibling(node_t) const;
 237
 238   /**
 239    * [first_element(n)] returns the first child of [n] which
 240    * corresponds to an element node. Returns xml_tree::NIL if
 241    * no such node exists.
 242    * Runs in O(1)
 243    */
 244   inline node_t first_element(node_t) const;
 245
 246   /**
 247    * [next_element(n)] returns the first following sibling of [n] which
 248    * corresponds to an element node. Returns xml_tree::NIL if
 249    * no such node exists.
 250    * Runs in O(1)
 251    */
 252   inline node_t next_element(node_t) const;
 253
 254   /**
 255    * [tagged_next(n, t)] returns the first node following [n] in pre-order
 256    * which has tag [t].  Returns xml_tree::NIL if no such node exists.
 257    * Runs in O(1)
 258    */
 259   inline node_t tagged_next(node_t, tag_t) const;
 260
 261   /**
 262    * [tagged_next_close(n, t)], like [tagged_next(n, t)] but uses a euristic to
 263    * return the result faster if the next tag is close to [n].
 264    * Runs in O(1)
 265    */
 266   inline node_t tagged_next_close(node_t, tag_t) const;
 267
 268   /**
 269    * [tagged_descendant(n, t)] returns the first descendant of [n] in
 270    * pre-order which has tag [t].  Returns xml_tree::NIL if no such node
 271    * exists.
 272    * Runs in O(1)
 273    */
 274   inline node_t tagged_descendant(node_t, tag_t) const;
 275
 276   /**
 277    * [tagged_following_before(n, t, m)] returns the first following node
 278    * of [n] in pre-order which has tag [t] and which occurs before node
 279    * [m]. Returns xml_tree::NIL if no such node exists.
 280    * Runs in O(1)
 281    */
 282   inline node_t tagged_following_before(node_t, tag_t, node_t) const;
 283
 284   /**
 285    * [tagged_child(n, t)] returns the first child of [n] in
 286    * pre-order which has tag [t].  Returns xml_tree::NIL if no such node
 287    * exists.
 288    * Runs in O(1)
 289    */
 290   inline node_t tagged_child(node_t, tag_t) const;
 291
 292   /**
 293    * [tagged_sibling(n, t)] returns the first following sibling of [n] in
 294    * pre-order which has tag [t].  Returns xml_tree::NIL if no such node
 295    * exists.
 296    * Runs in O(1)
 297    */
 298   inline node_t tagged_sibling(node_t, tag_t) const;
 299
 300   /**
 301    * [select_child(n, tags)] returns the first child of [n] in
 302    * pre-order which has a tag in [tags]. [tags] is a xml_tree::NIL_TAG_ID
 303    * terminated array of xml_tree::tag_t. Returns xml_tree::NIL if no such
 304    * node exists.
 305    * Runs in O(sizeof(tags))
 306    */
 307   node_t select_child(node_t, tag_t*) const;
 308
 309   /**
 310    * [select_descendant(n, tags)] returns the first descendant of [n] in
 311    * pre-order which has a tag in [tags]. [tags] is a xml_tree::NIL_TAG_ID
 312    * terminated array of xml_tree::tag_t. Returns xml_tree::NIL if no such
 313    * node exists.
 314    * Runs in O(sizeof(tags))
 315    */
 316   inline node_t select_descendant(node_t, tag_t*) const;
 317
 318   /**
 319    * [select_sibling(n, tags)] returns the first following sibling of
 320    * of [n] in pre-order which has a tag in [tags].
 321    * [tags] is a xml_tree::NIL_TAG_ID terminated array of xml_tree::tag_t.
 322    * Returns xml_tree::NIL if no such node exists.
 323    * Runs in O(sizeof(tags))
 324    */
 325   node_t select_sibling(node_t, tag_t*) const;
 326
 327   /**
 328    * [select_sibling(n, tags, m)] returns the first following node
 329    * of [n] in pre-order which has a tag in [tags] and which occurs before
 330    * node [m]. [tags] is a xml_tree::NIL_TAG_ID terminated array of
 331    * xml_tree::tag_t. Returns xml_tree::NIL if no such node exists.
 332    * Runs in O(sizeof(tags))
 333    */
 334   inline node_t select_following_before (node_t, tag_t*, node_t) const;
 335
 336   /**
 337    * [closing(n)] returns the node identifier corresponding to the closing
 338    * parenthesis associated with [n] in the underlying BP representation.
 339    * The result is undefined if [n] does not point to an opening parenthesis.
 340    * Runs in O(1).
 341    */
 342   inline node_t closing(node_t) const;
 343
 344   //Text functions
 345   /**
 346    * [parent_node(i)] returns the node identifier corresponding to the [i]th
 347    * text of the text collection. The result is undefined if [i] does not
 348    * denote a valid text identifier.
 349    * Runs in O(1) ?
 350    */
 351   inline node_t parent_node(int32_t) const;
 352
 353   /**
 354    * [get_text_collection()] returns a pointer to the underlying text collection.
 355    * The pointer may be 0 if text indexing was disabled during index creation.
 356    * Runs in O(1)
 357    */
 358   inline SXSI::TextCollection *get_text_collection() const;
 359
 360   /**
 361    * [text_id_range(n)] returns the identifier of the first and last text fragment
 362    * that occur below node [n]. Returns (-1, -1) if there are no text fragment
 363    * below [n] or if [n] does not denote a valid node.
 364    * Runs in O(1) ?
 365    */
 366   std::pair<int32_t, int32_t> text_id_range(node_t) const;
 367
 368   /**
 369    * [text_id(n)] returns the identifier of the text fragment associated with
 370    * node [n]. The result is unspecified if [n] is not an attribute data node
 371    * or a text node.
 372    * Runs in O(1) ?
 373    */
 374   int32_t text_id(node_t) const;
 375
 376   /**
 377    * [get_text(i)] returns the content of the [i]th text stored in the text
 378    * collection, has a 0 terminated string.
 379    * Runs in O(1) ?
 380    */
 381   const char* get_text(int32_t) const;
 382
 383   SXSI::TextCollection::document_result prefix(uchar const *s) const;
 384   SXSI::TextCollection::document_result suffix(uchar const *s) const;
 385   SXSI::TextCollection::document_result equals(uchar const *s) const;
 386   SXSI::TextCollection::document_result contains(uchar const *s) const;
 387   SXSI::TextCollection::document_result less_than(uchar const *s) const;
 388
 389
 390   bool naive_contains(node_t, uchar const *s) const;
 391
 392   //I/O functions
 393   void save(int, char*);
 394   static xml_tree* load(int, char*, bool, int);
 395   void print(node_t, int, bool no_text=false);
 396   void flush(int);
 397
 398 private:
 399   friend class xml_tree_builder;
 400   xml_tree();
 401   xml_tree(std::vector<int32_t>*,
 402            std::unordered_map<std::string, int32_t>*,
 403            bit_vector*,
 404            bool,
 405            SXSI::TextCollectionBuilder *,
 406            SXSI::TextCollectionBuilder::index_type_t,
 407            bit_vector*);
 408
 409   //Parenthesis sequence
 410   bp *par;
 411   //tag sequence
 412   std::vector<static_bitsequence_sdarray*> tags;
 413   uint32_t *tag_seq;
 414   uint32_t tag_seq_len;
 415   uint32_t bits_per_tag;
 416   //Mapping from tag_t identifiers to/from tagnames
 417   std::vector<std::string> *tag_names;
 418   std::unordered_map<std::string, tag_t> *tag_ids;
 419   //Set of tag ids that map to attribute nodes
 420   std::unordered_set<tag_t> *attribute_ids;
 421   //Text index
 422   SXSI::TextCollection *text_collection;
 423   static_bitsequence *text_positions;
 424   SXSI::TextCollectionBuilder::index_type_t text_index_type;
 425   //auxiliary data structures for efficient printing.
 426   std::vector<std::string> *print_stack;
 427   std::string *print_buffer;
 428
 429 #define BUFFER_SIZE (8192*2)
 430
 431   void uflush(int);
 432   void uflush_r(int, size_t);
 433   void uput_str(std::string s, int fd);
 434   void uputs(const char* s, int fd);
 435   void uputc(const char c, int fd);
 436   size_t uprintf(const char*s, int fd);
 437 };
 438
 439 #define XML_TREE_INTERNAL__ 1
 440 #include "xml-tree-inc.hpp"
 441
 442 #endif //XML_TREE_HPP_