Update code according to libbp renaming.

 * remove hard-coded 'fast' functions (these are now inline static in libbp)
 * remove dead code

git-svn-id: svn+ssh://idea.nguyen.vg/svn/sxsi/branches/XMLTree/library-split@1215 3cdefd35-fc62-479d-8e8d-bae585ffb9ca

diff --git a/Makefile b/Makefile
index 5cc06f8..910eb1d 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -13,7 +13,7 @@ else
        OPT_FLAGS=-O4 $(POPCOUNT_FLAG) -fno-PIC -static
 endif
 
-CXXFLAGS= -std=c++0x $(INC_FLAGS) $(OPT_FLAGS)
+CXXFLAGS=-std=c++0x $(INC_FLAGS) $(OPT_FLAGS)
 CXX=g++
 
 OBJECTS_XMLTREE=XMLTree.o XMLTreeBuilder.o

diff --git a/XMLTree.cpp b/XMLTree.cpp
index c455460..65a577b 100644 (file)
--- a/XMLTree.cpp
+++ b/XMLTree.cpp
@@ -30,8 +30,8 @@ static treeNode fast_sibling(bp* Par,treeNode x,TagType tag){
 \r
   if (tag == PCDATA_TAG_ID){\r
     x = x+2;\r
-    return fast_inspect(Par,x)==OP ? x : NULLT;\r
-  } else return fast_next_sibling(Par,x);\r
+    return bp_inspect(Par,x)==OP ? x : NULLT;\r
+  } else return bp_next_sibling(Par,x);\r
 \r
 }\r
 \r
