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
|
from math import floor
class Sorter:
def __init__(self):
self.data = []
def __len__(self):
return len(self.data)
def comp(self, item1, item2): #these should be dim's
#will return 'e' for equal, 'l' for less (i.e. item1 < item2), and 'g' for greater
if item1[0] < item2[0]:
return 'l'
if item1[0] == item2[0] and item1[1] < item2[1]:
return 'l'
if item1[0] == item2[0] and item1[1] == item2[1]:
return 'e'
if item1[0] == item2[0] and item1[1] > item2[1]:
return 'g'
if item1[0] > item2[0]:
return 'g'
def __contains__(self, item):
if len(self) == 0: #messes up the code if length == 0
return False
lo = 0
hi = len(self) - 1
while hi > lo:
mid = floor((hi-lo)/2)+lo
dif = self.comp(self[mid],item)
if dif == 'l':
hi = mid-1
if dif == 'g':
lo = mid+1
if dif == 'e':
return True
if self[lo] == item:
return True
return False
def __getitem__(self, ind):
return self.data[ind]
def insert(self, item):
if len(self) == 0:
self.data.insert(0, item)
return 0
lo = 0
hi = len(self) - 1
while hi > lo:
mid = floor((hi-lo)/2)+lo
dif = self.comp(self[mid],item)
if dif == 'l':
hi = mid-1
if dif == 'g':
lo = mid+1
if dif == 'e':
self.data.insert(mid, item)
return mid+1
dif = self.comp(self[lo],item)
if dif == 'l':
self.data.insert(lo,item)
return lo
if dif == 'e' or dif == 'g':
self.data.insert(lo+1,item)
return lo+1
def index(self, item):
lo = 0
hi = len(self) - 1
while hi > lo:
mid = floor((hi-lo)/2)+lo
dif = self.comp(self[mid],item)
if dif == 'l':
hi = mid-1
if dif == 'g':
lo = mid+1
if dif == 'e':
return mid
if item == self[lo]:
return lo
else:
raise(IndexError)
def remove(self, item):
ind = self.index(item)
self.data.pop(ind)
return ind
def __repr__(self):
return str(self.data)
test = Sorter()
test.insert((1,2))
test.insert((1,3))
print(test.insert((0,2)))
print((1,4) in test)
|
