"""
Mixin class for easy creation of user lists.

Connelly Barnes 2005.  Public domain.

Use ListMixin to make classes which implement the Python list
interface.  Note that in many cases it is easier to subclass the
Python builtin list class.  If one subclasses list, then the data
is stored in-memory with the Python standard storage scheme.  The
ListMixin class is useful for different storage schemes, more
complicated data structures, or other nefarious hackery.

Features:
 - Compatible with Python 2.3, 2.4, and Psyco.

Example:

 >>> import listmixin
 >>> class TestList(listmixin.ListMixin):
 ...   def __init__(self, L=[]):
 ...     self.L = list(L)
 ...   def _constructor(self, iterable):
 ...     return TestList(iterable)
 ...   def __len__(self):
 ...     return len(self.L)
 ...   def _get_element(self, i):
 ...     assert 0 <= i < len(self)
 ...     return self.L[i]
 ...   def _set_element(self, i, x):
 ...     assert 0 <= i < len(self)
 ...     self.L[i] = x
 ...   def _resize_region(self, start, end, new_size):
 ...     assert 0 <= start <= len(self)
 ...     assert 0 <= end   <= len(self)
 ...     self.L[start:end] = [None] * new_size
 ...
 >>> # Now TestList() has behavior identical to that of list().
 >>> x = TestList([1, 2, 3]) + TestList([4, 5, 6])
 >>> x.extend([9, 8])
 >>> x.append(5)
 >>> x[5:8] = [7, 8]
 >>> x[1:9:3] = [1, 2, 3]
 >>> list(x)
 [1, 1, 3, 4, 2, 7, 8, 3]

"""

__version__ = '1.0.3'

import copy
import sys

