Lichen

lib/__builtins__/set.py

775:c8ba74a474eb
2017-03-25 Paul Boddie Fixed method name.
     1 #!/usr/bin/env python     2      3 """     4 Set objects.     5      6 Copyright (C) 2015, 2016, 2017 Paul Boddie <paul@boddie.org.uk>     7      8 This program is free software; you can redistribute it and/or modify it under     9 the terms of the GNU General Public License as published by the Free Software    10 Foundation; either version 3 of the License, or (at your option) any later    11 version.    12     13 This program is distributed in the hope that it will be useful, but WITHOUT    14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS    15 FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more    16 details.    17     18 You should have received a copy of the GNU General Public License along with    19 this program.  If not, see <http://www.gnu.org/licenses/>.    20 """    21     22 from __builtins__.mapping import hashtable    23     24 class frozenset(hashtable):    25     26     "An immutable set representation holding a collection of distinct values."    27     28     def __init__(self, iterable=None):    29     30         "Initialise the set with any given 'iterable'."    31     32         self.clear()    33     34         if iterable is not None:    35             for value in iterable:    36                 self._setitem(self.buckets, value)    37     38     # Implementation methods.    39     40     def _find_entry(self, buckets, value, index):    41     42         """    43         Search in 'buckets' for 'value', using an 'index' identifying the bucket    44         involved.    45         """    46     47         i = 0    48     49         for found in buckets[index]:    50             if found == value:    51                 return i    52             i += 1    53     54         return None    55     56     def _resize(self, capacity):    57     58         "Resize the hashtable to have the given 'capacity'."    59     60         buckets = self._get_buckets(capacity)    61     62         for value in self._items():    63             self._setitem(buckets, value)    64     65         self.buckets = buckets    66     67     def _setitem(self, buckets, value):    68     69         "Set in the 'buckets' an item having the given 'value'."    70     71         index, i = self._get_entry(buckets, value)    72     73         # With no existing entry, append to the bucket.    74     75         if i is None:    76             buckets[index].append(value)    77             self.size += 1    78     79         # With an existing entry, replace the item.    80     81         else:    82             buckets[index][i] = value    83     84     # String representations.    85     86     def _str(self, name):    87     88         "Return a string representation."    89     90         b = buffer()    91         b.append(name)    92         b.append("(")    93         b.append(self._items().__repr__())    94         b.append(")")    95         return str(b)    96     97     def __str__(self):    98     99         "Return a string representation."   100    101         return self._str("frozenset")   102    103     __repr__ = __str__   104    105     # Public special methods.   106    107     def __contains__(self, value):   108    109         "Return whether 'value' is in the set."   110    111         index, i = self._get_entry(self.buckets, value)   112         return i is not None   113    114     def __iter__(self):   115    116         "Return an iterator."   117    118         return setiterator(self)   119    120     # Public conventional methods.   121    122     def copy(self):   123    124         "Return a copy of this set."   125    126         result = set()   127         result.update(self)   128         return result   129    130     def difference(self, other):   131    132         """   133         Return a set containing only those values in this set that are not in   134         'other'.   135         """   136    137         result = set()   138    139         for value in self:   140             if value not in other:   141                 result.add(value)   142    143         return result   144    145     def intersection(self, other):   146    147         "Return a set containing only those values in this set and in 'other'."   148    149         result = set()   150    151         for value in self:   152             if value in other:   153                 result.add(value)   154    155         return result   156    157     def issubset(self, other):   158    159         "Return whether this set is a subset of 'other'."   160    161         for value in self:   162             if value not in other:   163                 return False   164    165         return True   166    167     def issuperset(self, other):   168    169         "Return whether this set is a superset of 'other'."   170    171         for value in other:   172             if value not in self:   173                 return False   174    175         return True   176    177     def symmetric_difference(self, other):   178    179         """   180         Return a set containing only the values either in this set or in 'other'   181         but not in both.   182         """   183    184         result = set()   185    186         for value in self:   187             if value not in other:   188                 result.add(value)   189    190         for value in other:   191             if value not in self:   192                 result.add(value)   193    194         return result   195    196     def union(self, other):   197    198         "Return a set combining this set and 'other'."   199    200         result = set()   201    202         for value in self:   203             result.add(value)   204    205         for value in other:   206             result.add(value)   207    208         return result   209    210 class set(frozenset):   211    212     "A mutable set representation holding a collection of distinct values."   213    214     # String representation methods.   215    216     def __str__(self):   217    218         "Return a string representation."   219    220         return self._str("set")   221    222     __repr__ = __str__   223    224     # Public conventional methods.   225    226     def add(self, value):   227    228         "Add the given 'value' to the set."   229    230         capacity = len(self.buckets)   231    232         if self.size > capacity:   233             self._resize(capacity * 2)   234    235         self._setitem(self.buckets, value)   236    237     def difference_update(self, other):   238    239         "Remove from this set all values from 'other'."   240    241         for value in other:   242             self.discard(value)   243    244     def discard(self, value):   245    246         "Remove 'value' from the set, if present."   247    248         try:   249             self.remove(value)   250         except KeyError:   251             pass   252    253     def intersection_update(self, other):   254    255         "Preserve in this set only values in this set found in 'other'."   256    257         to_remove = set()   258    259         for value in self:   260             if value not in other:   261                 to_remove.add(value)   262    263         for value in to_remove:   264             self.remove(value)   265    266     def pop(self):   267    268         "Remove and return an arbitrary value."   269    270         # Get the last element from the first non-empty bucket.   271    272         for bucket in self.buckets:   273             if bucket:   274                 self.size -= 1   275                 return bucket.pop()   276    277         raise KeyError   278    279     def remove(self, value):   280    281         "Remove 'value' from the set."   282    283         self._remove_entry(value)   284    285     def symmetric_difference_update(self, other):   286    287         """   288         Remove from this set all values found in 'other', adding values only   289         found in 'other'.   290         """   291    292         to_add = other.difference(self)   293         self.difference_update(other)   294         self.update(to_add)   295    296     def update(self, other):   297    298         "Update this set using the contents of 'other'."   299    300         for value in other:   301             self.add(value)   302    303 class setiterator:   304    305     "An iterator for set types."   306    307     def __init__(self, mapping):   308    309         "Initialise the iterator with the given 'mapping'."   310    311         self.mapping = mapping   312         self.index = 0   313         self.i = 0   314    315     def next(self):   316    317         "Return the next value."   318    319         while True:   320    321             # Access the current bucket. If no such bucket exists, stop.   322    323             try:   324                 bucket = self.mapping.buckets[self.index]   325             except IndexError:   326                 raise StopIteration   327    328             # Access the current item. If no such item exists, get another   329             # bucket.   330    331             try:   332                 value = bucket[self.i]   333                 self.i += 1   334                 return value   335    336             except IndexError:   337                 self.index += 1   338                 self.i = 0   339    340 # vim: tabstop=4 expandtab shiftwidth=4