X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=xml-tree.cpp;h=82f00b0af86742bfd66720272e51c0fd9e650c26;hb=HEAD;hp=575ba8f76697adca17a6ab6f275a0c1d8d9b398e;hpb=2b67e586d2ea45d87648ac3977306139110c4e78;p=SXSI%2FXMLTree.git diff --git a/xml-tree.cpp b/xml-tree.cpp index 575ba8f..82f00b0 100644 --- a/xml-tree.cpp +++ b/xml-tree.cpp @@ -95,15 +95,24 @@ xml_tree::xml_tree(std::vector *tags_, delete parbitmap; this->tag_ids = tag_ids; + tag_names = new std::vector(); tag_names->resize(tag_ids->size()); - for(auto val : *(this->tag_ids)) - (*this->tag_names)[val.second] = val.first; + this->attribute_ids = new std::unordered_set(); + std::unordered_map::iterator val; + for(val = this->tag_ids->begin(); val != this->tag_ids->end(); ++val){ + (*tag_names)[val->second] = val->first; + if (val->first.size() >= 3 && + val->first[0] == '<' && + val->first[1] == '@' && + val->first[2] == '>'){ + this->attribute_ids->insert(val->second); + }; + } uint32_t max_tag = tag_names->size() - 1; - bit_vector *tmp_bitmap = new bit_vector(npar, 1, 0); - uint32_t * buff = tmp_bitmap->get_vector_ptr(); + uint32_t * buff; for(int32_t i = 0; i <= max_tag; i++){ uint32_t ones = 0; for (size_t k = 0; k < npar; k++){ @@ -111,12 +120,13 @@ xml_tree::xml_tree(std::vector *tags_, tmp_bitmap->set(k, t); ones += t; }; - + buff = tmp_bitmap->get_vector_ptr(); this->tags.push_back(new static_bitsequence_sdarray(buff, npar, ones)); } delete tmp_bitmap; delete [] buff; + //static_bitsequence_builder *bmb = new static_bitsequence_builder_sdarray(); //alphabet_mapper *am = new alphabet_mapper_none(); @@ -162,6 +172,7 @@ xml_tree::~xml_tree() delete [] tag_seq; delete tag_names; delete tag_ids; + delete attribute_ids; if (text_collection) delete text_collection; if (text_positions) delete text_positions; } @@ -279,6 +290,7 @@ xml_tree* xml_tree::load(int fd, char* name, bool load_tc, int sf) tree->par = loadTree(fp); //TODO use new api tree->tag_names = new std::vector(); tree->tag_ids = new std::unordered_map(); + tree->attribute_ids = new std::unordered_set(); std::string s; int ntags; @@ -293,6 +305,9 @@ xml_tree* xml_tree::load(int fd, char* name, bool load_tc, int sf) tree->tag_names->push_back(s); tree->tag_ids->insert(std::make_pair(s, static_cast(i))); + if (s.size() >= 3 && s[0] == '<' && s[1] == '@' && s[2] == '>'){ + tree->attribute_ids->insert(static_cast(i)); + }; }; @@ -302,7 +317,7 @@ xml_tree* xml_tree::load(int fd, char* name, bool load_tc, int sf) //tree->tags = static_sequence_bs::load(fp); ufread(&tree->bits_per_tag, sizeof(uint), 1, fp); - fprintf(stderr, "\nBits per tag: %u\n", tree->bits_per_tag); + //fprintf(stderr, "\nBits per tag: %u\n", tree->bits_per_tag); ufread(&tree->tag_seq_len, sizeof(uint), 1, fp); size_t size = uint_len(tree->bits_per_tag, tree->tag_seq_len); tree->tag_seq = new uint[size]; @@ -366,12 +381,17 @@ xml_tree::node_t xml_tree::child(xml_tree::node_t x, uint32_t i) const std::pair xml_tree::text_id_range(xml_tree::node_t x) const { int32_t i, j; - i = text_positions->rank1(x) - 1; - j = text_positions->rank1(x + 2 * bp_subtree_size(par, x) - 2); + xml_tree::node_t y = bp_find_close(par, x); + if (x == root()) + i = 0; + else + i = text_positions->rank1(x-1); + j = text_positions->rank1(y); + if (i == j) return std::make_pair(xml_tree::NIL, xml_tree::NIL); else - return std::make_pair(i + 1, j); + return std::make_pair(i, j); } int32_t xml_tree::text_id(xml_tree::node_t x) const @@ -379,9 +399,9 @@ int32_t xml_tree::text_id(xml_tree::node_t x) const return (int32_t) text_positions->rank1(x) - 1; } -unsigned char* xml_tree::get_text(int32_t id) const +const char* xml_tree::get_text(int32_t id) const { - unsigned char * s = text_collection->GetText(id); + const char * s = reinterpret_cast(text_collection->GetText(id)); return s + (s[0] == 1); } @@ -430,17 +450,16 @@ void xml_tree::uputc(const char c, int fd) const char * xml_tree::get_tag_name_by_ref(xml_tree::tag_t tagid) const { - - unsigned char *s; if (tagid < 0 || tagid >= tag_names->size()) return ""; - return (const char *) (*tag_names)[tagid].c_str(); + return (*tag_names)[tagid].c_str(); } xml_tree::tag_t xml_tree::register_tag(char *s) { - auto found = tag_ids->find(std::string(s)); + std::unordered_map::iterator found; + found = tag_ids->find(std::string(s)); if (found == tag_ids->end()) return xml_tree::NIL_TAG_ID; else @@ -493,12 +512,19 @@ void xml_tree::print(xml_tree::node_t x, int fd, bool no_text) unsigned char * orig_text; unsigned char * current_text; - auto r = text_id_range(x); + std::pair r = text_id_range(x); if (r.first == xml_tree::NIL) current_text = 0; - else + else { current_text = text_collection->GetText(r.first, r.second); - current_text += (current_text[0] == 1); + current_text += (current_text[0] == 1); + }; + + //fprintf(stderr, "Printing node %i, tag: %s\n", x, get_tag_name_by_ref(tag(x))); + // fprintf(stderr, "Beggining of text is (%i):%s\n", r.first, current_text); + //fflush(stderr); + + orig_text = current_text; @@ -542,6 +568,7 @@ void xml_tree::print(xml_tree::node_t x, int fd, bool no_text) uputs((const char*) &(get_tag_name_by_ref(tag(n))[3]), fd); n++; uputs("=\"", fd); + current_text += (current_text[0] == 1); read = uprintf((const char*) current_text, fd); current_text += read + 1; uputc('"', fd); @@ -555,11 +582,11 @@ void xml_tree::print(xml_tree::node_t x, int fd, bool no_text) label = tag(n); } else uputc('>', fd); - } else { + } else { uputs("/>", fd); n++; label = tag(n); - }; + }; }; } else do { uputs("clear(); -// print_stack = new std::vector(); -// print_stack->reserve(256); -// }; - -// xml_tree::node_t fin = bp_find_close(par, x); -// xml_tree::node_t n = x; -// xml_tree::tag_t label = tag(n); -// unsigned char * current_text; - - -// while (n <= fin) { - -// if (bp_inspect(par, n)) { -// if (label == xml_tree::PCDATA_OPEN_TAG_ID){ -// if (no_text) { -// uputs("<$/>", fd); -// } else { -// current_text = get_text(text_id(n)); -// uprintf( (const char*) (current_text + (current_text[0] == 1)), fd); - -// if (current_text && text_index_type != TextCollectionBuilder::index_type_default) -// text_collection->DeleteText(current_text); - -// n += 2; // skip closin $ -// label = tag(n); -// }; -// } else { -// uputc('<', fd); -// uput_str((*tag_names)[label], fd); -// n++; -// if (bp_inspect(par, n)) { -// print_stack->push_back((*tag_names)[label]); -// label = tag(n); -// if (label == xml_tree::ATTRIBUTE_OPEN_TAG_ID) { -// n++; -// if (no_text) uputs("><@@>", fd); - -// while (bp_inspect(par, n)) -// if (no_text) { -// uputc('<', fd); -// uputs((const char*) &(get_tag_name_by_ref(tag(n))[3]), fd); -// uputc('>', fd); -// uputs("<$@/>', fd); -// n += 4; -// } else { -// uputc(' ', fd); -// uputs((const char*) &(get_tag_name_by_ref(tag(n))[3]), fd); -// n+= 2; -// uputs("=\"", fd); -// current_text = get_text(text_id(n)); -// uprintf((const char*) (current_text + (current_text[0] == 1)), fd); -// if (current_text && text_index_type != TextCollectionBuilder::index_type_default) -// text_collection->DeleteText(current_text); -// uputc('"', fd); -// n += 2; -// }; - -// if (no_text) -// uputs("", fd); -// else uputc('>', fd); -// n++; -// label = tag(n); -// } else -// uputc('>', fd); -// } else { -// uputs("/>", fd); -// n++; -// label = tag(n); -// }; -// }; -// } else do { -// uputs("back(), fd); -// uputc('>', fd); -// print_stack->pop_back(); -// n++; -// } while (!bp_inspect(par, n) && !print_stack->empty()); -// label = tag(n); -// }; -// uputc('\n', fd); - -// } + +static inline uchar * next_char(uchar *s, size_t &numtexts) +{ + uchar c; + s++; + c = *s; + while (c <= 1){ + if (c == 0) { + numtexts--; + if (numtexts == 0) return 0; + }; + s++; + c = *s; + }; + return s; +} + +static inline bool naive_char_contains(uchar const *s, uchar c, size_t numtexts) +{ + uchar sc; + while(numtexts != 0){ + sc = *s; + if (c == sc) return true; + if (sc == 0) numtexts--; + s++; + }; + return false; +} + +bool xml_tree::naive_contains(xml_tree::node_t n, uchar const *w) const +{ + if (w[0] == 0) + return true; + // fprintf(stderr, "Calling naive_contains on node: %i, with tag: %s\n", + // n, + // get_tag_name_by_ref(tag(n))); + // fflush(stderr); + std::pair range = text_id_range(n); + + //pattern is at least one char + if (range.first == xml_tree::NIL) + return false; + + uchar * text = this->text_collection->GetText(range.first, range.second); + size_t num_texts = + subtree_tags(n, ATTRIBUTE_DATA_OPEN_TAG_ID) + + subtree_tags(n, PCDATA_OPEN_TAG_ID); + + if (w[1] == 0) + return naive_char_contains(text, w[0], num_texts); + + //KMP is overkill + uchar * s = text; + uchar * ss; + uchar const *ww; + size_t nnum_texts; + while (true) { + // fprintf(stderr, "Current char in s: %c, num_texts is: %lu\n", *s, num_texts); + // fflush(stderr); + ss = s; + ww = w; + nnum_texts = num_texts; + while (true){ + // fprintf(stderr, " Current char in w: %c, num_texts is: %lu\n", *ww, num_texts); + // fprintf(stderr, " Current char in s: %c\n", *ss); + // fflush(stderr); + + if (*ww == 0) return true; + if (*ww != *ss) break; + ww++; + ss = next_char(ss, nnum_texts); + if (ss == 0) return (*ww == 0); + }; + // fprintf(stderr, "Not found, returning\n"); + // fflush(stderr); + // fprintf(stderr, "Current string s is: %s\n", s); + s = next_char(s, num_texts); + if (s == 0) return false; +// fprintf(stderr, "After next_char, string s is: %s\n", s); +// fflush(stderr); + }; + +}