class ListMixin(object):
  """
  Defines all list operations from a small subset of methods.

  Subclasses should define _get_element(i), _set_element(i, value),
  __len__(), _resize_region(start, end, new_size) and
  _constructor(iterable).  Define __iter__() for extra speed.

  The _get_element() and _set_element() methods are given indices with
  0 <= i < len(self).

  The _resize_region() method should resize the slice self[start:end]
  so that it has size new_size.  It is given indices such that
  start <= end, 0 <= start <= len(self) and 0 <= end <= len(self).
  The resulting elements in self[start:start+new_size] can be set to
  None or arbitrary Python values.

  The _constructor() method accepts an iterable and should return a
  new instance of the same class as self, populated with the elements
  of the given iterable.
  """
  def __cmp__(self, other):
    return cmp(list(self), list(other))

  def __hash__(self):
    raise TypeError('list objects are unhashable')

  def __iter__(self):
    for i in xrange(len(self)):
      yield self._get_element(i)

  def _tuple_from_slice(self, i):
    """
    Get (start, end, step) tuple from slice object.
    """
    (start, end, step) = i.indices(len(self))
    # Replace (0, -1, 1) with (0, 0, 1) (misfeature in .indices()).
    if step == 1:
      if end < start:
        end = start
      step = None
    if i.step == None:
      step = None
    return (start, end, step)

  def _fix_index(self, i):
    if i < 0:
      i += len(self)
    if i < 0 or i >= len(self):
      raise IndexError('list index out of range')
    return i

  def __getitem__(self, i):
    if isinstance(i, slice):
      (start, end, step) = self._tuple_from_slice(i)
      if step == None:
        indices = xrange(start, end)
      else:
        indices = xrange(start, end, step)
      return self._constructor([self._get_element(i) for i in indices])
    else:
      return self._get_element(self._fix_index(i))

  def __setitem__(self, i, value):
    if isinstance(i, slice):
      (start, end, step) = self._tuple_from_slice(i)
      if step != None:
        # Extended slice
        indices = range(start, end, step)
        if len(value) != len(indices):
          raise ValueError(('attempt to assign sequence of size %d' +
                            ' to extended slice of size %d') %
                           (len(value), len(indices)))
        for (j, assign_val) in enumerate(value):
          self._set_element(indices[j], assign_val)
      else:
        # Normal slice
        if len(value) != (end - start):
          self._resize_region(start, end, len(value))
        for (j, assign_val) in enumerate(value):
          self._set_element(start + j, assign_val)
    else:
      # Single element
      self._set_element(self._fix_index(i), value)

  def __delitem__(self, i):
    if isinstance(i, slice):
      (start, end, step) = self._tuple_from_slice(i)
      if step != None:
        # Extended slice
        indices = range(start, end, step)
        # Sort indices descending
        if len(indices) > 0 and indices[0] < indices[-1]:
          indices.reverse()
        for j in indices:
          del self[j]
      else:
        # Normal slice
        self._resize_region(start, end, 0)
    else:
      # Single element
      i = self._fix_index(i)
      self._resize_region(i, i + 1, 0)

  def __add__(self, other):
    if isinstance(other, self.__class__):
      ans = self._constructor(self)
      ans += other
      return ans
    return list(self) + other

  def __mul__(self, other):
    ans = self._constructor(self)
    ans *= other
    return ans

  def __radd__(self, other):
    if isinstance(other, self.__class__):
      ans = other._constructor(self)
      ans += self
      return ans
    return other + list(self)

  def __rmul__(self, other):
    return self * other

  def __iadd__(self, other):
    self[len(self):len(self)] = other
    return self

  def __imul__(self, other):
    if other <= 0:
      self[:] = []
    elif other > 1:
      aux = list(self)
      for i in xrange(other-1):
        self.extend(aux)
    return self

  def append(self, other):
    self[len(self):len(self)] = [other]

  def extend(self, other):
    self[len(self):len(self)] = other

  def count(self, other):
    ans = 0
    for item in self:
      if item == other:
        ans += 1
    return ans

  def reverse(self):
    for i in xrange(len(self)//2):
      j = len(self) - 1 - i
      (self[i], self[j]) = (self[j], self[i])

  def index(self, x, i=0, j=None):
    if i != 0 or j is not None:
      (i, j, ignore) = self._tuple_from_slice(slice(i, j))
    if j is None:
      j = len(self)
    for k in xrange(i, j):
      if self._get_element(k) == x:
        return k
    raise ValueError('index(x): x not in list')

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

  def pop(self, i=None):
    if i == None:
      i = len(self)-1
    ans = self[i]
    del self[i]
    return ans

  def remove(self, x):
    for i in xrange(len(self)):
      if self._get_element(i) == x:
        del self[i]
        return
    raise ValueError('remove(x): x not in list')

  # Define sort() as appropriate for the Python version.
  if sys.version_info[:3] < (2, 4, 0):
    def sort(self, cmpfunc=None):
      ans = list(self)
      ans.sort(cmpfunc)
      self[:] = ans
  else:
    def sort(self, cmpfunc=None, key=None, reverse=False):
      ans = list(self)
      if reverse == True:
        ans.sort(cmpfunc, key, reverse)
      elif key != None:
        ans.sort(cmpfunc, key)
      else:
        ans.sort(cmpfunc)
      self[:] = ans

  def __copy__(self):
    return self._constructor(self)

  def __deepcopy__(self, memo={}):
    ans = self._constructor([])
    memo[id(self)] = ans
    ans[:] = copy.deepcopy(tuple(self), memo)
    return ans

  # Tracking idea from R. Hettinger's deque class.  It's not
  # multithread safe, but does work with the builtin Python classes.
  def __str__(self, track=[]):
    if id(self) in track:
      return '...'
    track.append(id(self))
    ans = '%r' % (list(self),)
    track.remove(id(self))
    return ans

  def __repr__(self):
    return self.__class__.__name__ + '(' + str(self) + ')'


class TestList(ListMixin):
  """
  Simple list class built using ListMixin.
  """
  def __init__(self, L=[]):
    self.L = list(L)

  def _constructor(self, iterable):
    return TestList(iterable)

  def __len__(self):
    return len(self.L)

  def _get_element(self, i):
    assert 0 <= i < len(self)
    return self.L[i]

  def _set_element(self, i, x):
    assert 0 <= i < len(self)
    self.L[i] = x

  def _resize_region(self, start, end, new_size):
    assert 0 <= start <= len(self)
    assert 0 <= end   <= len(self)
    assert start <= end
    self.L[start:end] = [None] * new_size

  def __iter__(self):
    return iter(self.L)


def test_list_mixin(list_class=TestList, rand_elem=None):
  """
  Unit test for ListMixin.
  """
  if list_class is TestList:
    L1 = TestList()
    L2 = TestList()
    L3 = TestList()
    L1.extend([L1, L2, L3])
    L2.append(L3)
    L3.append(L1)
    assert (repr(L1) == 'TestList([TestList(...), TestList([TestList'+
                   '([TestList(...)])]), TestList([TestList(...)])])')
    L1 = TestList()
    L1.append(L1)
    L2 = copy.deepcopy(L1)
    assert id(L1) == id(L1[0])
    assert id(L2) == id(L2[0])
    L3 = copy.copy(L2)
    assert id(L3) != id(L3[0])
    assert id(L3[0]) == id(L2[0]) == id(L2)

  if rand_elem is None:
    def rand_elem():
      return random.randrange(50)

  def get_or_none(obj, getindex):
    try:
      return obj[getindex]
    except IndexError:
      return None

  def set_or_none(obj, setindex, setvalue):
    try:
      obj[setindex] = setvalue
      return setvalue
    except IndexError:
      return None

  def extended_set_or_none(obj, setindex, setvalue):
    try:
      obj[setindex] = setvalue
      return setvalue
    except ValueError:
      return None

  def insert_or_none(obj, insertindex, insertvalue):
    try:
      obj.insert(insertindex, insertvalue)
    except IndexError:
      return None

  def pop_or_none(obj, *popargs):
    try:
      obj.pop(*popargs)
    except IndexError:
      return None

  def remove_or_none(obj, removevalue):
    try:
      obj.remove(removevalue)
    except IndexError:
      return None

  import random
  import sets
  import sys
  for i in [1, 3, 8, 16, 18, 29, 59, 111, 213, 501, 1013,
            2021, 3122, 4039, 5054]:
    x = [rand_elem() for j in range(i)]
    y = list_class(x)

    assert isinstance(y[:], list_class)
    assert isinstance(y[:5], list_class)
    assert isinstance(y[:5:2], list_class)

    for j in range(100):
      r = random.randrange(13)
      if r == 0:
        # Set element at a random index
        if len(x) != 0:
          k = random.randrange(-2*len(x),2*len(x))
          v = rand_elem()
          assert set_or_none(x, k, v) == set_or_none(y, k, v)
      elif r == 1:
        # Delete element at random index
        if len(x) != 0:
          k = random.randrange(len(x))
          del x[k]
          del y[k]
      elif r == 2:
        # In place add some elements
        addelems = [rand_elem() for inx in range(random.randrange(4))]
        x += addelems
        y += addelems
      elif r == 3:
        # In place add an element
        addelem = rand_elem()
        x.append(addelem)
        y.append(addelem)
      elif r == 4:
        # In place add some elements
        addelems = [rand_elem() for inx in range(random.randrange(4))]
        x += addelems
        y += addelems
      elif r == 5:
        # Insert an element
        addelem = rand_elem()
        insertidx = random.randrange(-2*len(x), 2*len(x)+1)
        assert insert_or_none(x, insertidx, addelem) == \
               insert_or_none(y, insertidx, addelem)
      elif r == 6:
        # Pop an element
        popidx = random.randrange(-2*len(x), 2*len(x)+1)
        assert pop_or_none(x, popidx) == pop_or_none(y, popidx)
      elif r == 7:
        # Pop last element
        assert pop_or_none(x) == pop_or_none(y)
      elif r == 8:
        # Remove an element
        if len(x) != 0:
          remvalue = random.choice(x)
          assert remove_or_none(x, remvalue) == remove_or_none(y, remvalue)
      elif r == 9:
        if random.randrange(5) == 0:
          # Sort
          if sys.version_info[:3] >= (2, 4, 0):
            r2 = random.randrange(6)
          else:
            r2 = random.randrange(2)

          def keyfunc(keyitem):
            return (keyitem - 5) ** 2
          def cmpfunc(a, b):
            return cmp((a+9)**2, (b-5)**3)

          if r2 == 0:
            x.sort()
            y.sort()
          elif r2 == 1:
            x.sort(cmpfunc)
            y.sort(cmpfunc)
          elif r2 == 2:
            x.sort(cmpfunc, keyfunc)
            y.sort(cmpfunc, keyfunc)
          elif r2 == 3:
            x.sort(cmpfunc, keyfunc, True)
            y.sort(cmpfunc, keyfunc, True)
          elif r2 == 4:
            x.sort(cmpfunc, reverse=True)
            y.sort(cmpfunc, reverse=True)
          elif r2 == 5:
            x.sort(None, keyfunc, True)
            y.sort(None, keyfunc, True)
      elif r == 10:
        # Remove a slice
        start = random.randrange(-2*len(x), 2*len(x)+1)
        end   = random.randrange(-2*len(x), 2*len(x)+1)
        step  = random.randrange(-2*len(x), 2*len(x)+1)
        r2 = random.randrange(3)
        if r2 == 0:
          step = random.randrange(-5, 5)
        elif r2 == 1:
          step = 1
        if step == 0:
          step = 1
        del x[start:end:step]
        del y[start:end:step]
      elif r == 11:
        # Assign to a regular slice
        start = random.randrange(-2*len(x), 2*len(x)+1)
        end   = random.randrange(-2*len(x), 2*len(x)+1)
        assignval = [rand_elem() for assignidx in
                     range(random.randrange(10))]
        x[start:end] = assignval
        y[start:end] = assignval
      elif r == 12:
        # Assign to an extended slice
        start = random.randrange(-2*len(x), 2*len(x)+1)
        end   = random.randrange(-2*len(x), 2*len(x)+1)
        step  = random.randrange(-2*len(x), 2*len(x)+1)
        r2 = random.randrange(3)
        if r2 == 0:
          step = random.randrange(-5, 5)
        elif r2 == 1:
          step = 1
        if step == 0:
          step = 1
        if step == 1:
          step = 2
        indices = range(*slice(start, end, step).indices(len(x)))
        assignval = [rand_elem() for assignidx in
                     indices]
        if random.randrange(2) == 0:
          # Make right hand value have incorrect length
          if random.randrange(2) == 0 and len(assignval) > 0:
            if random.randrange(2) == 0:
              assignval.pop()
            else:
              assignval = []
          else:
            assignval.append(1)
        assert (extended_set_or_none(x, slice(start, end, step), assignval) == 
                extended_set_or_none(y, slice(start, end, step), assignval))

      # Check that x == y in a variety of ways.
      
      if len(x) != 0:
        for i4 in range(20):
          i3 = random.randrange(-2*len(x), 2*len(x))
          assert get_or_none(x, i3) == get_or_none(y, i3)

      assert list(iter(x)) == list(iter(y))
      assert list(iter(iter(x))) == list(iter(iter(y)))

      assert str(x) == str(y)

      assert x + [1,2] == y + [1,2]
      assert x * 0 == y * 0
      assert x * -1 == y * -1
      assert x * -5000 == y * -5000
      assert x * 1 == y * 1
      assert x * 2 == y * 2
      assert isinstance(x + y, list)
      assert x + y == x + list(y)
      elems = sets.Set(x)
      elems2 = sets.Set(y)
      assert elems == elems2
      def index_or_none(obj, search, *args):
        try:
          return obj.index(search, *args)
        except ValueError:
          return None
      for key in elems:
        assert x.count(key) == y.count(key)
        assert index_or_none(x, key) == index_or_none(y, key)
        i1 = random.randrange(-len(x)-2,len(x)+2)
        i2 = random.randrange(-len(x)-2,len(x)+2)
        assert index_or_none(x, key, i1, i2) == \
               index_or_none(y, key, i1, i2)
      assert x[:] == y[:]
      # Get slices
      for sliceidx in range(10):
        if len(x) != 0:
          start = random.randrange(-2*len(x), 2*len(x)+1)
          end   = random.randrange(-2*len(x), 2*len(x)+1)
          step  = random.randrange(-2*len(x), 2*len(x))
          r2 = random.randrange(3)
          if r2 == 0:
            step = random.randrange(-5, 5)
          elif r2 == 1:
            step = 1
          if step == 0:
            step = 1
          assert x[start:end:step] == y[start:end:step]
      assert cmp(x, y) == 0
      assert len(x) == len(y)
      assert x == y
      x.reverse()
      y.reverse()
      assert x == y
      x.reverse()
      y.reverse()
      for k in range(len(x)):
        assert x[k] == y[k]


def test(list_class=TestList):
  """
  Unit test main routine.
  """
  print 'Testing:'
  test_list_mixin(list_class)
  print '  ListMixin:     OK'


if __name__ == '__main__':
  test()