forked from mit-dig/air-reasoner
-
Notifications
You must be signed in to change notification settings - Fork 0
/
OrderedSequence.py
100 lines (87 loc) · 2.58 KB
/
OrderedSequence.py
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
"""Utility functions for ordered seqeunces
When you are dealing with sequences which you know are ordered, then
set operations are linear instead of square in the length of the
sequences. This makes an ordered sequence a practical representation
of a set.
@@ Now python has sets, these should be used where the ordering is not
otherwise necessary.
@@ check
$Id: OrderedSequence.py,v 1.2 2007/06/26 02:36:15 syosi Exp $
"""
def merge(a,b):
"""Merge sorted sequences
The fact that the sequences are sorted makes this faster"""
i = 0
j = 0
m = len(a)
n = len(b)
result = []
while 1:
if i == m: # No more of a, return rest of b
return result + b[j:]
if j == n:
return result + a[i:]
if a[i] < b[j]:
result.append(a[i])
i = i + 1
elif a[i] > b[j]:
result.append(b[j])
j = j + 1
else: # a[i]=b[j]
result.append(a[i])
i = i + 1
j = j + 1
def intersection(a,b):
"""Find intersection of sorted sequences.
The fact that the sequences are sorted makes this faster."""
i = 0
j = 0
m = len(a)
n = len(b)
# progress(" &&& Intersection of %s and %s" %(a,b))
result = []
while 1:
if i == m or j == n: # No more of one, return what we have
return result
if a[i] < b[j]:
i = i + 1
elif a[i] > b[j]:
j = j + 1
else: # a[i]=b[j]
result.append(a[i])
i = i + 1
j = j + 1
def minus(a,b):
"""Those in a but not in b for sorted sequences
The fact that the sequences are sorted makes this faster"""
i = 0
j = 0
m = len(a)
n = len(b)
result = []
# progress(" &&& minus of %s and %s" %(a,b))
while 1:
if j == n: # No more of b, return rest of a
return result + a[i:]
if i == m: # No more of a, some of b - error
raise ValueError("Cannot remove items" + `b[j:]`)
return result + b[j:]
if a[i] < b[j]:
result.append(a[i])
i = i + 1
elif a[i] > b[j]:
raise ValueError("Cannot remove item" + `b[j]`)
j = j + 1
else: # a[i]=b[j]
i = i + 1
j = j + 1
#______________________________________________ More utilities
def indentString(str):
""" Return a string indented by 4 spaces"""
s = " "
for ch in str:
s = s + ch
if ch == "\n": s = s + " "
if s.endswith(" "):
s = s[:-4]
return s