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:
9f4d7d46dd 2014-01-13 57: if last_pair in self.__pairs and pair[0] <= self.__pairs[last_pair]:
9f4d7d46dd 2014-01-13 58: if pair[1] > self.__pairs[last_pair]:
9f4d7d46dd 2014-01-13 59: self.__pairs[last_pair] = pair[1]
9f4d7d46dd 2014-01-13 60: del(self.__pairs[pair[0]])
bfe3da6658 2010-10-14 61: else:
bfe3da6658 2010-10-14 62: last_pair = pair[0]
bfe3da6658 2010-10-14 63: self.clear()
bfe3da6658 2010-10-14 64:
bfe3da6658 2010-10-14 65: def rewind(self):
bfe3da6658 2010-10-14 66: '''Reinitialises internal ordered list of ranges.'''
bfe3da6658 2010-10-14 67: self.__walk_list = list(self.__pairs.keys())
bfe3da6658 2010-10-14 68: self.__walk_list.sort()
bfe3da6658 2010-10-14 69:
bfe3da6658 2010-10-14 70: def clear(self):
bfe3da6658 2010-10-14 71: '''Clears internal ordered list of ranges.'''
bfe3da6658 2010-10-14 72: self.__walk_list = None
bfe3da6658 2010-10-14 73:
bfe3da6658 2010-10-14 74: def pop(self):
bfe3da6658 2010-10-14 75: '''Returns next range from ordered list of ranges.'''
bfe3da6658 2010-10-14 76: if self.__walk_list != None:
bfe3da6658 2010-10-14 77: if len(self.__walk_list) > 0:
bfe3da6658 2010-10-14 78: next = self.__walk_list.pop(0)
bfe3da6658 2010-10-14 79: return([next, self.__pairs[next]])
bfe3da6658 2010-10-14 80: return([None, None])
bfe3da6658 2010-10-14 81:
bfe3da6658 2010-10-14 82: def __repr__(self):
bfe3da6658 2010-10-14 83: '''Returns the inner dict with ranges.'''
bfe3da6658 2010-10-14 84: return(repr(self.__pairs))
bfe3da6658 2010-10-14 85:
bfe3da6658 2010-10-14 86: def __and__(self, other):
bfe3da6658 2010-10-14 87: '''Returns new space map with ranges that appears both in A and B.'''
886158fbf4 2011-12-19 88: if type(other) != SpaceMap:
bfe3da6658 2010-10-14 89: return(False)
bfe3da6658 2010-10-14 90: new = {}
bfe3da6658 2010-10-14 91: self.rewind()
bfe3da6658 2010-10-14 92: other.rewind()
bfe3da6658 2010-10-14 93: my_pair = self.pop()
bfe3da6658 2010-10-14 94: other_pair = other.pop()
bfe3da6658 2010-10-14 95: # if there are no pairs in B - we have nothing to do
bfe3da6658 2010-10-14 96: if other_pair[0] == None or my_pair[0] == None:
bfe3da6658 2010-10-14 97: all_parts_found = True
bfe3da6658 2010-10-14 98: else:
bfe3da6658 2010-10-14 99: all_parts_found = False
bfe3da6658 2010-10-14 100: while not all_parts_found:
bfe3da6658 2010-10-14 101: if my_pair[0] > other_pair[0]:
bfe3da6658 2010-10-14 102: # when my pair starts after other pair starts
bfe3da6658 2010-10-14 103: # m---
bfe3da6658 2010-10-14 104: # o---
bfe3da6658 2010-10-14 105: if my_pair[0] > other_pair[1]:
bfe3da6658 2010-10-14 106: # when my pair starts after other pair ends
bfe3da6658 2010-10-14 107: # m---
bfe3da6658 2010-10-14 108: # o---o
bfe3da6658 2010-10-14 109: other_pair = other.pop()
bfe3da6658 2010-10-14 110: # tossing out other pair
bfe3da6658 2010-10-14 111: if other_pair[0] == None:
bfe3da6658 2010-10-14 112: all_parts_found = True
bfe3da6658 2010-10-14 113: else:
bfe3da6658 2010-10-14 114: # when my pair starts before other pair ends
bfe3da6658 2010-10-14 115: # m--- | m---
bfe3da6658 2010-10-14 116: # o---o | o---o
bfe3da6658 2010-10-14 117: if my_pair[1] > other_pair[1]:
bfe3da6658 2010-10-14 118: # when my pair ends after other pair ends
bfe3da6658 2010-10-14 119: # m---m | m---m
bfe3da6658 2010-10-14 120: # o---o | o---o
bfe3da6658 2010-10-14 121: other_pair[0] = my_pair[0]
bfe3da6658 2010-10-14 122: # trimming other pair by my pair start
bfe3da6658 2010-10-14 123: # m---m
bfe3da6658 2010-10-14 124: # o.o-o
bfe3da6658 2010-10-14 125: else:
bfe3da6658 2010-10-14 126: # when my pair ends before other pair ends
bfe3da6658 2010-10-14 127: # m---m
bfe3da6658 2010-10-14 128: # o-----o
bfe3da6658 2010-10-14 129: new[my_pair[0]] = my_pair[1]
bfe3da6658 2010-10-14 130: # my pair is covered and should be added to result
bfe3da6658 2010-10-14 131: my_pair = self.pop()
bfe3da6658 2010-10-14 132: # tossing out my pair
bfe3da6658 2010-10-14 133: if my_pair[0] == None:
bfe3da6658 2010-10-14 134: all_parts_found = True
bfe3da6658 2010-10-14 135: elif my_pair[0] < other_pair[0]:
bfe3da6658 2010-10-14 136: # when my pair starts before other one
bfe3da6658 2010-10-14 137: # m---
bfe3da6658 2010-10-14 138: # o---
bfe3da6658 2010-10-14 139: if my_pair[1] < other_pair[0]:
bfe3da6658 2010-10-14 140: # when my pair ends before other pair starts
bfe3da6658 2010-10-14 141: # m---m
bfe3da6658 2010-10-14 142: # o---
bfe3da6658 2010-10-14 143: my_pair = self.pop()
bfe3da6658 2010-10-14 144: # tossing out my pair
bfe3da6658 2010-10-14 145: if my_pair[0] == None:
bfe3da6658 2010-10-14 146: all_parts_found = True
bfe3da6658 2010-10-14 147: else:
bfe3da6658 2010-10-14 148: # when my pair ends before other pair starts
bfe3da6658 2010-10-14 149: # m---m
bfe3da6658 2010-10-14 150: # o---
bfe3da6658 2010-10-14 151: my_pair[0] = other_pair[0]
bfe3da6658 2010-10-14 152: # trimming my pair by other pair start
bfe3da6658 2010-10-14 153: # m.m-m
bfe3da6658 2010-10-14 154: # o---
bfe3da6658 2010-10-14 155: else:
bfe3da6658 2010-10-14 156: # when both pairs starts simultaneously
bfe3da6658 2010-10-14 157: # m---
bfe3da6658 2010-10-14 158: # o---
bfe3da6658 2010-10-14 159: if my_pair[1] < other_pair[1]:
bfe3da6658 2010-10-14 160: # when my pair ends before other pair
bfe3da6658 2010-10-14 161: # m---m
bfe3da6658 2010-10-14 162: # o-----o
bfe3da6658 2010-10-14 163: new[my_pair[0]] = my_pair[1]
bfe3da6658 2010-10-14 164: # my pair is covered and should be added to result
bfe3da6658 2010-10-14 165: my_pair = self.pop()
bfe3da6658 2010-10-14 166: # tossing out my pair
bfe3da6658 2010-10-14 167: if my_pair[0] == None:
bfe3da6658 2010-10-14 168: all_parts_found = True
bfe3da6658 2010-10-14 169: else:
bfe3da6658 2010-10-14 170: # when my pair ends after other pair
bfe3da6658 2010-10-14 171: # m-----m
bfe3da6658 2010-10-14 172: # o---o
bfe3da6658 2010-10-14 173: new[my_pair[0]] = other_pair[1]
bfe3da6658 2010-10-14 174: # part of my pair is covered and should be added to result
bfe3da6658 2010-10-14 175: other_pair = other.pop()
bfe3da6658 2010-10-14 176: # tossing out other pair
bfe3da6658 2010-10-14 177: if other_pair[0] == None:
bfe3da6658 2010-10-14 178: all_parts_found = True
bfe3da6658 2010-10-14 179: self.clear()
bfe3da6658 2010-10-14 180: other.clear()
bfe3da6658 2010-10-14 181: return(SpaceMap(new, self.__bottom, self.__top))
bfe3da6658 2010-10-14 182:
bfe3da6658 2010-10-14 183: def __sub__(self, other):
bfe3da6658 2010-10-14 184: '''Returns new space map with ranges in A not covered by B.'''
886158fbf4 2011-12-19 185: if type(other) != SpaceMap:
bfe3da6658 2010-10-14 186: return(False)
bfe3da6658 2010-10-14 187: new = {}
bfe3da6658 2010-10-14 188: self.rewind()
bfe3da6658 2010-10-14 189: other.rewind()
bfe3da6658 2010-10-14 190: my_pair = self.pop()
bfe3da6658 2010-10-14 191: other_pair = other.pop()
bfe3da6658 2010-10-14 192: # if there are no pairs in B - copy this one to new SpaceMap
bfe3da6658 2010-10-14 193: if other_pair[0] == None:
bfe3da6658 2010-10-14 194: new[my_pair[0]] = my_pair[1]
bfe3da6658 2010-10-14 195: all_parts_found = True
bfe3da6658 2010-10-14 196: elif my_pair[0] == None:
bfe3da6658 2010-10-14 197: all_parts_found = True
bfe3da6658 2010-10-14 198: else:
bfe3da6658 2010-10-14 199: all_parts_found = False
bfe3da6658 2010-10-14 200: while not all_parts_found:
bfe3da6658 2010-10-14 201: if my_pair[0] > other_pair[0]:
bfe3da6658 2010-10-14 202: # when my pair starts after other pair starts
bfe3da6658 2010-10-14 203: # m---
bfe3da6658 2010-10-14 204: # o---
bfe3da6658 2010-10-14 205: if my_pair[0] > other_pair[1]:
bfe3da6658 2010-10-14 206: # when my pair starts after other pair ends
bfe3da6658 2010-10-14 207: # m---
bfe3da6658 2010-10-14 208: # o---o
bfe3da6658 2010-10-14 209: other_pair = other.pop()
bfe3da6658 2010-10-14 210: # tossing out other pair
bfe3da6658 2010-10-14 211: if other_pair[0] == None:
bfe3da6658 2010-10-14 212: # this was last one - my pair goes to result
bfe3da6658 2010-10-14 213: new[my_pair[0]] = my_pair[1]
bfe3da6658 2010-10-14 214: all_parts_found = True
bfe3da6658 2010-10-14 215: else:
bfe3da6658 2010-10-14 216: # when my pair starts before other pair ends
bfe3da6658 2010-10-14 217: # m--- | m---
bfe3da6658 2010-10-14 218: # o---o | o---o
bfe3da6658 2010-10-14 219: if my_pair[1] > other_pair[1]:
bfe3da6658 2010-10-14 220: # when my pair ends after other pair ends
bfe3da6658 2010-10-14 221: # m---m | m---m
bfe3da6658 2010-10-14 222: # o---o | o---o
bfe3da6658 2010-10-14 223: my_pair[0] = other_pair[1]
bfe3da6658 2010-10-14 224: # trimming my pair by other pair end
bfe3da6658 2010-10-14 225: # m.m-m
bfe3da6658 2010-10-14 226: # o---o
bfe3da6658 2010-10-14 227: other_pair = other.pop()
bfe3da6658 2010-10-14 228: # tossing out other pair
bfe3da6658 2010-10-14 229: if other_pair[0] == None:
bfe3da6658 2010-10-14 230: # this was last one - my pair goes to result
bfe3da6658 2010-10-14 231: new[my_pair[0]] = my_pair[1]
bfe3da6658 2010-10-14 232: all_parts_found = True
bfe3da6658 2010-10-14 233: else:
bfe3da6658 2010-10-14 234: # when my pair ends before other pair ends
bfe3da6658 2010-10-14 235: # m---m
bfe3da6658 2010-10-14 236: # o-----o
bfe3da6658 2010-10-14 237: my_pair = self.pop()
bfe3da6658 2010-10-14 238: # tossing out my pair
bfe3da6658 2010-10-14 239: if my_pair[0] == None:
bfe3da6658 2010-10-14 240: all_parts_found = True
bfe3da6658 2010-10-14 241: elif my_pair[0] < other_pair[0]:
bfe3da6658 2010-10-14 242: # when my pair starts before other one
bfe3da6658 2010-10-14 243: # m---
bfe3da6658 2010-10-14 244: # o---
bfe3da6658 2010-10-14 245: if my_pair[1] < other_pair[0]:
bfe3da6658 2010-10-14 246: # when my pair ends before other pair starts
bfe3da6658 2010-10-14 247: # m---m
bfe3da6658 2010-10-14 248: # o---
bfe3da6658 2010-10-14 249: new[my_pair[0]] = my_pair[1]
bfe3da6658 2010-10-14 250: # my pair is not covered and should be added to result
bfe3da6658 2010-10-14 251: my_pair = self.pop()
bfe3da6658 2010-10-14 252: # tossing out my pair
bfe3da6658 2010-10-14 253: if my_pair[0] == None:
bfe3da6658 2010-10-14 254: all_parts_found = True
bfe3da6658 2010-10-14 255: else:
bfe3da6658 2010-10-14 256: # when my pair ends before other pair starts
bfe3da6658 2010-10-14 257: # m---m
bfe3da6658 2010-10-14 258: # o---
bfe3da6658 2010-10-14 259: new[my_pair[0]] = other_pair[0]
bfe3da6658 2010-10-14 260: # start of my pair is not covered and should be added to result
bfe3da6658 2010-10-14 261: my_pair[0] = other_pair[0]
bfe3da6658 2010-10-14 262: # trimming my pair by other pair start
bfe3da6658 2010-10-14 263: # m.m-m
bfe3da6658 2010-10-14 264: # o---
bfe3da6658 2010-10-14 265: else:
bfe3da6658 2010-10-14 266: # when both pairs starts simultaneously
bfe3da6658 2010-10-14 267: # m---
bfe3da6658 2010-10-14 268: # o---
bfe3da6658 2010-10-14 269: if my_pair[1] < other_pair[1]:
bfe3da6658 2010-10-14 270: # when my pair ends before other pair
bfe3da6658 2010-10-14 271: # m---m
bfe3da6658 2010-10-14 272: # o-----o
bfe3da6658 2010-10-14 273: my_pair = self.pop()
bfe3da6658 2010-10-14 274: # tossing out my pair
bfe3da6658 2010-10-14 275: if my_pair[0] == None:
bfe3da6658 2010-10-14 276: all_parts_found = True
bfe3da6658 2010-10-14 277: else:
bfe3da6658 2010-10-14 278: # when my pair ends after other pair
bfe3da6658 2010-10-14 279: # m-----m
bfe3da6658 2010-10-14 280: # o---o
bfe3da6658 2010-10-14 281: my_pair[0] = other_pair[1]
bfe3da6658 2010-10-14 282: # trimming my pair by other pair end
bfe3da6658 2010-10-14 283: # m...m-m
bfe3da6658 2010-10-14 284: # o---o
bfe3da6658 2010-10-14 285: other_pair = other.pop()
bfe3da6658 2010-10-14 286: # tossing out other pair
bfe3da6658 2010-10-14 287: if other_pair[0] == None:
bfe3da6658 2010-10-14 288: # this was last one - my pair goes to result
bfe3da6658 2010-10-14 289: new[my_pair[0]] = my_pair[1]
bfe3da6658 2010-10-14 290: all_parts_found = True
bfe3da6658 2010-10-14 291: while True:
bfe3da6658 2010-10-14 292: # copy any leftover in A to new SpaceMap
bfe3da6658 2010-10-14 293: my_pair = self.pop()
bfe3da6658 2010-10-14 294: if my_pair[0] == None:
bfe3da6658 2010-10-14 295: break
bfe3da6658 2010-10-14 296: else:
bfe3da6658 2010-10-14 297: new[my_pair[0]] = my_pair[1]
bfe3da6658 2010-10-14 298: self.clear()
bfe3da6658 2010-10-14 299: other.clear()
bfe3da6658 2010-10-14 300: return(SpaceMap(new, self.__bottom, self.__top))
bfe3da6658 2010-10-14 301:
bfe3da6658 2010-10-14 302: def __eq__(self, other):
bfe3da6658 2010-10-14 303: '''Compares two space maps.'''
bfe3da6658 2010-10-14 304: if type(other) != SpaceMap:
bfe3da6658 2010-10-14 305: return(False)
bfe3da6658 2010-10-14 306: self.rewind()
bfe3da6658 2010-10-14 307: other.rewind()
bfe3da6658 2010-10-14 308: result = None
bfe3da6658 2010-10-14 309: while True:
bfe3da6658 2010-10-14 310: this = self.pop()
bfe3da6658 2010-10-14 311: that = other.pop()
bfe3da6658 2010-10-14 312: if this != that:
bfe3da6658 2010-10-14 313: result = False
bfe3da6658 2010-10-14 314: break
bfe3da6658 2010-10-14 315: if this == [None, None] and that == [None, None]:
bfe3da6658 2010-10-14 316: result = True
bfe3da6658 2010-10-14 317: break
bfe3da6658 2010-10-14 318: self.clear()
bfe3da6658 2010-10-14 319: other.clear()
bfe3da6658 2010-10-14 320: return(result)
bfe3da6658 2010-10-14 321:
213edd15a6 2011-12-21 322: def __ne__(self, other):
213edd15a6 2011-12-21 323: return(not self == other)
213edd15a6 2011-12-21 324:
bfe3da6658 2010-10-14 325: def end(self):
bfe3da6658 2010-10-14 326: '''Returns last known point.'''
bfe3da6658 2010-10-14 327: end = None
bfe3da6658 2010-10-14 328: self.rewind()
bfe3da6658 2010-10-14 329: while True:
bfe3da6658 2010-10-14 330: this = self.pop()
bfe3da6658 2010-10-14 331: if this == [None, None]:
bfe3da6658 2010-10-14 332: break
bfe3da6658 2010-10-14 333: elif end == None or this[1] > end:
bfe3da6658 2010-10-14 334: end = this[1]
bfe3da6658 2010-10-14 335: self.clear()
bfe3da6658 2010-10-14 336: return(end)
bfe3da6658 2010-10-14 337:
bfe3da6658 2010-10-14 338: def __len__(self):
bfe3da6658 2010-10-14 339: return(len(self.__pairs))
9f4d7d46dd 2014-01-13 340:
9f4d7d46dd 2014-01-13 341: def max(self):
9f4d7d46dd 2014-01-13 342: result = None
9f4d7d46dd 2014-01-13 343: for last in self.__pairs.itervalues():
9f4d7d46dd 2014-01-13 344: if result == None or result < last:
9f4d7d46dd 2014-01-13 345: result = last
9f4d7d46dd 2014-01-13 346: return(result)