banshee r4216 - in trunk/banshee: . src/Libraries/Hyena/Hyena.Collections src/Libraries/Hyena/Hyena.Collections/Tests

[abock svn gnome org]

Author: abock
Date: Wed Jul 16 15:18:25 2008
New Revision: 4216
URL: http://svn.gnome.org/viewvc/banshee?rev=4216&view=rev

Log:
2008-07-16  Aaron Bockover  <abock gnome org>

    * src/Libraries/Hyena/Hyena.Collections/Tests/RangeCollectionTests.cs:
    Added some more tests, including negative indexes, and a real world
    IP address range test from Alan

    * src/Libraries/Hyena/Hyena.Collections/RangeCollection.cs: Fixed a serious
    bug with range and value-in-range comparisons exposed by MS.NET. The
    IComparable interface was removed from Range and the comparisons were
    split into the respective binary search implementations; no longer is
    Array.BinarySearch used either when searching for a value in a range
    so the comparison can be done inline without extra method calls; should
    be ever so slightly more efficient and works (all tests pass) on Mono
    and MS.NET



Modified:
   trunk/banshee/ChangeLog
   trunk/banshee/src/Libraries/Hyena/Hyena.Collections/RangeCollection.cs
   trunk/banshee/src/Libraries/Hyena/Hyena.Collections/Tests/RangeCollectionTests.cs

