// *** Required Headers from the STL
#include <algorithm>
+#include <cstddef>
#include <functional>
#include <istream>
#include <ostream>
typedef iterator self;
private:
+ friend class weighted_btree;
+
// *** Members
/// The currently referenced leaf node of the tree
// *** 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)
{ }
typedef const_iterator self;
private:
+ friend class weighted_btree;
+
// *** Members
/// The currently referenced leaf node of the tree
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
{
leaf_node *leaf = static_cast<leaf_node*>(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<const inner_node*>(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;
const inner_node *inner = static_cast<const inner_node*>(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<leaf_node*>(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];
? iterator(leaf, slot) : end();
}
+
///
weight_type summed_weight(const key_type &key)
{
}
/// 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;
slot -= inner->slotuse+1;
inner = static_cast<inner_node*>(*splitnode);
- BTREE_PRINT("btree::insert_descend switching to splitted node " << inner << " slot " << slot <<std::endl);
+ BTREE_PRINT("btree::insert_descend switching to split node " << inner << " slot " << slot <<std::endl);
}
}
{
leaf_node *leaf = static_cast<leaf_node*>(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, bool>(iterator(leaf, slot), false);
// 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];