class SpaceMap(object):
''' Here we have:
__bottom - minimum space address possible;
__top - maximum space address possible;
__pairs - internal list of ranges;
__walk_list - internal list of keys.'''
__slots__ = frozenset(('__bottom', '__pairs', '__top', '__walk_list'))
def __init__(self, source = None, bottom = 0, top = None):
''' This one can be bootstrapped by giving a dict in format {x:y, x:y}.'''
self.__pairs = {}
self.__walk_list = None
self.__bottom = bottom
self.__top = top
if type(source) == dict:
for key in source:
self.__set(key, source[key])
self.fold()
def __getitem__(self, name):
'''Returns last range address by first range address.'''
if name in self.__pairs:
return(self.__pairs[name])
else:
return(None)
def __set(self, name, value):
'''Internal function to add ranges without folding. Also checks for range correctness.'''
if type(name) != int or type(value) != int or name >= value:
return(False)
if self.__bottom != None:
if name < self.__bottom or value < self.__bottom:
return(False)
if self.__top != None:
if name >= self.__top or value >= self.__top:
return(False)
self.__pairs[name] = value
return True
def __setitem__(self, name, value):
'''Adds one more range and tries to fold a space map.'''
self.__set(name, value)
self.fold()
def fold(self):
'''Tries to normalize spacemap by joining coaligned or overlapping ranges.'''
self.rewind()
pairs = ()
while True:
pair = self.pop()
if pair[0] == None:
break
pairs += pair,
last_pair = self.__bottom
for pair in pairs:
if last_pair in self.__pairs and pair[0] <= self.__pairs[last_pair]:
if pair[1] > self.__pairs[last_pair]:
self.__pairs[last_pair] = pair[1]
del(self.__pairs[pair[0]])
else:
last_pair = pair[0]
self.clear()
def rewind(self):
'''Reinitialises internal ordered list of ranges.'''
self.__walk_list = list(self.__pairs.keys())
self.__walk_list.sort()
def clear(self):
'''Clears internal ordered list of ranges.'''
self.__walk_list = None
def pop(self):
'''Returns next range from ordered list of ranges.'''
if self.__walk_list != None:
if len(self.__walk_list) > 0:
next = self.__walk_list.pop(0)
return([next, self.__pairs[next]])
return([None, None])
def __repr__(self):
'''Returns the inner dict with ranges.'''
return(repr(self.__pairs))
def __and__(self, other):
'''Returns new space map with ranges that appears both in A and B.'''
if type(other) != SpaceMap:
return(False)
new = {}
self.rewind()
other.rewind()
my_pair = self.pop()
other_pair = other.pop()
# if there are no pairs in B - we have nothing to do
if other_pair[0] == None or my_pair[0] == None:
all_parts_found = True
else:
all_parts_found = False
while not all_parts_found:
if my_pair[0] > other_pair[0]:
# when my pair starts after other pair starts
# m---
# o---
if my_pair[0] > other_pair[1]:
# when my pair starts after other pair ends
# m---
# o---o
other_pair = other.pop()
# tossing out other pair
if other_pair[0] == None:
all_parts_found = True
else:
# when my pair starts before other pair ends
# m--- | m---
# o---o | o---o
if my_pair[1] > other_pair[1]:
# when my pair ends after other pair ends
# m---m | m---m
# o---o | o---o
other_pair[0] = my_pair[0]
# trimming other pair by my pair start
# m---m
# o.o-o
else:
# when my pair ends before other pair ends
# m---m
# o-----o
new[my_pair[0]] = my_pair[1]
# my pair is covered and should be added to result
my_pair = self.pop()
# tossing out my pair
if my_pair[0] == None:
all_parts_found = True
elif my_pair[0] < other_pair[0]:
# when my pair starts before other one
# m---
# o---
if my_pair[1] < other_pair[0]:
# when my pair ends before other pair starts
# m---m
# o---
my_pair = self.pop()
# tossing out my pair
if my_pair[0] == None:
all_parts_found = True
else:
# when my pair ends before other pair starts
# m---m
# o---
my_pair[0] = other_pair[0]
# trimming my pair by other pair start
# m.m-m
# o---
else:
# when both pairs starts simultaneously
# m---
# o---
if my_pair[1] < other_pair[1]:
# when my pair ends before other pair
# m---m
# o-----o
new[my_pair[0]] = my_pair[1]
# my pair is covered and should be added to result
my_pair = self.pop()
# tossing out my pair
if my_pair[0] == None:
all_parts_found = True
else:
# when my pair ends after other pair
# m-----m
# o---o
new[my_pair[0]] = other_pair[1]
# part of my pair is covered and should be added to result
other_pair = other.pop()
# tossing out other pair
if other_pair[0] == None:
all_parts_found = True
self.clear()
other.clear()
return(SpaceMap(new, self.__bottom, self.__top))
def __sub__(self, other):
'''Returns new space map with ranges in A not covered by B.'''
if type(other) != SpaceMap:
return(False)
new = {}
self.rewind()
other.rewind()
my_pair = self.pop()
other_pair = other.pop()
# if there are no pairs in B - copy this one to new SpaceMap
if other_pair[0] == None:
new[my_pair[0]] = my_pair[1]
all_parts_found = True
elif my_pair[0] == None:
all_parts_found = True
else:
all_parts_found = False
while not all_parts_found:
if my_pair[0] > other_pair[0]:
# when my pair starts after other pair starts
# m---
# o---
if my_pair[0] > other_pair[1]:
# when my pair starts after other pair ends
# m---
# o---o
other_pair = other.pop()
# tossing out other pair
if other_pair[0] == None:
# this was last one - my pair goes to result
new[my_pair[0]] = my_pair[1]
all_parts_found = True
else:
# when my pair starts before other pair ends
# m--- | m---
# o---o | o---o
if my_pair[1] > other_pair[1]:
# when my pair ends after other pair ends
# m---m | m---m
# o---o | o---o
my_pair[0] = other_pair[1]
# trimming my pair by other pair end
# m.m-m
# o---o
other_pair = other.pop()
# tossing out other pair
if other_pair[0] == None:
# this was last one - my pair goes to result
new[my_pair[0]] = my_pair[1]
all_parts_found = True
else:
# when my pair ends before other pair ends
# m---m
# o-----o
my_pair = self.pop()
# tossing out my pair
if my_pair[0] == None:
all_parts_found = True
elif my_pair[0] < other_pair[0]:
# when my pair starts before other one
# m---
# o---
if my_pair[1] < other_pair[0]:
# when my pair ends before other pair starts
# m---m
# o---
new[my_pair[0]] = my_pair[1]
# my pair is not covered and should be added to result
my_pair = self.pop()
# tossing out my pair
if my_pair[0] == None:
all_parts_found = True
else:
# when my pair ends before other pair starts
# m---m
# o---
new[my_pair[0]] = other_pair[0]
# start of my pair is not covered and should be added to result
my_pair[0] = other_pair[0]
# trimming my pair by other pair start
# m.m-m
# o---
else:
# when both pairs starts simultaneously
# m---
# o---
if my_pair[1] < other_pair[1]:
# when my pair ends before other pair
# m---m
# o-----o
my_pair = self.pop()
# tossing out my pair
if my_pair[0] == None:
all_parts_found = True
else:
# when my pair ends after other pair
# m-----m
# o---o
my_pair[0] = other_pair[1]
# trimming my pair by other pair end
# m...m-m
# o---o
other_pair = other.pop()
# tossing out other pair
if other_pair[0] == None:
# this was last one - my pair goes to result
new[my_pair[0]] = my_pair[1]
all_parts_found = True
while True:
# copy any leftover in A to new SpaceMap
my_pair = self.pop()
if my_pair[0] == None:
break
else:
new[my_pair[0]] = my_pair[1]
self.clear()
other.clear()
return(SpaceMap(new, self.__bottom, self.__top))
def __eq__(self, other):
'''Compares two space maps.'''
if type(other) != SpaceMap:
return(False)
self.rewind()
other.rewind()
result = None
while True:
this = self.pop()
that = other.pop()
if this != that:
result = False
break
if this == [None, None] and that == [None, None]:
result = True
break
self.clear()
other.clear()
return(result)
def __ne__(self, other):
return(not self == other)
def end(self):
'''Returns last known point.'''
end = None
self.rewind()
while True:
this = self.pop()
if this == [None, None]:
break
elif end == None or this[1] > end:
end = this[1]
self.clear()
return(end)
def __len__(self):
return(len(self.__pairs))
def max(self):
result = None
for last in self.__pairs.itervalues():
if result == None or result < last:
result = last
return(result)