locked
SortedDictionaly/SortedList lower bound RRS feed

  • Question

  • Hi, 

    I'm looking for a way to get iterator pointing to nearest key in sorted dictionary.
    Something like lower_bound / upper_bound  does in STL.
    Since SortedDictionaly is binary tree, there has to be a way to efficiently find closest key without iterating over whoole collection.

    Thanks
    Irakli
    Tuesday, July 22, 2008 4:27 PM

Answers

  • You could do something very hacky, and likely to break with changes to the .Net framework...

    If you supply your own Comparer to the dictionary, you can track what comparisons are being made. You could therefore find the nearest values to a target value being searched for via TryGetValue().

    It doesn't seem a very safe way of doing it, even though it works for the current implementation of SortedDictionary.

    Here's some sample code that does it:

    using System; 

    using System.Collections.Generic; 
    using System.Diagnostics; 
     
    namespace Demo 
        public class Program 
        { 
            public static void Main() 
            { 
                MyComparer myComparer = new MyComparer(); 
     
                SortedDictionary<string, string> test = new SortedDictionary<string, string>(myComparer); 
     
                for (int i = 0; i < 100000; ++i) 
                { 
                    if (i != 50000) 
                    { 
                        string s = i.ToString("d5"); 
                        test.Add(s, s); 
                    } 
                } 
     
                string result; 
     
                myComparer.WantDiagnostics = true
                myComparer.Reset(); 
     
                if (test.TryGetValue("50000", out result)) 
                { 
                    Console.WriteLine("Found value"); 
                } 
                else 
                { 
                    Console.WriteLine 
                    ( 
                        "Value not found, nearest preceeding = "  
                        + myComparer.NearestPreceeding  
                        + ", nearest following = "  
                        + myComparer.NearestFollowing 
                    ); 
                } 
            } 
     
            private class MyComparer: IComparer<string> 
            { 
                public int Compare(string x, string y) 
                { 
                    if (_wantDiagnostics) 
                    { 
                        Console.WriteLine("Comparing " + x + " to " + y); 
     
                        if  
                        ( 
                            (string.Compare(y, x) < 0)  
                            && ((_nearestPreceeding == null) || (string.Compare(y, _nearestPreceeding) > 0)) 
                        ) 
                        { 
                            _nearestPreceeding = y
                        } 
     
                        if  
                        ( 
                            (string.Compare(y, x) > 0)  
                            && ((_nearestFollowing == null) || (string.Compare(y, _nearestFollowing) < 0)) 
                        ) 
                        { 
                            _nearestFollowing = y
                        } 
                    } 
     
                    return string.Compare(x, y); 
                } 
     
                public bool WantDiagnostics 
                { 
                    get 
                    { 
                        return _wantDiagnostics; 
                    } 
     
                    set 
                    { 
                        _wantDiagnostics = value
                    } 
                } 
     
     
                public string NearestPreceeding 
                { 
                    get 
                    { 
                        return _nearestPreceeding; 
                    } 
                } 
     
                public string NearestFollowing 
                { 
                    get 
                    { 
                        return _nearestFollowing; 
                    } 
                } 
     
                public void Reset() 
                { 
                    _nearestFollowing  = null
                    _nearestPreceeding = null
                } 
     
                private bool   _wantDiagnostics; 
                private string _nearestPreceeding; 
                private string _nearestFollowing; 
            } 
        } 
     

    • Edited by Matthew Watson Thursday, July 24, 2008 11:10 AM Fixed typo
    • Marked as answer by Hanzheng Zou Friday, July 25, 2008 6:30 AM
    Thursday, July 24, 2008 11:09 AM

