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