It uses radix trie , where each node contains its subtrees leaf node count to index. And lower bound and upper bound are calculated based on last node that had other way to go if the current path doesnt leads to a leaf. Insertion and deletion has complexity of O(log(m)) where m is the integer we want to insert(basically that of a radix trie)
class intOrderedListNode:
def __init__(self):
self.zero_next=None
self.zero_size=0
self.one_next=None
self.one_size=0
class intOrderedList(intOrderedListNode):
def __init__(self):
self.node=intOrderedListNode()
self.max_depth=1
self.size=0
def insert(self, value: int) -> None:
while self.max_depth<value:
temp=self.node
self.node=intOrderedListNode()
self.node.zero_next=temp
self.node.zero_size=temp.zero_size+temp.one_size
self.max_depth<<=1
temp=self.max_depth
itr=self.node
while temp>0:
if value&temp:
itr.one_size+=1
if itr.one_next is None:
itr.one_next=intOrderedListNode()
itr=itr.one_next
else:
itr.zero_size+=1
if itr.zero_next is None:
itr.zero_next=intOrderedListNode()
itr=itr.zero_next
temp>>=1
self.size+=1
def __iter__(self):
self.idx=0
return self
def __next__(self):
if self.idx>=self.size:
raise StopIteration
result=self.index(self.idx)
self.idx+=1
return result
def index(self, idx: int) -> int:
if idx<0 or idx>=self.size:
raise IndexError
result=0
temp=self.max_depth
itr=self.node
while temp>0:
if itr.zero_size>idx:
itr=itr.zero_next
else:
result|=temp
idx-=itr.zero_size
itr=itr.one_next
temp>>=1
return result
def __len__(self):
return self.size
def __contains__(self, value: int) -> bool:
temp=self.max_depth
itr=self.node
while temp>0:
if value&temp:
if itr.one_size==0:
return False
itr=itr.one_next
else:
if itr.zero_size==0:
return False
itr=itr.zero_next
temp>>=1
return True
def lower_bound(self, value: int) -> int:
temp=self.max_depth
itr=self.node
result=0
last=None
last_temp=temp
chk=1
while temp>0:
if value&temp:
if chk:
result+=itr.zero_size
if itr.one_next :
itr=itr.one_next
else:
if last:
itr=last
itr=itr.zero_next
temp=last_temp
chk=0
value=0
else:
return self.size
else:
if itr.zero_next:
if itr.one_next:
last=itr
last_temp=temp
itr=itr.zero_next
else:
itr=itr.one_next
chk=0
value=0
temp>>=1
return result
def upper_bound(self, value: int) -> int:
temp=self.max_depth
itr=self.node
result=0
last=None
last_temp=temp
chk=1
while temp>0:
if value&temp:
result+=itr.zero_size
if itr.one_next :
if temp==1 and chk:
result+=itr.one_size
itr=itr.one_next
else:
if last:
itr=last
itr=itr.zero_next
temp=last_temp
value=0
else:
return self.size
else:
if itr.zero_next:
if itr.one_next:
last=itr
last_temp=temp
if temp==1 and chk:
result+=itr.zero_size
itr=itr.zero_next
else:
itr=itr.one_next
chk=0
value=0
temp>>=1
return result
def pop(self, idx: int) -> int:
if idx<0 or idx>=self.size:
raise IndexError
temp=self.max_depth
itr=self.node
result=0
while temp>0:
if itr.zero_size>idx:
itr.zero_size-=1
if itr.zero_size==0:
itr.zero_next=None
itr=itr.zero_next
else:
result|=temp
itr.one_size-=1
if itr.one_size==0:
itr.one_next=None
idx-=itr.zero_size
itr=itr.one_next
temp>>=1
self.size-=1
while self.node.one_size==0:
self.node=self.node.zero_next
self.max_depth>>=1
return result
