Package list
464ff713-9d15-4539-ba6d-39003ae9b060/main

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77``` ```# Binary search tree that holds status of sweep line. Only leaves hold values. # Operations for finding left and right neighbors of a query point p and finding which segments contain p. # Author: Sam Lichtenberg # Email: splichte@princeton.edu # Date: 09/02/2013 from pauvre.lsi.helper import * ev = 0.00000001 class Q: def __init__(self, key, value): self.key = key self.value = value self.left = None self.right = None def find(self, key): if self.key is None: return False c = compare_by_y(key, self.key) if c==0: return True elif c==-1: if self.left: self.left.find(key) else: return False else: if self.right: self.right.find(key) else: return False def insert(self, key, value): if self.key is None: self.key = key self.value = value c = compare_by_y(key, self.key) if c==0: self.value += value elif c==-1: if self.left is None: self.left = Q(key, value) else: self.left.insert(key, value) else: if self.right is None: self.right = Q(key, value) else: self.right.insert(key, value) # must return key AND value def get_and_del_min(self, parent=None): if self.left is not None: return self.left.get_and_del_min(self) else: k = self.key v = self.value if parent: parent.left = self.right # i.e. is root node else: if self.right: self.key = self.right.key self.value = self.right.value self.left = self.right.left self.right = self.right.right else: self.key = None return k,v def print_tree(self): if self.left: self.left.print_tree() print(self.key) print(self.value) if self.right: self.right.print_tree() ```