Modified: trunk/banshee/src/Libraries/Hyena/Hyena.Collections/RangeCollection.cs
==============================================================================
--- trunk/banshee/src/Libraries/Hyena/Hyena.Collections/RangeCollection.cs	(original)
+++ trunk/banshee/src/Libraries/Hyena/Hyena.Collections/RangeCollection.cs	Wed Jul 16 15:18:25 2008
@@ -53,50 +53,32 @@
         ICollection
 #endif
     {
-        public struct Range :
-#if NET_2_0
-            IComparable<Range>
-#else
-            IComparable
-#endif
+        public struct Range
         {
-            public int Start;
-            public int End;
+            private int start;
+            private int end;
             
             public Range (int start, int end)
             {
                 Start = start;
                 End = end;
             }
-            
-#if !NET_2_0
-            public int CompareTo (object o)
-            {
-                return CompareTo ((Range)o);
-            }
-#endif
 
-            public int CompareTo (Range x)
-            {
-                // When End == -1, a comparison is created to
-                // match an index inside of a range; otherwise
-                // two actual ranges are being compared
-
-                return End == -1 
-                    ? (Start >= x.Start 
-                        ? (Start <= x.End 
-                            ? 0   // In Range
-                            : 1)  // Above Range
-                        : -1)     // Below Range
-                    : (Start + (End - Start)).CompareTo (
-                        x.Start + (x.End - x.Start));
-            }
-            
             public override string ToString ()
             {
                 return String.Format ("{0}-{1} ({2})", Start, End, Count);
             }
 
+            public int Start {
+                get { return start; }
+                set { start = value; }
+            }
+            
+            public int End {
+                get { return end; }
+                set { end = value; }
+            }
+            
             public int Count {
                 get { return End - Start + 1; }
             }
@@ -226,6 +208,11 @@
 
             return false;
         }
+        
+        private int CompareRanges (Range a, Range b)
+        {
+            return (a.Start + (a.End - a.Start)).CompareTo (b.Start + (b.End - b.Start));
+        }
 
         private int FindInsertionPosition (Range range)
         {
@@ -234,12 +221,12 @@
             
             while (min <= max) {
                 int mid = min + ((max - min) / 2);
-                int cmp = ranges[mid].CompareTo (range);
+                int cmp = CompareRanges (ranges[mid], range);
                  
                 if (cmp == 0) {
                     return mid;
                 } else if (cmp > 0) {
-                    if (mid > 0 && ranges[mid - 1].CompareTo (range) < 0) {
+                    if (mid > 0 && CompareRanges (ranges[mid - 1], range) < 0) {
                         return mid;
                     }
                     
@@ -253,8 +240,23 @@
         }
         
         public int FindRangeIndexForValue (int value)
-        {
-            return Array.BinarySearch (ranges, 0, range_count, new Range (value, -1));
+        {  
+            int min = 0;
+			int max = range_count - 1;
+			
+			while (min <= max) {
+				int mid = min + ((max - min) / 2);
+				Range range = ranges[mid];
+				if (value >= range.Start && value <= range.End) {
+				    return mid;    // In Range
+				} else if (value < range.Start) {
+					max = mid - 1; // Below Range
+				} else {
+					min = mid + 1; // Above Range
+		        }
+			}
+
+			return ~min;
         }
         
 #endregion 

Modified: trunk/banshee/src/Libraries/Hyena/Hyena.Collections/Tests/RangeCollectionTests.cs
==============================================================================
--- trunk/banshee/src/Libraries/Hyena/Hyena.Collections/Tests/RangeCollectionTests.cs	(original)
+++ trunk/banshee/src/Libraries/Hyena/Hyena.Collections/Tests/RangeCollectionTests.cs	Wed Jul 16 15:18:25 2008
@@ -76,6 +76,21 @@
         }
         
         [Test]
+        public void LargeSequentialContains ()
+        {
+            RangeCollection range = new RangeCollection ();
+            int i, n = 1000000;
+            
+            for (i = 0; i < n; i++) {
+                range.Add (i);
+            }
+            
+            for (i = 0; i < n; i++) {
+                Assert.AreEqual (true, range.Contains (i));
+            }
+        }
+        
+        [Test]
         public void LargeSequential ()
         { 
             RangeCollection range = new RangeCollection ();
@@ -427,6 +442,56 @@
             
             Assert.AreEqual (4, range.Count);
         }
+        
+        [Test]
+        public void NegativeIndices ()
+        {
+            RangeCollection c = new RangeCollection ();
+            c.Add (-10);
+            c.Add (-5);
+            c.Add (5);
+            c.Add (-8);
+            c.Add (10);
+            c.Add (-9);
+            c.Add (-11);
+
+            Assert.IsTrue (c.Contains(-10), "#1");
+            Assert.IsTrue (c.Contains(-5), "#2");
+            Assert.IsTrue (c.Contains(5), "#3");
+            Assert.IsTrue (c.Contains(-8), "#4");
+            Assert.AreEqual (4, c.RangeCount, "#5");
+            Assert.AreEqual (new RangeCollection.Range (-11, -8), c.Ranges[0], "#6");
+            Assert.AreEqual (new RangeCollection.Range (-5, -5), c.Ranges[1], "#7");
+            Assert.AreEqual (new RangeCollection.Range (5, 5), c.Ranges[2], "#8");
+            Assert.AreEqual (new RangeCollection.Range (10, 10), c.Ranges[3], "#9");
+            
+            Assert.AreEqual (0, c.FindRangeIndexForValue (-9), "#10");
+            Assert.IsTrue (c.FindRangeIndexForValue (-7) < 0, "#11");
+        }
+
+        [Test]
+        public void IPAddressRanges ()
+        {
+            RangeCollection ranges = new RangeCollection ();
+
+            int start = GetAddress ("127.0.0.1");
+            int end = GetAddress ("127.0.0.50");
+
+            for (int i = start; i <= end; i++) {
+                ranges.Add (i);
+            }
+            
+            Assert.IsTrue (ranges.Contains (GetAddress ("127.0.0.15")));
+            Assert.IsFalse (ranges.Contains (GetAddress ("127.0.0.0")));
+            Assert.IsFalse (ranges.Contains (GetAddress ("127.0.0.51")));
+        }
+        
+        private static int GetAddress (string addressStr)
+        {
+            System.Net.IPAddress address = System.Net.IPAddress.Parse (addressStr);
+            return (int)(System.Net.IPAddress.NetworkToHostOrder (
+                BitConverter.ToInt32 (address.GetAddressBytes (), 0)) >> 32);
+        }
     }
 }