Insertion sorted python list

insertionlist.py

#By Tim Sheerman-Chase
#Released under CC0 license


class InsertionSortedList():
	#Yay! I have re-invented insertion sort!

	def __init__(self):
		self._vals = []
	
	def index(self, val):
		ci = self.closestindex(val)
		if ci == -1:
			raise ValueError(str(val)+" is not in set")
		valAtCursor = self._vals[ci]
		if valAtCursor == val:
			return ci
		raise ValueError(str(val)+" is not in set")
		
	def closestindex(self, val):
		#Divide and conquer!
		upperLimit = len(self._vals)
		lowerLimit = 0
		steps = 0

		if len(self._vals) == 0 or val < self._vals[0]:
			return -1 #The value is lower than any number in the list
		if val > self._vals[-1]:
			return len(self._vals)-1
	
		while True:
			cursor = (upperLimit + lowerLimit)/2
			valAtCursor = self._vals[cursor]

			if valAtCursor == val: 
				return cursor #This is the correct index

			if valAtCursor > val:
				upperLimit = cursor
			else:
				lowerLimit = cursor

			if lowerLimit + 1 == upperLimit:
				return lowerLimit #This is as close as we can get
			steps += 1

	def __contains__(self, val):
		try:
			ind = self.index(val)
			return True
		except ValueError:
			return False

	def add(self, val, suppressDuplicates = False):
		ci = self.closestindex(val)
		if suppressDuplicates:
			valAtCursor = self._vals[ci]
			if val == valAtCursor: return
		insertBefore = ci + 1
		self._vals.insert(insertBefore, val)

	def remove(self, val):
		ind = self.index(val)
		self._vals.pop(ind)

	def __repr__(self):
		return self._vals.__repr__()

	def __len__(self):
		return len(self._vals)

	def __iter__(self):
		return self._vals.__iter__()

	def __getitem__(self, ind):
		return self._vals[ind]

class CompressedIntSet():
	#Contains a set of compressed integers
	#Compression is based on ranges of numbers

	def __init__(self):
		self._rangeLower = InsertionSortedList()
		self._rangeUpper = []

	def add(self, val):
		if not isinstance(val, int):
			raise ValueError("Unexpected input type")

		ci = self._rangeLower.closestindex(val)

		if ci != -1:
			lowerLimit = self._rangeLower[ci]
			upperLimit = self._rangeUpper[ci]
			if lowerLimit <= val and upperLimit >= val:
				return #Already in range
			if lowerLimit <= val and upperLimit+1 >= val:
				self._rangeUpper[ci] = val #Extend range upward
				return

		if ci+1 < len(self._rangeLower):
			nextLowerLimit = self._rangeLower[ci+1]
			nextUpperLimit = self._rangeUpper[ci+1]
			if nextLowerLimit-1 <= val and nextUpperLimit >= val:
				self._rangeLower._vals[ci+1] = val #Extend range downward
				return
		
		#Insert new stand alone range
		self._rangeLower._vals.insert(ci+1, val)
		self._rangeUpper.insert(ci+1, val)
		return

	def __contains__(self, val):
		ci = self._rangeLower.closestindex(val)
		if ci == -1: return False
		lowerLimit = self._rangeLower[ci]
		upperLimit = self._rangeUpper[ci]
		return lowerLimit <= val and upperLimit >= val

	def __repr__(self):
		return str([(l, u) for l, u in zip(self._rangeLower, self._rangeUpper)])
			
	def __len__(self):
		count = 0
		for l, u in zip(self._rangeLower, self._rangeUpper):
			count += u - l + 1
		return count

	def compress(self):
		#Perform further compression of internal structure
		filteredLower = []
		filteredUpper = []
		changesMade = False
		i = 0
		while i < len(self._rangeLower)-1:
			if self._rangeUpper[i] + 1 == self._rangeLower[i+1]:
				filteredLower.append(self._rangeLower[i])
				filteredUpper.append(self._rangeUpper[i+1])
				changesMade = True
				i += 2
			else:
				filteredLower.append(self._rangeLower[i])
				filteredUpper.append(self._rangeUpper[i])
				i += 1

		if i < len(self._rangeLower):
			filteredLower.append(self._rangeLower[i])
			filteredUpper.append(self._rangeUpper[i])

		if changesMade:
			self._rangeLower._vals = filteredLower
			self._rangeUpper = filteredUpper