@@ -71,13 +71,12 @@ XMLTree::XMLTree( pb * const par, uint npar,  vector<string> * const TN,  TagIdM
  {\r
    buffer = 0;\r
    print_stack = 0;\r
-    // creates the data structure for the tree topology\r
-    Par = (bp *)umalloc(sizeof(bp));\r
-    STARTTIMER();\r
-    bp_construct(Par, npar, (pb*) par, OPT_FAST_PREORDER_SELECT | OPT_DEGREE|0);\r
-    STOPTIMER(Building);\r
-    PRINTTIME("Building parenthesis struct", Building);\r
-    STARTTIMER();\r
+   // creates the data structure for the tree topology\r
+   STARTTIMER();\r
+   Par = bp_construct(npar, (pb*) par, OPT_FAST_PREORDER_SELECT | OPT_DEGREE|0);\r
+   STOPTIMER(Building);\r
+   PRINTTIME("Building parenthesis struct", Building);\r
+   STARTTIMER();\r
 \r
 \r
     // creates structure for tags\r
@@ -130,8 +129,8 @@ XMLTree::~XMLTree()
  {\r
     int i;\r
 \r
-    destroyTree(Par);\r
-    free(Par); // frees the memory of struct Par\r
+    bp_delete(Par);\r
+    Par = NULL;\r
 \r
     delete tIdMap;\r
     tIdMap = NULL;\r
@@ -234,9 +233,7 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor, char * name)
     XML_Tree = new XMLTree();\r
     STARTTIMER();\r
     // Load the tree structure\r
-    XML_Tree->Par = (bp *)umalloc(sizeof(bp));\r
-\r
-    loadTree(XML_Tree->Par, fp);\r
+    XML_Tree->Par = loadTree(fp);\r
     STOPTIMER(Loading);\r
     PRINTTIME("Loading parenthesis struct", Loading);\r
     STARTTIMER();\r
@@ -333,42 +330,24 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor, char * name)
 \r
 \r
 \r
-// SubtreeSize(x): the number of nodes (and attributes) in the subtree of node x.\r
-/*int XMLTree::SubtreeSize(treeNode x)\r
- {\r
-    return subtree_size(Par, x);\r
- }\r
-*/\r
-// SubtreeTags(x,tag): the number of occurrences of tag within the subtree of node x.\r
-/*\r
-int XMLTree::SubtreeTags(treeNode x, TagType tag)\r
- {\r
-    if (x == Root())\r
-      x = fast_first_child(Par,x);\r
-\r
 \r
-    int s = x + 2*subtree_size(Par, x) - 1;\r
-\r
-    return (Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1))+1;\r
- }\r
-*/\r
 int XMLTree::SubtreeElements(treeNode x)\r
  {\r
 \r
-    int size = subtree_size(Par,x);\r
+    int size = bp_subtree_size(Par, x);\r
     if (x == Root()){\r
-      x = fast_first_child(Par,x);\r
+      x = bp_first_child(Par,x);\r
       size = size - 1;\r
     };\r
 \r
     int s = x + 2*size - 1;\r
     int ntext = Tags->rank(PCDATA_TAG_ID, s) - Tags->rank(PCDATA_TAG_ID, node2tagpos(x)-1);\r
     size = size - ntext;\r
-    treeNode fin = fast_find_close(Par,x);\r
+    treeNode fin = bp_find_close(Par,x);\r
     treeNode y = Tags->select_next(ATTRIBUTE_TAG_ID,node2tagpos(x));\r
     while (y != NULLT && y < fin){\r
       size -= SubtreeSize(y);\r
-      y = Tags->select_next(ATTRIBUTE_TAG_ID,node2tagpos(y));\r
+      y = Tags->select_next(ATTRIBUTE_TAG_ID, node2tagpos(y));\r
     };\r
     return size;\r
  }\r
@@ -378,68 +357,56 @@ int XMLTree::SubtreeElements(treeNode x)
 bool XMLTree::IsLeaf(treeNode x)\r
  {\r
    NULLT_IF(x==NULLT);\r
-   return fast_isleaf(Par, x);\r
+   return bp_isleaf(Par, x);\r
  }\r
 \r
 // IsAncestor(x,y): returns whether node x is ancestor of node y.\r
 bool XMLTree::IsAncestor(treeNode x, treeNode y)\r
  {\r
-    return fast_is_ancestor(Par, x, y);\r
+    return bp_is_ancestor(Par, x, y);\r
  }\r
 \r
 // IsChild(x,y): returns whether node x is parent of node y.\r
 bool XMLTree::IsChild(treeNode x, treeNode y)\r
  {\r
-    if (!fast_is_ancestor(Par, x, y)) return false;\r
-    return depth(Par, x) == (depth(Par, y) + 1);\r
+    if (!bp_is_ancestor(Par, x, y)) return false;\r
+    return bp_depth(Par, x) == (bp_depth(Par, y) + 1);\r
  }\r
 \r
-// IsFirstChild(x): returns whether node x is the first child of its parent.\r
-/*bool XMLTree::IsFirstChild(treeNode x)\r
- {\r
-    return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == (treeNode)-1));\r
- }\r
-*/\r
 \r
 // NumChildren(x): number of children of node x. Constant time with the data structure\r
 // of Sadakane.\r
 int XMLTree::NumChildren(treeNode x)\r
  {\r
-    return degree(Par, x);\r
+    return bp_degree(Par, x);\r
  }\r
 \r
 // ChildNumber(x): returns i if node x is the i-th children of its parent.\r
 int XMLTree::ChildNumber(treeNode x)\r
  {\r
-    return child_rank(Par, x);\r
+    return bp_child_rank(Par, x);\r
  }\r
 \r
 // Depth(x): depth of node x, a simple binary rank on the parentheses sequence.\r
 int XMLTree::Depth(treeNode x)\r
  {\r
-    return depth(Par, x);\r
+    return bp_depth(Par, x);\r
  }\r
 \r
 // Preorder(x): returns the preorder number of node x, just counting the tree\r
 // nodes (i.e., tags, it disregards the texts in the tree).\r
 int XMLTree::Preorder(treeNode x)\r
  {\r
-    return preorder_rank(Par, x);\r
+    return bp_preorder_rank(Par, x);\r
  }\r
 \r
 // Postorder(x): returns the postorder number of node x, just counting the tree\r
 // nodes (i.e., tags, it disregards the texts in the tree).\r
 int XMLTree::Postorder(treeNode x)\r
  {\r
-    return postorder_rank(Par, x);\r
+    return bp_postorder_rank(Par, x);\r
  }\r
-/*\r
-// Tag(x): returns the tag identifier of node x.\r
-TagType XMLTree::Tag(treeNode x)\r
- {\r
-    return fast_get_field(tags_fix,tags_blen,node2tagpos(x));\r
- }\r
-*/\r
+\r
 // DocIds(x): returns the range of text identifiers that descend from node x.\r
 // returns {NULLT, NULLT} when there are no texts descending from x.\r
 range XMLTree::DocIds(treeNode x)\r
@@ -451,7 +418,7 @@ range XMLTree::DocIds(treeNode x)
      return r;\r
    };\r
    int min = EBVector->rank1(x-1);\r
-   int max = EBVector->rank1(x+2*subtree_size(Par, x)-2);\r
+   int max = EBVector->rank1(x+2*bp_subtree_size(Par, x)-2);\r
    if (min==max) { // range is empty, no texts within the subtree of x\r
      r.min = NULLT;\r
      r.max = NULLT;\r
@@ -463,127 +430,21 @@ range XMLTree::DocIds(treeNode x)
    return r;\r
  }\r
 \r
