#!/usr/bin/env python
"""
listdict.py - List-Dictionary Hybrid
Author: Sean B. Palmer, inamidst.com
Additional notes: 
   Inspired by Jim Ley having pointed out that Python lacks 
   the "confused" array-dict type from Javascript
   http://svg.jibbering.com/svg/2005-04-12.html#T13-34-30
"""

def slicerange(s): 
   if (not isinstance(s, slice)) or (s.start == s.stop): 
      raise ValueError("Expected non-zero sized slice object")
   return xrange(s.start, s.stop, s.step or 1)

class NotImplemented(Exception): 
   """For <= Python 2.3 users."""
   pass

class Listdict(dict): 
   """A List-Dictionary Hybrid.
   The constructor acts like dict(...) unless a list is passed: 
   Listdict(list) -> new list-dictionary made with list array sequence
   """

   def __init__(self, *args, **kargs): 
      self.__length = 0

      if (len(args) == 1) and isinstance(args[0], list):  
         members = args[0]
         args = tuple()
      else: members = False

      super(Listdict, self).__init__(*args, **kargs)
      for key in self.iterkeys(): 
         if isinstance(key, int): 
            nlen = key + 1
            if nlen > self.__length: 
               self.__length = nlen
      if members: self.extend(members)

   def __len__(self): 
      """Get the length of the Listdict as a list."""
      return self.__length

   def dictlen(self): 
      """Get the length of the Listdict as a dict."""
      return super(Listdict, self).__len__()

   # def __cmp__(self, obj): 
   #    """Compare objects based on type: list if list, dict otherwise."""
   #    return super(Listdict, self).__cmp__(obj)

   def __eq__(self, obj): 
      """Compare objects based on type."""
      if isinstance(obj, list): 
         return list(self).__eq__(obj)
      elif self.__cmp__(obj) == 1: 
         return True
      return False

   def __ne__(self, obj): 
      """Compare objects based on type."""
      if isinstance(obj, list): 
         return list(self).__ne__(obj)
      elif self.__cmp__(obj) == 1: 
         return False
      return True

   def __add__(self, obj): 
      if not isinstance(obj, Listdict): 
         ValueError("Object is not a Listdict.")
      result = Listdict(self)
      result.extend(obj)
      return result

   def __iadd__(self, obj): 
      if not isinstance(obj, Listdict): 
         ValueError("Object is not a Listdict.")
      self.extend(obj)
      return self

   def __mul__(self, i): 
      result = Listdict(self)
      result.extend(list(self) * (i - 1))
      return result

   def __imul__(self, i): 
      extension = list(self) * (i - 1)
      self.extend(extension)
      return self

   def __rmul__(self, i): 
      self.__mul__(i)

   def __contains__(self, obj): 
      """Contains as a list."""
      # Use Listdict.has_key for dict-like behaviour
      for item in self: 
         if item == obj: return True
      return False

   def __iter__(self): 
      """Iterate over the Listdict as a list."""
      for i in xrange(self.__length): 
         yield self[i]

   # def __reversed__(self): 
   #    import copy
   #    new = copy.deepcopy(self)
   #    new.reverse()
   #    return new

   def __getitem__(self, item): 
      if isinstance(item, int): # @@ long, float
         return self.get(item)
      elif isinstance(item, slice): 
         if item.start != item.stop: 
            # was: Listdict(list(self)[item])
            result = Listdict()
            # @@ when more people upgrade, use listless syntax
            result.extend([self[i] for i in slicerange(item)])
            return result
         else: return Listdict()
      return super(Listdict, self).__getitem__(item)

   def __setitem__(self, key, item): 
      if not isinstance(key, slice): 
         if isinstance(key, int): 
            nlen = key + 1
            if nlen > self.__length: 
               self.__length = nlen
         super(Listdict, self).__setitem__(key, item)
      elif key.start != key.stop: 
         if key.stop != self.__length: 
            memo = self[key.stop:self.__length] # @@ as list!
         else: memo = []
         rest = xrange(key.stop, self.__length)
         self.truncate(key.start)
         self.extend(item)
         self.extend(memo)
      else: 
         length = len(item)
         for i in xrange(key.start, self.__length): 
            obj = self[i]
            del self[i]
            self[i + length] = obj
         for (i, obj) in enumerate(item): 
            self[i + key.start] = obj

   def __delitem__(self, key): 
      if isinstance(key, int): 
         if key == self.__length - 1: 
            self.__length -= 1
         elif key >= self.__length: 
            raise KeyError("Index out of bounds.")
      if self.has_key(key): 
         super(Listdict, self).__delitem__(key)

   def count(self, obj): 
      result = 0
      for i in range(0, self.__length): 
         if self[i] == obj: 
            result += 1
      return result

   def append(self, obj): 
      # __setitem__ increments the length itself
      self[self.__length] = obj

   def extend(self, objs): 
      for obj in objs: 
         self.append(obj)

   def delete(self, i): 
      """Delete index as a list."""
      # print 'delete(%s, %s) -> ' % (self, i),
      if i >= self.__length: 
         raise ValueError("Index out of bounds.")
      del self[i]
      for n in xrange(i + 1, self.__length): 
         obj = self[n]
         del self[n]
         self[n - 1] = obj
      # print self

   def index(self, obj, i=None, j=None): 
      if i is None: i = 0
      if j is None: j = self.__length

      for n in xrange(i, j): 
         if self[n] == obj: 
            return n
      raise ValueError("Listdict.index(obj): obj not in list")

   def insert(self, i, item): 
      self[i:i] = [item]

   def pop(self): 
      lastidx = self.__length - 1
      result = self[lastidx]
      del self[lastidx]
      return result

   def remove(self, i): 
      self.delete(self.index(i))

   def truncate(self, i): 
      """Truncate to min(i, len(listdict)) entries as a list."""
      i = min(i, self.__length)
      for n in xrange(i, self.__length): 
         del self[n]
      self.__length = i

   def sort(self): 
      try: sorted
      except NameError: 
         raise NotImplemented("Requires Python 2.4")

      for (i, item) in enumerate(sorted(self)): 
         # @@ does anything sort before None?
         self[i] = item

   def reverse(self): 
      try: sorted
      except NameError: 
         raise NotImplemented("Requires Python 2.4")

      for (i, item) in enumerate(reversed(self)): 
         # @@ only set final marker None
         self[i] = item

