X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=src%2Fsupport%2Fweighted_btree.h;h=0b833740d0a31aaa3a3bc6c46b249c88aa8004d5;hb=59e4d16ab9611732dbc208f23d3de4b9da321dce;hp=4418a8313631afdd884752a22323dff45e1d095c;hpb=ca63ce553c95dbc79412e036c90b2cb1b709a6b1;p=lyx.git diff --git a/src/support/weighted_btree.h b/src/support/weighted_btree.h index 4418a83136..0b833740d0 100644 --- a/src/support/weighted_btree.h +++ b/src/support/weighted_btree.h @@ -29,6 +29,7 @@ // *** Required Headers from the STL #include +#include #include #include #include @@ -412,6 +413,8 @@ public: typedef iterator self; private: + friend class weighted_btree; + // *** Members /// The currently referenced leaf node of the tree @@ -436,7 +439,7 @@ public: // *** Methods /// Constructor of a mutable iterator - inline iterator(typename weighted_btree::leaf_node *l, unsigned short s) + inline iterator(typename weighted_btree::leaf_node *l, unsigned short s) : currnode(l), currslot(s) { } @@ -601,6 +604,8 @@ public: typedef const_iterator self; private: + friend class weighted_btree; + // *** Members /// The currently referenced leaf node of the tree @@ -657,6 +662,12 @@ public: return currnode->slotkey[currslot]; } + /// Weight of the current slot + inline weight_type weight() const + { + return currnode->weights[currslot]; + } + /// Read-only reference to the current data object inline const data_type& data() const { @@ -1313,13 +1324,41 @@ public: leaf_node *leaf = static_cast(n); - int slot = find_lower(leaf, key); + unsigned short slot = find_lower(leaf, key); return (slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot])) ? iterator(leaf, slot) : end(); } + /// Changes the weight of the first node with the given key to the + /// new weight. + void change_weight(iterator & it, weight_type w) + { + node *n = root; + if (!n) return; + if (it.weight() == w) + return; + + while(!n->isleafnode()) + { + const inner_node *inner = static_cast(n); + int slot = find_lower(inner, it.key()); + + // two step because weight_type might be unsigned + n->weight -= it.weight(); + n->weight += w; + + n = inner->childid[slot]; + } + + BTREE_ASSERT(n == it.curnode); + n->weight -= it.weight(); + n->weight += w; + it.currnode->weights[it.currslot] = w; + } + /// Tries to locate a summed weight in the B+ tree and returns an iterator to the - /// key/data slot if found. If unsuccessful it returns end(). + /// key/data slot if found. If unsuccessful it returns end(). It is + /// ignoring zero-weight nodes during this. iterator find_summed_weight(weight_type weight) { node *n = root; @@ -1330,15 +1369,15 @@ public: const inner_node *inner = static_cast(n); int slot = find_summed_weight_lower(inner, weight); - for (unsigned short s = 0; s < slot; ++s) - weight -= inner->childid[s]->weight; + for (unsigned short s = 0; s < slot; ++s) + weight -= inner->childid[s]->weight; - n = inner->childid[slot]; + n = inner->childid[slot]; } leaf_node *leaf = static_cast(n); - int slot = find_summed_weight_lower(leaf, weight); + unsigned short slot = find_summed_weight_lower(leaf, weight); for (unsigned short s = 0; s < slot; ++s) weight -= leaf->weights[s]; @@ -1346,6 +1385,7 @@ public: ? iterator(leaf, slot) : end(); } + /// weight_type summed_weight(const key_type &key) { @@ -1397,7 +1437,8 @@ public: } /// Tries to locate a summed weight in the B+ tree and returns an iterator to the - /// key/data slot if found. If unsuccessful it returns end(). + /// key/data slot if found. If unsuccessful it returns end(). It is + /// ignoring zero-weight nodes during this. const_iterator find_summed_weight(weight_type weight) const { node *n = root; @@ -1728,7 +1769,7 @@ public: clear(); key_less = other.key_comp(); - if (other.size() != 0) + if (!other.empty()) { stats.leaves = stats.innernodes = 0; root = copy_recursive(other.root); @@ -1747,7 +1788,7 @@ public: stats( other.stats ), key_less( other.key_comp() ) { - if (size() > 0) + if (!empty()) { stats.leaves = stats.innernodes = 0; root = copy_recursive(other.root); @@ -1982,7 +2023,7 @@ private: slot -= inner->slotuse+1; inner = static_cast(*splitnode); - BTREE_PRINT("btree::insert_descend switching to splitted node " << inner << " slot " << slot <(n); - int slot = find_lower(leaf, key); + unsigned short slot = find_lower(leaf, key); if (!allow_duplicates && slot < leaf->slotuse && key_equal(key, leaf->slotkey[slot])) { return std::pair(iterator(leaf, slot), false); @@ -2306,9 +2347,9 @@ private: // if the last key of the leaf was changed, the parent is notified // and updates the key of this leaf - if (slot == leaf->slotuse) + if (slot == leaf->slotuse && parent) { - if (parent && parentslot < parent->slotuse) + if (parentslot < parent->slotuse) { BTREE_ASSERT(parent->childid[parentslot] == curr); parent->slotkey[parentslot] = leaf->slotkey[leaf->slotuse - 1]; @@ -2547,7 +2588,7 @@ private: left->weights[left->slotuse + i] = right->weights[i]; } left->slotuse += right->slotuse; - left->weight += right.weight; + left->weight += right->weight; left->nextleaf = right->nextleaf; if (left->nextleaf) @@ -2600,7 +2641,7 @@ private: left->childid[left->slotuse + i] = right->childid[i]; } left->slotuse += right->slotuse; - left->weight += right.weight; + left->weight += right->weight; left->childid[left->slotuse] = right->childid[right->slotuse];