-// Parent(x): returns the parent node of node x.\r
-/*\r
-treeNode XMLTree::Parent(treeNode x)\r
- {\r
-    if (x == Root())\r
-      return NULLT;\r
-    else\r
-      return  parent(Par, x);;\r
- }*/\r
 \r
 // Child(x,i): returns the i-th child of node x, assuming it exists.\r
 treeNode XMLTree::Child(treeNode x, int i)\r
 {\r
-    if (i <= OPTD) return naive_child(Par, x, i);\r
-    else return child(Par, x, i);\r
+    if (i <= OPTD) return bp_naive_child(Par, x, i);\r
+    else return bp_child(Par, x, i);\r
 }\r
 \r
-// FirstChild(x): returns the first child of node x, assuming it exists. Very fast in BP.\r
-/*\r
-treeNode XMLTree::FirstChild(treeNode x)\r
- {\r
-   NULLT_IF(x==NULLT);\r
-   return fast_first_child(Par, x);\r
- }\r
-*/\r
-/*\r
-treeNode XMLTree::FirstElement(treeNode x)\r
- {\r
-   NULLT_IF(x==NULLT);\r
-   x = fast_first_child(Par, x);\r
-   NULLT_IF(x == NULLT);\r
-   switch (Tag(x)){\r
-\r
-   case PCDATA_TAG_ID:\r
-     x = x+2;\r
-     return (fast_inspect(Par,x)==OP)? x : NULLT;\r
-\r
-   case ATTRIBUTE_TAG_ID:\r
-     x = fast_next_sibling(Par,x);\r
-     if (x != NULLT && Tag(x) == PCDATA_TAG_ID){\r
-       x = x+2;\r
-       return (fast_inspect(Par,x)==OP)? x : NULLT;\r
-     }\r
-     else return x;\r
-   default:\r
-     return x;\r
-   }\r
- }\r
-*//*\r
-treeNode XMLTree::NextElement(treeNode x)\r
-{\r
-  NULLT_IF(x==NULLT);\r
-  x = fast_next_sibling(Par, x);\r
-  NULLT_IF(x == NULLT);\r
-  if (Tag(x) == PCDATA_TAG_ID){\r
-    x = x+2;\r
-     return (fast_inspect(Par,x)==OP)? x : NULLT;\r
-  }\r
-  else return x;\r
-  }*/\r
-\r
-// LastChild(x): returns the last child of node x.\r
-   /*treeNode XMLTree::LastChild(treeNode x)\r
- {\r
-   NULLT_IF(x == NULLT || fast_isleaf(Par,x));\r
-   return find_open(Par, fast_find_close(Par, x)-1);\r
- }\r
-   */\r
-// NextSibling(x): returns the next sibling of node x, assuming it exists.\r
-/*treeNode XMLTree::NextSibling(treeNode x)\r
- {\r
-   NULLT_IF(x==NULLT || x == Root() );\r
-   x = fast_find_close(Par,x)+1;\r
-   return (fast_inspect(Par,x) == CP ? NULLT : x);\r
- }\r
-*/\r
-\r
-// PrevSibling(x): returns the previous sibling of node x, assuming it exists.\r
-/*treeNode XMLTree::PrevSibling(treeNode x)\r
- {\r
-   NULLT_IF(x==NULLT);\r
-   return prev_sibling(Par, x);\r
- }\r
-*/\r
-// TaggedChild(x,tag): returns the first child of node x tagged tag, or NULLT if there is none.\r
-// Because of the balanced-parentheses representation of the tree, this operation is not supported\r
-// efficiently, just iterating among the children of node x until finding the desired child.\r
-/*\r
-treeNode XMLTree::TaggedChild(treeNode x, TagType tag)\r
- {\r
 \r
-   NULLT_IF(x==NULLT || fast_isleaf(Par,x));\r
-   treeNode child;\r
-   child = fast_first_child(Par, x); // starts at first child of node x\r
-   if (Tag(child) == tag)\r
-     return child;\r
-   else\r
-     return TaggedFollowingSibling(child,tag);\r
- }\r
-\r
-// TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or NULLT if there is none.\r
-treeNode XMLTree::TaggedFollowingSibling(treeNode x, TagType tag)\r
-{\r
-  NULLT_IF(x==NULLT);\r
-  treeNode sibling = fast_next_sibling(Par, x);\r
-  TagType ctag;\r
-  while (sibling != NULLT) {\r
-    ctag = Tag(sibling);\r
-    if (ctag == tag) // current sibling is labeled with tag of interest\r
-      return sibling;\r
-    sibling = fast_sibling(Par, sibling, ctag); // OK, let's try with the next sibling\r
-  }\r
-  return NULLT; // no such sibling was found\r
-}\r
-*/\r
 treeNode XMLTree::SelectChild(treeNode x, TagIdSet *tags)\r
 {\r
 \r
-  NULLT_IF(x==NULLT || fast_isleaf(Par,x));\r
+  NULLT_IF(x==NULLT || bp_isleaf(Par,x));\r
   int i;\r
-  treeNode child = fast_first_child(Par, x);\r
+  treeNode child = bp_first_child(Par, x);\r
   TagType t;\r
   while (child != NULLT) {\r
     t = Tag(child);\r
@@ -600,7 +461,7 @@ treeNode XMLTree::SelectFollowingSibling(treeNode x, TagIdSet *tags)
    NULLT_IF(x==NULLT);\r
    int i;\r
    TagType t;\r
-   treeNode sibling = fast_next_sibling(Par, x);\r
+   treeNode sibling = bp_next_sibling(Par, x);\r
    while (sibling != NULLT) {\r
      t = Tag(sibling);\r
      if (tags->find(t) != tags->end()) return sibling;\r
@@ -610,41 +471,6 @@ treeNode XMLTree::SelectFollowingSibling(treeNode x, TagIdSet *tags)
  }\r
 \r
 \r
-// TaggedDescendant(x,tag): returns the first node tagged tag with larger preorder than x and within\r
-// the subtree of x. Returns NULLT if there is none.\r
-/*\r
-treeNode XMLTree::TaggedDescendant(treeNode x, TagType tag)\r
- {\r
-   //NULLT_IF(x==NULLT || fast_isleaf(Par,x));\r
-\r
-   int s = (int) Tags->select_next(tag,node2tagpos(x));\r
-   NULLT_IF (s == -1);\r
-\r
-   treeNode y = tagpos2node(s); // transforms the tag position into a node position\r
-\r
-   return (fast_is_ancestor(Par,x,y) ? y : NULLT);\r
- }\r
-*/\r
-/*\r
-treeNode XMLTree::SelectDescendant(treeNode x, TagIdSet *tags)\r
- {\r
-   NULLT_IF (x ==NULLT || fast_isleaf(Par,x));\r
-   int i;\r
-   treeNode min = NULLT;\r
-   treeNode fc = fast_first_child(Par,x);\r
-   treeNode aux;\r
-   TagIdSet::const_iterator tagit;\r
-   for (tagit = tags->begin(); tagit != tags->end(); tagit++) {\r
-     aux = TaggedDescendant(x, (TagType) *tagit);\r
-     if (aux == fc) return fc;\r
-     if (aux == NULLT) continue;\r
-     if ((min == NULLT) || (aux < min)) min = aux;\r
-   };\r
-   return min;\r
- }\r
-\r
-*/\r
-\r
 // TaggedPrec(x,tag): returns the first node tagged tag with smaller preorder than x and not an\r
 // ancestor of x. Returns NULLT if there is none.\r
 treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag)\r
@@ -654,9 +480,9 @@ treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag)
     r = (int)Tags->rank(tag, node2tagpos(x)-1);\r
     if (r==0) return NULLT; // there is no such node.\r
     s = (int)Tags->select(tag, r);\r
