Fix LaTeX length export of big numbers (bug 9416)

[lyx.git] / src / support / weighted_btree.h

diff --git a/src/support/weighted_btree.h b/src/support/weighted_btree.h
index 4418a8313631afdd884752a22323dff45e1d095c..0b833740d0a31aaa3a3bc6c46b249c88aa8004d5 100644 (file)
--- a/src/support/weighted_btree.h
+++ b/src/support/weighted_btree.h
@@ -29,6 +29,7 @@
 // *** Required Headers from the STL
 
 #include <algorithm>
+#include <cstddef>
 #include <functional>
 #include <istream>
 #include <ostream>
@@ -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<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;
@@ -1330,15 +1369,15 @@ public:
             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];
 
@@ -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<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);
                     }
                 }
 
@@ -2009,7 +2050,7 @@ private:
         {
             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);
@@ -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];