Set indexable weak ordered en Python

Question

Me preguntaba si existe una manera fácil de construir un conjunto ordenado débil indexable en Python. Traté de construir uno yo mismo. Esto es lo que se me ocurrió:

""" 
An indexable, ordered set of objects, which are held by weak reference. 
""" 
from nose.tools import * 
import blist 
import weakref 


class WeakOrderedSet(blist.weaksortedset): 
    """ 
    A blist.weaksortedset whose key is the insertion order. 
    """ 
    def __init__(self, iterable=()): 
     self.insertion_order = weakref.WeakKeyDictionary() # value_type to int 
     self.last_key = 0 
     super().__init__(key=self.insertion_order.__getitem__) 
     for item in iterable: 
      self.add(item) 

    def __delitem__(self, index): 
     values = super().__getitem__(index) 
     super().__delitem__(index) 
     if not isinstance(index, slice): 
      # values is just one element 
      values = [values] 
     for value in values: 
      if value not in self: 
       del self.insertion_order[value] 

    def add(self, value): 
     # Choose a key so that value is on the end. 
     if value not in self.insertion_order: 
      key = self.last_key 
      self.last_key += 1 
      self.insertion_order[value] = key 
     super().add(value) 

    def discard(self, value): 
     super().discard(value) 
     if value not in self: 
      del self.insertion_order[value] 

    def remove(self, value): 
     super().remove(value) 
     if value not in self: 
      del self.insertion_order[value] 

    def pop(self, *args, **kwargs): 
     value = super().pop(*args, **kwargs) 
     if value not in self: 
      del self.insertion_order[value] 

    def clear(self): 
     super().clear() 
     self.insertion_order.clear() 

    def update(self, *args): 
     for arg in args: 
      for item in arg: 
       self.add(item) 


if __name__ == '__main__': 
    class Dummy: 
     def __init__(self, value): 
      self.value = value 

    x = [Dummy(i) for i in range(10)] 
    w = WeakOrderedSet(reversed(x)) 
    del w[2:8] 
    assert_equals([9,8,1,0], [i.value for i in w]) 
    del w[0] 
    assert_equals([8,1,0], [i.value for i in w]) 
    del x 
    assert_equals([], [i.value for i in w]) 

¿Hay alguna manera más fácil de hacerlo?

Answer 1

La forma más fácil de hacerlo es aprovechar los componentes existentes en la biblioteca estándar.

OrderedDict y MutableSet ABC hacen que sea más fácil escribir un OrderedSet.

Del mismo modo, se puede reutilizar el weakref.WeakSet existente y sustituir su conjunto subyacente() con un orderedSet:

import collections, weakref 

class OrderedSet(collections.MutableSet): 
    def __init__(self, values=()): 
     self._od = collections.OrderedDict().fromkeys(values) 
    def __len__(self): 
     return len(self._od) 
    def __iter__(self): 
     return iter(self._od) 
    def __contains__(self, value): 
     return value in self._od 
    def add(self, value): 
     self._od[value] = None 
    def discard(self, value): 
     self._od.pop(value, None) 

class OrderedWeakrefSet(weakref.WeakSet): 
    def __init__(self, values=()): 
     super(OrderedWeakrefSet, self).__init__() 
     self.data = OrderedSet() 
     for elem in values: 
      self.add(elem) 

Answer 2

Raymond tiene una gran respuesta y sucinta, como de costumbre, pero en realidad yo he venido aquí un tiempo volver interesado en la parte indexable, más que la parte weakref. Finalmente construí mi propia respuesta, que se convirtió en the IndexedSet type in the boltons utility library. Básicamente, son todas las mejores partes de las API list y set, combinadas.

>>> x = IndexedSet(list(range(4)) + list(range(8))) 
>>> x 
IndexedSet([0, 1, 2, 3, 4, 5, 6, 7]) 
>>> x - set(range(2)) 
IndexedSet([2, 3, 4, 5, 6, 7]) 
>>> x[-1] 
7 
>>> fcr = IndexedSet('freecreditreport.com') 
>>> ''.join(fcr[:fcr.index('.')]) 
'frecditpo' 

Si la parte weakref es crítico es probable que puedes añadir a través de herencia o modificación directa de una copia del código (el módulo es independiente, puro-Python, y 2/3 compatibles).