# Linked lists class Link: empty = () def __init__(self, first, rest=empty): assert rest is Link.empty or isinstance(rest, Link) self.first = first self.rest = rest def __repr__(self): if self.rest: rest_str = ', ' + repr(self.rest) else: rest_str = '' return 'Link({0}{1})'.format(self.first, rest_str) def filter_link(f, s): """Return elements e of s for which f(e) is true.""" if s is Link.empty: return s else: filtered = filter_link(f, s.rest) if f(s.first): return Link(s.first, filtered) else: return filtered def extend_link(s, t): if empty(s): return t else: return Link(s.first, extend_link(s.rest, t)) # Sets as sorted sequences def make_set(vals): """The set containing the values in list VALS.""" result = Link.empty while def empty(s): return s is Link.empty def contains(s, v): """Return true if set s contains value v as an element. >>> s = Link(1, Link(2, Link(3))) >>> contains(s, 2) True >>> contains(s, 5) False """ if empty(s): return False elif s.first == v: return True else: return contains(s.rest, v) def adjoin(s, v): """Return a set containing all elements of s and element v. >>> s = Link(1, Link(2, Link(3))) >>> t = adjoin(s, 4) >>> t Link(4, Link(1, Link(2, Link(3)))) """ if contains(s, v): return s else: return Link(v, s) def intersect(set1, set2): """Return a set containing all elements common to set1 and set2. >>> s = Link(1, Link(2, Link(3))) >>> t = adjoin(s, 4) >>> intersect(t, Link(1, Link(4, Link(9)))) Link(4, Link(1)) """ in_set2 = lambda v: contains(set2, v) return filter_link(in_set2, set1) def union(set1, set2): """Return a set containing all elements either in set1 or set2. >>> s = Link(1, Link(2, Link(3))) >>> t = adjoin(s, 4) >>> union(t, s) Link(4, Link(1, Link(2, Link(3)))) """ not_in_set2 = lambda v: not contains(set2, v) set1_not_set2 = filter_link(not_in_set2, set1) return extend_link(set1_not_set2, set2) # Sets as (sorted) ordered sequences def contains2(s, v): """Return true if set s contains value v as an element. >>> s = Link(1, Link(2, Link(3))) >>> contains2(s, 2) True >>> contains2(s, 5) False """ if empty(s) or s.first > v: return False elif s.first == v: return True else: return contains2(s.rest, v) def adjoin2(s, v): """Return a set containing all elements of s and element v. >>> s = Link(1, Link(2, Link(3))) >>> t = adjoin2(s, 4) >>> t Link(1, Link(2, Link(3, Link(4)))) """ if empty(s) or s.first > v: return Link(v, s) elif s.first == v: return s else: return Link(s.first, adjoin2(s.rest, v)) def add(s, v): """Add v to a set s, returning modified s. If s is not empty, returns same object. >>> s = Link(1, Link(3, Link(5))) >>> add(s, 0) Link(0, Link(1, Link(3, Link(5)))) >>> add(s, 3) Link(0, Link(1, Link(3, Link(5)))) >>> add(s, 4) Link(0, Link(1, Link(3, Link(4, Link(5))))) >>> add(s, 6) Link(0, Link(1, Link(3, Link(4, Link(5, Link(6)))))) """ if empty(s): return Link(v) if s.first > v: s.first, s.rest = v, Link(s.first, s.rest) elif s.first < v and empty(s.rest): s.rest = Link(v, s.rest) elif s.first < v: add(s.rest, v) return s def intersect2(set1, set2): """Return a set containing all elements common to set1 and set2. >>> s = Link(1, Link(2, Link(3))) >>> t = Link(2, Link(3, Link(4))) >>> intersect2(s, t) Link(2, Link(3)) """ if empty(set1) or empty(set2): return Link.empty else: e1, e2 = set1.first, set2.first if e1 == e2: return Link(e1, intersect2(set1.rest, set2.rest)) elif e1 < e2: return intersect2(set1.rest, set2) elif e2 < e1: return intersect2(set1, set2.rest) def union2(set1, set2): """Return a set containing all elements either in set1 or set2. >>> s = Link(1, Link(2, Link(3))) >>> t = Link(2, Link(3, Link(4))) >>> union2(s, t) Link(1, Link(2, Link(3, Link(4)))) """ if empty(set1): return set2 elif empty(set2): return set1 else: e1, e2 = set1.first, set2.first if e1 == e2: return Link(e1, union2(set1.rest, set2.rest)) elif e1 < e2: return Link(e1, union2(set1.rest, set2)) elif e2 < e1: return Link(e2, union2(set1, set2.rest))