ivals-fast.py

from iquery import IQuery
from entry import Entry

class IQueryFast(IQuery):
	def __init__(self, sz, e):
		super(IQueryFast, self).__init__(sz)
		e = [x for x in e]

		e.append(Entry(0, sz, None))

		s = list()
		for x in e:
			a = (x.lo, False, x.val)
			b = (x.hi, True, x.val)
			s.append(a)
			s.append(b)
		s.sort()

		entries = []

		def emit(lo, hi, valstk):
			v = list()
			for x in valstk.values():
				v.extend(x)
			v = filter(lambda x:x is not None, v)
			v.sort()
			entries.append((lo, hi, v))

		last_num = 0
		stk = {}
		for num, is_end, val in s:
			if not is_end:
				if last_num != num:
					emit(last_num, num - 1, stk)
					last_num = num
				stk.setdefault(val, list()).append(val)
			else:
				if last_num < num + 1:
					emit(last_num, num, stk)
					last_num = num + 1
				stk[val].pop()
				if not stk[val]:
					del stk[val]

		self.__e = tuple(entries)

	def __getitem__(self, k):
		assert(k <= self._sz)
		for lo, hi, val in self.__e:
			if k >= lo and k <= hi:
				return val
		return list()