[PEAK] trellis.SortedSet bug and patch

[Grant Baillie]

I was running a doctest involving collections.SortedSet and ran into a  
bug where the sorting got out of whack. It turns out there's a funny  
comparison going on in collections.py, line 221: we're comparing a  
single value to a 2-element tuple, which is probably not what's  
intended.

Then I found the obvious attempt to fix it could also be broken with  
similar edge cases. So, below find the patch, and the 4 tests I wrote.

Actually, in retrospect, I'm wondering if we should just bypass the  
"shortcut" case completely. Is it that much of a performance win?

--Grant

------ patch ------
Index: peak/events/collections.py
===================================================================
--- peak/events/collections.py	(revision 2595)
+++ peak/events/collections.py	(working copy)
@@ -218,8 +218,12 @@

          for k, op, ob in changes:
              ind = (k, ob)
-            if lo<hi and items[hi-1][0]>=ind:
-                pos = hi-1    # shortcut
+            if lo<hi and ind>=items[hi-1]:
+                # shortcut
+                if ind==items[hi-1]:
+                    pos = hi-1
+                else:
+                    pos = hi
              else:
                  pos = bisect.bisect_left(items, ind, lo, hi)


------ test case ------
import unittest
from peak.events import collections, trellis

class SortedSetTestCase(unittest.TestCase):

     def testUnicodeSort(self):
         data = trellis.Set([1, 2])
         sorted_set = collections.SortedSet(data=data,  
sort_key=unicode, reverse=True)

         self.failUnlessEqual(list(sorted_set), [2, 1])
         data.add(0)
         self.failUnlessEqual(list(sorted_set), [2, 1, 0])

     def testStrSort(self):
         data = trellis.Set([1, 3, 4])
         sorted_set = collections.SortedSet(data=data, sort_key=str)

         self.failUnlessEqual(list(sorted_set), [1, 3, 4])
         data.add(2)
         self.failUnlessEqual(list(sorted_set), [1, 2, 3, 4])

     def testRemoveLast(self):
         data = trellis.Set([1, 2])
         sorted_set = collections.SortedSet(data=data)
         data.remove(2)
         self.failUnlessEqual(list(sorted_set), [1])

     def testAddToEnd(self):
         data = trellis.Set([1])
         sorted_set = collections.SortedSet(data=data)
         data.add(2)
         self.failUnlessEqual(list(sorted_set), [1, 2])

if __name__ == "__main__":
     unittest.main()