Best way to make a list unique?

[Michael Spencer]

Marc Christiansen wrote:
> Michael Spencer <mahs at telcopartners.com> wrote:
> 
> Nice. When you replace None by an object(), you have no restriction on
> the elements any more:
> 
> 
Thanks for the suggestion, Marc.

Note that if there is no need to access the middle of the collection, then the 
implementation is simpler, and less resource-intensive, since the items can be 
singly-linked

class UniqueQueue(object):
     def __init__(self, iterable):
         self._data = _data = {}
         self._last = self._root = object() # An object the user is unlikely to
                                            # reference - thanks Marc
         self.update(iterable)

     def push(self, obj):
         if not obj in self._data:
             self._data[self._last] = obj
             self._last = obj

     def pop(self):
         data = self._data
         first = data.pop(self._root)
         self._root = first
         return first

     def update(self, iterable):
         last = self._last
         data = self._data
         for item in iterable:
             if item not in data:
                 data[last] = item
                 last = item
         self._last = last

     def __iter__(self):
         data = self._data
         next = self._root
         try:
             while 1:
                 next = data[next]
                 yield next
         except KeyError:
             raise StopIteration

     def __repr__(self):
         return "%s(%s)" % (self.__class__.__name__,list(self))


  >>> q = UniqueQueue(range(5))
  >>> q.update(range(3,8))
  >>> q
  UniqueQueue([0, 1, 2, 3, 4, 5, 6, 7])
  >>> q.pop()
  0
  >>> q
  UniqueQueue([1, 2, 3, 4, 5, 6, 7])
  >>>
  >>> q.push(None)
  >>> q
  UniqueQueue([1, 2, 3, 4, 5, 6, 7, None])
  >>>


Michael