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)