final commit

1 files changed, 96 insertions, 0 deletions

diff --git a/sorter.py b/sorter.py
new file mode 100644
index 0000000..ced8d7f
--- /dev/null
+++ b/sorter.py
@@ -0,0 +1,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)