-    root = root_node(Par);\r
+    root = bp_root_node(Par);\r
     node_s = tagpos2node(s);\r
-    while (fast_is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x\r
+    while (bp_is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x\r
        r--;\r
        if (r==0) return NULLT; // there is no such node\r
        s = (int)Tags->select(tag, r);  // we should use select_prev instead when provided\r
@@ -671,37 +497,11 @@ treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag)
 treeNode XMLTree::TaggedFollowing(treeNode x, TagType tag)\r
  {\r
    NULLT_IF (x ==NULLT || x == Root());\r
-   return tagpos2node(Tags->select_next(tag,fast_find_close(Par, x)));\r
+   return tagpos2node(Tags->select_next(tag, bp_find_close(Par, x)));\r
 \r
  }\r
 \r
-// TaggedFollBelow(x,tag,root): returns the first node tagged tag with larger preorder than x\r
-// and not in the subtree of x. Returns NULLT if there is none.\r
-/*\r
-treeNode XMLTree::TaggedFollowingBelow(treeNode x, TagType tag, treeNode ancestor)\r
-{\r
-  // NULLT_IF (x == NULLT || x == Root() || x == ancestor);\r
-\r
-  //Special optimisation, test for the following sibling first\r
-  treeNode close = fast_find_close(Par, x);\r
-  treeNode s = tagpos2node(Tags->select_next(tag, close));\r
-\r
-  if (ancestor == Root() || s==NULLT || s < fast_find_close(Par,ancestor)) return s;\r
-  else return NULLT;\r
-}\r
-*/\r
- /*\r
-treeNode XMLTree::TaggedFollowingBefore(treeNode x, TagType tag, treeNode closing)\r
-{\r
-\r
-  NULLT_IF (x == NULLT || x == Root());\r
-\r
-  treeNode s = tagpos2node(Tags->select_next(tag, fast_find_close(Par, x)));\r
-  NULLT_IF (s == NULLT || s >= closing);\r
 \r
-  return s;\r
-}\r
- */\r
 /* Here we inline TaggedFoll to find the min globally, and only at the end\r
    we check if the min is below the context node */\r
 treeNode XMLTree::SelectFollowingBelow(treeNode x, TagIdSet *tags, treeNode ancestor)\r
@@ -709,9 +509,9 @@ treeNode XMLTree::SelectFollowingBelow(treeNode x, TagIdSet *tags, treeNode ance
 \r
    NULLT_IF(x==NULLT || x==Root());\r
 \r
-   treeNode close = fast_find_close(Par,x);\r
+   treeNode close = bp_find_close(Par,x);\r
    treeNode ns = close+1;\r
-   if ( (fast_inspect(Par,ns) == OP) && (tags->find(Tag(ns)) != tags->end()))\r
+   if ( (bp_inspect(Par,ns) == OP) && (tags->find(Tag(ns)) != tags->end()))\r
      return ns;\r
 \r
    int i;\r
@@ -730,76 +530,10 @@ treeNode XMLTree::SelectFollowingBelow(treeNode x, TagIdSet *tags, treeNode ance
    // found the smallest node in preorder which is after x.\r
    // if ctx is the root node, just return what we found.\r
 \r
-   if (ancestor == Root() || min == NULLT || min < fast_find_close(Par, ancestor)) return min;\r
+   if (ancestor == Root() || min == NULLT || min < bp_find_close(Par, ancestor)) return min;\r
    else return NULLT;\r
 \r
  }\r
-/*\r
-treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode ancestor_closing)\r
- {\r
-\r
-   NULLT_IF(x==NULLT || x==Root());\r
-\r
-   treeNode close = fast_find_close(Par,x);\r
-   treeNode ns = close+1;\r
-   if ( (fast_inspect(Par,ns) == OP) && (tags->find(Tag(ns)) != tags->end()))\r
-     return ns;\r
-\r
-   int i;\r
-   treeNode min = NULLT;\r
-   treeNode aux;\r
-\r
-\r
-   TagIdSet::const_iterator tagit;\r
-   for (tagit = tags->begin(); tagit != tags->end(); ++tagit) {\r
-\r
-     aux = tagpos2node(Tags->select_next(*tagit, close));\r
-     if (aux == NULLT) continue;\r
-     if ((min == NULLT) || (aux < min)) min = aux;\r
-   };\r
-\r
-   // found the smallest node in preorder which is after x.\r
-   // if ctx is the root node, just return what we found.\r
-\r
-   if (ancestor_closing == Root() || min == NULLT || min < ancestor_closing) return min;\r
-   else return NULLT;\r
-\r
- }\r
-*/\r
-/*\r
-treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode closing)\r
- {\r
-\r
-   NULLT_IF(x==NULLT || x==Root());\r
-   int i;\r
-   treeNode min = NULLT;\r
-   treeNode ns = fast_next_sibling(Par, x);\r
-   treeNode close = ns - 1;\r
-   treeNode aux;\r
-   TagIdSet::const_iterator tagit;\r
-   for (tagit = tags->begin(); tagit != tags->end(); tagit++) {\r
-\r
-     aux = tagpos2node(Tags->select_next(*tagit, close));\r
-\r
-     // The next sibling of x is guaranteed to be below ctx\r
-     // and is the node with lowest preorder which is after ctx.\r
-     // if we find it, we return early;\r
-\r
-     if (aux == ns ) return ns;\r
-     if (aux == NULLT) continue;\r
-     if ((min == NULLT) || (aux < min)) min = aux;\r
-   };\r
-\r
-   // found the smallest node in preorder which is after x.\r
-   // if ctx is the root node, just return what we found.\r
-\r
-   NULLT_IF (min == NULLT || min >= closing);\r
-\r
-   return min;\r
-\r
- }\r
-*/\r
-\r
 // TaggedAncestor(x, tag): returns the closest ancestor of x tagged tag. Return\r
 // NULLT is there is none.\r
 treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag)\r
@@ -807,10 +541,10 @@ treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag)
     if (x == NULLT || x == Root())\r
        return NULLT;\r
 \r
