Set ordinabile debole indicizzabile in Python

Question

Mi chiedevo se esiste un modo semplice per creare un set ordinato debole indicizzabile in Python. Ho provato a costruirne uno anch'io. Ecco quello che mi si avvicinò con:

""" 
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]) 

C'è un modo più semplice per fare questo?

Answer 1

Il modo più semplice per trarre vantaggio dai componenti esistenti nella libreria standard.

OrderedDict e MutableSet ABC semplificano la scrittura di un OrderedSet.

Allo stesso modo, è possibile riutilizzare il weakref.WeakSet esistente e sostituire il suo set di fondo() 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 ha una risposta grande e succinta, come al solito, ma in realtà è venuto qui un po ' torna interessato alla parte indicizzabile, più della parte weakref. Alla fine ho costruito la mia risposta, che è diventata the IndexedSet type in the boltons utility library. Fondamentalmente, sono tutte le parti migliori delle API list e set, combinate.

>>> 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' 

Se la parte weakref è critico probabilmente è possibile aggiungerlo tramite eredità o la modifica diretta di una copia del codice (il modulo è autonomo, puro Python, e 2/3 compatibile).