X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=src%2Fsupport%2Fweighted_btree.h;h=86063c3ae98355ac73fa33fc7149ef6a84eb95fb;hb=7b0f9d95248820bc70b820dd6b558de4a6713bae;hp=d5d6c300c123acccaf87c446f8c60939e6274a47;hpb=1669c17c0fdc20ca12d0d2d30bad364b17a31e3d;p=lyx.git diff --git a/src/support/weighted_btree.h b/src/support/weighted_btree.h index d5d6c300c1..86063c3ae9 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 @@ -150,7 +151,7 @@ public: /// typedef _Weight weight_type; - + /// Second template parameter: The data type associated with each /// key. Stored in the B+ tree's leaves typedef _Data data_type; @@ -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; @@ -1478,13 +1519,13 @@ public: return iterator(leaf, slot); } - /// Searches the B+ tree and returns an iterator to the first summed weight + /// Searches the B+ tree and returns an iterator to the first summed weight /// less or equal to the parameter. If unsuccessful it returns end(). iterator lower_summed_weight_bound(weight_type weight) { node *n = root; if (!n) return end(); - + while(!n->isleafnode()) { const inner_node *inner = static_cast(n); int slot = find_summed_weight_lower(inner, weight); @@ -1526,7 +1567,7 @@ public: return const_iterator(leaf, slot); } - /// Searches the B+ tree and returns an iterator to the first summed weight + /// Searches the B+ tree and returns an iterator to the first summed weight /// less or equal to the parameter. If unsuccessful it returns end(). const_iterator lower_summed_weight_bound(weight_type weight) const { @@ -1596,7 +1637,7 @@ public: return const_iterator(leaf, slot); } - /// Searches the B+ tree and returns an iterator to the first summed weight + /// Searches the B+ tree and returns an iterator to the first summed weight /// greater than the parameter. If unsuccessful it returns end(). iterator upper_summed_weight_bound(weight_type weight) { @@ -1624,7 +1665,7 @@ public: return iterator(leaf, slot); } - /// Searches the B+ tree and returns an iterator to the first summed weight + /// Searches the B+ tree and returns an iterator to the first summed weight /// greater than the parameter. If unsuccessful it returns end(). const_iterator upper_summed_weight_bound(weight_type weight) const { @@ -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];