-    treeNode s = parent(Par, x), r = Root();\r
+    treeNode s = bp_parent(Par, x), r = Root();\r
     while (s != r) {\r
       if (Tag(s) == tag) return s;\r
-       s = parent(Par, s);\r
+       s = bp_parent(Par, s);\r
     }\r
     return NULLT;\r
  }\r
@@ -845,7 +579,7 @@ int XMLTree::TextXMLId(DocID d)
  {\r
    NULLT_IF(d == NULLT);\r
      int s = EBVector->select1(d+1);\r
-   return rank_open(Par, s) + d + 1; // +1 because root has preorder 1\r
+   return bp_rank_open(Par, s) + d + 1; // +1 because root has preorder 1\r
 \r
  }\r
 \r
@@ -856,7 +590,7 @@ int XMLTree::NodeXMLId(treeNode x)
  {\r
    NULLT_IF(x == NULLT);\r
    if (x == Root()) return 1; // root node has preorder 1\r
-   return rank_open(Par, x) + EBVector->rank1(x-1);\r
+   return bp_rank_open(Par, x) + EBVector->rank1(x-1);\r
  }\r
 \r
 // ParentNode(d): returns the parent node of document identifier d.\r
@@ -917,9 +651,9 @@ TagType XMLTree::RegisterTag(unsigned char *tagname)
 \r
 \r
 treeNode XMLTree::Closing(treeNode x) {\r
-  return fast_find_close(Par,x);\r
+  return bp_find_close(Par,x);\r
 }\r
