from time import time from sys import argv TIME = time() def checkpoint (): """ A stopwatch. Prints seconds elapsed since last call to checkpoint. """ global TIME if TIME > 0: elapsed_time = time() - TIME print ('............. Elapsed time : ' + str(elapsed_time) ) TIME = time() class Element: """ It is pretty straightforward, a key together with an array of values form a pair. Clients are welcome to directly manipulate values' array. """ def __init__(self, key, val): """ Constructor takes a key and first associated value. """ self.key = key self.values = [val] def __repr__(self): return "( {} ↦ {} )".format (self.key, self.values) class BinaryNode: """ A node with payload and two children. We use it to simplify splitting algorithm. """ def __init__ (self, element, left = None, right = None): """ Create an binary node """ self.element = element self.left = left self.right = right class Node: """ A node from 2-3 tree. It could contain 1 or 2 Elements. Let x designate the first Element, and let y correspond to the second one (possibly non-existent). The x.key should always be less than y.key. A node may have up to 3 children. Some children could be empty. They equal to None. The left subtree contains nodes whose elements have keys less than x.key. The keys of elements of the middle subtree are between x.key and y.key. The right subtree contains only elements with keys greater than y.key. Always x < y (comparing keys) _____ |x|y| +-+-+ / | \ / | \ / | \ / | \ ----- ------- ----- |. 0: node = stack.pop() if node.x is not None : yield node.x if node.y is not None : yield node.y if node.left is not None : stack.append (node.left) if node.middle is not None : stack.append (node.middle) if node.right is not None : stack.append (node.right) def is_leaf (self): """ Really important """ return self.middle == None and self.left == None and self.right == None def add (self, a): """ Add BinaryNode 'a' to the current node ensuring key's order x.key < y.key and moving pointers to children comme il faut. Return False if there is no place (see split). """ if self.y is not None: return False left = a.left right = a.right if self.x is None: # very first case, when the root is empty self.left, self.x, self.middle = left, a.element, right ## if a.element.key < self.x.key ## ## BEFORE ==================> AFTER ## ## self self ## __________ ____________ ## |x| None | | e | x | ## +-+------+ +---+------+ ## / | \ / | \ ## | M None left right M ## ^ ## | Wherefrom Binary Node comes ## | e.key < x.key ## --- ## | e | ## --- ## / \ ## left right ## ## The figures of the same kind are useful ## to better understand the code of add(...) ans split(...) ## Feel free to draw it yourself ! if a.element.key < self.x.key: self.x, self.y = a.element, self.x self.left, self.middle, self.right = left, right, self.middle if a.element.key > self.x.key: self.y = a.element self.middle, self.right = left, right return True def split (self, splitter): """ Split current node using a given binary_node, returns a new binary_node. Return False if we should not split the node. """ if self.y is None: return False x, y = self.x, self.y if splitter.element.key < x.key : el = self.x left = Node (splitter.element) left.left, left.middle = splitter.left, splitter.right right = Node (self.y) right.left, right.middle = self.middle, self.right elif splitter.element.key > y.key : el = self.y left = Node (self.x) left.left, left.middle = self.left, self.middle right = Node (splitter.element) right.left, right.middle = splitter.left, splitter.right else: el = splitter.element left = Node (self.x) left.left, left.middle = self.left, splitter.left right = Node (self.y) right.left, right.middle = splitter.right, self.right return BinaryNode (el, left, right) def add_split_repeat (self, bnode, path_to_leaf): """ Add BinaryNode element to the last node of the path_to_leaf, spliting and pushing up to the root when needed. Nodes from path_to_leaf should correspond to the path from the root to the leaf. Return the (possibly new) root. """ root = path_to_leaf[0] while len (path_to_leaf) > 0: node = path_to_leaf.pop() added = node.add (bnode) if added: return root if not added: bnode = node.split (bnode) if len (path_to_leaf) == 0: new_root = Node(bnode.element) new_root.left = bnode.left new_root.middle = bnode.right return new_root def __repr__ (self): """ For debug purposes """ return "[ left = {}, x = {}, middle = {}, y = {}, right = {}] ".format( self.left, self.x, self.middle, self.y, self.right ) class Arbalet: """ Key-value store "Arbalet v2", based on 2-3 variant of a B-tree. See https://kirgizov.link/teaching/esirem/information-systems-2021/TD-6-7.pdf """ def __init__(self): """ Creates a 2-3 B-tree """ self.root = Node() def search (self, key): """ Find a corresponding list of values or return None if key does not exists in Arbalet. WARNING! It returns a pointer to the list actually stored in the tree. """ c = self.root while True: if c is None : return None if c.x is None : return None if key == c.x.key : return c.x.values if key < c.x.key : c = c.left; continue if c.y is None : c = c.middle; continue if key == c.y.key : return c.y.values if key < c.y.key : c = c.middle; continue c = c.right def __iter__ (self): """ Simple DFS iteration over the tree. WARNING! The iteration does not preserve keys' order. """ yield from self.root.parcours() def insert (self, key, value): """ Associate value to the key. """ ### When Arbalet already knows about the key v = self.search (key) if v is not None : v.append (value); return ### When key is a new new = BinaryNode (Element (key, value)) c = self.root ### Find a corresponding leaf, remembering the path path_to_leaf = [] while True: path_to_leaf.append (c) if c.is_leaf (): self.root = c.add_split_repeat (new, path_to_leaf) return else: if key < c.x.key : c = c.left; continue if c.y is None : c = c.middle; continue if key < c.y.key : c = c.middle; continue c = c.right def __repr__(self): """ For debug purposes """ return str(list(self)) def delete_one (self, key, value): """ TODO: Delete a value associated to the key """ pass def delete_all (self, key): """ TODO: Delete all values associated to the key """ pass def test_arbalet(): print ('We test...') a = Arbalet() b = Arbalet() a.insert ("test", 0) a.insert ("tost", 0) a.insert ("hzhh", 1) a.insert ("test", 1) b.insert ("test", 0) assert a.search('hei') == None assert a.search('test') == [0,1] assert b.search('test') == [0] print ('Tests are OK!') def load_data (name, arbalet): """ Exercice 2.1 """ print ('Loading data from', name) with open(name) as f: for line in f: t = line.rstrip('\n').split(';') arbalet.insert (t[0], int(t[1])) print ('Done') if __name__ == "__main__": test_arbalet() a = Arbalet() if len (argv) < 2: print ("Usage : python {} file-with-notes.txt".format(argv[0])) exit (1) fname = argv[1] checkpoint() # Exercice 2.1 load_data (fname, a) checkpoint() # Exercice 2.2 mnotes = a.search ('Margaret Smith') print ('Mean note is', sum (mnotes) / len (mnotes), 'for Margaret Smith') checkpoint() # Exercice 2.3 ? prsn = [] for el in a: if any ( x > 18 for x in el.values ): prsn.append (el.key) print ('There are', len (prsn), 'bons notes (> 18)') checkpoint() # Exercice 2.4 ? prsn = [] for el in a: if any ( x == 0 for x in el.values ): prsn.append (el.key) print ('There are', len (prsn), 'notes 0') checkpoint() # Exercice 2.5 pl = 0 for el in a: if len (el.values) > 1 : pl += 1 print (pl, ' people have more than one note') checkpoint() print ('A+')