All replies

  • Been searching for about an hour now...

    SortedDictionary is not really a binary tree, it's a generic wrapper with a HAS-A relation of a binary tree.

    But you're right, in the end, somewhere in memory there's a binary tree wich should enable programmers to get the minvalue, maxvalue, iterate back- and forwards from any given starting point, ...

    But these methods don't currently exist in the standard C# language (I did find a commercial - expensive - component to do this).

    So I'm thinking there's wont be a simple answer to your question. 

    One way I see is to re-write the sorted dictionary class as a wrapper around a class in an external library (read: use the C/C++ orderedMap class). 
    Another way would be to get the in memory "footprint" of a SortedDictionary object then reading specific (min-max) memory addresses yourself.  Although this might be a disaster waiting to happen...
    The improbable we do, the impossible just takes a little longer. - Steven Parker
    Wednesday, July 23, 2008 8:57 AM
  • You could do something very hacky, and likely to break with changes to the .Net framework...

    If you supply your own Comparer to the dictionary, you can track what comparisons are being made. You could therefore find the nearest values to a target value being searched for via TryGetValue().

    It doesn't seem a very safe way of doing it, even though it works for the current implementation of SortedDictionary.

    Here's some sample code that does it:

    using System; 

    using System.Collections.Generic; 
    using System.Diagnostics; 
     
    namespace Demo 
        public class Program 
        { 
            public static void Main() 
            { 
                MyComparer myComparer = new MyComparer(); 
     
                SortedDictionary<string, string> test = new SortedDictionary<string, string>(myComparer); 
     
                for (int i = 0; i < 100000; ++i) 
                { 
                    if (i != 50000) 
                    { 
                        string s = i.ToString("d5"); 
                        test.Add(s, s); 
                    } 
                } 
     
                string result; 
     
                myComparer.WantDiagnostics = true
                myComparer.Reset(); 
     
                if (test.TryGetValue("50000", out result)) 
                { 
                    Console.WriteLine("Found value"); 
                } 
                else 
                { 
                    Console.WriteLine 
                    ( 
                        "Value not found, nearest preceeding = "  
                        + myComparer.NearestPreceeding  
                        + ", nearest following = "  
                        + myComparer.NearestFollowing 
                    ); 
                } 
            } 
     
            private class MyComparer: IComparer<string> 
            { 
                public int Compare(string x, string y) 
                { 
                    if (_wantDiagnostics) 
                    { 
                        Console.WriteLine("Comparing " + x + " to " + y); 
     
                        if  
                        ( 
                            (string.Compare(y, x) < 0)  
                            && ((_nearestPreceeding == null) || (string.Compare(y, _nearestPreceeding) > 0)) 
                        ) 
                        { 
                            _nearestPreceeding = y
                        } 
     
                        if  
                        ( 
                            (string.Compare(y, x) > 0)  
                            && ((_nearestFollowing == null) || (string.Compare(y, _nearestFollowing) < 0)) 
                        ) 
                        { 
                            _nearestFollowing = y
                        } 
                    } 
     
                    return string.Compare(x, y); 
                } 
     
                public bool WantDiagnostics 
                { 
                    get 
                    { 
                        return _wantDiagnostics; 
                    } 
     
                    set 
                    { 
                        _wantDiagnostics = value
                    } 
                } 
     
     
                public string NearestPreceeding 
                { 
                    get 
                    { 
                        return _nearestPreceeding; 
                    } 
                } 
     
                public string NearestFollowing 
                { 
                    get 
                    { 
                        return _nearestFollowing; 
                    } 
                } 
     
                public void Reset() 
                { 
                    _nearestFollowing  = null
                    _nearestPreceeding = null
                } 
     
                private bool   _wantDiagnostics; 
                private string _nearestPreceeding; 
                private string _nearestFollowing; 
            } 
        } 
     

    • Edited by Matthew Watson Thursday, July 24, 2008 11:10 AM Fixed typo
    • Marked as answer by Hanzheng Zou Friday, July 25, 2008 6:30 AM
    Thursday, July 24, 2008 11:09 AM
  • Matthew,
    I like your way of thinking!

    I'm a bit afraid this may cause performance issues on bigger lists etc due to more CPU cycles?

    Eitherway, nice approach!
    The improbable we do, the impossible just takes a little longer. - Steven Parker
    Thursday, July 24, 2008 11:48 AM
  • Sorry to bump an old thread, but I'd like LowerBound/UpperBound added to .NET too.  Any Microsofties around? :)
    Sunday, February 1, 2009 1:39 AM
  • Here is a function that performs that job...basically a binary search search with a memory of the last tested boundary (array 'nearest'). Of course, the provided list must be sorted. The function is generalized to allow custom comparer and subrange of the list to be searched. However, you can simply input null for these parameters and sensible defaults will be used (as you can see).

    public static int[] FindNearest<T>(
        IList<T> sortedList, T value, 
        int? pMaxLeft, int? pMaxRight, Comparer<T> pComparer
        )
    {
        const int left = 0;
        const int right = 1;
        const int outsideList = -1;
        
        const int LT = -1;
        const int GT = 1;
        const int EQ = 0;
    
        Comparer<T> comparer = (pComparer ?? Comparer<T>.Default);
        int maxRight = pMaxRight.GetValueOrDefault(sortedList.Count - 1);
        int maxLeft = pMaxLeft.GetValueOrDefault(0);
        
        int[] partition = new int[] { maxLeft, maxRight };
        int[] nearest = (int[])partition.Clone();
        while (partition[right] >= partition[left])
        {
            int split = partition[left] + (partition[right] - partition[left]) / 2;
            int order = comparer.Compare(value, sortedList[split]);
            switch (order)
            {
                case LT:
                    nearest[right] = split;
                    partition[right] = split - 1;
                    break;
                case GT:
                    nearest[left] = split;
                    partition[left] = split + 1;
                    break;
                case EQ:
                    nearest = new int[] { split, split };
                    return nearest;
            }
        }
    
        if (partition[right] < maxLeft)
            nearest = new int[] { outsideList, maxLeft };
        else if (partition[left] > maxRight)
            nearest = new int[] { maxRight, outsideList };
    
        return nearest;
    }
    
    Wednesday, April 1, 2009 4:09 PM
  • Here is a function that performs that job...

    Yea, but insertion and deletion are O(n) for the array. Then there's no point in using a SortedDictionary anymore. 

    SortedDictionary really needs a LowerBound equivalent...

    I see that the implementation has an internal class called TreeSet that's a red-black tree. So it'd be a pretty trivial thing to add to the framework.
    Tuesday, March 8, 2011 12:22 AM
  • I agree to Sergey, add LowerBound to next versions of framework please.
    Monday, May 9, 2011 1:12 AM
  • I cannot believe C# / .NET does not have the equivalent of C++ Map::lower[upper]_bound(), which I have used many times in the past. Does anyone know if this will be added in future version of .NET framework? Thanks.
    Wednesday, May 16, 2012 6:34 PM
  • I cannot believe C# / .NET does not have the equivalent of C++ Map::lower[upper]_bound(), which I have used many times in the past. Does anyone know if this will be added in future version of .NET framework? Thanks.

    SortedDictionary/SortedSet are not a classes used to expose a Binary Search Tree, it's simply a Set that happens to use a BinarySearchTree as an implementation mechanism, and as such it doesn't expose manual tree traversal externally.

    Rather than waiting for it to be added to the language (which is generally unlikely) you're probably better off just making your own BinarySearchTree class that allows for more manual tree traversal.  You can even decompile the SortedSet/Dictionary classes to use that code as a starting point if you want.

    Wednesday, May 16, 2012 6:47 PM
  • I came across the C5 collection library.  C5.TreeDictionary<> does the job.
    Friday, May 18, 2012 3:34 PM
  • You also might want to consider Wintellect's power collections.
    Wednesday, May 23, 2012 9:15 AM