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(attribute_ids->size()+3)
  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   inline bool is_leaf(node_t) const;
  99   inline bool is_ancestor(node_t, node_t) const;
 100   inline bool is_right_descendant(node_t, node_t) const;
 101   bool is_child(node_t, node_t) const;
 102   inline bool is_first_child(node_t) const;
 103   inline bool is_nil(node_t) const;
 104   inline bool is_open(node_t) const;
 105
 106   uint32_t depth(node_t) const;
 107   uint32_t preorder(node_t) const;
 108   uint32_t postorder(node_t) const;
 109
 110   //Tag functions
 111   inline tag_t tag(node_t) const;
 112   const char* get_tag_name_by_ref(tag_t) const;
 113   tag_t register_tag(char *s);
 114
 115   //Navigation functions
 116   inline node_t root () const;
 117   node_t child(node_t, uint32_t) const;
 118   inline node_t parent(node_t) const;
 119   inline node_t first_child(node_t) const;
 120   inline node_t last_child(node_t) const;
 121   inline node_t next_sibling(node_t) const;
 122   inline node_t prev_sibling(node_t) const;
 123   inline node_t first_element(node_t) const;
 124   inline node_t next_element(node_t) const;
 125   inline node_t tagged_next_close(node_t, tag_t) const;
 126   inline node_t tagged_next(node_t, tag_t) const;
 127   inline node_t tagged_descendant(node_t, tag_t) const;
 128   inline node_t tagged_following_before(node_t, tag_t, node_t) const;
 129   inline node_t tagged_child(node_t, tag_t) const;
 130   inline node_t tagged_sibling(node_t, tag_t) const;
 131   node_t select_child(node_t, tag_t*) const;
 132   inline node_t select_descendant(node_t, tag_t*) const;
 133   node_t select_sibling(node_t, tag_t*) const;
 134   inline node_t select_following_before (node_t, tag_t*, node_t) const;
 135   inline node_t closing(node_t) const;
 136
 137   //Text functions
 138   inline node_t parent_node(int32_t) const;
 139   inline SXSI::TextCollection *get_text_collection() const;
 140   std::pair<int32_t, int32_t> text_id_range(node_t) const;
 141   int32_t text_id(node_t) const;
 142   unsigned char* get_text(int32_t) const;
 143
 144   SXSI::TextCollection::document_result prefix(uchar const *s) const;
 145   SXSI::TextCollection::document_result suffix(uchar const *s) const;
 146   SXSI::TextCollection::document_result equals(uchar const *s) const;
 147   SXSI::TextCollection::document_result contains(uchar const *s) const;
 148   SXSI::TextCollection::document_result less_than(uchar const *s) const;
 149
 150
 151   bool naive_contains(node_t, uchar const *s) const;
 152
 153   //I/O functions
 154   void save(int, char*);
 155   static xml_tree* load(int, char*, bool, int);
 156   void print(node_t, int, bool no_text=false);
 157   void flush(int);
 158
 159 private:
 160   friend class xml_tree_builder;
 161   xml_tree();
 162   xml_tree(std::vector<int32_t>*,
 163            std::unordered_map<std::string, int32_t>*,
 164            bit_vector*,
 165            bool,
 166            SXSI::TextCollectionBuilder *,
 167            SXSI::TextCollectionBuilder::index_type_t,
 168            bit_vector*);
 169
 170   //Parenthesis sequence
 171   bp *par;
 172   //tag sequence
 173   std::vector<static_bitsequence_sdarray*> tags;
 174   uint32_t *tag_seq;
 175   uint32_t tag_seq_len;
 176   uint32_t bits_per_tag;
 177   //Mapping from tag_t identifiers to/from tagnames
 178   std::vector<std::string> *tag_names;
 179   std::unordered_map<std::string, tag_t> *tag_ids;
 180   //Set of tag ids that map to attribute nodes
 181   std::unordered_set<tag_t> *attribute_ids;
 182   //Text index
 183   SXSI::TextCollection *text_collection;
 184   static_bitsequence *text_positions;
 185   SXSI::TextCollectionBuilder::index_type_t text_index_type;
 186   //auxiliary data structures for efficient printing.
 187   std::vector<std::string> *print_stack;
 188   std::string *print_buffer;
 189
 190 #define BUFFER_SIZE (8192*2)
 191
 192   void uflush(int);
 193   void uflush_r(int, size_t);
 194   void uput_str(std::string s, int fd);
 195   void uputs(const char* s, int fd);
 196   void uputc(const char c, int fd);
 197   size_t uprintf(const char*s, int fd);
 198 };
 199
 200 #define XML_TREE_INTERNAL__ 1
 201 #include "xml-tree-inc.hpp"
 202
 203 #endif //XML_TREE_HPP_