def test(): 
   import unittest

   class TestListdict(unittest.TestCase): 
      def verify(self, *args, **kargs): 
         return self.failUnless(*args, **kargs)

      def testempty(self): 
         arr = Listdict()
         self.verify(arr[5] == None)
         self.verify(len(arr) == 0)

      def testgrow(self): 
         arr = Listdict()
         arr[5] = 'chicken'
         self.verify(len(arr) == 6)
         self.verify(arr[3] == None)
         self.verify(arr[5] == 'chicken')
         self.verify(arr[8] == None)

      def testmembers(self): 
         arr = Listdict({5: 'chicken'})
         reference = [None, None, None, None, None, 'chicken']
         for (i, item) in enumerate(arr): 
            self.verify(reference[i] == item)
         for (expected, actual) in zip(reference, arr): 
            self.verify(expected == actual)

      def testassign(self): 
         arr = Listdict({5: 'chicken'})
         arr['mykey'] = 'myvalue'
         self.verify(len(arr) == 6)
         self.verify(arr['mykey'] == 'myvalue')
         self.assertRaises(KeyError, lambda: arr['nosuchkey'])

      def testappend(self): 
         arr = Listdict({5: 'chicken'})
         arr.append('chickette')
         self.verify(len(arr) == 7)
         self.verify(arr[6] == 'chickette')

      def testextend(self): 
         arr = Listdict({5: 'chicken'})
         arr.extend(['p-chicken', 'q-chicken', 'r-chicken'])
         self.verify(len(arr) == 9)
         self.verify(arr[7] == 'q-chicken')

      def testpop(self): 
         arr = Listdict({5: 'chicken'})
         self.verify(arr.pop() == 'chicken')
         self.verify(arr[5] == None)
         self.verify(arr.pop() == None)
         self.verify(arr.pop() == None)
         self.verify(len(arr) == 3)

      def testdel(self): 
         arr = Listdict({5: 'chicken', 7: 'chickette'})
         def deletekey(arr=arr): del arr[8]
         self.assertRaises(KeyError, deletekey)

         del arr[7]
         self.verify(arr[7] == None)
         self.verify(len(arr) == 7)

         del arr[5]
         self.verify(len(arr) == 7)
         del arr[6]
         del arr[5]
         self.verify(len(arr) == 5)

      def testsort(self): 
         try: sorted
         except NameError: return

         arr = Listdict({5: 'chicken', 7: 'chickette'})
         arr = sorted(arr)
         self.verify(arr[5] == None)
         self.verify(arr[6] == 'chicken')
         self.verify(arr[7] == 'chickette')

         arr = Listdict({5: 'chicken', 7: 'chickette'})
         arr.sort()
         self.verify(arr[5] == None)
         self.verify(arr[6] == 'chicken')
         self.verify(arr[7] == 'chickette')

      def testreverse(self): 
         try: reversed
         except NameError: return

         arr = Listdict({5: 'chicken', 7: 'chickette'})
         arrlist = list(reversed(arr))
         self.verify(arrlist[0] == 'chickette')
         self.verify(arrlist[2] == 'chicken')

         arr = Listdict({5: 'chicken', 7: 'chickette'})
         arr.reverse()
         self.verify(arr[0] == 'chickette')
         self.verify(arr[2] == 'chicken')

      def testmembership(self): 
         arr = Listdict({5: 'chicken'})
         self.verify('chicken' in arr)
         self.verify(not(0 in arr))
         self.verify(not(1 in arr))

         arr['mykey'] = 'myvalue'
         self.verify(not('myvalue' in arr))

      def testslice(self): 
         arr = Listdict({1: 'chicken', 2: 'chickette'})
         self.verify(arr[1:3] == ['chicken', 'chickette'])

      def testslices(self): 
         pqr = Listdict(['p', 'q', 'r'])
         pqr[1:1] = ['x', 'y']
         self.verify(pqr == ['p', 'x', 'y', 'q', 'r'])

         pqr = Listdict(['p', 'q', 'r'])
         pqr[1:2] = ['x', 'y']
         self.verify(pqr == ['p', 'x', 'y', 'r'])

         pqr = Listdict(['p', 'q', 'r'])
         pqr[1:3] = ['x', 'y']
         self.verify(pqr == ['p', 'x', 'y'])

         pqr = Listdict(['p', 'q', 'r'])
         pqr[1:4] = ['x', 'y']
         self.verify(pqr == ['p', 'x', 'y'])

         pqr = Listdict(['p', 'q', 'r'])
         pqr[5:8] = ['x', 'y']
         self.verify(pqr == ['p', 'q', 'r', 'x', 'y'])

      def testindex(self): 
         pqr = Listdict(['p', 'q', 'r'])
         self.verify(pqr.index('q') == 1)
         pqr.remove('q')
         self.verify(pqr == ['p', 'r'])

      def testadd(self): 
         pqr = Listdict(['p', 'q', 'r'])
         self.verify(pqr + pqr == ['p', 'q', 'r', 'p', 'q', 'r'])
         self.verify(pqr == ['p', 'q', 'r'])
         pqr += pqr
         self.verify(pqr == ['p', 'q', 'r', 'p', 'q', 'r'])

      def testmul(self): 
         pqr = Listdict(['p', 'q', 'r'])
         self.verify(pqr * 3 == ['p', 'q', 'r'] * 3)
         self.verify(pqr == ['p', 'q', 'r'])
         pqr *= 3
         self.verify(pqr == ['p', 'q', 'r'] * 3)

      def testcount(self): 
         arr = Listdict(list('abcadaefgahaaijkalam'))
         self.verify(arr.count('a') == 8)

   print __doc__.lstrip()
   print "Running tests..."
   suite = unittest.makeSuite(TestListdict)
   tester = unittest.TextTestRunner(verbosity=2)
   tester.run(suite)

if __name__=="__main__": 
   test()