Changeset 3971

Timestamp:

10/05/08 00:59:53 (2 months ago)

Author:

kris

Message:

fixes #1244 :: SortedMap? now supports directional iterators, plus proximal key-matching

Kudos to tslam for providing patches ... thanks!

Files:

• trunk/tango/util/container/RedBlack.d (modified) (2 diffs)
• trunk/tango/util/container/SortedMap.d (modified) (10 diffs)

trunk/tango/util/container/RedBlack.d

@@ -7 +7 @@
-        version:        Apr 2008: Initial release
-
-
+, tsalm
-
-        Since:          0.99.7
@@ -266 +266 @@
-
-        /**
+         * Return node of subtree matching "value" 
+         * or, if none found, the one just after or before  
+         * if it doesn't exist, return null
+         * Uses Comparator cmp to find and to check equality.
+        **/
+        Ref findFirst (V value, Compare!(V) cmp, bool after = true)
+        {
+                auto t = this;
+                auto tLower = this;
+                auto tGreater  = this;
+            
+                for (;;)
+                    {
+                    auto diff = cmp (value, t.value);
+                    if (diff is 0)
+                        return t;
+                   else
+                      if (diff < 0)
+                         {
+                         tGreater = t;
+                         t = t.left;
+                         }
+                      else
+                         {
+                         tLower = t;
+                         t = t.right;
+                         }
+                   if (t is null)
+                       break;
+                   }
+    
+                if (after)
+                   { 
+                   if (cmp (value, tGreater.value) > 0)
+                       return null;
+                   else 
+                      if (cmp (value , tGreater.value) < 0)
+                          return tGreater;
+                   }
+                else
+                   {
+                   if (cmp (value, tLower.value) < 0)
+                       return null;
+                   else 
+                      if (cmp (value , tLower.value) > 0)
+                          return tLower;
+                   }
+        }
+        
+        /**
-         * Return number of nodes of current subtree containing value.
-         * Uses Comparator cmp to find and to check equality.

trunk/tango/util/container/SortedMap.d

@@ -30 +30 @@
-
-        ---
-
+
+
-        int opApply (int delegate (ref V value) dg)
-        int opApply (int delegate (ref K key, ref V value) dg)
@@ -50 +51 @@
-        bool replacePair (K key, V oldElement, V newElement)
-        bool opIndexAssign (V element, K key)
+        K    nearbyKey (K key, bool greater)
-        V    opIndex (K key)
-        V*   opIn_r (K key)
@@ -141 +143 @@
-        ***********************************************************************/
-
-
+bool forward = true
-        {
-                Iterator i = void;
-
+
+
-                i.mutation = mutation;
-                i.owner = this;
-                i.prior = null;
+                return i;
+        }
+      
+        /***********************************************************************
+
+                Return an iterator which return all elements matching 
+                or greater/lesser than the key in argument. The second
+                argument dictates traversal direction.
+
+                Return a generic iterator for contained elements
+                
+        ***********************************************************************/
+
+        final Iterator iterator (K key, bool forward)
+        {
+                Iterator i = iterator (forward);
+                i.node = tree ? tree.findFirst(key, cmp, forward) : null;
-                return i;
-        }
@@ -288 +308 @@
-                   }
-                return false;
+        }
+
+        /***********************************************************************
+
+                Return the value of the key exactly matching the provided
+                key or, if none, the key just after/before it based on the
+                setting of the second argument
+    
+                param: key a key
+                param: after indicates whether to look beyond or before
+                       the given key, where there is no exact match
+                Throws: NoSUchElementException if none found
+                Returns: a pointer to the value, or null if not present
+             
+        ***********************************************************************/
+        K nearbyKey (K key, bool after)
+        {
+                if (count)
+                   {
+                   auto p = tree.findFirst (key, cmp, after);
+                   if (p)
+                       return p.value;
+                   }
+            
+                throw new NoSuchElementException ("Element not found");
-        }
-
@@ -791 +836 @@
-        /***********************************************************************
-
-                foreach support for iterators
-                
-        ***********************************************************************/
-
-        private struct Freach
-        {
-                bool delegate(ref K, ref V) next;
-                
-                int opApply (int delegate(ref K key, ref V value) dg)
-                {
-                        K   key;
-                        V   value;
-                        int result;
-
-                        while (next (key, value))
-                               if ((result = dg(key, value)) != 0)
-                                    break;
-                        return result;
-                }               
-        }
-        
-        /***********************************************************************
-
-                Iterator with no filtering
-
@@ -820 +842 @@
-        private struct Iterator
-        {
-
-
-
-
+
+
+
+
+
-
-                /***************************************************************
@@ -865 +888 @@
-                           k = node.value;
-                           r = &node.attribute;
-node.successor
+bump (node)
-                           }
-                        return r;
@@ -884 +907 @@
-                              {
-                              prior = n;
-n.successor
+bump (n)
-                              if ((result = dg(n.value, n.attribute)) != 0)
-                                   break;
@@ -913 +936 @@
-                        return false;
-                }
+
+                /***************************************************************
+
+                ***************************************************************/
+
+                Iterator reverse ()
+                {
+                        if (bump is &fore)
+                            bump = &back;
+                        else
+                           bump = &fore;
+                        return *this;
+                }
+
+                /***************************************************************
+
+                ***************************************************************/
+
+                private static Ref fore (Ref p)
+                {
+                        return p.successor;
+                }
+
+                /***************************************************************
+
+                ***************************************************************/
+
+                private static Ref back (Ref p)
+                {
+                        return p.predecessor;
+                }
-        }
-}
@@ -941 +995 @@
-                         Stdout.formatln ("{}:{}", key, value);
-
+                // explicit iteration
+                foreach (key, value; map.iterator("foo", false))
+                         Stdout.formatln ("{}:{}", key, value);
+
-                // generic iteration with optional remove
-                auto s = map.iterator;
-                foreach (key, value; s)
-
+{} //
-
-                // incremental iteration, with optional remove