-bool XMLTree::IsOpen(treeNode x) { return fast_inspect(Par,x); }\r
+bool XMLTree::IsOpen(treeNode x) { return bp_inspect(Par,x); }\r
 \r
 //WARNING this uses directly the underlying implementation for plain text\r
 \r
@@ -933,7 +667,7 @@ void XMLTree::Print(int fd,treeNode x, bool no_text){
     print_stack->reserve(256);\r
   };\r
 \r
-  treeNode fin = fast_find_close(Par,x);\r
+  treeNode fin = bp_find_close(Par,x);\r
   treeNode n = x;\r
   TagType tag = Tag(n);\r
 \r
@@ -957,7 +691,7 @@ void XMLTree::Print(int fd,treeNode x, bool no_text){
    size_t read = 0;\r
 \r
    while (n <= fin){\r
-     if (fast_inspect(Par,n)){\r
+     if (bp_inspect(Par,n)){\r
        if (tag == PCDATA_TAG_ID) {\r
 \r
         if (no_text)\r
@@ -974,14 +708,14 @@ void XMLTree::Print(int fd,treeNode x, bool no_text){
         _dputc('<',fd);\r
         _dput_str((*TagName)[tag], fd);\r
         n++;\r
-        if (fast_inspect(Par,n)) {\r
+        if (bp_inspect(Par,n)) {\r
           print_stack->push_back(&((*TagName)[tag]));\r
           tag = Tag(n);\r
           if (tag == ATTRIBUTE_TAG_ID){\r
             n++;\r
             if (no_text) _dputs("><@@>",fd);\r
 \r
-            while (fast_inspect(Par,n)){\r
+            while (bp_inspect(Par,n)){\r
               if (no_text) {\r
                 _dputc('<', fd);\r
                 _dputs((const char*) &(GetTagNameByRef(Tag(n))[3]), fd);\r
@@ -1021,7 +755,7 @@ void XMLTree::Print(int fd,treeNode x, bool no_text){
         _dputc('>', fd);\r
         print_stack->pop_back();\r
         n++;\r
-       } while (!(fast_inspect(Par,n) || print_stack->empty()));\r
+       } while (!(bp_inspect(Par,n) || print_stack->empty()));\r
      tag = Tag(n);\r
    };\r
    _dputc('\n', fd);\r

diff --git a/XMLTree.h b/XMLTree.h
index a96d1f1..1cab2aa 100644 (file)
--- a/XMLTree.h
+++ b/XMLTree.h
@@ -99,52 +99,6 @@ typedef TagIdMap::const_iterator TagIdMapIT;
 
 #define BUFFER_ALLOC (8192 * 2)
 #define BUFFER_SIZE (BUFFER_ALLOC / 2)
-static inline int fast_find_open(bp *b,int s)
-{
-  int r;
-  r = bwd_excess(b,s,0);
-  if (r >= -1) return r+1;
-  return -1;
-}
-
-static inline int fast_find_close(bp *b,int s)
-{
-  return fwd_excess(b,s,-1);
-}
-
-static inline int fast_find_parent_close(bp *b,int s)
-{
-  return fwd_excess(b,s,-2);
-}
-
-
-static inline int fast_inspect(bp* Par,treeNode i)
-{
-  int j,l;
-  j = i >> logD;
-  l = i & (D-1);
-  return (Par->B[j] >> (D-1-l)) & 1;
-}
-
-static bool fast_isleaf(bp* Par,treeNode x){
-  return (fast_inspect(Par, x+1) == CP);
-}
-
-static treeNode fast_first_child(bp *Par, treeNode x)
-{
-  x = x+1;
-  return (fast_inspect(Par,x) == OP) ? x : NULLT;
-}
-
-inline static treeNode fast_next_sibling(bp* Par,treeNode x)
-{
-  treeNode y = fast_find_close(Par,x)+1;
-  return (fast_inspect(Par, y) == OP) ? y : NULLT;
-}
-
-inline static bool fast_is_ancestor(bp * Par,treeNode x,treeNode y){
-  return (x <= y) && ((x==0) || (y <= fast_find_close(Par,x)));
-}
 
 // tag position -> tree node
 static treeNode tagpos2node(int t)
@@ -292,13 +246,13 @@ public:
 
    /** SubtreeSize(x): the number of nodes (and attributes) in the subtree of
     * node x. */
-   int SubtreeSize(treeNode x) { return subtree_size(Par, x); }
+   int SubtreeSize(treeNode x) { return bp_subtree_size(Par, x); }
 
    /** SubtreeTags(x,tag): the number of occurrences of tag within the subtree
     * of node x. */
    int SubtreeTags(treeNode x, TagType tag){
           //int s = x + 2*subtree_size(Par, x) - 1;
-          treeNode y = fast_find_close(Par, x);
+          treeNode y = bp_find_close(Par, x);
 
           if (y - x < 10) {
                   int count = 0;
@@ -328,8 +282,8 @@ public:
        not a descendant of the first child of x */
    bool IsRightDescendant(treeNode x, treeNode y) {
      if (x <= Root()) return false;
-     treeNode z = fast_find_parent_close(Par, x);
-     treeNode c = fast_find_close(Par, x);
+     treeNode z = bp_parent_close(Par, x);
+     treeNode c = bp_find_close(Par, x);
      return (y > c && y < z );
    }
 
@@ -340,7 +294,7 @@ public:
    /** IsFirstChild(x): returns whether node x is the first child of its parent. */
    /* OCAML */
    bool IsFirstChild(treeNode x) {
-          return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == (treeNode)-1));
+          return ((x != NULLT)&&(x==Root() || bp_prev_sibling(Par,x) == (treeNode)-1));
    };
 
    /** NumChildren(x): number of children of node x. Constant time with the
@@ -370,10 +324,7 @@ public:
 
    /** Parent(x): returns the parent node of node x. */
    treeNode Parent(treeNode x) {
-    if (x == Root())
-      return NULLT;
-    else
-      return parent(Par, x);
+     return (x == Root()) ? NULLT : bp_parent(Par, x);
    };
 
    treeNode BinaryParent(treeNode x){
@@ -381,7 +332,7 @@ public:
        return NULLT;
      else {
        treeNode prev = x - 1;
-       return (fast_inspect(Par, prev) == OP) ? prev : fast_find_open(Par, prev);
+       return (bp_inspect(Par, prev) == OP) ? prev : bp_find_open(Par, prev);
      };
    };
 
@@ -394,8 +345,8 @@ public:
 
    /** LastChild(x): returns the last child of node x.  */
    treeNode LastChild(treeNode x) {
-          NULLT_IF(x == NULLT || fast_isleaf(Par,x));
-          return fast_find_open(Par, fast_find_close(Par, x)-1);
+          NULLT_IF(x == NULLT || bp_isleaf(Par,x));
+          return bp_find_open(Par, bp_find_close(Par, x)-1);
    }
 
    /** PrevSibling(x): returns the previous sibling of node x, assuming it
@@ -404,7 +355,7 @@ public:
    treeNode PrevSibling(treeNode x)
    {
           NULLT_IF(x==NULLT);
-          return prev_sibling(Par, x);
+          return bp_prev_sibling(Par, x);
    }
 
 
@@ -427,7 +378,7 @@ public:
    treeNode SelectDescendant(treeNode x, TagIdSet * tags) {
    NULLT_IF (x == NULLT);
    treeNode fc = x+1;
-   if (fast_inspect(Par, fc) == CP) return NULLT;
+   if (bp_inspect(Par, fc) == CP) return NULLT;
    treeNode min = NULLT;
    treeNode aux;
 
@@ -460,7 +411,7 @@ public:
 
    NULLT_IF(x <= 0);
 
-   treeNode close = fast_find_close(Par,x);
+   treeNode close = bp_find_close(Par,x);
 
 
    treeNode min = NULLT;
@@ -688,7 +639,7 @@ public:
     */
    treeNode FirstChild(treeNode x) {
           NULLT_IF(x==NULLT);
-          return fast_first_child(Par, x);
+          return bp_first_child(Par, x);
    };
 
 
@@ -698,17 +649,17 @@ public:
    treeNode FirstElement(treeNode node){
      {
        NULLT_IF(node == NULLT);
-       treeNode x = fast_first_child(Par, node);
+       treeNode x = bp_first_child(Par, node);
        NULLT_IF(x == NULLT);
        switch (Tag(x)){
 
        case ATTRIBUTE_TAG_ID:
-              x = fast_next_sibling(Par,x);
+              x = bp_next_sibling(Par,x);
               if (x == NULLT || Tag(x) != PCDATA_TAG_ID) return x;
 
        case PCDATA_TAG_ID:
               x = x+2;
-              return (fast_inspect(Par,x)==OP)? x : NULLT;
+              return (bp_inspect(Par,x)==OP)? x : NULLT;
 
        default:
               return x;
@@ -721,7 +672,7 @@ public:
 
   treeNode NextSibling(treeNode x) {
     NULLT_IF (x <= 0);
-    return fast_next_sibling(Par, x);
+    return bp_next_sibling(Par, x);
   };
 
    /** NextElement(x): returns the first non text, non attribute sibling of node x, or NULLT
@@ -730,11 +681,11 @@ public:
   treeNode NextElement(treeNode x)
   {
     NULLT_IF(x <= 0);
-    x = fast_next_sibling(Par, x);
+    x = bp_next_sibling(Par, x);
     NULLT_IF(x == NULLT);
     if (Tag(x) == PCDATA_TAG_ID){
       int y = x+2;
-      return (fast_inspect(Par, y) == OP) ? y : NULLT;
+      return (bp_inspect(Par, y) == OP) ? y : NULLT;
     }
     else return x;
   };
@@ -753,21 +704,21 @@ public:
 
          treeNode y = tagpos2node(s); // transforms the tag position into a node position
 
-         return (fast_is_ancestor(Par,x,y) ? y : NULLT);
+         return (bp_is_ancestor(Par,x,y) ? y : NULLT);
   };
 
   inline treeNode TaggedFollowingBelow(treeNode x, TagType tag, treeNode ancestor)
   {
-         treeNode close = fast_find_close(Par, x);
+         treeNode close = bp_find_close(Par, x);
          treeNode s = tagpos2node(Tags->select_next(tag, close));
 
-         if (ancestor == Root() || s == NULLT || s < fast_find_close(Par,ancestor)) return s;
+         if (ancestor == Root() || s == NULLT || s < bp_find_close(Par,ancestor)) return s;
          else return NULLT;
   };
 
   inline treeNode TaggedFollowingBefore(treeNode x, TagType tag, treeNode ancestor_closing)
   {
-         treeNode close = fast_find_close(Par, x);
+         treeNode close = bp_find_close(Par, x);
          treeNode s = tagpos2node(Tags->select_next(tag, close));
 
          if (ancestor_closing == Root() || s == NULLT || s < ancestor_closing) return s;
@@ -776,9 +727,9 @@ public:
 
   inline treeNode NextNodeBefore(treeNode x, treeNode ancestor_closing)
   {
-    treeNode close = fast_find_close(Par, x);
-    int rank = rank_open(Par, close);
-    treeNode y = select_open(Par, rank+1);
+    treeNode close = bp_find_close(Par, x);
+    int rank = bp_rank_open(Par, close);
+    treeNode y = bp_select_open(Par, rank+1);
     return (y < ancestor_closing) ? y : NULLT;
   };
 
@@ -788,7 +739,7 @@ treeNode TaggedFollowingSibling(treeNode x, TagType tag)
   NULLT_IF(x==NULLT);
   treeNode sibling = x;
   TagType ctag;
-  while ((sibling = fast_next_sibling(Par, sibling)) != NULLT) {
+  while ((sibling = bp_next_sibling(Par, sibling)) != NULLT) {
     ctag = Tag(sibling);
     if (ctag == tag) return sibling;
   }
@@ -798,9 +749,9 @@ treeNode TaggedFollowingSibling(treeNode x, TagType tag)
 treeNode TaggedChild(treeNode x, TagType tag)
 {
 
-   NULLT_IF(x==NULLT || fast_isleaf(Par,x));
+   NULLT_IF(x==NULLT || bp_isleaf(Par,x));
    treeNode child;
-   child = fast_first_child(Par, x);
+   child = bp_first_child(Par, x);
 
 if (Tag(child) == tag)
      return child;

diff --git a/XMLTreeBuilder.cpp b/XMLTreeBuilder.cpp
index 0fc8d32..7ff1eff 100644 (file)
--- a/XMLTreeBuilder.cpp
+++ b/XMLTreeBuilder.cpp
@@ -108,7 +108,7 @@ int XMLTreeBuilder::NewOpenTag(string tagname)
        parArraySize *= 2;\r
     }\r
 \r
-    setbit(par_aux,npar,OP);  // marks a new opening parenthesis\r
+    bp_setbit(par_aux,npar,OP);  // marks a new opening parenthesis\r
 \r
     TagIdMapIT tag_id = tIdMap->find(tagname);\r
 \r
@@ -146,7 +146,7 @@ int XMLTreeBuilder::NewClosingTag(string tagname)
        parArraySize *= 2;\r
     }\r
 \r
-    setbit(par_aux,npar,CP);  // marks a new closing parenthesis\r
+    bp_setbit(par_aux,npar,CP);  // marks a new closing parenthesis\r
 \r
     //tagname.insert(0,"/");\r
 \r