Artifact
91cf92dc95a2b5dbe01e1f75c59beeca1c77c0bfc0c3ac94dfb861ddc2cd2a4c:
0000: 63 6c 61 73 73 20 53 70 61 63 65 4d 61 70 28 6f class SpaceMap(o
0010: 62 6a 65 63 74 29 3a 0a 09 27 27 27 20 48 65 72 bject):..''' Her
0020: 65 20 77 65 20 68 61 76 65 3a 0a 09 5f 5f 62 6f e we have:..__bo
0030: 74 74 6f 6d 20 2d 20 6d 69 6e 69 6d 75 6d 20 73 ttom - minimum s
0040: 70 61 63 65 20 61 64 64 72 65 73 73 20 70 6f 73 pace address pos
0050: 73 69 62 6c 65 3b 0a 09 5f 5f 74 6f 70 20 2d 20 sible;..__top -
0060: 6d 61 78 69 6d 75 6d 20 73 70 61 63 65 20 61 64 maximum space ad
0070: 64 72 65 73 73 20 70 6f 73 73 69 62 6c 65 3b 0a dress possible;.
0080: 09 5f 5f 70 61 69 72 73 20 2d 20 69 6e 74 65 72 .__pairs - inter
0090: 6e 61 6c 20 6c 69 73 74 20 6f 66 20 72 61 6e 67 nal list of rang
00a0: 65 73 3b 0a 09 5f 5f 77 61 6c 6b 5f 6c 69 73 74 es;..__walk_list
00b0: 20 2d 20 69 6e 74 65 72 6e 61 6c 20 6c 69 73 74 - internal list
00c0: 20 6f 66 20 6b 65 79 73 2e 27 27 27 0a 0a 09 5f of keys.'''..._
00d0: 5f 73 6c 6f 74 73 5f 5f 20 3d 20 66 72 6f 7a 65 _slots__ = froze
00e0: 6e 73 65 74 28 28 27 5f 5f 62 6f 74 74 6f 6d 27 nset(('__bottom'
00f0: 2c 20 27 5f 5f 70 61 69 72 73 27 2c 20 27 5f 5f , '__pairs', '__
0100: 74 6f 70 27 2c 20 27 5f 5f 77 61 6c 6b 5f 6c 69 top', '__walk_li
0110: 73 74 27 29 29 0a 0a 09 64 65 66 20 5f 5f 69 6e st'))...def __in
0120: 69 74 5f 5f 28 73 65 6c 66 2c 20 73 6f 75 72 63 it__(self, sourc
0130: 65 20 3d 20 4e 6f 6e 65 2c 20 62 6f 74 74 6f 6d e = None, bottom
0140: 20 3d 20 30 2c 20 74 6f 70 20 3d 20 4e 6f 6e 65 = 0, top = None
0150: 29 3a 0a 09 09 27 27 27 20 54 68 69 73 20 6f 6e ):...''' This on
0160: 65 20 63 61 6e 20 62 65 20 62 6f 6f 74 73 74 72 e can be bootstr
0170: 61 70 70 65 64 20 62 79 20 67 69 76 69 6e 67 20 apped by giving
0180: 61 20 64 69 63 74 20 69 6e 20 66 6f 72 6d 61 74 a dict in format
0190: 20 7b 78 3a 79 2c 20 78 3a 79 7d 2e 27 27 27 0a {x:y, x:y}.'''.
01a0: 09 09 73 65 6c 66 2e 5f 5f 70 61 69 72 73 20 3d ..self.__pairs =
01b0: 20 7b 7d 0a 09 09 73 65 6c 66 2e 5f 5f 77 61 6c {}...self.__wal
01c0: 6b 5f 6c 69 73 74 20 3d 20 4e 6f 6e 65 0a 09 09 k_list = None...
01d0: 73 65 6c 66 2e 5f 5f 62 6f 74 74 6f 6d 20 3d 20 self.__bottom =
01e0: 62 6f 74 74 6f 6d 0a 09 09 73 65 6c 66 2e 5f 5f bottom...self.__
01f0: 74 6f 70 20 3d 20 74 6f 70 0a 09 09 69 66 20 74 top = top...if t
0200: 79 70 65 28 73 6f 75 72 63 65 29 20 3d 3d 20 64 ype(source) == d
0210: 69 63 74 3a 0a 09 09 09 66 6f 72 20 6b 65 79 20 ict:....for key
0220: 69 6e 20 73 6f 75 72 63 65 3a 0a 09 09 09 09 73 in source:.....s
0230: 65 6c 66 2e 5f 5f 73 65 74 28 6b 65 79 2c 20 73 elf.__set(key, s
0240: 6f 75 72 63 65 5b 6b 65 79 5d 29 0a 09 09 09 73 ource[key])....s
0250: 65 6c 66 2e 66 6f 6c 64 28 29 0a 0a 09 64 65 66 elf.fold()...def
0260: 20 5f 5f 67 65 74 69 74 65 6d 5f 5f 28 73 65 6c __getitem__(sel
0270: 66 2c 20 6e 61 6d 65 29 3a 0a 09 09 27 27 27 52 f, name):...'''R
0280: 65 74 75 72 6e 73 20 6c 61 73 74 20 72 61 6e 67 eturns last rang
0290: 65 20 61 64 64 72 65 73 73 20 62 79 20 66 69 72 e address by fir
02a0: 73 74 20 72 61 6e 67 65 20 61 64 64 72 65 73 73 st range address
02b0: 2e 27 27 27 0a 09 09 69 66 20 6e 61 6d 65 20 69 .'''...if name i
02c0: 6e 20 73 65 6c 66 2e 5f 5f 70 61 69 72 73 3a 0a n self.__pairs:.
02d0: 09 09 09 72 65 74 75 72 6e 28 73 65 6c 66 2e 5f ...return(self._
02e0: 5f 70 61 69 72 73 5b 6e 61 6d 65 5d 29 0a 09 09 _pairs[name])...
02f0: 65 6c 73 65 3a 0a 09 09 09 72 65 74 75 72 6e 28 else:....return(
0300: 4e 6f 6e 65 29 0a 0a 09 64 65 66 20 5f 5f 73 65 None)...def __se
0310: 74 28 73 65 6c 66 2c 20 6e 61 6d 65 2c 20 76 61 t(self, name, va
0320: 6c 75 65 29 3a 0a 09 09 27 27 27 49 6e 74 65 72 lue):...'''Inter
0330: 6e 61 6c 20 66 75 6e 63 74 69 6f 6e 20 74 6f 20 nal function to
0340: 61 64 64 20 72 61 6e 67 65 73 20 77 69 74 68 6f add ranges witho
0350: 75 74 20 66 6f 6c 64 69 6e 67 2e 20 41 6c 73 6f ut folding. Also
0360: 20 63 68 65 63 6b 73 20 66 6f 72 20 72 61 6e 67 checks for rang
0370: 65 20 63 6f 72 72 65 63 74 6e 65 73 73 2e 27 27 e correctness.''
0380: 27 0a 09 09 69 66 20 74 79 70 65 28 6e 61 6d 65 '...if type(name
0390: 29 20 21 3d 20 69 6e 74 20 6f 72 20 74 79 70 65 ) != int or type
03a0: 28 76 61 6c 75 65 29 20 21 3d 20 69 6e 74 20 6f (value) != int o
03b0: 72 20 6e 61 6d 65 20 3e 3d 20 76 61 6c 75 65 3a r name >= value:
03c0: 0a 09 09 09 72 65 74 75 72 6e 28 46 61 6c 73 65 ....return(False
03d0: 29 0a 09 09 69 66 20 73 65 6c 66 2e 5f 5f 62 6f )...if self.__bo
03e0: 74 74 6f 6d 20 21 3d 20 4e 6f 6e 65 3a 0a 09 09 ttom != None:...
03f0: 09 69 66 20 6e 61 6d 65 20 3c 20 73 65 6c 66 2e .if name < self.
0400: 5f 5f 62 6f 74 74 6f 6d 20 6f 72 20 76 61 6c 75 __bottom or valu
0410: 65 20 3c 20 73 65 6c 66 2e 5f 5f 62 6f 74 74 6f e < self.__botto
0420: 6d 3a 0a 09 09 09 09 72 65 74 75 72 6e 28 46 61 m:.....return(Fa
0430: 6c 73 65 29 0a 09 09 69 66 20 73 65 6c 66 2e 5f lse)...if self._
0440: 5f 74 6f 70 20 21 3d 20 4e 6f 6e 65 3a 0a 09 09 _top != None:...
0450: 09 69 66 20 6e 61 6d 65 20 3e 3d 20 73 65 6c 66 .if name >= self
0460: 2e 5f 5f 74 6f 70 20 6f 72 20 76 61 6c 75 65 20 .__top or value
0470: 3e 3d 20 73 65 6c 66 2e 5f 5f 74 6f 70 3a 0a 09 >= self.__top:..
0480: 09 09 09 72 65 74 75 72 6e 28 46 61 6c 73 65 29 ...return(False)
0490: 0a 09 09 73 65 6c 66 2e 5f 5f 70 61 69 72 73 5b ...self.__pairs[
04a0: 6e 61 6d 65 5d 20 3d 20 76 61 6c 75 65 0a 09 09 name] = value...
04b0: 72 65 74 75 72 6e 20 54 72 75 65 0a 0a 09 64 65 return True...de
04c0: 66 20 5f 5f 73 65 74 69 74 65 6d 5f 5f 28 73 65 f __setitem__(se
04d0: 6c 66 2c 20 6e 61 6d 65 2c 20 76 61 6c 75 65 29 lf, name, value)
04e0: 3a 0a 09 09 27 27 27 41 64 64 73 20 6f 6e 65 20 :...'''Adds one
04f0: 6d 6f 72 65 20 72 61 6e 67 65 20 61 6e 64 20 74 more range and t
0500: 72 69 65 73 20 74 6f 20 66 6f 6c 64 20 61 20 73 ries to fold a s
0510: 70 61 63 65 20 6d 61 70 2e 27 27 27 0a 09 09 73 pace map.'''...s
0520: 65 6c 66 2e 5f 5f 73 65 74 28 6e 61 6d 65 2c 20 elf.__set(name,
0530: 76 61 6c 75 65 29 0a 09 09 73 65 6c 66 2e 66 6f value)...self.fo
0540: 6c 64 28 29 0a 0a 09 64 65 66 20 66 6f 6c 64 28 ld()...def fold(
0550: 73 65 6c 66 29 3a 0a 09 09 27 27 27 54 72 69 65 self):...'''Trie
0560: 73 20 74 6f 20 6e 6f 72 6d 61 6c 69 7a 65 20 73 s to normalize s
0570: 70 61 63 65 6d 61 70 20 62 79 20 6a 6f 69 6e 69 pacemap by joini
0580: 6e 67 20 63 6f 61 6c 69 67 6e 65 64 20 6f 72 20 ng coaligned or
0590: 6f 76 65 72 6c 61 70 70 69 6e 67 20 72 61 6e 67 overlapping rang
05a0: 65 73 2e 27 27 27 0a 09 09 73 65 6c 66 2e 72 65 es.'''...self.re
05b0: 77 69 6e 64 28 29 0a 09 09 70 61 69 72 73 20 3d wind()...pairs =
05c0: 20 28 29 0a 09 09 77 68 69 6c 65 20 54 72 75 65 ()...while True
05d0: 3a 0a 09 09 09 70 61 69 72 20 3d 20 73 65 6c 66 :....pair = self
05e0: 2e 70 6f 70 28 29 0a 09 09 09 69 66 20 70 61 69 .pop()....if pai
05f0: 72 5b 30 5d 20 3d 3d 20 4e 6f 6e 65 3a 0a 09 09 r[0] == None:...
0600: 09 09 62 72 65 61 6b 0a 09 09 09 70 61 69 72 73 ..break....pairs
0610: 20 2b 3d 20 70 61 69 72 2c 0a 09 09 6c 61 73 74 += pair,...last
0620: 5f 70 61 69 72 20 3d 20 73 65 6c 66 2e 5f 5f 62 _pair = self.__b
0630: 6f 74 74 6f 6d 0a 09 09 66 6f 72 20 70 61 69 72 ottom...for pair
0640: 20 69 6e 20 70 61 69 72 73 3a 0a 09 09 09 69 66 in pairs:....if
0650: 20 6c 61 73 74 5f 70 61 69 72 20 69 6e 20 73 65 last_pair in se
0660: 6c 66 2e 5f 5f 70 61 69 72 73 20 61 6e 64 20 70 lf.__pairs and p
0670: 61 69 72 5b 30 5d 20 3c 3d 20 73 65 6c 66 2e 5f air[0] <= self._
0680: 5f 70 61 69 72 73 5b 6c 61 73 74 5f 70 61 69 72 _pairs[last_pair
0690: 5d 3a 0a 09 09 09 09 69 66 20 70 61 69 72 5b 31 ]:.....if pair[1
06a0: 5d 20 3e 20 73 65 6c 66 2e 5f 5f 70 61 69 72 73 ] > self.__pairs
06b0: 5b 6c 61 73 74 5f 70 61 69 72 5d 3a 0a 09 09 09 [last_pair]:....
06c0: 09 09 73 65 6c 66 2e 5f 5f 70 61 69 72 73 5b 6c ..self.__pairs[l
06d0: 61 73 74 5f 70 61 69 72 5d 20 3d 20 70 61 69 72 ast_pair] = pair
06e0: 5b 31 5d 0a 09 09 09 09 09 64 65 6c 28 73 65 6c [1]......del(sel
06f0: 66 2e 5f 5f 70 61 69 72 73 5b 70 61 69 72 5b 30 f.__pairs[pair[0
0700: 5d 5d 29 0a 09 09 09 65 6c 73 65 3a 0a 09 09 09 ]])....else:....
0710: 09 6c 61 73 74 5f 70 61 69 72 20 3d 20 70 61 69 .last_pair = pai
0720: 72 5b 30 5d 0a 09 09 73 65 6c 66 2e 63 6c 65 61 r[0]...self.clea
0730: 72 28 29 0a 0a 09 64 65 66 20 72 65 77 69 6e 64 r()...def rewind
0740: 28 73 65 6c 66 29 3a 0a 09 09 27 27 27 52 65 69 (self):...'''Rei
0750: 6e 69 74 69 61 6c 69 73 65 73 20 69 6e 74 65 72 nitialises inter
0760: 6e 61 6c 20 6f 72 64 65 72 65 64 20 6c 69 73 74 nal ordered list
0770: 20 6f 66 20 72 61 6e 67 65 73 2e 27 27 27 0a 09 of ranges.'''..
0780: 09 73 65 6c 66 2e 5f 5f 77 61 6c 6b 5f 6c 69 73 .self.__walk_lis
0790: 74 20 3d 20 6c 69 73 74 28 73 65 6c 66 2e 5f 5f t = list(self.__
07a0: 70 61 69 72 73 2e 6b 65 79 73 28 29 29 0a 09 09 pairs.keys())...
07b0: 73 65 6c 66 2e 5f 5f 77 61 6c 6b 5f 6c 69 73 74 self.__walk_list
07c0: 2e 73 6f 72 74 28 29 0a 0a 09 64 65 66 20 63 6c .sort()...def cl
07d0: 65 61 72 28 73 65 6c 66 29 3a 0a 09 09 27 27 27 ear(self):...'''
07e0: 43 6c 65 61 72 73 20 69 6e 74 65 72 6e 61 6c 20 Clears internal
07f0: 6f 72 64 65 72 65 64 20 6c 69 73 74 20 6f 66 20 ordered list of
0800: 72 61 6e 67 65 73 2e 27 27 27 0a 09 09 73 65 6c ranges.'''...sel
0810: 66 2e 5f 5f 77 61 6c 6b 5f 6c 69 73 74 20 3d 20 f.__walk_list =
0820: 4e 6f 6e 65 0a 0a 09 64 65 66 20 70 6f 70 28 73 None...def pop(s
0830: 65 6c 66 29 3a 0a 09 09 27 27 27 52 65 74 75 72 elf):...'''Retur
0840: 6e 73 20 6e 65 78 74 20 72 61 6e 67 65 20 66 72 ns next range fr
0850: 6f 6d 20 6f 72 64 65 72 65 64 20 6c 69 73 74 20 om ordered list
0860: 6f 66 20 72 61 6e 67 65 73 2e 27 27 27 0a 09 09 of ranges.'''...
0870: 69 66 20 73 65 6c 66 2e 5f 5f 77 61 6c 6b 5f 6c if self.__walk_l
0880: 69 73 74 20 21 3d 20 4e 6f 6e 65 3a 0a 09 09 09 ist != None:....
0890: 69 66 20 6c 65 6e 28 73 65 6c 66 2e 5f 5f 77 61 if len(self.__wa
08a0: 6c 6b 5f 6c 69 73 74 29 20 3e 20 30 3a 0a 09 09 lk_list) > 0:...
08b0: 09 09 6e 65 78 74 20 3d 20 73 65 6c 66 2e 5f 5f ..next = self.__
08c0: 77 61 6c 6b 5f 6c 69 73 74 2e 70 6f 70 28 30 29 walk_list.pop(0)
08d0: 0a 09 09 09 09 72 65 74 75 72 6e 28 5b 6e 65 78 .....return([nex
08e0: 74 2c 20 73 65 6c 66 2e 5f 5f 70 61 69 72 73 5b t, self.__pairs[
08f0: 6e 65 78 74 5d 5d 29 0a 09 09 72 65 74 75 72 6e next]])...return
0900: 28 5b 4e 6f 6e 65 2c 20 4e 6f 6e 65 5d 29 0a 0a ([None, None])..
0910: 09 64 65 66 20 5f 5f 72 65 70 72 5f 5f 28 73 65 .def __repr__(se
0920: 6c 66 29 3a 0a 09 09 27 27 27 52 65 74 75 72 6e lf):...'''Return
0930: 73 20 74 68 65 20 69 6e 6e 65 72 20 64 69 63 74 s the inner dict
0940: 20 77 69 74 68 20 72 61 6e 67 65 73 2e 27 27 27 with ranges.'''
0950: 0a 09 09 72 65 74 75 72 6e 28 72 65 70 72 28 73 ...return(repr(s
0960: 65 6c 66 2e 5f 5f 70 61 69 72 73 29 29 0a 0a 09 elf.__pairs))...
0970: 64 65 66 20 5f 5f 61 6e 64 5f 5f 28 73 65 6c 66 def __and__(self
0980: 2c 20 6f 74 68 65 72 29 3a 0a 09 09 27 27 27 52 , other):...'''R
0990: 65 74 75 72 6e 73 20 6e 65 77 20 73 70 61 63 65 eturns new space
09a0: 20 6d 61 70 20 77 69 74 68 20 72 61 6e 67 65 73 map with ranges
09b0: 20 74 68 61 74 20 61 70 70 65 61 72 73 20 62 6f that appears bo
09c0: 74 68 20 69 6e 20 41 20 61 6e 64 20 42 2e 27 27 th in A and B.''
09d0: 27 0a 09 09 69 66 20 74 79 70 65 28 6f 74 68 65 '...if type(othe
09e0: 72 29 20 21 3d 20 53 70 61 63 65 4d 61 70 3a 0a r) != SpaceMap:.
09f0: 09 09 09 72 65 74 75 72 6e 28 46 61 6c 73 65 29 ...return(False)
0a00: 0a 09 09 6e 65 77 20 3d 20 7b 7d 0a 09 09 73 65 ...new = {}...se
0a10: 6c 66 2e 72 65 77 69 6e 64 28 29 0a 09 09 6f 74 lf.rewind()...ot
0a20: 68 65 72 2e 72 65 77 69 6e 64 28 29 0a 09 09 6d her.rewind()...m
0a30: 79 5f 70 61 69 72 20 3d 20 73 65 6c 66 2e 70 6f y_pair = self.po
0a40: 70 28 29 0a 09 09 6f 74 68 65 72 5f 70 61 69 72 p()...other_pair
0a50: 20 3d 20 6f 74 68 65 72 2e 70 6f 70 28 29 0a 09 = other.pop()..
0a60: 09 23 20 69 66 20 74 68 65 72 65 20 61 72 65 20 .# if there are
0a70: 6e 6f 20 70 61 69 72 73 20 69 6e 20 42 20 2d 20 no pairs in B -
0a80: 77 65 20 68 61 76 65 20 6e 6f 74 68 69 6e 67 20 we have nothing
0a90: 74 6f 20 64 6f 0a 09 09 69 66 20 6f 74 68 65 72 to do...if other
0aa0: 5f 70 61 69 72 5b 30 5d 20 3d 3d 20 4e 6f 6e 65 _pair[0] == None
0ab0: 20 6f 72 20 6d 79 5f 70 61 69 72 5b 30 5d 20 3d or my_pair[0] =
0ac0: 3d 20 4e 6f 6e 65 3a 0a 09 09 09 61 6c 6c 5f 70 = None:....all_p
0ad0: 61 72 74 73 5f 66 6f 75 6e 64 20 3d 20 54 72 75 arts_found = Tru
0ae0: 65 0a 09 09 65 6c 73 65 3a 0a 09 09 09 61 6c 6c e...else:....all
0af0: 5f 70 61 72 74 73 5f 66 6f 75 6e 64 20 3d 20 46 _parts_found = F
0b00: 61 6c 73 65 0a 09 09 77 68 69 6c 65 20 6e 6f 74 alse...while not
0b10: 20 61 6c 6c 5f 70 61 72 74 73 5f 66 6f 75 6e 64 all_parts_found
0b20: 3a 0a 09 09 09 69 66 20 6d 79 5f 70 61 69 72 5b :....if my_pair[
0b30: 30 5d 20 3e 20 6f 74 68 65 72 5f 70 61 69 72 5b 0] > other_pair[
0b40: 30 5d 3a 0a 09 09 09 09 23 20 77 68 65 6e 20 6d 0]:.....# when m
0b50: 79 20 70 61 69 72 20 73 74 61 72 74 73 20 61 66 y pair starts af
0b60: 74 65 72 20 6f 74 68 65 72 20 70 61 69 72 20 73 ter other pair s
0b70: 74 61 72 74 73 0a 09 09 09 09 23 20 20 6d 2d 2d tarts.....# m--
0b80: 2d 0a 09 09 09 09 23 20 6f 2d 2d 2d 0a 09 09 09 -.....# o---....
0b90: 09 69 66 20 6d 79 5f 70 61 69 72 5b 30 5d 20 3e .if my_pair[0] >
0ba0: 20 6f 74 68 65 72 5f 70 61 69 72 5b 31 5d 3a 0a other_pair[1]:.
0bb0: 09 09 09 09 09 23 20 77 68 65 6e 20 6d 79 20 70 .....# when my p
0bc0: 61 69 72 20 73 74 61 72 74 73 20 61 66 74 65 72 air starts after
0bd0: 20 6f 74 68 65 72 20 70 61 69 72 20 65 6e 64 73 other pair ends
0be0: 0a 09 09 09 09 09 23 20 20 20 20 20 20 20 6d 2d ......# m-
0bf0: 2d 2d 0a 09 09 09 09 09 23 20 6f 2d 2d 2d 6f 0a --......# o---o.
0c00: 09 09 09 09 09 6f 74 68 65 72 5f 70 61 69 72 20 .....other_pair
0c10: 3d 20 6f 74 68 65 72 2e 70 6f 70 28 29 0a 09 09 = other.pop()...
0c20: 09 09 09 23 20 74 6f 73 73 69 6e 67 20 6f 75 74 ...# tossing out
0c30: 20 6f 74 68 65 72 20 70 61 69 72 0a 09 09 09 09 other pair.....
0c40: 09 69 66 20 6f 74 68 65 72 5f 70 61 69 72 5b 30 .if other_pair[0
0c50: 5d 20 3d 3d 20 4e 6f 6e 65 3a 0a 09 09 09 09 09 ] == None:......
0c60: 09 61 6c 6c 5f 70 61 72 74 73 5f 66 6f 75 6e 64 .all_parts_found
0c70: 20 3d 20 54 72 75 65 0a 09 09 09 09 65 6c 73 65 = True.....else
0c80: 3a 0a 09 09 09 09 09 23 20 77 68 65 6e 20 6d 79 :......# when my
0c90: 20 70 61 69 72 20 73 74 61 72 74 73 20 62 65 66 pair starts bef
0ca0: 6f 72 65 20 6f 74 68 65 72 20 70 61 69 72 20 65 ore other pair e
0cb0: 6e 64 73 0a 09 09 09 09 09 23 20 20 20 20 6d 2d nds......# m-
0cc0: 2d 2d 20 7c 20 20 20 20 20 6d 2d 2d 2d 0a 09 09 -- | m---...
0cd0: 09 09 09 23 20 6f 2d 2d 2d 6f 20 20 20 7c 20 6f ...# o---o | o
0ce0: 2d 2d 2d 6f 0a 09 09 09 09 09 69 66 20 6d 79 5f ---o......if my_
0cf0: 70 61 69 72 5b 31 5d 20 3e 20 6f 74 68 65 72 5f pair[1] > other_
0d00: 70 61 69 72 5b 31 5d 3a 0a 09 09 09 09 09 09 23 pair[1]:.......#
0d10: 20 77 68 65 6e 20 6d 79 20 70 61 69 72 20 65 6e when my pair en
0d20: 64 73 20 61 66 74 65 72 20 6f 74 68 65 72 20 70 ds after other p
0d30: 61 69 72 20 65 6e 64 73 0a 09 09 09 09 09 09 23 air ends.......#
0d40: 20 20 20 20 6d 2d 2d 2d 6d 20 7c 20 20 20 20 20 m---m |
0d50: 6d 2d 2d 2d 6d 0a 09 09 09 09 09 09 23 20 6f 2d m---m.......# o-
0d60: 2d 2d 6f 20 20 20 20 7c 20 6f 2d 2d 2d 6f 0a 09 --o | o---o..
0d70: 09 09 09 09 09 6f 74 68 65 72 5f 70 61 69 72 5b .....other_pair[
0d80: 30 5d 20 3d 20 6d 79 5f 70 61 69 72 5b 30 5d 0a 0] = my_pair[0].
0d90: 09 09 09 09 09 09 23 20 74 72 69 6d 6d 69 6e 67 ......# trimming
0da0: 20 6f 74 68 65 72 20 70 61 69 72 20 62 79 20 6d other pair by m
0db0: 79 20 70 61 69 72 20 73 74 61 72 74 0a 09 09 09 y pair start....
0dc0: 09 09 09 23 20 20 20 6d 2d 2d 2d 6d 0a 09 09 09 ...# m---m....
0dd0: 09 09 09 23 20 6f 2e 6f 2d 6f 0a 09 09 09 09 09 ...# o.o-o......
0de0: 65 6c 73 65 3a 0a 09 09 09 09 09 09 23 20 77 68 else:.......# wh
0df0: 65 6e 20 6d 79 20 70 61 69 72 20 65 6e 64 73 20 en my pair ends
0e00: 62 65 66 6f 72 65 20 6f 74 68 65 72 20 70 61 69 before other pai
0e10: 72 20 65 6e 64 73 0a 09 09 09 09 09 09 23 20 20 r ends.......#
0e20: 6d 2d 2d 2d 6d 0a 09 09 09 09 09 09 23 20 6f 2d m---m.......# o-
0e30: 2d 2d 2d 2d 6f 0a 09 09 09 09 09 09 6e 65 77 5b ----o.......new[
0e40: 6d 79 5f 70 61 69 72 5b 30 5d 5d 20 3d 20 6d 79 my_pair[0]] = my
0e50: 5f 70 61 69 72 5b 31 5d 0a 09 09 09 09 09 09 23 _pair[1].......#
0e60: 20 6d 79 20 70 61 69 72 20 69 73 20 63 6f 76 65 my pair is cove
0e70: 72 65 64 20 61 6e 64 20 73 68 6f 75 6c 64 20 62 red and should b
0e80: 65 20 61 64 64 65 64 20 74 6f 20 72 65 73 75 6c e added to resul
0e90: 74 0a 09 09 09 09 09 09 6d 79 5f 70 61 69 72 20 t.......my_pair
0ea0: 3d 20 73 65 6c 66 2e 70 6f 70 28 29 0a 09 09 09 = self.pop()....
0eb0: 09 09 09 23 20 74 6f 73 73 69 6e 67 20 6f 75 74 ...# tossing out
0ec0: 20 6d 79 20 70 61 69 72 0a 09 09 09 09 09 09 69 my pair.......i
0ed0: 66 20 6d 79 5f 70 61 69 72 5b 30 5d 20 3d 3d 20 f my_pair[0] ==
0ee0: 4e 6f 6e 65 3a 0a 09 09 09 09 09 09 09 61 6c 6c None:........all
0ef0: 5f 70 61 72 74 73 5f 66 6f 75 6e 64 20 3d 20 54 _parts_found = T
0f00: 72 75 65 0a 09 09 09 65 6c 69 66 20 6d 79 5f 70 rue....elif my_p
0f10: 61 69 72 5b 30 5d 20 3c 20 6f 74 68 65 72 5f 70 air[0] < other_p
0f20: 61 69 72 5b 30 5d 3a 0a 09 09 09 09 23 20 77 68 air[0]:.....# wh
0f30: 65 6e 20 6d 79 20 70 61 69 72 20 73 74 61 72 74 en my pair start
0f40: 73 20 62 65 66 6f 72 65 20 6f 74 68 65 72 20 6f s before other o
0f50: 6e 65 0a 09 09 09 09 23 20 6d 2d 2d 2d 0a 09 09 ne.....# m---...
0f60: 09 09 23 20 20 6f 2d 2d 2d 0a 09 09 09 09 69 66 ..# o---.....if
0f70: 20 6d 79 5f 70 61 69 72 5b 31 5d 20 3c 20 6f 74 my_pair[1] < ot
0f80: 68 65 72 5f 70 61 69 72 5b 30 5d 3a 0a 09 09 09 her_pair[0]:....
0f90: 09 09 23 20 77 68 65 6e 20 6d 79 20 70 61 69 72 ..# when my pair
0fa0: 20 65 6e 64 73 20 62 65 66 6f 72 65 20 6f 74 68 ends before oth
0fb0: 65 72 20 70 61 69 72 20 73 74 61 72 74 73 0a 09 er pair starts..
0fc0: 09 09 09 09 23 20 6d 2d 2d 2d 6d 0a 09 09 09 09 ....# m---m.....
0fd0: 09 23 20 20 20 20 20 20 20 6f 2d 2d 2d 0a 09 09 .# o---...
0fe0: 09 09 09 6d 79 5f 70 61 69 72 20 3d 20 73 65 6c ...my_pair = sel
0ff0: 66 2e 70 6f 70 28 29 0a 09 09 09 09 09 23 20 74 f.pop()......# t
1000: 6f 73 73 69 6e 67 20 6f 75 74 20 6d 79 20 70 61 ossing out my pa
1010: 69 72 0a 09 09 09 09 09 69 66 20 6d 79 5f 70 61 ir......if my_pa
1020: 69 72 5b 30 5d 20 3d 3d 20 4e 6f 6e 65 3a 0a 09 ir[0] == None:..
1030: 09 09 09 09 09 61 6c 6c 5f 70 61 72 74 73 5f 66 .....all_parts_f
1040: 6f 75 6e 64 20 3d 20 54 72 75 65 0a 09 09 09 09 ound = True.....
1050: 65 6c 73 65 3a 0a 09 09 09 09 09 23 20 77 68 65 else:......# whe
1060: 6e 20 6d 79 20 70 61 69 72 20 65 6e 64 73 20 62 n my pair ends b
1070: 65 66 6f 72 65 20 6f 74 68 65 72 20 70 61 69 72 efore other pair
1080: 20 73 74 61 72 74 73 0a 09 09 09 09 09 23 20 6d starts......# m
1090: 2d 2d 2d 6d 0a 09 09 09 09 09 23 20 20 20 6f 2d ---m......# o-
10a0: 2d 2d 0a 09 09 09 09 09 6d 79 5f 70 61 69 72 5b --......my_pair[
10b0: 30 5d 20 3d 20 6f 74 68 65 72 5f 70 61 69 72 5b 0] = other_pair[
10c0: 30 5d 0a 09 09 09 09 09 23 20 74 72 69 6d 6d 69 0]......# trimmi
10d0: 6e 67 20 6d 79 20 70 61 69 72 20 62 79 20 6f 74 ng my pair by ot
10e0: 68 65 72 20 70 61 69 72 20 73 74 61 72 74 0a 09 her pair start..
10f0: 09 09 09 09 23 20 6d 2e 6d 2d 6d 0a 09 09 09 09 ....# m.m-m.....
1100: 09 23 20 20 20 6f 2d 2d 2d 0a 09 09 09 65 6c 73 .# o---....els
1110: 65 3a 0a 09 09 09 09 23 20 77 68 65 6e 20 62 6f e:.....# when bo
1120: 74 68 20 70 61 69 72 73 20 73 74 61 72 74 73 20 th pairs starts
1130: 73 69 6d 75 6c 74 61 6e 65 6f 75 73 6c 79 0a 09 simultaneously..
1140: 09 09 09 23 20 6d 2d 2d 2d 0a 09 09 09 09 23 20 ...# m---.....#
1150: 6f 2d 2d 2d 0a 09 09 09 09 69 66 20 6d 79 5f 70 o---.....if my_p
1160: 61 69 72 5b 31 5d 20 3c 20 6f 74 68 65 72 5f 70 air[1] < other_p
1170: 61 69 72 5b 31 5d 3a 0a 09 09 09 09 09 23 20 77 air[1]:......# w
1180: 68 65 6e 20 6d 79 20 70 61 69 72 20 65 6e 64 73 hen my pair ends
1190: 20 62 65 66 6f 72 65 20 6f 74 68 65 72 20 70 61 before other pa
11a0: 69 72 0a 09 09 09 09 09 23 20 6d 2d 2d 2d 6d 0a ir......# m---m.
11b0: 09 09 09 09 09 23 20 6f 2d 2d 2d 2d 2d 6f 0a 09 .....# o-----o..
11c0: 09 09 09 09 6e 65 77 5b 6d 79 5f 70 61 69 72 5b ....new[my_pair[
11d0: 30 5d 5d 20 3d 20 6d 79 5f 70 61 69 72 5b 31 5d 0]] = my_pair[1]
11e0: 0a 09 09 09 09 09 23 20 6d 79 20 70 61 69 72 20 ......# my pair
11f0: 69 73 20 63 6f 76 65 72 65 64 20 61 6e 64 20 73 is covered and s
1200: 68 6f 75 6c 64 20 62 65 20 61 64 64 65 64 20 74 hould be added t
1210: 6f 20 72 65 73 75 6c 74 0a 09 09 09 09 09 6d 79 o result......my
1220: 5f 70 61 69 72 20 3d 20 73 65 6c 66 2e 70 6f 70 _pair = self.pop
1230: 28 29 0a 09 09 09 09 09 23 20 74 6f 73 73 69 6e ()......# tossin
1240: 67 20 6f 75 74 20 6d 79 20 70 61 69 72 0a 09 09 g out my pair...
1250: 09 09 09 69 66 20 6d 79 5f 70 61 69 72 5b 30 5d ...if my_pair[0]
1260: 20 3d 3d 20 4e 6f 6e 65 3a 0a 09 09 09 09 09 09 == None:.......
1270: 61 6c 6c 5f 70 61 72 74 73 5f 66 6f 75 6e 64 20 all_parts_found
1280: 3d 20 54 72 75 65 0a 09 09 09 09 65 6c 73 65 3a = True.....else:
1290: 0a 09 09 09 09 09 23 20 77 68 65 6e 20 6d 79 20 ......# when my
12a0: 70 61 69 72 20 65 6e 64 73 20 61 66 74 65 72 20 pair ends after
12b0: 6f 74 68 65 72 20 70 61 69 72 0a 09 09 09 09 09 other pair......
12c0: 23 20 6d 2d 2d 2d 2d 2d 6d 0a 09 09 09 09 09 23 # m-----m......#
12d0: 20 6f 2d 2d 2d 6f 0a 09 09 09 09 09 6e 65 77 5b o---o......new[
12e0: 6d 79 5f 70 61 69 72 5b 30 5d 5d 20 3d 20 6f 74 my_pair[0]] = ot
12f0: 68 65 72 5f 70 61 69 72 5b 31 5d 0a 09 09 09 09 her_pair[1].....
1300: 09 23 20 70 61 72 74 20 6f 66 20 6d 79 20 70 61 .# part of my pa
1310: 69 72 20 69 73 20 63 6f 76 65 72 65 64 20 61 6e ir is covered an
1320: 64 20 73 68 6f 75 6c 64 20 62 65 20 61 64 64 65 d should be adde
1330: 64 20 74 6f 20 72 65 73 75 6c 74 0a 09 09 09 09 d to result.....
1340: 09 6f 74 68 65 72 5f 70 61 69 72 20 3d 20 6f 74 .other_pair = ot
1350: 68 65 72 2e 70 6f 70 28 29 0a 09 09 09 09 09 23 her.pop()......#
1360: 20 74 6f 73 73 69 6e 67 20 6f 75 74 20 6f 74 68 tossing out oth
1370: 65 72 20 70 61 69 72 0a 09 09 09 09 09 69 66 20 er pair......if
1380: 6f 74 68 65 72 5f 70 61 69 72 5b 30 5d 20 3d 3d other_pair[0] ==
1390: 20 4e 6f 6e 65 3a 0a 09 09 09 09 09 09 61 6c 6c None:.......all
13a0: 5f 70 61 72 74 73 5f 66 6f 75 6e 64 20 3d 20 54 _parts_found = T
13b0: 72 75 65 0a 09 09 73 65 6c 66 2e 63 6c 65 61 72 rue...self.clear
13c0: 28 29 0a 09 09 6f 74 68 65 72 2e 63 6c 65 61 72 ()...other.clear
13d0: 28 29 0a 09 09 72 65 74 75 72 6e 28 53 70 61 63 ()...return(Spac
13e0: 65 4d 61 70 28 6e 65 77 2c 20 73 65 6c 66 2e 5f eMap(new, self._
13f0: 5f 62 6f 74 74 6f 6d 2c 20 73 65 6c 66 2e 5f 5f _bottom, self.__
1400: 74 6f 70 29 29 0a 0a 09 64 65 66 20 5f 5f 73 75 top))...def __su
1410: 62 5f 5f 28 73 65 6c 66 2c 20 6f 74 68 65 72 29 b__(self, other)
1420: 3a 0a 09 09 27 27 27 52 65 74 75 72 6e 73 20 6e :...'''Returns n
1430: 65 77 20 73 70 61 63 65 20 6d 61 70 20 77 69 74 ew space map wit
1440: 68 20 72 61 6e 67 65 73 20 69 6e 20 41 20 6e 6f h ranges in A no
1450: 74 20 63 6f 76 65 72 65 64 20 62 79 20 42 2e 27 t covered by B.'
1460: 27 27 0a 09 09 69 66 20 74 79 70 65 28 6f 74 68 ''...if type(oth
1470: 65 72 29 20 21 3d 20 53 70 61 63 65 4d 61 70 3a er) != SpaceMap:
1480: 0a 09 09 09 72 65 74 75 72 6e 28 46 61 6c 73 65 ....return(False
1490: 29 0a 09 09 6e 65 77 20 3d 20 7b 7d 0a 09 09 73 )...new = {}...s
14a0: 65 6c 66 2e 72 65 77 69 6e 64 28 29 0a 09 09 6f elf.rewind()...o
14b0: 74 68 65 72 2e 72 65 77 69 6e 64 28 29 0a 09 09 ther.rewind()...
14c0: 6d 79 5f 70 61 69 72 20 3d 20 73 65 6c 66 2e 70 my_pair = self.p
14d0: 6f 70 28 29 0a 09 09 6f 74 68 65 72 5f 70 61 69 op()...other_pai
14e0: 72 20 3d 20 6f 74 68 65 72 2e 70 6f 70 28 29 0a r = other.pop().
14f0: 09 09 23 20 69 66 20 74 68 65 72 65 20 61 72 65 ..# if there are
1500: 20 6e 6f 20 70 61 69 72 73 20 69 6e 20 42 20 2d no pairs in B -
1510: 20 63 6f 70 79 20 74 68 69 73 20 6f 6e 65 20 74 copy this one t
1520: 6f 20 6e 65 77 20 53 70 61 63 65 4d 61 70 0a 09 o new SpaceMap..
1530: 09 69 66 20 6f 74 68 65 72 5f 70 61 69 72 5b 30 .if other_pair[0
1540: 5d 20 3d 3d 20 4e 6f 6e 65 3a 0a 09 09 09 6e 65 ] == None:....ne
1550: 77 5b 6d 79 5f 70 61 69 72 5b 30 5d 5d 20 3d 20 w[my_pair[0]] =
1560: 6d 79 5f 70 61 69 72 5b 31 5d 0a 09 09 09 61 6c my_pair[1]....al
1570: 6c 5f 70 61 72 74 73 5f 66 6f 75 6e 64 20 3d 20 l_parts_found =
1580: 54 72 75 65 0a 09 09 65 6c 69 66 20 6d 79 5f 70 True...elif my_p
1590: 61 69 72 5b 30 5d 20 3d 3d 20 4e 6f 6e 65 3a 0a air[0] == None:.
15a0: 09 09 09 61 6c 6c 5f 70 61 72 74 73 5f 66 6f 75 ...all_parts_fou
15b0: 6e 64 20 3d 20 54 72 75 65 0a 09 09 65 6c 73 65 nd = True...else
15c0: 3a 0a 09 09 09 61 6c 6c 5f 70 61 72 74 73 5f 66 :....all_parts_f
15d0: 6f 75 6e 64 20 3d 20 46 61 6c 73 65 0a 09 09 77 ound = False...w
15e0: 68 69 6c 65 20 6e 6f 74 20 61 6c 6c 5f 70 61 72 hile not all_par
15f0: 74 73 5f 66 6f 75 6e 64 3a 0a 09 09 09 69 66 20 ts_found:....if
1600: 6d 79 5f 70 61 69 72 5b 30 5d 20 3e 20 6f 74 68 my_pair[0] > oth
1610: 65 72 5f 70 61 69 72 5b 30 5d 3a 0a 09 09 09 09 er_pair[0]:.....
1620: 23 20 77 68 65 6e 20 6d 79 20 70 61 69 72 20 73 # when my pair s
1630: 74 61 72 74 73 20 61 66 74 65 72 20 6f 74 68 65 tarts after othe
1640: 72 20 70 61 69 72 20 73 74 61 72 74 73 0a 09 09 r pair starts...
1650: 09 09 23 20 20 6d 2d 2d 2d 0a 09 09 09 09 23 20 ..# m---.....#
1660: 6f 2d 2d 2d 0a 09 09 09 09 69 66 20 6d 79 5f 70 o---.....if my_p
1670: 61 69 72 5b 30 5d 20 3e 20 6f 74 68 65 72 5f 70 air[0] > other_p
1680: 61 69 72 5b 31 5d 3a 0a 09 09 09 09 09 23 20 77 air[1]:......# w
1690: 68 65 6e 20 6d 79 20 70 61 69 72 20 73 74 61 72 hen my pair star
16a0: 74 73 20 61 66 74 65 72 20 6f 74 68 65 72 20 70 ts after other p
16b0: 61 69 72 20 65 6e 64 73 0a 09 09 09 09 09 23 20 air ends......#
16c0: 20 20 20 20 20 20 6d 2d 2d 2d 0a 09 09 09 09 09 m---......
16d0: 23 20 6f 2d 2d 2d 6f 0a 09 09 09 09 09 6f 74 68 # o---o......oth
16e0: 65 72 5f 70 61 69 72 20 3d 20 6f 74 68 65 72 2e er_pair = other.
16f0: 70 6f 70 28 29 0a 09 09 09 09 09 23 20 74 6f 73 pop()......# tos
1700: 73 69 6e 67 20 6f 75 74 20 6f 74 68 65 72 20 70 sing out other p
1710: 61 69 72 0a 09 09 09 09 09 69 66 20 6f 74 68 65 air......if othe
1720: 72 5f 70 61 69 72 5b 30 5d 20 3d 3d 20 4e 6f 6e r_pair[0] == Non
1730: 65 3a 0a 09 09 09 09 09 09 23 20 74 68 69 73 20 e:.......# this
1740: 77 61 73 20 6c 61 73 74 20 6f 6e 65 20 2d 20 6d was last one - m
1750: 79 20 70 61 69 72 20 67 6f 65 73 20 74 6f 20 72 y pair goes to r
1760: 65 73 75 6c 74 0a 09 09 09 09 09 09 6e 65 77 5b esult.......new[
1770: 6d 79 5f 70 61 69 72 5b 30 5d 5d 20 3d 20 6d 79 my_pair[0]] = my
1780: 5f 70 61 69 72 5b 31 5d 0a 09 09 09 09 09 09 61 _pair[1].......a
1790: 6c 6c 5f 70 61 72 74 73 5f 66 6f 75 6e 64 20 3d ll_parts_found =
17a0: 20 54 72 75 65 0a 09 09 09 09 65 6c 73 65 3a 0a True.....else:.
17b0: 09 09 09 09 09 23 20 77 68 65 6e 20 6d 79 20 70 .....# when my p
17c0: 61 69 72 20 73 74 61 72 74 73 20 62 65 66 6f 72 air starts befor
17d0: 65 20 6f 74 68 65 72 20 70 61 69 72 20 65 6e 64 e other pair end
17e0: 73 0a 09 09 09 09 09 23 20 20 20 20 6d 2d 2d 2d s......# m---
17f0: 20 7c 20 20 20 20 20 6d 2d 2d 2d 0a 09 09 09 09 | m---.....
1800: 09 23 20 6f 2d 2d 2d 6f 20 20 20 7c 20 6f 2d 2d .# o---o | o--
1810: 2d 6f 0a 09 09 09 09 09 69 66 20 6d 79 5f 70 61 -o......if my_pa
1820: 69 72 5b 31 5d 20 3e 20 6f 74 68 65 72 5f 70 61 ir[1] > other_pa
1830: 69 72 5b 31 5d 3a 0a 09 09 09 09 09 09 23 20 77 ir[1]:.......# w
1840: 68 65 6e 20 6d 79 20 70 61 69 72 20 65 6e 64 73 hen my pair ends
1850: 20 61 66 74 65 72 20 6f 74 68 65 72 20 70 61 69 after other pai
1860: 72 20 65 6e 64 73 0a 09 09 09 09 09 09 23 20 20 r ends.......#
1870: 20 20 6d 2d 2d 2d 6d 20 7c 20 20 20 20 20 6d 2d m---m | m-
1880: 2d 2d 6d 0a 09 09 09 09 09 09 23 20 6f 2d 2d 2d --m.......# o---
1890: 6f 20 20 20 20 7c 20 6f 2d 2d 2d 6f 0a 09 09 09 o | o---o....
18a0: 09 09 09 6d 79 5f 70 61 69 72 5b 30 5d 20 3d 20 ...my_pair[0] =
18b0: 6f 74 68 65 72 5f 70 61 69 72 5b 31 5d 0a 09 09 other_pair[1]...
18c0: 09 09 09 09 23 20 74 72 69 6d 6d 69 6e 67 20 6d ....# trimming m
18d0: 79 20 70 61 69 72 20 62 79 20 6f 74 68 65 72 20 y pair by other
18e0: 70 61 69 72 20 65 6e 64 0a 09 09 09 09 09 09 23 pair end.......#
18f0: 20 20 20 6d 2e 6d 2d 6d 0a 09 09 09 09 09 09 23 m.m-m.......#
1900: 20 6f 2d 2d 2d 6f 0a 09 09 09 09 09 09 6f 74 68 o---o.......oth
1910: 65 72 5f 70 61 69 72 20 3d 20 6f 74 68 65 72 2e er_pair = other.
1920: 70 6f 70 28 29 0a 09 09 09 09 09 09 23 20 74 6f pop().......# to
1930: 73 73 69 6e 67 20 6f 75 74 20 6f 74 68 65 72 20 ssing out other
1940: 70 61 69 72 0a 09 09 09 09 09 09 69 66 20 6f 74 pair.......if ot
1950: 68 65 72 5f 70 61 69 72 5b 30 5d 20 3d 3d 20 4e her_pair[0] == N
1960: 6f 6e 65 3a 0a 09 09 09 09 09 09 23 20 74 68 69 one:.......# thi
1970: 73 20 77 61 73 20 6c 61 73 74 20 6f 6e 65 20 2d s was last one -
1980: 20 6d 79 20 70 61 69 72 20 67 6f 65 73 20 74 6f my pair goes to
1990: 20 72 65 73 75 6c 74 0a 09 09 09 09 09 09 09 6e result........n
19a0: 65 77 5b 6d 79 5f 70 61 69 72 5b 30 5d 5d 20 3d ew[my_pair[0]] =
19b0: 20 6d 79 5f 70 61 69 72 5b 31 5d 0a 09 09 09 09 my_pair[1].....
19c0: 09 09 09 61 6c 6c 5f 70 61 72 74 73 5f 66 6f 75 ...all_parts_fou
19d0: 6e 64 20 3d 20 54 72 75 65 0a 09 09 09 09 09 65 nd = True......e
19e0: 6c 73 65 3a 0a 09 09 09 09 09 09 23 20 77 68 65 lse:.......# whe
19f0: 6e 20 6d 79 20 70 61 69 72 20 65 6e 64 73 20 62 n my pair ends b
1a00: 65 66 6f 72 65 20 6f 74 68 65 72 20 70 61 69 72 efore other pair
1a10: 20 65 6e 64 73 0a 09 09 09 09 09 09 23 20 20 6d ends.......# m
1a20: 2d 2d 2d 6d 0a 09 09 09 09 09 09 23 20 6f 2d 2d ---m.......# o--
1a30: 2d 2d 2d 6f 0a 09 09 09 09 09 09 6d 79 5f 70 61 ---o.......my_pa
1a40: 69 72 20 3d 20 73 65 6c 66 2e 70 6f 70 28 29 0a ir = self.pop().
1a50: 09 09 09 09 09 09 23 20 74 6f 73 73 69 6e 67 20 ......# tossing
1a60: 6f 75 74 20 6d 79 20 70 61 69 72 0a 09 09 09 09 out my pair.....
1a70: 09 09 69 66 20 6d 79 5f 70 61 69 72 5b 30 5d 20 ..if my_pair[0]
1a80: 3d 3d 20 4e 6f 6e 65 3a 0a 09 09 09 09 09 09 09 == None:........
1a90: 61 6c 6c 5f 70 61 72 74 73 5f 66 6f 75 6e 64 20 all_parts_found
1aa0: 3d 20 54 72 75 65 0a 09 09 09 65 6c 69 66 20 6d = True....elif m
1ab0: 79 5f 70 61 69 72 5b 30 5d 20 3c 20 6f 74 68 65 y_pair[0] < othe
1ac0: 72 5f 70 61 69 72 5b 30 5d 3a 0a 09 09 09 09 23 r_pair[0]:.....#
1ad0: 20 77 68 65 6e 20 6d 79 20 70 61 69 72 20 73 74 when my pair st
1ae0: 61 72 74 73 20 62 65 66 6f 72 65 20 6f 74 68 65 arts before othe
1af0: 72 20 6f 6e 65 0a 09 09 09 09 23 20 6d 2d 2d 2d r one.....# m---
1b00: 0a 09 09 09 09 23 20 20 6f 2d 2d 2d 0a 09 09 09 .....# o---....
1b10: 09 69 66 20 6d 79 5f 70 61 69 72 5b 31 5d 20 3c .if my_pair[1] <
1b20: 20 6f 74 68 65 72 5f 70 61 69 72 5b 30 5d 3a 0a other_pair[0]:.
1b30: 09 09 09 09 09 23 20 77 68 65 6e 20 6d 79 20 70 .....# when my p
1b40: 61 69 72 20 65 6e 64 73 20 62 65 66 6f 72 65 20 air ends before
1b50: 6f 74 68 65 72 20 70 61 69 72 20 73 74 61 72 74 other pair start
1b60: 73 0a 09 09 09 09 09 23 20 6d 2d 2d 2d 6d 0a 09 s......# m---m..
1b70: 09 09 09 09 23 20 20 20 20 20 20 20 6f 2d 2d 2d ....# o---
1b80: 0a 09 09 09 09 09 6e 65 77 5b 6d 79 5f 70 61 69 ......new[my_pai
1b90: 72 5b 30 5d 5d 20 3d 20 6d 79 5f 70 61 69 72 5b r[0]] = my_pair[
1ba0: 31 5d 0a 09 09 09 09 09 23 20 6d 79 20 70 61 69 1]......# my pai
1bb0: 72 20 69 73 20 6e 6f 74 20 63 6f 76 65 72 65 64 r is not covered
1bc0: 20 61 6e 64 20 73 68 6f 75 6c 64 20 62 65 20 61 and should be a
1bd0: 64 64 65 64 20 74 6f 20 72 65 73 75 6c 74 0a 09 dded to result..
1be0: 09 09 09 09 6d 79 5f 70 61 69 72 20 3d 20 73 65 ....my_pair = se
1bf0: 6c 66 2e 70 6f 70 28 29 0a 09 09 09 09 09 23 20 lf.pop()......#
1c00: 74 6f 73 73 69 6e 67 20 6f 75 74 20 6d 79 20 70 tossing out my p
1c10: 61 69 72 0a 09 09 09 09 09 69 66 20 6d 79 5f 70 air......if my_p
1c20: 61 69 72 5b 30 5d 20 3d 3d 20 4e 6f 6e 65 3a 0a air[0] == None:.
1c30: 09 09 09 09 09 09 61 6c 6c 5f 70 61 72 74 73 5f ......all_parts_
1c40: 66 6f 75 6e 64 20 3d 20 54 72 75 65 0a 09 09 09 found = True....
1c50: 09 65 6c 73 65 3a 0a 09 09 09 09 09 23 20 77 68 .else:......# wh
1c60: 65 6e 20 6d 79 20 70 61 69 72 20 65 6e 64 73 20 en my pair ends
1c70: 62 65 66 6f 72 65 20 6f 74 68 65 72 20 70 61 69 before other pai
1c80: 72 20 73 74 61 72 74 73 0a 09 09 09 09 09 23 20 r starts......#
1c90: 6d 2d 2d 2d 6d 0a 09 09 09 09 09 23 20 20 20 6f m---m......# o
1ca0: 2d 2d 2d 0a 09 09 09 09 09 6e 65 77 5b 6d 79 5f ---......new[my_
1cb0: 70 61 69 72 5b 30 5d 5d 20 3d 20 6f 74 68 65 72 pair[0]] = other
1cc0: 5f 70 61 69 72 5b 30 5d 0a 09 09 09 09 09 23 20 _pair[0]......#
1cd0: 73 74 61 72 74 20 6f 66 20 6d 79 20 70 61 69 72 start of my pair
1ce0: 20 69 73 20 6e 6f 74 20 63 6f 76 65 72 65 64 20 is not covered
1cf0: 61 6e 64 20 73 68 6f 75 6c 64 20 62 65 20 61 64 and should be ad
1d00: 64 65 64 20 74 6f 20 72 65 73 75 6c 74 0a 09 09 ded to result...
1d10: 09 09 09 6d 79 5f 70 61 69 72 5b 30 5d 20 3d 20 ...my_pair[0] =
1d20: 6f 74 68 65 72 5f 70 61 69 72 5b 30 5d 0a 09 09 other_pair[0]...
1d30: 09 09 09 23 20 74 72 69 6d 6d 69 6e 67 20 6d 79 ...# trimming my
1d40: 20 70 61 69 72 20 62 79 20 6f 74 68 65 72 20 70 pair by other p
1d50: 61 69 72 20 73 74 61 72 74 0a 09 09 09 09 09 23 air start......#
1d60: 20 6d 2e 6d 2d 6d 0a 09 09 09 09 09 23 20 20 20 m.m-m......#
1d70: 6f 2d 2d 2d 0a 09 09 09 65 6c 73 65 3a 0a 09 09 o---....else:...
1d80: 09 09 23 20 77 68 65 6e 20 62 6f 74 68 20 70 61 ..# when both pa
1d90: 69 72 73 20 73 74 61 72 74 73 20 73 69 6d 75 6c irs starts simul
1da0: 74 61 6e 65 6f 75 73 6c 79 0a 09 09 09 09 23 20 taneously.....#
1db0: 6d 2d 2d 2d 0a 09 09 09 09 23 20 6f 2d 2d 2d 0a m---.....# o---.
1dc0: 09 09 09 09 69 66 20 6d 79 5f 70 61 69 72 5b 31 ....if my_pair[1
1dd0: 5d 20 3c 20 6f 74 68 65 72 5f 70 61 69 72 5b 31 ] < other_pair[1
1de0: 5d 3a 0a 09 09 09 09 09 23 20 77 68 65 6e 20 6d ]:......# when m
1df0: 79 20 70 61 69 72 20 65 6e 64 73 20 62 65 66 6f y pair ends befo
1e00: 72 65 20 6f 74 68 65 72 20 70 61 69 72 0a 09 09 re other pair...
1e10: 09 09 09 23 20 6d 2d 2d 2d 6d 0a 09 09 09 09 09 ...# m---m......
1e20: 23 20 6f 2d 2d 2d 2d 2d 6f 0a 09 09 09 09 09 6d # o-----o......m
1e30: 79 5f 70 61 69 72 20 3d 20 73 65 6c 66 2e 70 6f y_pair = self.po
1e40: 70 28 29 0a 09 09 09 09 09 23 20 74 6f 73 73 69 p()......# tossi
1e50: 6e 67 20 6f 75 74 20 6d 79 20 70 61 69 72 0a 09 ng out my pair..
1e60: 09 09 09 09 69 66 20 6d 79 5f 70 61 69 72 5b 30 ....if my_pair[0
1e70: 5d 20 3d 3d 20 4e 6f 6e 65 3a 0a 09 09 09 09 09 ] == None:......
1e80: 09 61 6c 6c 5f 70 61 72 74 73 5f 66 6f 75 6e 64 .all_parts_found
1e90: 20 3d 20 54 72 75 65 0a 09 09 09 09 65 6c 73 65 = True.....else
1ea0: 3a 0a 09 09 09 09 09 23 20 77 68 65 6e 20 6d 79 :......# when my
1eb0: 20 70 61 69 72 20 65 6e 64 73 20 61 66 74 65 72 pair ends after
1ec0: 20 6f 74 68 65 72 20 70 61 69 72 0a 09 09 09 09 other pair.....
1ed0: 09 23 20 6d 2d 2d 2d 2d 2d 6d 0a 09 09 09 09 09 .# m-----m......
1ee0: 23 20 6f 2d 2d 2d 6f 0a 09 09 09 09 09 6d 79 5f # o---o......my_
1ef0: 70 61 69 72 5b 30 5d 20 3d 20 6f 74 68 65 72 5f pair[0] = other_
1f00: 70 61 69 72 5b 31 5d 0a 09 09 09 09 09 23 20 74 pair[1]......# t
1f10: 72 69 6d 6d 69 6e 67 20 6d 79 20 70 61 69 72 20 rimming my pair
1f20: 62 79 20 6f 74 68 65 72 20 70 61 69 72 20 65 6e by other pair en
1f30: 64 0a 09 09 09 09 09 23 20 6d 2e 2e 2e 6d 2d 6d d......# m...m-m
1f40: 0a 09 09 09 09 09 23 20 6f 2d 2d 2d 6f 0a 09 09 ......# o---o...
1f50: 09 09 09 6f 74 68 65 72 5f 70 61 69 72 20 3d 20 ...other_pair =
1f60: 6f 74 68 65 72 2e 70 6f 70 28 29 0a 09 09 09 09 other.pop().....
1f70: 09 23 20 74 6f 73 73 69 6e 67 20 6f 75 74 20 6f .# tossing out o
1f80: 74 68 65 72 20 70 61 69 72 0a 09 09 09 09 09 69 ther pair......i
1f90: 66 20 6f 74 68 65 72 5f 70 61 69 72 5b 30 5d 20 f other_pair[0]
1fa0: 3d 3d 20 4e 6f 6e 65 3a 0a 09 09 09 09 09 09 23 == None:.......#
1fb0: 20 74 68 69 73 20 77 61 73 20 6c 61 73 74 20 6f this was last o
1fc0: 6e 65 20 2d 20 6d 79 20 70 61 69 72 20 67 6f 65 ne - my pair goe
1fd0: 73 20 74 6f 20 72 65 73 75 6c 74 0a 09 09 09 09 s to result.....
1fe0: 09 09 6e 65 77 5b 6d 79 5f 70 61 69 72 5b 30 5d ..new[my_pair[0]
1ff0: 5d 20 3d 20 6d 79 5f 70 61 69 72 5b 31 5d 0a 09 ] = my_pair[1]..
2000: 09 09 09 09 09 61 6c 6c 5f 70 61 72 74 73 5f 66 .....all_parts_f
2010: 6f 75 6e 64 20 3d 20 54 72 75 65 0a 09 09 77 68 ound = True...wh
2020: 69 6c 65 20 54 72 75 65 3a 0a 09 09 09 23 20 63 ile True:....# c
2030: 6f 70 79 20 61 6e 79 20 6c 65 66 74 6f 76 65 72 opy any leftover
2040: 20 69 6e 20 41 20 74 6f 20 6e 65 77 20 53 70 61 in A to new Spa
2050: 63 65 4d 61 70 0a 09 09 09 6d 79 5f 70 61 69 72 ceMap....my_pair
2060: 20 3d 20 73 65 6c 66 2e 70 6f 70 28 29 0a 09 09 = self.pop()...
2070: 09 69 66 20 6d 79 5f 70 61 69 72 5b 30 5d 20 3d .if my_pair[0] =
2080: 3d 20 4e 6f 6e 65 3a 0a 09 09 09 09 62 72 65 61 = None:.....brea
2090: 6b 0a 09 09 09 65 6c 73 65 3a 0a 09 09 09 09 6e k....else:.....n
20a0: 65 77 5b 6d 79 5f 70 61 69 72 5b 30 5d 5d 20 3d ew[my_pair[0]] =
20b0: 20 6d 79 5f 70 61 69 72 5b 31 5d 0a 09 09 73 65 my_pair[1]...se
20c0: 6c 66 2e 63 6c 65 61 72 28 29 0a 09 09 6f 74 68 lf.clear()...oth
20d0: 65 72 2e 63 6c 65 61 72 28 29 0a 09 09 72 65 74 er.clear()...ret
20e0: 75 72 6e 28 53 70 61 63 65 4d 61 70 28 6e 65 77 urn(SpaceMap(new
20f0: 2c 20 73 65 6c 66 2e 5f 5f 62 6f 74 74 6f 6d 2c , self.__bottom,
2100: 20 73 65 6c 66 2e 5f 5f 74 6f 70 29 29 0a 0a 09 self.__top))...
2110: 64 65 66 20 5f 5f 65 71 5f 5f 28 73 65 6c 66 2c def __eq__(self,
2120: 20 6f 74 68 65 72 29 3a 0a 09 09 27 27 27 43 6f other):...'''Co
2130: 6d 70 61 72 65 73 20 74 77 6f 20 73 70 61 63 65 mpares two space
2140: 20 6d 61 70 73 2e 27 27 27 0a 09 09 69 66 20 74 maps.'''...if t
2150: 79 70 65 28 6f 74 68 65 72 29 20 21 3d 20 53 70 ype(other) != Sp
2160: 61 63 65 4d 61 70 3a 0a 09 09 09 72 65 74 75 72 aceMap:....retur
2170: 6e 28 46 61 6c 73 65 29 0a 09 09 73 65 6c 66 2e n(False)...self.
2180: 72 65 77 69 6e 64 28 29 0a 09 09 6f 74 68 65 72 rewind()...other
2190: 2e 72 65 77 69 6e 64 28 29 0a 09 09 72 65 73 75 .rewind()...resu
21a0: 6c 74 20 3d 20 4e 6f 6e 65 0a 09 09 77 68 69 6c lt = None...whil
21b0: 65 20 54 72 75 65 3a 0a 09 09 09 74 68 69 73 20 e True:....this
21c0: 3d 20 73 65 6c 66 2e 70 6f 70 28 29 0a 09 09 09 = self.pop()....
21d0: 74 68 61 74 20 3d 20 6f 74 68 65 72 2e 70 6f 70 that = other.pop
21e0: 28 29 0a 09 09 09 69 66 20 74 68 69 73 20 21 3d ()....if this !=
21f0: 20 74 68 61 74 3a 0a 09 09 09 09 72 65 73 75 6c that:.....resul
2200: 74 20 3d 20 46 61 6c 73 65 0a 09 09 09 09 62 72 t = False.....br
2210: 65 61 6b 0a 09 09 09 69 66 20 74 68 69 73 20 3d eak....if this =
2220: 3d 20 5b 4e 6f 6e 65 2c 20 4e 6f 6e 65 5d 20 61 = [None, None] a
2230: 6e 64 20 74 68 61 74 20 3d 3d 20 5b 4e 6f 6e 65 nd that == [None
2240: 2c 20 4e 6f 6e 65 5d 3a 0a 09 09 09 09 72 65 73 , None]:.....res
2250: 75 6c 74 20 3d 20 54 72 75 65 0a 09 09 09 09 62 ult = True.....b
2260: 72 65 61 6b 0a 09 09 73 65 6c 66 2e 63 6c 65 61 reak...self.clea
2270: 72 28 29 0a 09 09 6f 74 68 65 72 2e 63 6c 65 61 r()...other.clea
2280: 72 28 29 0a 09 09 72 65 74 75 72 6e 28 72 65 73 r()...return(res
2290: 75 6c 74 29 0a 0a 09 64 65 66 20 5f 5f 6e 65 5f ult)...def __ne_
22a0: 5f 28 73 65 6c 66 2c 20 6f 74 68 65 72 29 3a 0a _(self, other):.
22b0: 09 09 72 65 74 75 72 6e 28 6e 6f 74 20 73 65 6c ..return(not sel
22c0: 66 20 3d 3d 20 6f 74 68 65 72 29 0a 0a 09 64 65 f == other)...de
22d0: 66 20 65 6e 64 28 73 65 6c 66 29 3a 0a 09 09 27 f end(self):...'
22e0: 27 27 52 65 74 75 72 6e 73 20 6c 61 73 74 20 6b ''Returns last k
22f0: 6e 6f 77 6e 20 70 6f 69 6e 74 2e 27 27 27 0a 09 nown point.'''..
2300: 09 65 6e 64 20 3d 20 4e 6f 6e 65 0a 09 09 73 65 .end = None...se
2310: 6c 66 2e 72 65 77 69 6e 64 28 29 0a 09 09 77 68 lf.rewind()...wh
2320: 69 6c 65 20 54 72 75 65 3a 0a 09 09 09 74 68 69 ile True:....thi
2330: 73 20 3d 20 73 65 6c 66 2e 70 6f 70 28 29 0a 09 s = self.pop()..
2340: 09 09 69 66 20 74 68 69 73 20 3d 3d 20 5b 4e 6f ..if this == [No
2350: 6e 65 2c 20 4e 6f 6e 65 5d 3a 0a 09 09 09 09 62 ne, None]:.....b
2360: 72 65 61 6b 0a 09 09 09 65 6c 69 66 20 65 6e 64 reak....elif end
2370: 20 3d 3d 20 4e 6f 6e 65 20 6f 72 20 74 68 69 73 == None or this
2380: 5b 31 5d 20 3e 20 65 6e 64 3a 0a 09 09 09 09 65 [1] > end:.....e
2390: 6e 64 20 3d 20 74 68 69 73 5b 31 5d 0a 09 09 73 nd = this[1]...s
23a0: 65 6c 66 2e 63 6c 65 61 72 28 29 0a 09 09 72 65 elf.clear()...re
23b0: 74 75 72 6e 28 65 6e 64 29 0a 0a 09 64 65 66 20 turn(end)...def
23c0: 5f 5f 6c 65 6e 5f 5f 28 73 65 6c 66 29 3a 0a 09 __len__(self):..
23d0: 09 72 65 74 75 72 6e 28 6c 65 6e 28 73 65 6c 66 .return(len(self
23e0: 2e 5f 5f 70 61 69 72 73 29 29 0a 0a 09 64 65 66 .__pairs))...def
23f0: 20 6d 61 78 28 73 65 6c 66 29 3a 0a 09 09 72 65 max(self):...re
2400: 73 75 6c 74 20 3d 20 4e 6f 6e 65 0a 09 09 66 6f sult = None...fo
2410: 72 20 6c 61 73 74 20 69 6e 20 73 65 6c 66 2e 5f r last in self._
2420: 5f 70 61 69 72 73 2e 69 74 65 72 76 61 6c 75 65 _pairs.itervalue
2430: 73 28 29 3a 0a 09 09 09 69 66 20 72 65 73 75 6c s():....if resul
2440: 74 20 3d 3d 20 4e 6f 6e 65 20 6f 72 20 72 65 73 t == None or res
2450: 75 6c 74 20 3c 20 6c 61 73 74 3a 0a 09 09 09 09 ult < last:.....
2460: 72 65 73 75 6c 74 20 3d 20 6c 61 73 74 0a 09 09 result = last...
2470: 72 65 74 75 72 6e 28 72 65 73 75 6c 74 29 0a return(result).