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__.iteration.iterator import itemiterator 23 from __builtins__.mapping import hashtable 24 25 class frozenset(hashtable): 26 27 "An immutable set representation holding a collection of distinct values." 28 29 def __init__(self, iterable=None): 30 31 "Initialise the set with any given 'iterable'." 32 33 self.clear() 34 35 if iterable is not None: 36 for value in iterable: 37 self._setitem(self.buckets, value) 38 39 # Implementation methods. 40 41 def _find_entry(self, value, index): 42 43 "Search for 'value', using an 'index' identifying the bucket involved." 44 45 i = 0 46 47 for found in self.buckets[index]: 48 if found == value: 49 return i 50 i += 1 51 52 return None 53 54 def _resize(self, capacity): 55 56 "Resize the hashtable to have the given 'capacity'." 57 58 buckets = self._get_buckets(capacity) 59 60 for value in self._items(): 61 self._setitem(buckets, value) 62 63 self.buckets = buckets 64 65 def _setitem(self, buckets, value): 66 67 "Set in the 'buckets' an item having the given 'value'." 68 69 index, i = self._get_entry(value) 70 71 # With no existing entry, append to the bucket. 72 73 if i is None: 74 buckets[index].append(value) 75 self.size += 1 76 77 # With an existing entry, replace the item. 78 79 else: 80 buckets[index][i] = value 81 82 # String representations. 83 84 def _str(self, name): 85 86 "Return a string representation." 87 88 b = buffer() 89 b.append(name) 90 b.append("(") 91 b.append(self._items().__repr__()) 92 b.append(")") 93 return str(b) 94 95 def __str__(self): 96 97 "Return a string representation." 98 99 return self._str("frozenset") 100 101 __repr__ = __str__ 102 103 # Public special methods. 104 105 def __contains__(self, value): 106 107 "Return whether 'value' is in the set." 108 109 index, i = self._get_entry(value) 110 return i is not None 111 112 def __iter__(self): 113 114 "Return an iterator." 115 116 return itemiterator(list(self)) 117 118 # Public conventional methods. 119 120 def copy(self): pass 121 def difference(self, other): pass 122 def intersection(self, other): pass 123 def issubset(self, other): pass 124 def issuperset(self, other): pass 125 def symmetric_difference(self, other): pass 126 def union(self, other): pass 127 128 class set(frozenset): 129 130 "A mutable set representation holding a collection of distinct values." 131 132 # String representation methods. 133 134 def __str__(self): 135 136 "Return a string representation." 137 138 return self._str("set") 139 140 __repr__ = __str__ 141 142 # Public conventional methods. 143 144 def add(self, value): 145 146 "Add the given 'value' to the set." 147 148 capacity = len(self.buckets) 149 150 if self.size > capacity: 151 self._resize(capacity * 2) 152 153 self._setitem(self.buckets, value) 154 155 def difference_update(self, other): pass 156 157 def discard(self, value): 158 159 "Remove 'value' from the set, if present." 160 161 try: 162 self.remove(value) 163 except KeyError: 164 pass 165 166 def intersection_update(self, other): pass 167 168 def pop(self): pass 169 170 def remove(self, value): 171 172 "Remove 'value' from the set." 173 174 self._remove_entry(value) 175 176 def symmetric_difference_update(self, other): pass 177 178 def update(self, other): pass 179 180 # vim: tabstop=4 expandtab shiftwidth=4