Michael Spencer <[EMAIL PROTECTED]> wrote:
Nice. When you replace None by an object(), you have no restriction on
the elements any more:
> Here's something to work with:
>
> class OrdSet(object):
> def __init__(self, iterable):
> """Build an ordered, unique collection of hashable items"""
> #self._data = {None:[None, None]} # None is the pointer to the first
> # # element. This is unsatisfactory
> # # because it cannot then be a
> # # member of the collection
> #self._last = None
self._last = self._root = root = object()
self._data = {root:[root, root]}
> self.update(iterable)
>
> def add(self, obj):
> """Add an element to the collection"""
> data = self._data
> if not obj in data:
> last = self._last
> data[last][1] = obj
> #data[obj] = [last, None]
data[obj] = [last, self._root]
> self._last = obj
>
> def update(self, iterable):
> """Update the collection with the union of itself and another"""
> obj = self._last
> data = self._data
> last = data[obj][0]
> for item in iterable:
> if item not in data:
> data[obj] = [last, item]
> last, obj = obj, item
> #data[obj] = [last, None]
data[obj] = [last, self._root]
> self._last = obj
>
> def remove(self, item):
> """Remove an element from a set; it must be a member.
>
> If the element is not a member, raise a KeyError."""
> data = self._data
> prev, next = data[item]
> data[prev][1] = next
> data[next][0] = prev
>
> def discard(self, item):
> """Remove an element from a set if it is a member.
> If the element is not a member, do nothing."""
> try:
> self.remove(item)
> except KeyError:
> pass
>
> def __contains__(self, item):
> return item in self._data
>
> def pop(self):
> """Remove and the return the oldest element"""
> data = self._data
> #prev, first = data[None]
> #data[None] = [None,data[first][1]]
root = self._root
prev, first = data[root]
data[root] = [root,data[first][1]]
> return first
>
> def clear(self):
> self.__init__([])
>
> def __iter__(self):
> """Iterate over the collection in order"""
> data = self._data
> #prev, next = data[None]
> #while next is not None:
root = self._root
prev, next = data[root]
while next is not root:
> yield next
> prev, next = data[next]
>
> def __len__(self):
> return len(self._data)-1
>
> def __repr__(self):
> return "%s(%s)" % (self.__class__.__name__,list(self))
>>> a=OrdSet([None,1,None,3])
>>> a
OrdSet([None, 1, 3])
Marc
--
http://mail.python.org/mailman/listinfo/python-list
