Documentation step 3: Properly document node numbering functions.

[SXSI/XMLTree.git] / xml-tree.hpp

diff --git a/xml-tree.hpp b/xml-tree.hpp
index ff98f21..aba3160 100644 (file)
--- a/xml-tree.hpp
+++ b/xml-tree.hpp
@@ -3,9 +3,10 @@
 
 
 #include <cstdint>
+#include <unordered_set>
 #include <unordered_map>
-#include <bp/bp.h>
-#include <bp/bp-darray.h>
+#include <libbp/bp.h>
+#include <libbp/bp-darray.h>
 #include <libcds/includes/basics.h>
 #include <libcds/includes/static_bitsequence.h>
 #include <libcds/includes/alphabet_mapper.h>
@@ -46,26 +47,118 @@ public:
   ~xml_tree();
 
   //Counting functions
+  /**
+   * [size()] returns the size of the tree (number of nodes)
+   * Runs in O(1)
+   */
   inline uint32_t size() const;
+
+  /**
+   * [num_tags()] returns the number of distinct tags.
+   * Runs in O(1)
+   */
   inline uint32_t num_tags() const;
+
+  /**
+   * [subtree_size(n)] returns the size of the subtree (number of nodes)
+   * rooted at n.
+   * Runs in O(1)
+   */
   inline uint32_t subtree_size(node_t) const;
+
+  /**
+   * [subtree_tags(n, t)] returns the number of occurences of tag [t] in the
+   * subtree rooted at [n]
+   * Runs in O(1)
+   */
   inline uint32_t subtree_tags(node_t, tag_t) const;
-  uint32_t subtree_elements(node_t) const;
+
+  /**
+   * [subtree_elements(n)] returns the number of element nodes below [n]
+   * Runs in O(attribute_ids->size()+3)
+   */
+  inline uint32_t subtree_elements(node_t) const;
+
+  /**
+   * [num_children(n)] returns the number of child nodes of [n]
+   * (both text and elements, and including a fake <@> node if
+   * present).
+   * Runs in O(1) (?)
+   */
   uint32_t num_children(node_t) const;
+
+  /**
+   * [child_pos(n)] returns the position of [n] amongst its siblings
+   * Runs in O(1) (?)
+   */
   uint32_t child_pos(node_t) const;
 
 
   //Node_T tests
+  /**
+   * [is_leaf(n)] returns true if [n] is a leaf (i.e. if [num_children(n)]
+   * returns 0
+   * Runs in O(1)
+   */
   inline bool is_leaf(node_t) const;
+
+  /**
+   * [is_ancestor(n, m)] returns true if [n] is an ancestor of [m], false
+   * otherwise
+   * Runs in O(1)
+   */
   inline bool is_ancestor(node_t, node_t) const;
+
+  /**
+   * [is_right_descendant(n, m)] returns true if [m] is a descendant-or-self of
+   * a following-sibling of [n], false otherwise
+   * Runs in O(1)
+   */
   inline bool is_right_descendant(node_t, node_t) const;
+
+  /**
+   * [is_child(n, m)] returns true if [m] is a child of [n]
+   * Runs in O(1)
+   */
   bool is_child(node_t, node_t) const;
+
+  /**
+   * [is_first_child(n, m)] returns true if [m] is the first child of [n]
+   * Runs in O(1)
+   */
   inline bool is_first_child(node_t) const;
+
+  /**
+   * [is_nil(n)] returns true if [n] is equal to xml_tree::NIL
+   * Runs in O(1)
+   */
   inline bool is_nil(node_t) const;
+
+  /**
+   * [is_open(n)] returns true if [n], seen as an index in the
+   * underlying BP representation corresponds to an opening parenthesis.
+   * Runs in O(1)
+   */
   inline bool is_open(node_t) const;
 
+  //Numbering functions
+  /**
+   * [depth(n)] returns the depths of node [n]. The root has depth 1.
+   * Runs in O(1)
+   */
   uint32_t depth(node_t) const;
+
+  /**
+   * [preorder(n)] returns the preorder of node [n]. Equivalent to calling
+   * rank on the underlying BP representation.
+   * Runs in O(1)
+   */
   uint32_t preorder(node_t) const;
+
+  /**
+   * [preorder(n)] returns the postorder of node [n].
+   * Runs in O(1)
+   */
   uint32_t postorder(node_t) const;
 
   //Tag functions
@@ -83,15 +176,16 @@ public:
   inline node_t prev_sibling(node_t) const;
   inline node_t first_element(node_t) const;
   inline node_t next_element(node_t) const;
+  inline node_t tagged_next_close(node_t, tag_t) const;
   inline node_t tagged_next(node_t, tag_t) const;
   inline node_t tagged_descendant(node_t, tag_t) const;
   inline node_t tagged_following_before(node_t, tag_t, node_t) const;
   inline node_t tagged_child(node_t, tag_t) const;
   inline node_t tagged_sibling(node_t, tag_t) const;
   node_t select_child(node_t, tag_t*) const;
-  node_t select_descendant(node_t, tag_t*) const;
+  inline node_t select_descendant(node_t, tag_t*) const;
   node_t select_sibling(node_t, tag_t*) const;
-  node_t select_following_before (node_t, tag_t*, node_t) const;
+  inline node_t select_following_before (node_t, tag_t*, node_t) const;
   inline node_t closing(node_t) const;
 
   //Text functions
@@ -107,6 +201,9 @@ public:
   SXSI::TextCollection::document_result contains(uchar const *s) const;
   SXSI::TextCollection::document_result less_than(uchar const *s) const;
 
+
+  bool naive_contains(node_t, uchar const *s) const;
+
   //I/O functions
   void save(int, char*);
   static xml_tree* load(int, char*, bool, int);
@@ -127,13 +224,15 @@ private:
   //Parenthesis sequence
   bp *par;
   //tag sequence
-  static_sequence *tags;
+  std::vector<static_bitsequence_sdarray*> tags;
   uint32_t *tag_seq;
   uint32_t tag_seq_len;
   uint32_t bits_per_tag;
   //Mapping from tag_t identifiers to/from tagnames
   std::vector<std::string> *tag_names;
   std::unordered_map<std::string, tag_t> *tag_ids;
+  //Set of tag ids that map to attribute nodes
+  std::unordered_set<tag_t> *attribute_ids;
   //Text index
   SXSI::TextCollection *text_collection;
   static_bitsequence *text_positions;