886158fbf4 2011-12-19 1: class SpaceMap(object):
bfe3da6658 2010-10-14 2: ''' Here we have:
bfe3da6658 2010-10-14 3: __bottom - minimum space address possible;
bfe3da6658 2010-10-14 4: __top - maximum space address possible;
bfe3da6658 2010-10-14 5: __pairs - internal list of ranges;
bfe3da6658 2010-10-14 6: __walk_list - internal list of keys.'''
bfe3da6658 2010-10-14 7:
bfe3da6658 2010-10-14 8: __slots__ = frozenset(('__bottom', '__pairs', '__top', '__walk_list'))
bfe3da6658 2010-10-14 9:
bfe3da6658 2010-10-14 10: def __init__(self, source = None, bottom = 0, top = None):
bfe3da6658 2010-10-14 11: ''' This one can be bootstrapped by giving a dict in format {x:y, x:y}.'''
bfe3da6658 2010-10-14 12: self.__pairs = {}
bfe3da6658 2010-10-14 13: self.__walk_list = None
bfe3da6658 2010-10-14 14: self.__bottom = bottom
bfe3da6658 2010-10-14 15: self.__top = top
bfe3da6658 2010-10-14 16: if type(source) == dict:
bfe3da6658 2010-10-14 17: for key in source:
bfe3da6658 2010-10-14 18: self.__set(key, source[key])
bfe3da6658 2010-10-14 19: self.fold()
bfe3da6658 2010-10-14 20:
bfe3da6658 2010-10-14 21: def __getitem__(self, name):
bfe3da6658 2010-10-14 22: '''Returns last range address by first range address.'''
bfe3da6658 2010-10-14 23: if name in self.__pairs:
bfe3da6658 2010-10-14 24: return(self.__pairs[name])
bfe3da6658 2010-10-14 25: else:
bfe3da6658 2010-10-14 26: return(None)
bfe3da6658 2010-10-14 27:
bfe3da6658 2010-10-14 28: def __set(self, name, value):
bfe3da6658 2010-10-14 29: '''Internal function to add ranges without folding. Also checks for range correctness.'''
bfe3da6658 2010-10-14 30: if type(name) != int or type(value) != int or name >= value:
bfe3da6658 2010-10-14 31: return(False)
886158fbf4 2011-12-19 32: if self.__bottom != None:
bfe3da6658 2010-10-14 33: if name < self.__bottom or value < self.__bottom:
bfe3da6658 2010-10-14 34: return(False)
886158fbf4 2011-12-19 35: if self.__top != None:
bfe3da6658 2010-10-14 36: if name >= self.__top or value >= self.__top:
bfe3da6658 2010-10-14 37: return(False)
bfe3da6658 2010-10-14 38: self.__pairs[name] = value
bfe3da6658 2010-10-14 39: return True
bfe3da6658 2010-10-14 40:
bfe3da6658 2010-10-14 41: def __setitem__(self, name, value):
bfe3da6658 2010-10-14 42: '''Adds one more range and tries to fold a space map.'''
bfe3da6658 2010-10-14 43: self.__set(name, value)
bfe3da6658 2010-10-14 44: self.fold()
bfe3da6658 2010-10-14 45:
bfe3da6658 2010-10-14 46: def fold(self):
bfe3da6658 2010-10-14 47: '''Tries to normalize spacemap by joining coaligned or overlapping ranges.'''
bfe3da6658 2010-10-14 48: self.rewind()
bfe3da6658 2010-10-14 49: pairs = ()
bfe3da6658 2010-10-14 50: while True:
bfe3da6658 2010-10-14 51: pair = self.pop()
bfe3da6658 2010-10-14 52: if pair[0] == None:
bfe3da6658 2010-10-14 53: break
bfe3da6658 2010-10-14 54: pairs += pair,
bfe3da6658 2010-10-14 55: last_pair = self.__bottom
bfe3da6658 2010-10-14 56: for pair in pairs:
bfe3da6658 2010-10-14 57: if last_pair in self.__pairs and pair[0] <= self.__pairs[last_pair] and pair[1] > self.__pairs[last_pair]:
bfe3da6658 2010-10-14 58: self.__pairs[last_pair] = pair[1]
bfe3da6658 2010-10-14 59: del(self.__pairs[pair[0]])
bfe3da6658 2010-10-14 60: else:
bfe3da6658 2010-10-14 61: last_pair = pair[0]
bfe3da6658 2010-10-14 62: self.clear()
bfe3da6658 2010-10-14 63:
bfe3da6658 2010-10-14 64: def rewind(self):
bfe3da6658 2010-10-14 65: '''Reinitialises internal ordered list of ranges.'''
bfe3da6658 2010-10-14 66: self.__walk_list = list(self.__pairs.keys())
bfe3da6658 2010-10-14 67: self.__walk_list.sort()
bfe3da6658 2010-10-14 68:
bfe3da6658 2010-10-14 69: def clear(self):
bfe3da6658 2010-10-14 70: '''Clears internal ordered list of ranges.'''
bfe3da6658 2010-10-14 71: self.__walk_list = None
bfe3da6658 2010-10-14 72:
bfe3da6658 2010-10-14 73: def pop(self):
bfe3da6658 2010-10-14 74: '''Returns next range from ordered list of ranges.'''
bfe3da6658 2010-10-14 75: if self.__walk_list != None:
bfe3da6658 2010-10-14 76: if len(self.__walk_list) > 0:
bfe3da6658 2010-10-14 77: next = self.__walk_list.pop(0)
bfe3da6658 2010-10-14 78: return([next, self.__pairs[next]])
bfe3da6658 2010-10-14 79: return([None, None])
bfe3da6658 2010-10-14 80:
bfe3da6658 2010-10-14 81: def __repr__(self):
bfe3da6658 2010-10-14 82: '''Returns the inner dict with ranges.'''
bfe3da6658 2010-10-14 83: return(repr(self.__pairs))
bfe3da6658 2010-10-14 84:
bfe3da6658 2010-10-14 85: def __and__(self, other):
bfe3da6658 2010-10-14 86: '''Returns new space map with ranges that appears both in A and B.'''
886158fbf4 2011-12-19 87: if type(other) != SpaceMap:
bfe3da6658 2010-10-14 88: return(False)
bfe3da6658 2010-10-14 89: new = {}
bfe3da6658 2010-10-14 90: self.rewind()
bfe3da6658 2010-10-14 91: other.rewind()
bfe3da6658 2010-10-14 92: my_pair = self.pop()
bfe3da6658 2010-10-14 93: other_pair = other.pop()
bfe3da6658 2010-10-14 94: # if there are no pairs in B - we have nothing to do
bfe3da6658 2010-10-14 95: if other_pair[0] == None or my_pair[0] == None:
bfe3da6658 2010-10-14 96: all_parts_found = True
bfe3da6658 2010-10-14 97: else:
bfe3da6658 2010-10-14 98: all_parts_found = False
bfe3da6658 2010-10-14 99: while not all_parts_found:
bfe3da6658 2010-10-14 100: if my_pair[0] > other_pair[0]:
bfe3da6658 2010-10-14 101: # when my pair starts after other pair starts
bfe3da6658 2010-10-14 102: # m---
bfe3da6658 2010-10-14 103: # o---
bfe3da6658 2010-10-14 104: if my_pair[0] > other_pair[1]:
bfe3da6658 2010-10-14 105: # when my pair starts after other pair ends
bfe3da6658 2010-10-14 106: # m---
bfe3da6658 2010-10-14 107: # o---o
bfe3da6658 2010-10-14 108: other_pair = other.pop()
bfe3da6658 2010-10-14 109: # tossing out other pair
bfe3da6658 2010-10-14 110: if other_pair[0] == None:
bfe3da6658 2010-10-14 111: all_parts_found = True
bfe3da6658 2010-10-14 112: else:
bfe3da6658 2010-10-14 113: # when my pair starts before other pair ends
bfe3da6658 2010-10-14 114: # m--- | m---
bfe3da6658 2010-10-14 115: # o---o | o---o
bfe3da6658 2010-10-14 116: if my_pair[1] > other_pair[1]:
bfe3da6658 2010-10-14 117: # when my pair ends after other pair ends
bfe3da6658 2010-10-14 118: # m---m | m---m
bfe3da6658 2010-10-14 119: # o---o | o---o
bfe3da6658 2010-10-14 120: other_pair[0] = my_pair[0]
bfe3da6658 2010-10-14 121: # trimming other pair by my pair start
bfe3da6658 2010-10-14 122: # m---m
bfe3da6658 2010-10-14 123: # o.o-o
bfe3da6658 2010-10-14 124: else:
bfe3da6658 2010-10-14 125: # when my pair ends before other pair ends
bfe3da6658 2010-10-14 126: # m---m
bfe3da6658 2010-10-14 127: # o-----o
bfe3da6658 2010-10-14 128: new[my_pair[0]] = my_pair[1]
bfe3da6658 2010-10-14 129: # my pair is covered and should be added to result
bfe3da6658 2010-10-14 130: my_pair = self.pop()
bfe3da6658 2010-10-14 131: # tossing out my pair
bfe3da6658 2010-10-14 132: if my_pair[0] == None:
bfe3da6658 2010-10-14 133: all_parts_found = True
bfe3da6658 2010-10-14 134: elif my_pair[0] < other_pair[0]:
bfe3da6658 2010-10-14 135: # when my pair starts before other one
bfe3da6658 2010-10-14 136: # m---
bfe3da6658 2010-10-14 137: # o---
bfe3da6658 2010-10-14 138: if my_pair[1] < other_pair[0]:
bfe3da6658 2010-10-14 139: # when my pair ends before other pair starts
bfe3da6658 2010-10-14 140: # m---m
bfe3da6658 2010-10-14 141: # o---
bfe3da6658 2010-10-14 142: my_pair = self.pop()
bfe3da6658 2010-10-14 143: # tossing out my pair
bfe3da6658 2010-10-14 144: if my_pair[0] == None:
bfe3da6658 2010-10-14 145: all_parts_found = True
bfe3da6658 2010-10-14 146: else:
bfe3da6658 2010-10-14 147: # when my pair ends before other pair starts
bfe3da6658 2010-10-14 148: # m---m
bfe3da6658 2010-10-14 149: # o---
bfe3da6658 2010-10-14 150: my_pair[0] = other_pair[0]
bfe3da6658 2010-10-14 151: # trimming my pair by other pair start
bfe3da6658 2010-10-14 152: # m.m-m
bfe3da6658 2010-10-14 153: # o---
bfe3da6658 2010-10-14 154: else:
bfe3da6658 2010-10-14 155: # when both pairs starts simultaneously
bfe3da6658 2010-10-14 156: # m---
bfe3da6658 2010-10-14 157: # o---
bfe3da6658 2010-10-14 158: if my_pair[1] < other_pair[1]:
bfe3da6658 2010-10-14 159: # when my pair ends before other pair
bfe3da6658 2010-10-14 160: # m---m
bfe3da6658 2010-10-14 161: # o-----o
bfe3da6658 2010-10-14 162: new[my_pair[0]] = my_pair[1]
bfe3da6658 2010-10-14 163: # my pair is covered and should be added to result
bfe3da6658 2010-10-14 164: my_pair = self.pop()
bfe3da6658 2010-10-14 165: # tossing out my pair
bfe3da6658 2010-10-14 166: if my_pair[0] == None:
bfe3da6658 2010-10-14 167: all_parts_found = True
bfe3da6658 2010-10-14 168: else:
bfe3da6658 2010-10-14 169: # when my pair ends after other pair
bfe3da6658 2010-10-14 170: # m-----m
bfe3da6658 2010-10-14 171: # o---o
bfe3da6658 2010-10-14 172: new[my_pair[0]] = other_pair[1]
bfe3da6658 2010-10-14 173: # part of my pair is covered and should be added to result
bfe3da6658 2010-10-14 174: other_pair = other.pop()
bfe3da6658 2010-10-14 175: # tossing out other pair
bfe3da6658 2010-10-14 176: if other_pair[0] == None:
bfe3da6658 2010-10-14 177: all_parts_found = True
bfe3da6658 2010-10-14 178: self.clear()
bfe3da6658 2010-10-14 179: other.clear()
bfe3da6658 2010-10-14 180: return(SpaceMap(new, self.__bottom, self.__top))
bfe3da6658 2010-10-14 181:
bfe3da6658 2010-10-14 182: def __sub__(self, other):
bfe3da6658 2010-10-14 183: '''Returns new space map with ranges in A not covered by B.'''
886158fbf4 2011-12-19 184: if type(other) != SpaceMap:
bfe3da6658 2010-10-14 185: return(False)
bfe3da6658 2010-10-14 186: new = {}
bfe3da6658 2010-10-14 187: self.rewind()
bfe3da6658 2010-10-14 188: other.rewind()
bfe3da6658 2010-10-14 189: my_pair = self.pop()
bfe3da6658 2010-10-14 190: other_pair = other.pop()
bfe3da6658 2010-10-14 191: # if there are no pairs in B - copy this one to new SpaceMap
bfe3da6658 2010-10-14 192: if other_pair[0] == None:
bfe3da6658 2010-10-14 193: new[my_pair[0]] = my_pair[1]
bfe3da6658 2010-10-14 194: all_parts_found = True
bfe3da6658 2010-10-14 195: elif my_pair[0] == None:
bfe3da6658 2010-10-14 196: all_parts_found = True
bfe3da6658 2010-10-14 197: else:
bfe3da6658 2010-10-14 198: all_parts_found = False
bfe3da6658 2010-10-14 199: while not all_parts_found:
bfe3da6658 2010-10-14 200: if my_pair[0] > other_pair[0]:
bfe3da6658 2010-10-14 201: # when my pair starts after other pair starts
bfe3da6658 2010-10-14 202: # m---
bfe3da6658 2010-10-14 203: # o---
bfe3da6658 2010-10-14 204: if my_pair[0] > other_pair[1]:
bfe3da6658 2010-10-14 205: # when my pair starts after other pair ends
bfe3da6658 2010-10-14 206: # m---
bfe3da6658 2010-10-14 207: # o---o
bfe3da6658 2010-10-14 208: other_pair = other.pop()
bfe3da6658 2010-10-14 209: # tossing out other pair
bfe3da6658 2010-10-14 210: if other_pair[0] == None:
bfe3da6658 2010-10-14 211: # this was last one - my pair goes to result
bfe3da6658 2010-10-14 212: new[my_pair[0]] = my_pair[1]
bfe3da6658 2010-10-14 213: all_parts_found = True
bfe3da6658 2010-10-14 214: else:
bfe3da6658 2010-10-14 215: # when my pair starts before other pair ends
bfe3da6658 2010-10-14 216: # m--- | m---
bfe3da6658 2010-10-14 217: # o---o | o---o
bfe3da6658 2010-10-14 218: if my_pair[1] > other_pair[1]:
bfe3da6658 2010-10-14 219: # when my pair ends after other pair ends
bfe3da6658 2010-10-14 220: # m---m | m---m
bfe3da6658 2010-10-14 221: # o---o | o---o
bfe3da6658 2010-10-14 222: my_pair[0] = other_pair[1]
bfe3da6658 2010-10-14 223: # trimming my pair by other pair end
bfe3da6658 2010-10-14 224: # m.m-m
bfe3da6658 2010-10-14 225: # o---o
bfe3da6658 2010-10-14 226: other_pair = other.pop()
bfe3da6658 2010-10-14 227: # tossing out other pair
bfe3da6658 2010-10-14 228: if other_pair[0] == None:
bfe3da6658 2010-10-14 229: # this was last one - my pair goes to result
bfe3da6658 2010-10-14 230: new[my_pair[0]] = my_pair[1]
bfe3da6658 2010-10-14 231: all_parts_found = True
bfe3da6658 2010-10-14 232: else:
bfe3da6658 2010-10-14 233: # when my pair ends before other pair ends
bfe3da6658 2010-10-14 234: # m---m
bfe3da6658 2010-10-14 235: # o-----o
bfe3da6658 2010-10-14 236: my_pair = self.pop()
bfe3da6658 2010-10-14 237: # tossing out my pair
bfe3da6658 2010-10-14 238: if my_pair[0] == None:
bfe3da6658 2010-10-14 239: all_parts_found = True
bfe3da6658 2010-10-14 240: elif my_pair[0] < other_pair[0]:
bfe3da6658 2010-10-14 241: # when my pair starts before other one
bfe3da6658 2010-10-14 242: # m---
bfe3da6658 2010-10-14 243: # o---
bfe3da6658 2010-10-14 244: if my_pair[1] < other_pair[0]:
bfe3da6658 2010-10-14 245: # when my pair ends before other pair starts
bfe3da6658 2010-10-14 246: # m---m
bfe3da6658 2010-10-14 247: # o---
bfe3da6658 2010-10-14 248: new[my_pair[0]] = my_pair[1]
bfe3da6658 2010-10-14 249: # my pair is not covered and should be added to result
bfe3da6658 2010-10-14 250: my_pair = self.pop()
bfe3da6658 2010-10-14 251: # tossing out my pair
bfe3da6658 2010-10-14 252: if my_pair[0] == None:
bfe3da6658 2010-10-14 253: all_parts_found = True
bfe3da6658 2010-10-14 254: else:
bfe3da6658 2010-10-14 255: # when my pair ends before other pair starts
bfe3da6658 2010-10-14 256: # m---m
bfe3da6658 2010-10-14 257: # o---
bfe3da6658 2010-10-14 258: new[my_pair[0]] = other_pair[0]
bfe3da6658 2010-10-14 259: # start of my pair is not covered and should be added to result
bfe3da6658 2010-10-14 260: my_pair[0] = other_pair[0]
bfe3da6658 2010-10-14 261: # trimming my pair by other pair start
bfe3da6658 2010-10-14 262: # m.m-m
bfe3da6658 2010-10-14 263: # o---
bfe3da6658 2010-10-14 264: else:
bfe3da6658 2010-10-14 265: # when both pairs starts simultaneously
bfe3da6658 2010-10-14 266: # m---
bfe3da6658 2010-10-14 267: # o---
bfe3da6658 2010-10-14 268: if my_pair[1] < other_pair[1]:
bfe3da6658 2010-10-14 269: # when my pair ends before other pair
bfe3da6658 2010-10-14 270: # m---m
bfe3da6658 2010-10-14 271: # o-----o
bfe3da6658 2010-10-14 272: my_pair = self.pop()
bfe3da6658 2010-10-14 273: # tossing out my pair
bfe3da6658 2010-10-14 274: if my_pair[0] == None:
bfe3da6658 2010-10-14 275: all_parts_found = True
bfe3da6658 2010-10-14 276: else:
bfe3da6658 2010-10-14 277: # when my pair ends after other pair
bfe3da6658 2010-10-14 278: # m-----m
bfe3da6658 2010-10-14 279: # o---o
bfe3da6658 2010-10-14 280: my_pair[0] = other_pair[1]
bfe3da6658 2010-10-14 281: # trimming my pair by other pair end
bfe3da6658 2010-10-14 282: # m...m-m
bfe3da6658 2010-10-14 283: # o---o
bfe3da6658 2010-10-14 284: other_pair = other.pop()
bfe3da6658 2010-10-14 285: # tossing out other pair
bfe3da6658 2010-10-14 286: if other_pair[0] == None:
bfe3da6658 2010-10-14 287: # this was last one - my pair goes to result
bfe3da6658 2010-10-14 288: new[my_pair[0]] = my_pair[1]
bfe3da6658 2010-10-14 289: all_parts_found = True
bfe3da6658 2010-10-14 290: while True:
bfe3da6658 2010-10-14 291: # copy any leftover in A to new SpaceMap
bfe3da6658 2010-10-14 292: my_pair = self.pop()
bfe3da6658 2010-10-14 293: if my_pair[0] == None:
bfe3da6658 2010-10-14 294: break
bfe3da6658 2010-10-14 295: else:
bfe3da6658 2010-10-14 296: new[my_pair[0]] = my_pair[1]
bfe3da6658 2010-10-14 297: self.clear()
bfe3da6658 2010-10-14 298: other.clear()
bfe3da6658 2010-10-14 299: return(SpaceMap(new, self.__bottom, self.__top))
bfe3da6658 2010-10-14 300:
bfe3da6658 2010-10-14 301: def __eq__(self, other):
bfe3da6658 2010-10-14 302: '''Compares two space maps.'''
bfe3da6658 2010-10-14 303: if type(other) != SpaceMap:
bfe3da6658 2010-10-14 304: return(False)
bfe3da6658 2010-10-14 305: self.rewind()
bfe3da6658 2010-10-14 306: other.rewind()
bfe3da6658 2010-10-14 307: result = None
bfe3da6658 2010-10-14 308: while True:
bfe3da6658 2010-10-14 309: this = self.pop()
bfe3da6658 2010-10-14 310: that = other.pop()
bfe3da6658 2010-10-14 311: if this != that:
bfe3da6658 2010-10-14 312: result = False
bfe3da6658 2010-10-14 313: break
bfe3da6658 2010-10-14 314: if this == [None, None] and that == [None, None]:
bfe3da6658 2010-10-14 315: result = True
bfe3da6658 2010-10-14 316: break
bfe3da6658 2010-10-14 317: self.clear()
bfe3da6658 2010-10-14 318: other.clear()
bfe3da6658 2010-10-14 319: return(result)
bfe3da6658 2010-10-14 320:
bfe3da6658 2010-10-14 321: def end(self):
bfe3da6658 2010-10-14 322: '''Returns last known point.'''
bfe3da6658 2010-10-14 323: end = None
bfe3da6658 2010-10-14 324: self.rewind()
bfe3da6658 2010-10-14 325: while True:
bfe3da6658 2010-10-14 326: this = self.pop()
bfe3da6658 2010-10-14 327: if this == [None, None]:
bfe3da6658 2010-10-14 328: break
bfe3da6658 2010-10-14 329: elif end == None or this[1] > end:
bfe3da6658 2010-10-14 330: end = this[1]
bfe3da6658 2010-10-14 331: self.clear()
bfe3da6658 2010-10-14 332: return(end)
bfe3da6658 2010-10-14 333:
bfe3da6658 2010-10-14 334: def __len__(self):
bfe3da6658 2010-10-14 335: return(len(self.__pairs))