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