# Module: calculus.py import enum class entry_not_found(Exception): """Raised when an entry is not found in a collection""" pass class entry_already_exists(Exception): """Raised when an entry already exists in a collection""" pass class state(enum.Enum): header = 0 left_high = 1 right_high = 2 balanced = 3 class direction(enum.Enum): from_left = 0 from_right = 1 from abc import ABC, abstractmethod class comparer(ABC): @abstractmethod def compare(self,t): pass class node(comparer): def __init__(self): self.parent = None self.left = self self.right = self self.balance = state.header def compare(self,t): if self.key < t: return -1 elif t < self.key: return 1 else: return 0 def is_header(self): return self.balance == state.header def length(self): if self != None: if self.left != None: left = self.left.length() else: left = 0 if self.right != None: right = self.right.length() else: right = 0 return left + right + 1 else: return 0 def rotate_left(self): _parent = self.parent x = self.right self.parent = x x.parent = _parent if x.left is not None: x.left.parent = self self.right = x.left x.left = self return x def rotate_right(self): _parent = self.parent x = self.left self.parent = x x.parent = _parent; if x.right is not None: x.right.parent = self self.left = x.right x.right = self return x def balance_left(self): _left = self.left if _left is None: return self; if _left.balance == state.left_high: self.balance = state.balanced _left.balance = state.balanced self = self.rotate_right() elif _left.balance == state.right_high: subright = _left.right if subright.balance == state.balanced: self.balance = state.balanced _left.balance = state.balanced elif subright.balance == state.right_high: self.balance = state.balanced _left.balance = state.left_high elif subright.balance == left_high: root.balance = state.right_high _left.balance = state.balanced subright.balance = state.balanced _left = _left.rotate_left() self.left = _left self = self.rotate_right() elif _left.balance == state.balanced: self.balance = state.left_high _left.balance = state.right_high self = self.rotate_right() return self; def balance_right(self): _right = self.right if _right is None: return self; if _right.balance == state.right_high: self.balance = state.balanced _right.balance = state.balanced self = self.rotate_left() elif _right.balance == state.left_high: subleft = _right.left; if subleft.balance == state.balanced: self.balance = state.balanced _right.balance = state.balanced elif subleft.balance == state.left_high: self.balance = state.balanced _right.balance = state.right_high elif subleft.balance == state.right_high: self.balance = state.left_high _right.balance = state.balanced subleft.balance = state.balanced _right = _right.rotate_right() self.right = _right self = self.rotate_left() elif _right.balance == state.balanced: self.balance = state.right_high _right.balance = state.left_high self = self.rotate_left() return self def balance_tree(self, direct): taller = True while taller: _parent = self.parent; if _parent.left == self: next_from = direction.from_left else: next_from = direction.from_right; if direct == direction.from_left: if self.balance == state.left_high: if _parent.is_header(): _parent.parent = _parent.parent.balance_left() elif _parent.left == self: _parent.left = _parent.left.balance_left() else: _parent.right = _parent.right.balance_left() taller = False elif self.balance == state.balanced: self.balance = state.left_high taller = True elif self.balance == state.right_high: self.balance = state.balanced taller = False else: if self.balance == state.left_high: self.balance = state.balanced taller = False elif self.balance == state.balanced: self.balance = state.right_high taller = True elif self.balance == state.right_high: if _parent.is_header(): _parent.parent = _parent.parent.balance_right() elif _parent.left == self: _parent.left = _parent.left.balance_right() else: _parent.right = _parent.right.balance_right() taller = False if taller: if _parent.is_header(): taller = False else: self = _parent direct = next_from def balance_tree_remove(self, _from): if self.is_header(): return; shorter = True; while shorter: _parent = self.parent; if _parent.left == self: next_from = direction.from_left else: next_from = direction.from_right if _from == direction.from_left: if self.balance == state.left_high: shorter = True elif self.balance == state.balanced: self.balance = state.right_high; shorter = False elif self.balance == state.right_high: if self.right is not None: if self.right.balance == state.balanced: shorter = False else: shorter = True else: shorter = False; if _parent.is_header(): _parent.parent = _parent.parent.balance_right() elif _parent.left == self: _parent.left = _parent.left.balance_right(); else: _parent.right = _parent.right.balance_right() else: if self.balance == state.right_high: self.balance = state.balanced shorter = True elif self.balance == state.balanced: self.balance = state.left_high shorter = False elif self.balance == state.left_high: if self.left is not None: if self.left.balance == state.balanced: shorter = False else: shorter = True else: short = False; if _parent.is_header(): _parent.parent = _parent.parent.balance_left(); elif _parent.left == self: _parent.left = _parent.left.balance_left(); else: _parent.right = _parent.right.balance_left(); if shorter: if _parent.is_header(): shorter = False else: _from = next_from self = _parent def previous(self): if self.is_header(): return self.right if self.left is not None: y = self.left while y.right is not None: y = y.right return y else: y = self.parent; if y.is_header(): return y x = self while x == y.left: x = y y = y.parent return y def next(self): if self.is_header(): return self.left if self.right is not None: y = self.right while y.left is not None: y = y.left return y; else: y = self.parent if y.is_header(): return y x = self; while x == y.right: x = y y = y.parent; return y def swap_nodes(a, b): if b == a.left: if b.left is not None: b.left.parent = a if b.right is not None: b.right.parent = a if a.right is not None: a.right.parent = b if not a.parent.is_header(): if a.parent.left == a: a.parent.left = b else: a.parent.right = b; else: a.parent.parent = b b.parent = a.parent a.parent = b a.left = b.left b.left = a temp = a.right a.right = b.right b.right = temp elif b == a.right: if b.right is not None: b.right.parent = a if b.left is not None: b.left.parent = a if a.left is not None: a.left.parent = b if not a.parent.is_header(): if a.parent.left == a: a.parent.left = b else: a.parent.right = b else: a.parent.parent = b b.parent = a.parent a.parent = b a.right = b.right b.right = a temp = a.left a.left = b.left b.left = temp elif a == b.left: if a.left is not None: a.left.parent = b if a.right is not None: a.right.parent = b if b.right is not None: b.right.parent = a if not parent.is_header(): if b.parent.left == b: b.parent.left = a else: b.parent.right = a else: b.parent.parent = a a.parent = b.parent b.parent = a b.left = a.left a.left = b temp = a.right a.right = b.right b.right = temp elif a == b.right: if a.right is not None: a.right.parent = b if a.left is not None: a.left.parent = b if b.left is not None: b.left.parent = a if not b.parent.is_header(): if b.parent.left == b: b.parent.left = a else: b.parent.right = a else: b.parent.parent = a a.parent = b.parent b.parent = a b.right = a.right a.right = b temp = a.left a.left = b.left b.left = temp else: if a.parent == b.parent: temp = a.parent.left a.parent.left = a.parent.right a.parent.right = temp else: if not a.parent.is_header(): if a.parent.left == a: a.parent.left = b else: a.parent.right = b else: a.parent.parent = b if not b.parent.is_header(): if b.parent.left == b: b.parent.left = a else: b.parent.right = a else: b.parent.parent = a if b.left is not None: b.left.parent = a if b.right is not None: b.right.parent = a if a.left is not None: a.left.parent = b if a.right is not None: a.right.parent = b temp1 = a.left a.left = b.left b.left = temp1 temp2 = a.right a.right = b.right b.right = temp2 temp3 = a.parent a.parent = b.parent b.parent = temp3 balance = a.balance a.balance = b.balance b.balance = balance class parent_node(node): def __init__(self, parent): self.parent = parent self.left = None self.right = None self.balance = state.balanced class set_node(node): def __init__(self, parent, key): self.parent = parent self.left = None self.right = None self.balance = state.balanced self.key = key class ordered_set: def __init__(self): self.header = node() def __iter__(self): self.node = self.header return self def __next__(self): self.node = self.node.next() if self.node.is_header(): raise StopIteration return self.node.key def __delitem__(self, key): self.remove(key) def __lt__(self, other): first1 = self.header.left last1 = self.header first2 = other.header.left last2 = other.header while (first1 != last1) and (first2 != last2): l = first1.key < first2.key if not l: first1 = first1.next(); first2 = first2.next(); else: return True; a = self.__len__() b = other.__len__() return a < b def __hash__(self): h = 0 for i in self: h = h + i.__hash__() return h def __eq__(self, other): if self < other: return False if other < self: return False return True def __ne__(self, other): if self < other: return True if other < self: return True return False def __len__(self): return self.header.parent.length() def __getitem__(self, key): return self.contains(key) def __str__(self): l = self.header.right s = "{" i = self.header.left h = self.header while i != h: s = s + i.key.__str__() if i != l: s = s + "," i = i.next() s = s + "}" return s def __or__(self, other): r = ordered_set() first1 = self.header.left last1 = self.header first2 = other.header.left last2 = other.header while first1 != last1 and first2 != last2: les = first1.key < first2.key graater = first2.key < first1.key if les: r.add(first1.key) first1 = first1.next() elif graater: r.add(first2.key) first2 = first2.next() else: r.add(first1.key) first1 = first1.next() first2 = first2.next() while first1 != last1: r.add(first1.key) first1 = first1.next() while first2 != last2: r.add(first2.key) first2 = first2.next() return r def __and__(self, other): r = ordered_set() first1 = self.header.left last1 = self.header first2 = other.header.left last2 = other.header while first1 != last1 and first2 != last2: les = first1.key < first2.key graater = first2.key < first1.key if les: first1 = first1.next() elif graater: first2 = first2.next() else: r.add(first1.key) first1 = first1.next() first2 = first2.next() return r def __xor__(self, other): r = ordered_set() first1 = self.header.left last1 = self.header first2 = other.header.left last2 = other.header while first1 != last1 and first2 != last2: les = first1.key < first2.key graater = first2.key < first1.key if les: r.add(first1.key) first1 = first1.next() elif graater: r.add(first2.key) first2 = first2.next() else: first1 = first1.next() first2 = first2.next() while first1 != last1: r.add(first1.key) first1 = first1.next() while first2 != last2: r.add(first2.key) first2 = first2.next() return r def __sub__(self, other): r = ordered_set() first1 = self.header.left last1 = self.header first2 = other.header.left last2 = other.header while first1 != last1 and first2 != last2: les = first1.key < first2.key graater = first2.key < first1.key if les: r.add(first1.key) first1 = first1.next() elif graater: r.add(first2.key) first2 = first2.next() else: first1 = first1.next() first2 = first2.next() while first1 != last1: r.add(first1.key) first1 = first1.next() return r def __lshift__(self, data): self.add(data) return self def __rshift__(self, data): self.remove(data) return self def is_subset(self, other): first1 = self.header.left last1 = self.header first2 = other.header.left last2 = other.header is_subet = True while first1 != last1 and first2 != last2: if first1.key < first2.key: is_subset = False break elif first2.key < first1.key: first2 = first2.next() else: first1 = first1.next() first2 = first2.next() if is_subet: if first1 != last1: is_subet = False return is_subet def is_superset(self,other): return other.is_subset(self) def add(self, data): if self.header.parent is None: self.header.parent = set_node(self.header,data) self.header.left = self.header.parent self.header.right = self.header.parent else: root = self.header.parent while True: c = root.compare(data) if c >= 0: if root.left is not None: root = root.left else: new_node = set_node(root,data) root.left = new_node if self.header.left == root: self.header.left = new_node root.balance_tree(direction.from_left) return else: if root.right is not None: root = root.right else: new_node = set_node(root, data) root.right = new_node if self.header.right == root: self.header.right = new_node root.balance_tree(direction.from_right) return def remove(self,data): root = self.header.parent; while True: if root is None: raise entry_not_found("Entry not found in collection") c = root.compare(data) if c < 0: root = root.left; elif c > 0: root = root.right; else: if root.left is not None: if root.right is not None: replace = root.left while replace.right is not None: replace = replace.right root.swap_nodes(replace) _parent = root.parent if _parent.left == root: _from = direction.from_left else: _from = direction.from_right if self.header.left == root: n = root.next(); if n.is_header(): self.header.left = self.header self.header.right = self.header else: self.header.left = n elif self.header.right == root: p = root.previous(); if p.is_header(): self.header.left = self.header self.header.right = self.header else: self.header.right = p if root.left is None: if _parent == self.header: self.header.parent = root.right elif _parent.left == root: _parent.left = root.right else: _parent.right = root.right if root.right is not None: root.right.parent = _parent else: if _parent == self.header: self.header.parent = root.left elif _parent.left == root: _parent.left = root.left else: _parent.right = root.left if root.left is not None: root.left.parent = _parent; _parent.balance_tree_remove(_from) return def contains(self,data): root = self.header.parent; while True: if root == None: return False c = root.compare(data); if c > 0: root = root.left; elif c < 0: root = root.right; else: return True def find(self,data): root = self.header.parent; while True: if root == None: raise entry_not_found("An entry is not found in a collection") c = root.compare(data); if c > 0: root = root.left; elif c < 0: root = root.right; else: return root.key; class key_value(comparer): def __init__(self, key, value): self.key = key self.value = value def compare(self,kv): if self.key < kv.key: return -1 elif kv.key < self.key: return 1 else: return 0 def __lt__(self, other): return self.key < other.key def __str__(self): return '(' + self.key.__str__() + ',' + self.value.__str__() + ')' def __eq__(self, other): return self.key == other.key def __hash__(self): return hash(self.key) class dictionary: def __init__(self): self.set = ordered_set() return None def __lt__(self, other): if self.keys() < other.keys(): return true if other.keys() < self.keys(): return false first1 = self.set.header.left last1 = self.set.header first2 = other.set.header.left last2 = other.set.header while (first1 != last1) and (first2 != last2): l = first1.key.value < first2.key.value if not l: first1 = first1.next(); first2 = first2.next(); else: return True; a = self.__len__() b = other.__len__() return a < b def add(self, key, value): try: self.set.remove(key_value(key,None)) except entry_not_found: pass self.set.add(key_value(key,value)) return def remove(self, key): self.set.remove(key_value(key,None)) return def clear(self): self.set.header = node() def sort(self): sort_bag = bag() for e in self: sort_bag.add(e.value) keys_set = self.keys() self.clear() i = sort_bag.__iter__() i = sort_bag.__next__() try: for e in keys_set: self.add(e,i) i = sort_bag.__next__() except: return def keys(self): keys_set = ordered_set() for e in self: keys_set.add(e.key) return keys_set def __len__(self): return self.set.header.parent.length() def __str__(self): l = self.set.header.right; s = "{" i = self.set.header.left; h = self.set.header; while i != h: s = s + "(" s = s + i.key.key.__str__() s = s + "," s = s + i.key.value.__str__() s = s + ")" if i != l: s = s + "," i = i.next() s = s + "}" return s; def __iter__(self): self.set.node = self.set.header return self def __next__(self): self.set.node = self.set.node.next() if self.set.node.is_header(): raise StopIteration return key_value(self.set.node.key.key,self.set.node.key.value) def __getitem__(self, key): kv = self.set.find(key_value(key,None)) return kv.value def __setitem__(self, key, value): self.add(key,value) return def __delitem__(self, key): self.set.remove(key_value(key,None)) class array: def __init__(self): self.dictionary = dictionary() return None def __len__(self): return self.dictionary.__len__() def push(self, value): k = self.dictionary.set.header.right if k == self.dictionary.set.header: self.dictionary.add(0,value) else: self.dictionary.add(k.key.key+1,value) return def pop(self): if self.dictionary.set.header.parent != None: data = self.dictionary.set.header.right.key.value self.remove(self.dictionary.set.header.right.key.key) return data def add(self, key, value): try: self.dictionary.remove(key) except entry_not_found: pass self.dictionary.add(key,value) return def remove(self, key): self.dictionary.remove(key) return def sort(self): self.dictionary.sort() def clear(self): self.dictionary.header = node(); def __iter__(self): self.dictionary.node = self.dictionary.set.header return self def __next__(self): self.dictionary.node = self.dictionary.node.next() if self.dictionary.node.is_header(): raise StopIteration return self.dictionary.node.key.value def __getitem__(self, key): kv = self.dictionary.set.find(key_value(key,None)) return kv.value def __setitem__(self, key, value): self.add(key,value) return def __delitem__(self, key): self.dictionary.remove(key) def __lshift__(self, data): self.push(data) return self def __lt__(self, other): return self.dictionary < other.dictionary def __str__(self): l = self.dictionary.set.header.right; s = "{" i = self.dictionary.set.header.left; h = self.dictionary.set.header; while i != h: s = s + i.key.value.__str__() if i != l: s = s + "," i = i.next() s = s + "}" return s; class bag: def __init__(self): self.header = node() def __iter__(self): self.node = self.header return self def __delitem__(self, key): self.remove(key) def __next__(self): self.node = self.node.next() if self.node.is_header(): raise StopIteration return self.node.key def __str__(self): l = self.header.right; s = "(" i = self.header.left; h = self.header; while i != h: s = s + i.key.__str__() if i != l: s = s + "," i = i.next() s = s + ")" return s; def __len__(self): return self.header.parent.length() def __lshift__(self, data): self.add(data) return self def add(self, data): if self.header.parent is None: self.header.parent = set_node(self.header,data) self.header.left = self.header.parent self.header.right = self.header.parent else: root = self.header.parent while True: c = root.compare(data) if c >= 0: if root.left is not None: root = root.left else: new_node = set_node(root,data) root.left = new_node if self.header.left == root: self.header.left = new_node root.balance_tree(direction.from_left) return else: if root.right is not None: root = root.right else: new_node = set_node(root, data) root.right = new_node if self.header.right == root: self.header.right = new_node root.balance_tree(direction.from_right) return def remove_first(self,data): root = self.header.parent; while True: if root is None: return False; c = root.compare(data); if c > 0: root = root.left; elif c < 0: root = root.right; else: if root.left is not None: if root.right is not None: replace = root.left; while replace.right is not None: replace = replace.right; root.swap_nodes(replace); _parent = root.parent if _parent.left == root: _from = direction.from_left else: _from = direction.from_right if self.header.left == root: n = root.next(); if n.is_header(): self.header.left = self.header self.header.right = self.header else: self.header.left = n; elif self.header.right == root: p = root.previous(); if p.is_header(): self.header.left = self.header self.header.right = self.header else: self.header.right = p if root.left is None: if _parent == self.header: self.header.parent = root.right elif _parent.left == root: _parent.left = root.right else: _parent.right = root.right if root.right is not None: root.right.parent = _parent else: if _parent == self.header: self.header.parent = root.left elif _parent.left == root: _parent.left = root.left else: _parent.right = root.left if root.left is not None: root.left.parent = _parent; _parent.balance_tree_remove(_from) return True; def remove(self,data): success = self.remove_first(data) while success: success = self.remove_first(data) def remove_node(self, root): if root.left != None and root.right != None: replace = root.left while replace.right != None: replace = replace.right root.swap_nodes(replace) parent = root.parent; if parent.left == root: next_from = direction.from_left else: next_from = direction.from_right if self.header.left == root: n = root.next() if n.is_header(): self.header.left = self.header; self.header.right = self.header else: self.header.left = n elif self.header.right == root: p = root.previous() if p.is_header(): root.header.left = root.header root.header.right = header else: self.header.right = p if root.left == None: if parent == self.header: self.header.parent = root.right elif parent.left == root: parent.left = root.right else: parent.right = root.right if root.right != None: root.right.parent = parent else: if parent == self.header: self.header.parent = root.left elif parent.left == root: parent.left = root.left else: parent.right = root.left if root.left != None: root.left.parent = parent; parent.balance_tree_remove(next_from) def remove_at(self, data, ophset): p = self.search(data); if p == None: return else: lower = p after = after(data) s = 0 while True: if ophset == s: remove_node(lower); return; lower = lower.next_node() if after == lower: break s = s+1 return def search(self, key): s = before(key) s.next() if s.is_header(): return None c = s.compare(s.key) if c != 0: return None return s def before(self, data): y = self.header; x = self.header.parent; while x != None: if x.compare(data) >= 0: x = x.left; else: y = x; x = x.right; return y def after(self, data): y = self.header; x = self.header.parent; while x != None: if x.compare(data) > 0: y = x x = x.left else: x = x.right return y; def find(self,data): root = self.header.parent; results = array() while True: if root is None: break; p = self.before(data) p = p.next() if not p.is_header(): i = p l = self.after(data) while i != l: results.push(i.key) i = i.next() return results else: break; return results class bag_dictionary: def __init__(self): self.bag = bag() return None def add(self, key, value): self.bag.add(key_value(key,value)) return def remove(self, key): self.bag.remove(key_value(key,None)) return def remove_at(self, key, index): self.bag.remove_at(key_value(key,None), index) return def clear(self): self.bag.header = node() def __len__(self): return self.bag.header.parent.length() def __str__(self): l = self.bag.header.right; s = "{" i = self.bag.header.left; h = self.bag.header; while i != h: s = s + "(" s = s + i.key.key.__str__() s = s + "," s = s + i.key.value.__str__() s = s + ")" if i != l: s = s + "," i = i.next() s = s + "}" return s; def __iter__(self): self.bag.node = self.bag.header return self def __next__(self): self.bag.node = self.bag.node.next() if self.bag.node.is_header(): raise StopIteration return key_value(self.bag.node.key.key,self.bag.node.key.value) def __getitem__(self, key): kv_array = self.bag.find(key_value(key,None)) return kv_array def __setitem__(self, key, value): self.add(key,value) return def __delitem__(self, key): self.bag.remove(key_value(key,None)) class unordered_set: def __init__(self): self.bag_dictionary = bag_dictionary() def __len__(self): return self.bag_dictionary.__len__() def __hash__(self): h = 0 for i in self: h = h + i.__hash__() return h def __eq__(self, other): for t in self: if not other.contains(t): return False for u in other: if self.contains(u): return False return true; def __ne__(self, other): return not self == other def __or__(self, other): r = unordered_set() for t in self: r.add(t); for u in other: if not self.contains(u): r.add(u); return r def __and__(self, other): r = unordered_set() for t in self: if other.contains(t): r.add(t) for u in other: if self.contains(u) and not r.contains(u): r.add(u); return r def __xor__(self, other): r = unordered_set() for t in self: if not other.contains(t): r.add(t) for u in other: if not self.contains(u) and not r.contains(u): r.add(u) return r def __sub__(self, other): r = ordered_set() for t in self: if not other.contains(t): r.add(t); return r def __lshift__(self, data): self.add(data) return self def __rshift__(self, data): self.remove(data) return self def __getitem__(self, key): return self.contains(key) def is_subset(self, other): is_subet = True for t in self: if not other.contains(t): subset = False break return is_subet def is_superset(self,other): return other.is_subset(self) def add(self, value): if not self.contains(value): self.bag_dictionary.add(hash(value),value) else: raise entry_already_exists("Entry already exists in the unordered set") def contains(self, data): if self.bag_dictionary.bag.header.parent == None: return False; else: index = hash(data); _search = self.bag_dictionary.bag.header.parent; search_index = _search.key.key; if index < search_index: _search = _search.left elif index > search_index: _search = _search.right if _search == None: return False while _search != None: search_index = _search.key.key; if index < search_index: _search = _search.left elif index > search_index: _search = _search.right else: break if _search == None: return False return self.contains_node(data, _search) def contains_node(self,data,_node): previous = _node.previous() save = _node while not previous.is_header() and previous.key.key == _node.key.key: save = previous; previous = previous.previous() c = _node.key.value _node = save if c == data: return True next = _node.next() while not next.is_header() and next.key.key == _node.key.key: _node = next c = _node.key.value if c == data: return True; next = _node.next() return False; def find(self,data,_node): previous = _node.previous() save = _node while not previous.is_header() and previous.key.key == _node.key.key: save = previous; previous = previous.previous(); _node = save; c = _node.key.value if c == data: return _node next = _node.next() while not next.is_header() and next.key.key == _node.key.key: _node = next c = _node.data.value if c == data: return _node next = _node.next() return None def search(self, data): if self.bag_dictionary.bag.header.parent == None: return None else: index = hash(data) _search = self.bag_dictionary.bag.header.parent c = _search.key.key if index < c: _search = _search.left; elif index > c: _search = _search.right; while _search != None: if index != c: break c = _search.key.key if index < c: _search = _search.left; elif index > c: _search = _search.right; else: break if _search == None: return None return self.find(data, _search) def remove(self,data): found = self.search(data); if found != None: self.bag_dictionary.bag.remove_node(found); else: raise entry_not_found("Entry not found in the unordered set") def clear(self): self.bag_dictionary.bag.header = node() def __str__(self): l = self.bag_dictionary.bag.header.right; s = "{" i = self.bag_dictionary.bag.header.left; h = self.bag_dictionary.bag.header; while i != h: s = s + i.key.value.__str__() if i != l: s = s + "," i = i.next() s = s + "}" return s; def __iter__(self): self.bag_dictionary.bag.node = self.bag_dictionary.bag.header return self def __next__(self): self.bag_dictionary.bag.node = self.bag_dictionary.bag.node.next() if self.bag_dictionary.bag.node.is_header(): raise StopIteration return self.bag_dictionary.bag.node.key.value class map: def __init__(self): self.set = unordered_set() return None def __len__(self): return self.set.__len__() def add(self, key, value): try: self.set.remove(key_value(key,None)) except entry_not_found: pass self.set.add(key_value(key,value)) return def remove(self, key): self.set.remove(key_value(key,None)) return def clear(self): self.set.clear() def __str__(self): l = self.set.bag_dictionary.bag.header.right; s = "{" i = self.set.bag_dictionary.bag.header.left; h = self.set.bag_dictionary.bag.header; while i != h: s = s + "(" s = s + i.key.value.key.__str__() s = s + "," s = s + i.key.value.value.__str__() s = s + ")" if i != l: s = s + "," i = i.next() s = s + "}" return s; def __iter__(self): self.set.node = self.set.bag_dictionary.bag.header return self def __next__(self): self.set.node = self.set.node.next() if self.set.node.is_header(): raise StopIteration return key_value(self.set.node.key.key,self.set.node.key.value) def __getitem__(self, key): kv = self.set.find(key_value(key,None)) return kv.value def __setitem__(self, key, value): self.add(key,value) return def __delitem__(self, key): self.remove(key)