Artifact
292e80c5470190759af7add959ed51e4eb66d73a23e01dd484b4d69dc112de85:
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 20 61 6e 64 20 70 61 69 72 5b 31 5d 20 3e 20 ] and pair[1] >
06a0: 73 65 6c 66 2e 5f 5f 70 61 69 72 73 5b 6c 61 73 self.__pairs[las
06b0: 74 5f 70 61 69 72 5d 3a 0a 09 09 09 09 73 65 6c t_pair]:.....sel
06c0: 66 2e 5f 5f 70 61 69 72 73 5b 6c 61 73 74 5f 70 f.__pairs[last_p
06d0: 61 69 72 5d 20 3d 20 70 61 69 72 5b 31 5d 0a 09 air] = pair[1]..
06e0: 09 09 09 64 65 6c 28 73 65 6c 66 2e 5f 5f 70 61 ...del(self.__pa
06f0: 69 72 73 5b 70 61 69 72 5b 30 5d 5d 29 0a 09 09 irs[pair[0]])...
0700: 09 65 6c 73 65 3a 0a 09 09 09 09 6c 61 73 74 5f .else:.....last_
0710: 70 61 69 72 20 3d 20 70 61 69 72 5b 30 5d 0a 09 pair = pair[0]..
0720: 09 73 65 6c 66 2e 63 6c 65 61 72 28 29 0a 0a 09 .self.clear()...
0730: 64 65 66 20 72 65 77 69 6e 64 28 73 65 6c 66 29 def rewind(self)
0740: 3a 0a 09 09 27 27 27 52 65 69 6e 69 74 69 61 6c :...'''Reinitial
0750: 69 73 65 73 20 69 6e 74 65 72 6e 61 6c 20 6f 72 ises internal or
0760: 64 65 72 65 64 20 6c 69 73 74 20 6f 66 20 72 61 dered list of ra
0770: 6e 67 65 73 2e 27 27 27 0a 09 09 73 65 6c 66 2e nges.'''...self.
0780: 5f 5f 77 61 6c 6b 5f 6c 69 73 74 20 3d 20 6c 69 __walk_list = li
0790: 73 74 28 73 65 6c 66 2e 5f 5f 70 61 69 72 73 2e st(self.__pairs.
07a0: 6b 65 79 73 28 29 29 0a 09 09 73 65 6c 66 2e 5f keys())...self._
07b0: 5f 77 61 6c 6b 5f 6c 69 73 74 2e 73 6f 72 74 28 _walk_list.sort(
07c0: 29 0a 0a 09 64 65 66 20 63 6c 65 61 72 28 73 65 )...def clear(se
07d0: 6c 66 29 3a 0a 09 09 27 27 27 43 6c 65 61 72 73 lf):...'''Clears
07e0: 20 69 6e 74 65 72 6e 61 6c 20 6f 72 64 65 72 65 internal ordere
07f0: 64 20 6c 69 73 74 20 6f 66 20 72 61 6e 67 65 73 d list of ranges
0800: 2e 27 27 27 0a 09 09 73 65 6c 66 2e 5f 5f 77 61 .'''...self.__wa
0810: 6c 6b 5f 6c 69 73 74 20 3d 20 4e 6f 6e 65 0a 0a lk_list = None..
0820: 09 64 65 66 20 70 6f 70 28 73 65 6c 66 29 3a 0a .def pop(self):.
0830: 09 09 27 27 27 52 65 74 75 72 6e 73 20 6e 65 78 ..'''Returns nex
0840: 74 20 72 61 6e 67 65 20 66 72 6f 6d 20 6f 72 64 t range from ord
0850: 65 72 65 64 20 6c 69 73 74 20 6f 66 20 72 61 6e ered list of ran
0860: 67 65 73 2e 27 27 27 0a 09 09 69 66 20 73 65 6c ges.'''...if sel
0870: 66 2e 5f 5f 77 61 6c 6b 5f 6c 69 73 74 20 21 3d f.__walk_list !=
0880: 20 4e 6f 6e 65 3a 0a 09 09 09 69 66 20 6c 65 6e None:....if len
0890: 28 73 65 6c 66 2e 5f 5f 77 61 6c 6b 5f 6c 69 73 (self.__walk_lis
08a0: 74 29 20 3e 20 30 3a 0a 09 09 09 09 6e 65 78 74 t) > 0:.....next
08b0: 20 3d 20 73 65 6c 66 2e 5f 5f 77 61 6c 6b 5f 6c = self.__walk_l
08c0: 69 73 74 2e 70 6f 70 28 30 29 0a 09 09 09 09 72 ist.pop(0).....r
08d0: 65 74 75 72 6e 28 5b 6e 65 78 74 2c 20 73 65 6c eturn([next, sel
08e0: 66 2e 5f 5f 70 61 69 72 73 5b 6e 65 78 74 5d 5d f.__pairs[next]]
08f0: 29 0a 09 09 72 65 74 75 72 6e 28 5b 4e 6f 6e 65 )...return([None
0900: 2c 20 4e 6f 6e 65 5d 29 0a 0a 09 64 65 66 20 5f , None])...def _
0910: 5f 72 65 70 72 5f 5f 28 73 65 6c 66 29 3a 0a 09 _repr__(self):..
0920: 09 27 27 27 52 65 74 75 72 6e 73 20 74 68 65 20 .'''Returns the
0930: 69 6e 6e 65 72 20 64 69 63 74 20 77 69 74 68 20 inner dict with
0940: 72 61 6e 67 65 73 2e 27 27 27 0a 09 09 72 65 74 ranges.'''...ret
0950: 75 72 6e 28 72 65 70 72 28 73 65 6c 66 2e 5f 5f urn(repr(self.__
0960: 70 61 69 72 73 29 29 0a 0a 09 64 65 66 20 5f 5f pairs))...def __
0970: 61 6e 64 5f 5f 28 73 65 6c 66 2c 20 6f 74 68 65 and__(self, othe
0980: 72 29 3a 0a 09 09 27 27 27 52 65 74 75 72 6e 73 r):...'''Returns
0990: 20 6e 65 77 20 73 70 61 63 65 20 6d 61 70 20 77 new space map w
09a0: 69 74 68 20 72 61 6e 67 65 73 20 74 68 61 74 20 ith ranges that
09b0: 61 70 70 65 61 72 73 20 62 6f 74 68 20 69 6e 20 appears both in
09c0: 41 20 61 6e 64 20 42 2e 27 27 27 0a 09 09 69 66 A and B.'''...if
09d0: 20 74 79 70 65 28 6f 74 68 65 72 29 20 21 3d 20 type(other) !=
09e0: 53 70 61 63 65 4d 61 70 3a 0a 09 09 09 72 65 74 SpaceMap:....ret
09f0: 75 72 6e 28 46 61 6c 73 65 29 0a 09 09 6e 65 77 urn(False)...new
0a00: 20 3d 20 7b 7d 0a 09 09 73 65 6c 66 2e 72 65 77 = {}...self.rew
0a10: 69 6e 64 28 29 0a 09 09 6f 74 68 65 72 2e 72 65 ind()...other.re
0a20: 77 69 6e 64 28 29 0a 09 09 6d 79 5f 70 61 69 72 wind()...my_pair
0a30: 20 3d 20 73 65 6c 66 2e 70 6f 70 28 29 0a 09 09 = self.pop()...
0a40: 6f 74 68 65 72 5f 70 61 69 72 20 3d 20 6f 74 68 other_pair = oth
0a50: 65 72 2e 70 6f 70 28 29 0a 09 09 23 20 69 66 20 er.pop()...# if
0a60: 74 68 65 72 65 20 61 72 65 20 6e 6f 20 70 61 69 there are no pai
0a70: 72 73 20 69 6e 20 42 20 2d 20 77 65 20 68 61 76 rs in B - we hav
0a80: 65 20 6e 6f 74 68 69 6e 67 20 74 6f 20 64 6f 0a e nothing to do.
0a90: 09 09 69 66 20 6f 74 68 65 72 5f 70 61 69 72 5b ..if other_pair[
0aa0: 30 5d 20 3d 3d 20 4e 6f 6e 65 20 6f 72 20 6d 79 0] == None or my
0ab0: 5f 70 61 69 72 5b 30 5d 20 3d 3d 20 4e 6f 6e 65 _pair[0] == None
0ac0: 3a 0a 09 09 09 61 6c 6c 5f 70 61 72 74 73 5f 66 :....all_parts_f
0ad0: 6f 75 6e 64 20 3d 20 54 72 75 65 0a 09 09 65 6c ound = True...el
0ae0: 73 65 3a 0a 09 09 09 61 6c 6c 5f 70 61 72 74 73 se:....all_parts
0af0: 5f 66 6f 75 6e 64 20 3d 20 46 61 6c 73 65 0a 09 _found = False..
0b00: 09 77 68 69 6c 65 20 6e 6f 74 20 61 6c 6c 5f 70 .while not all_p
0b10: 61 72 74 73 5f 66 6f 75 6e 64 3a 0a 09 09 09 69 arts_found:....i
0b20: 66 20 6d 79 5f 70 61 69 72 5b 30 5d 20 3e 20 6f f my_pair[0] > o
0b30: 74 68 65 72 5f 70 61 69 72 5b 30 5d 3a 0a 09 09 ther_pair[0]:...
0b40: 09 09 23 20 77 68 65 6e 20 6d 79 20 70 61 69 72 ..# when my pair
0b50: 20 73 74 61 72 74 73 20 61 66 74 65 72 20 6f 74 starts after ot
0b60: 68 65 72 20 70 61 69 72 20 73 74 61 72 74 73 0a her pair starts.
0b70: 09 09 09 09 23 20 20 6d 2d 2d 2d 0a 09 09 09 09 ....# m---.....
0b80: 23 20 6f 2d 2d 2d 0a 09 09 09 09 69 66 20 6d 79 # o---.....if my
0b90: 5f 70 61 69 72 5b 30 5d 20 3e 20 6f 74 68 65 72 _pair[0] > other
0ba0: 5f 70 61 69 72 5b 31 5d 3a 0a 09 09 09 09 09 23 _pair[1]:......#
0bb0: 20 77 68 65 6e 20 6d 79 20 70 61 69 72 20 73 74 when my pair st
0bc0: 61 72 74 73 20 61 66 74 65 72 20 6f 74 68 65 72 arts after other
0bd0: 20 70 61 69 72 20 65 6e 64 73 0a 09 09 09 09 09 pair ends......
0be0: 23 20 20 20 20 20 20 20 6d 2d 2d 2d 0a 09 09 09 # m---....
0bf0: 09 09 23 20 6f 2d 2d 2d 6f 0a 09 09 09 09 09 6f ..# o---o......o
0c00: 74 68 65 72 5f 70 61 69 72 20 3d 20 6f 74 68 65 ther_pair = othe
0c10: 72 2e 70 6f 70 28 29 0a 09 09 09 09 09 23 20 74 r.pop()......# t
0c20: 6f 73 73 69 6e 67 20 6f 75 74 20 6f 74 68 65 72 ossing out other
0c30: 20 70 61 69 72 0a 09 09 09 09 09 69 66 20 6f 74 pair......if ot
0c40: 68 65 72 5f 70 61 69 72 5b 30 5d 20 3d 3d 20 4e her_pair[0] == N
0c50: 6f 6e 65 3a 0a 09 09 09 09 09 09 61 6c 6c 5f 70 one:.......all_p
0c60: 61 72 74 73 5f 66 6f 75 6e 64 20 3d 20 54 72 75 arts_found = Tru
0c70: 65 0a 09 09 09 09 65 6c 73 65 3a 0a 09 09 09 09 e.....else:.....
0c80: 09 23 20 77 68 65 6e 20 6d 79 20 70 61 69 72 20 .# when my pair
0c90: 73 74 61 72 74 73 20 62 65 66 6f 72 65 20 6f 74 starts before ot
0ca0: 68 65 72 20 70 61 69 72 20 65 6e 64 73 0a 09 09 her pair ends...
0cb0: 09 09 09 23 20 20 20 20 6d 2d 2d 2d 20 7c 20 20 ...# m--- |
0cc0: 20 20 20 6d 2d 2d 2d 0a 09 09 09 09 09 23 20 6f m---......# o
0cd0: 2d 2d 2d 6f 20 20 20 7c 20 6f 2d 2d 2d 6f 0a 09 ---o | o---o..
0ce0: 09 09 09 09 69 66 20 6d 79 5f 70 61 69 72 5b 31 ....if my_pair[1
0cf0: 5d 20 3e 20 6f 74 68 65 72 5f 70 61 69 72 5b 31 ] > other_pair[1
0d00: 5d 3a 0a 09 09 09 09 09 09 23 20 77 68 65 6e 20 ]:.......# when
0d10: 6d 79 20 70 61 69 72 20 65 6e 64 73 20 61 66 74 my pair ends aft
0d20: 65 72 20 6f 74 68 65 72 20 70 61 69 72 20 65 6e er other pair en
0d30: 64 73 0a 09 09 09 09 09 09 23 20 20 20 20 6d 2d ds.......# m-
0d40: 2d 2d 6d 20 7c 20 20 20 20 20 6d 2d 2d 2d 6d 0a --m | m---m.
0d50: 09 09 09 09 09 09 23 20 6f 2d 2d 2d 6f 20 20 20 ......# o---o
0d60: 20 7c 20 6f 2d 2d 2d 6f 0a 09 09 09 09 09 09 6f | o---o.......o
0d70: 74 68 65 72 5f 70 61 69 72 5b 30 5d 20 3d 20 6d ther_pair[0] = m
0d80: 79 5f 70 61 69 72 5b 30 5d 0a 09 09 09 09 09 09 y_pair[0].......
0d90: 23 20 74 72 69 6d 6d 69 6e 67 20 6f 74 68 65 72 # trimming other
0da0: 20 70 61 69 72 20 62 79 20 6d 79 20 70 61 69 72 pair by my pair
0db0: 20 73 74 61 72 74 0a 09 09 09 09 09 09 23 20 20 start.......#
0dc0: 20 6d 2d 2d 2d 6d 0a 09 09 09 09 09 09 23 20 6f m---m.......# o
0dd0: 2e 6f 2d 6f 0a 09 09 09 09 09 65 6c 73 65 3a 0a .o-o......else:.
0de0: 09 09 09 09 09 09 23 20 77 68 65 6e 20 6d 79 20 ......# when my
0df0: 70 61 69 72 20 65 6e 64 73 20 62 65 66 6f 72 65 pair ends before
0e00: 20 6f 74 68 65 72 20 70 61 69 72 20 65 6e 64 73 other pair ends
0e10: 0a 09 09 09 09 09 09 23 20 20 6d 2d 2d 2d 6d 0a .......# m---m.
0e20: 09 09 09 09 09 09 23 20 6f 2d 2d 2d 2d 2d 6f 0a ......# o-----o.
0e30: 09 09 09 09 09 09 6e 65 77 5b 6d 79 5f 70 61 69 ......new[my_pai
0e40: 72 5b 30 5d 5d 20 3d 20 6d 79 5f 70 61 69 72 5b r[0]] = my_pair[
0e50: 31 5d 0a 09 09 09 09 09 09 23 20 6d 79 20 70 61 1].......# my pa
0e60: 69 72 20 69 73 20 63 6f 76 65 72 65 64 20 61 6e ir is covered an
0e70: 64 20 73 68 6f 75 6c 64 20 62 65 20 61 64 64 65 d should be adde
0e80: 64 20 74 6f 20 72 65 73 75 6c 74 0a 09 09 09 09 d to result.....
0e90: 09 09 6d 79 5f 70 61 69 72 20 3d 20 73 65 6c 66 ..my_pair = self
0ea0: 2e 70 6f 70 28 29 0a 09 09 09 09 09 09 23 20 74 .pop().......# t
0eb0: 6f 73 73 69 6e 67 20 6f 75 74 20 6d 79 20 70 61 ossing out my pa
0ec0: 69 72 0a 09 09 09 09 09 09 69 66 20 6d 79 5f 70 ir.......if my_p
0ed0: 61 69 72 5b 30 5d 20 3d 3d 20 4e 6f 6e 65 3a 0a air[0] == None:.
0ee0: 09 09 09 09 09 09 09 61 6c 6c 5f 70 61 72 74 73 .......all_parts
0ef0: 5f 66 6f 75 6e 64 20 3d 20 54 72 75 65 0a 09 09 _found = True...
0f00: 09 65 6c 69 66 20 6d 79 5f 70 61 69 72 5b 30 5d .elif my_pair[0]
0f10: 20 3c 20 6f 74 68 65 72 5f 70 61 69 72 5b 30 5d < other_pair[0]
0f20: 3a 0a 09 09 09 09 23 20 77 68 65 6e 20 6d 79 20 :.....# when my
0f30: 70 61 69 72 20 73 74 61 72 74 73 20 62 65 66 6f pair starts befo
0f40: 72 65 20 6f 74 68 65 72 20 6f 6e 65 0a 09 09 09 re other one....
0f50: 09 23 20 6d 2d 2d 2d 0a 09 09 09 09 23 20 20 6f .# m---.....# o
0f60: 2d 2d 2d 0a 09 09 09 09 69 66 20 6d 79 5f 70 61 ---.....if my_pa
0f70: 69 72 5b 31 5d 20 3c 20 6f 74 68 65 72 5f 70 61 ir[1] < other_pa
0f80: 69 72 5b 30 5d 3a 0a 09 09 09 09 09 23 20 77 68 ir[0]:......# wh
0f90: 65 6e 20 6d 79 20 70 61 69 72 20 65 6e 64 73 20 en my pair ends
0fa0: 62 65 66 6f 72 65 20 6f 74 68 65 72 20 70 61 69 before other pai
0fb0: 72 20 73 74 61 72 74 73 0a 09 09 09 09 09 23 20 r starts......#
0fc0: 6d 2d 2d 2d 6d 0a 09 09 09 09 09 23 20 20 20 20 m---m......#
0fd0: 20 20 20 6f 2d 2d 2d 0a 09 09 09 09 09 6d 79 5f o---......my_
0fe0: 70 61 69 72 20 3d 20 73 65 6c 66 2e 70 6f 70 28 pair = self.pop(
0ff0: 29 0a 09 09 09 09 09 23 20 74 6f 73 73 69 6e 67 )......# tossing
1000: 20 6f 75 74 20 6d 79 20 70 61 69 72 0a 09 09 09 out my pair....
1010: 09 09 69 66 20 6d 79 5f 70 61 69 72 5b 30 5d 20 ..if my_pair[0]
1020: 3d 3d 20 4e 6f 6e 65 3a 0a 09 09 09 09 09 09 61 == None:.......a
1030: 6c 6c 5f 70 61 72 74 73 5f 66 6f 75 6e 64 20 3d ll_parts_found =
1040: 20 54 72 75 65 0a 09 09 09 09 65 6c 73 65 3a 0a True.....else:.
1050: 09 09 09 09 09 23 20 77 68 65 6e 20 6d 79 20 70 .....# when my p
1060: 61 69 72 20 65 6e 64 73 20 62 65 66 6f 72 65 20 air ends before
1070: 6f 74 68 65 72 20 70 61 69 72 20 73 74 61 72 74 other pair start
1080: 73 0a 09 09 09 09 09 23 20 6d 2d 2d 2d 6d 0a 09 s......# m---m..
1090: 09 09 09 09 23 20 20 20 6f 2d 2d 2d 0a 09 09 09 ....# o---....
10a0: 09 09 6d 79 5f 70 61 69 72 5b 30 5d 20 3d 20 6f ..my_pair[0] = o
10b0: 74 68 65 72 5f 70 61 69 72 5b 30 5d 0a 09 09 09 ther_pair[0]....
10c0: 09 09 23 20 74 72 69 6d 6d 69 6e 67 20 6d 79 20 ..# trimming my
10d0: 70 61 69 72 20 62 79 20 6f 74 68 65 72 20 70 61 pair by other pa
10e0: 69 72 20 73 74 61 72 74 0a 09 09 09 09 09 23 20 ir start......#
10f0: 6d 2e 6d 2d 6d 0a 09 09 09 09 09 23 20 20 20 6f m.m-m......# o
1100: 2d 2d 2d 0a 09 09 09 65 6c 73 65 3a 0a 09 09 09 ---....else:....
1110: 09 23 20 77 68 65 6e 20 62 6f 74 68 20 70 61 69 .# when both pai
1120: 72 73 20 73 74 61 72 74 73 20 73 69 6d 75 6c 74 rs starts simult
1130: 61 6e 65 6f 75 73 6c 79 0a 09 09 09 09 23 20 6d aneously.....# m
1140: 2d 2d 2d 0a 09 09 09 09 23 20 6f 2d 2d 2d 0a 09 ---.....# o---..
1150: 09 09 09 69 66 20 6d 79 5f 70 61 69 72 5b 31 5d ...if my_pair[1]
1160: 20 3c 20 6f 74 68 65 72 5f 70 61 69 72 5b 31 5d < other_pair[1]
1170: 3a 0a 09 09 09 09 09 23 20 77 68 65 6e 20 6d 79 :......# when my
1180: 20 70 61 69 72 20 65 6e 64 73 20 62 65 66 6f 72 pair ends befor
1190: 65 20 6f 74 68 65 72 20 70 61 69 72 0a 09 09 09 e other pair....
11a0: 09 09 23 20 6d 2d 2d 2d 6d 0a 09 09 09 09 09 23 ..# m---m......#
11b0: 20 6f 2d 2d 2d 2d 2d 6f 0a 09 09 09 09 09 6e 65 o-----o......ne
11c0: 77 5b 6d 79 5f 70 61 69 72 5b 30 5d 5d 20 3d 20 w[my_pair[0]] =
11d0: 6d 79 5f 70 61 69 72 5b 31 5d 0a 09 09 09 09 09 my_pair[1]......
11e0: 23 20 6d 79 20 70 61 69 72 20 69 73 20 63 6f 76 # my pair is cov
11f0: 65 72 65 64 20 61 6e 64 20 73 68 6f 75 6c 64 20 ered and should
1200: 62 65 20 61 64 64 65 64 20 74 6f 20 72 65 73 75 be added to resu
1210: 6c 74 0a 09 09 09 09 09 6d 79 5f 70 61 69 72 20 lt......my_pair
1220: 3d 20 73 65 6c 66 2e 70 6f 70 28 29 0a 09 09 09 = self.pop()....
1230: 09 09 23 20 74 6f 73 73 69 6e 67 20 6f 75 74 20 ..# tossing out
1240: 6d 79 20 70 61 69 72 0a 09 09 09 09 09 69 66 20 my pair......if
1250: 6d 79 5f 70 61 69 72 5b 30 5d 20 3d 3d 20 4e 6f my_pair[0] == No
1260: 6e 65 3a 0a 09 09 09 09 09 09 61 6c 6c 5f 70 61 ne:.......all_pa
1270: 72 74 73 5f 66 6f 75 6e 64 20 3d 20 54 72 75 65 rts_found = True
1280: 0a 09 09 09 09 65 6c 73 65 3a 0a 09 09 09 09 09 .....else:......
1290: 23 20 77 68 65 6e 20 6d 79 20 70 61 69 72 20 65 # when my pair e
12a0: 6e 64 73 20 61 66 74 65 72 20 6f 74 68 65 72 20 nds after other
12b0: 70 61 69 72 0a 09 09 09 09 09 23 20 6d 2d 2d 2d pair......# m---
12c0: 2d 2d 6d 0a 09 09 09 09 09 23 20 6f 2d 2d 2d 6f --m......# o---o
12d0: 0a 09 09 09 09 09 6e 65 77 5b 6d 79 5f 70 61 69 ......new[my_pai
12e0: 72 5b 30 5d 5d 20 3d 20 6f 74 68 65 72 5f 70 61 r[0]] = other_pa
12f0: 69 72 5b 31 5d 0a 09 09 09 09 09 23 20 70 61 72 ir[1]......# par
1300: 74 20 6f 66 20 6d 79 20 70 61 69 72 20 69 73 20 t of my pair is
1310: 63 6f 76 65 72 65 64 20 61 6e 64 20 73 68 6f 75 covered and shou
1320: 6c 64 20 62 65 20 61 64 64 65 64 20 74 6f 20 72 ld be added to r
1330: 65 73 75 6c 74 0a 09 09 09 09 09 6f 74 68 65 72 esult......other
1340: 5f 70 61 69 72 20 3d 20 6f 74 68 65 72 2e 70 6f _pair = other.po
1350: 70 28 29 0a 09 09 09 09 09 23 20 74 6f 73 73 69 p()......# tossi
1360: 6e 67 20 6f 75 74 20 6f 74 68 65 72 20 70 61 69 ng out other pai
1370: 72 0a 09 09 09 09 09 69 66 20 6f 74 68 65 72 5f r......if other_
1380: 70 61 69 72 5b 30 5d 20 3d 3d 20 4e 6f 6e 65 3a pair[0] == None:
1390: 0a 09 09 09 09 09 09 61 6c 6c 5f 70 61 72 74 73 .......all_parts
13a0: 5f 66 6f 75 6e 64 20 3d 20 54 72 75 65 0a 09 09 _found = True...
13b0: 73 65 6c 66 2e 63 6c 65 61 72 28 29 0a 09 09 6f self.clear()...o
13c0: 74 68 65 72 2e 63 6c 65 61 72 28 29 0a 09 09 72 ther.clear()...r
13d0: 65 74 75 72 6e 28 53 70 61 63 65 4d 61 70 28 6e eturn(SpaceMap(n
13e0: 65 77 2c 20 73 65 6c 66 2e 5f 5f 62 6f 74 74 6f ew, self.__botto
13f0: 6d 2c 20 73 65 6c 66 2e 5f 5f 74 6f 70 29 29 0a m, self.__top)).
1400: 0a 09 64 65 66 20 5f 5f 73 75 62 5f 5f 28 73 65 ..def __sub__(se
1410: 6c 66 2c 20 6f 74 68 65 72 29 3a 0a 09 09 27 27 lf, other):...''
1420: 27 52 65 74 75 72 6e 73 20 6e 65 77 20 73 70 61 'Returns new spa
1430: 63 65 20 6d 61 70 20 77 69 74 68 20 72 61 6e 67 ce map with rang
1440: 65 73 20 69 6e 20 41 20 6e 6f 74 20 63 6f 76 65 es in A not cove
1450: 72 65 64 20 62 79 20 42 2e 27 27 27 0a 09 09 69 red by B.'''...i
1460: 66 20 74 79 70 65 28 6f 74 68 65 72 29 20 21 3d f type(other) !=
1470: 20 53 70 61 63 65 4d 61 70 3a 0a 09 09 09 72 65 SpaceMap:....re
1480: 74 75 72 6e 28 46 61 6c 73 65 29 0a 09 09 6e 65 turn(False)...ne
1490: 77 20 3d 20 7b 7d 0a 09 09 73 65 6c 66 2e 72 65 w = {}...self.re
14a0: 77 69 6e 64 28 29 0a 09 09 6f 74 68 65 72 2e 72 wind()...other.r
14b0: 65 77 69 6e 64 28 29 0a 09 09 6d 79 5f 70 61 69 ewind()...my_pai
14c0: 72 20 3d 20 73 65 6c 66 2e 70 6f 70 28 29 0a 09 r = self.pop()..
14d0: 09 6f 74 68 65 72 5f 70 61 69 72 20 3d 20 6f 74 .other_pair = ot
14e0: 68 65 72 2e 70 6f 70 28 29 0a 09 09 23 20 69 66 her.pop()...# if
14f0: 20 74 68 65 72 65 20 61 72 65 20 6e 6f 20 70 61 there are no pa
1500: 69 72 73 20 69 6e 20 42 20 2d 20 63 6f 70 79 20 irs in B - copy
1510: 74 68 69 73 20 6f 6e 65 20 74 6f 20 6e 65 77 20 this one to new
1520: 53 70 61 63 65 4d 61 70 0a 09 09 69 66 20 6f 74 SpaceMap...if ot
1530: 68 65 72 5f 70 61 69 72 5b 30 5d 20 3d 3d 20 4e her_pair[0] == N
1540: 6f 6e 65 3a 0a 09 09 09 6e 65 77 5b 6d 79 5f 70 one:....new[my_p
1550: 61 69 72 5b 30 5d 5d 20 3d 20 6d 79 5f 70 61 69 air[0]] = my_pai
1560: 72 5b 31 5d 0a 09 09 09 61 6c 6c 5f 70 61 72 74 r[1]....all_part
1570: 73 5f 66 6f 75 6e 64 20 3d 20 54 72 75 65 0a 09 s_found = True..
1580: 09 65 6c 69 66 20 6d 79 5f 70 61 69 72 5b 30 5d .elif my_pair[0]
1590: 20 3d 3d 20 4e 6f 6e 65 3a 0a 09 09 09 61 6c 6c == None:....all
15a0: 5f 70 61 72 74 73 5f 66 6f 75 6e 64 20 3d 20 54 _parts_found = T
15b0: 72 75 65 0a 09 09 65 6c 73 65 3a 0a 09 09 09 61 rue...else:....a
15c0: 6c 6c 5f 70 61 72 74 73 5f 66 6f 75 6e 64 20 3d ll_parts_found =
15d0: 20 46 61 6c 73 65 0a 09 09 77 68 69 6c 65 20 6e False...while n
15e0: 6f 74 20 61 6c 6c 5f 70 61 72 74 73 5f 66 6f 75 ot all_parts_fou
15f0: 6e 64 3a 0a 09 09 09 69 66 20 6d 79 5f 70 61 69 nd:....if my_pai
1600: 72 5b 30 5d 20 3e 20 6f 74 68 65 72 5f 70 61 69 r[0] > other_pai
1610: 72 5b 30 5d 3a 0a 09 09 09 09 23 20 77 68 65 6e r[0]:.....# when
1620: 20 6d 79 20 70 61 69 72 20 73 74 61 72 74 73 20 my pair starts
1630: 61 66 74 65 72 20 6f 74 68 65 72 20 70 61 69 72 after other pair
1640: 20 73 74 61 72 74 73 0a 09 09 09 09 23 20 20 6d starts.....# m
1650: 2d 2d 2d 0a 09 09 09 09 23 20 6f 2d 2d 2d 0a 09 ---.....# o---..
1660: 09 09 09 69 66 20 6d 79 5f 70 61 69 72 5b 30 5d ...if my_pair[0]
1670: 20 3e 20 6f 74 68 65 72 5f 70 61 69 72 5b 31 5d > other_pair[1]
1680: 3a 0a 09 09 09 09 09 23 20 77 68 65 6e 20 6d 79 :......# when my
1690: 20 70 61 69 72 20 73 74 61 72 74 73 20 61 66 74 pair starts aft
16a0: 65 72 20 6f 74 68 65 72 20 70 61 69 72 20 65 6e er other pair en
16b0: 64 73 0a 09 09 09 09 09 23 20 20 20 20 20 20 20 ds......#
16c0: 6d 2d 2d 2d 0a 09 09 09 09 09 23 20 6f 2d 2d 2d m---......# o---
16d0: 6f 0a 09 09 09 09 09 6f 74 68 65 72 5f 70 61 69 o......other_pai
16e0: 72 20 3d 20 6f 74 68 65 72 2e 70 6f 70 28 29 0a r = other.pop().
16f0: 09 09 09 09 09 23 20 74 6f 73 73 69 6e 67 20 6f .....# tossing o
1700: 75 74 20 6f 74 68 65 72 20 70 61 69 72 0a 09 09 ut other pair...
1710: 09 09 09 69 66 20 6f 74 68 65 72 5f 70 61 69 72 ...if other_pair
1720: 5b 30 5d 20 3d 3d 20 4e 6f 6e 65 3a 0a 09 09 09 [0] == None:....
1730: 09 09 09 23 20 74 68 69 73 20 77 61 73 20 6c 61 ...# this was la
1740: 73 74 20 6f 6e 65 20 2d 20 6d 79 20 70 61 69 72 st one - my pair
1750: 20 67 6f 65 73 20 74 6f 20 72 65 73 75 6c 74 0a goes to result.
1760: 09 09 09 09 09 09 6e 65 77 5b 6d 79 5f 70 61 69 ......new[my_pai
1770: 72 5b 30 5d 5d 20 3d 20 6d 79 5f 70 61 69 72 5b r[0]] = my_pair[
1780: 31 5d 0a 09 09 09 09 09 09 61 6c 6c 5f 70 61 72 1].......all_par
1790: 74 73 5f 66 6f 75 6e 64 20 3d 20 54 72 75 65 0a ts_found = True.
17a0: 09 09 09 09 65 6c 73 65 3a 0a 09 09 09 09 09 23 ....else:......#
17b0: 20 77 68 65 6e 20 6d 79 20 70 61 69 72 20 73 74 when my pair st
17c0: 61 72 74 73 20 62 65 66 6f 72 65 20 6f 74 68 65 arts before othe
17d0: 72 20 70 61 69 72 20 65 6e 64 73 0a 09 09 09 09 r pair ends.....
17e0: 09 23 20 20 20 20 6d 2d 2d 2d 20 7c 20 20 20 20 .# m--- |
17f0: 20 6d 2d 2d 2d 0a 09 09 09 09 09 23 20 6f 2d 2d m---......# o--
1800: 2d 6f 20 20 20 7c 20 6f 2d 2d 2d 6f 0a 09 09 09 -o | o---o....
1810: 09 09 69 66 20 6d 79 5f 70 61 69 72 5b 31 5d 20 ..if my_pair[1]
1820: 3e 20 6f 74 68 65 72 5f 70 61 69 72 5b 31 5d 3a > other_pair[1]:
1830: 0a 09 09 09 09 09 09 23 20 77 68 65 6e 20 6d 79 .......# when my
1840: 20 70 61 69 72 20 65 6e 64 73 20 61 66 74 65 72 pair ends after
1850: 20 6f 74 68 65 72 20 70 61 69 72 20 65 6e 64 73 other pair ends
1860: 0a 09 09 09 09 09 09 23 20 20 20 20 6d 2d 2d 2d .......# m---
1870: 6d 20 7c 20 20 20 20 20 6d 2d 2d 2d 6d 0a 09 09 m | m---m...
1880: 09 09 09 09 23 20 6f 2d 2d 2d 6f 20 20 20 20 7c ....# o---o |
1890: 20 6f 2d 2d 2d 6f 0a 09 09 09 09 09 09 6d 79 5f o---o.......my_
18a0: 70 61 69 72 5b 30 5d 20 3d 20 6f 74 68 65 72 5f pair[0] = other_
18b0: 70 61 69 72 5b 31 5d 0a 09 09 09 09 09 09 23 20 pair[1].......#
18c0: 74 72 69 6d 6d 69 6e 67 20 6d 79 20 70 61 69 72 trimming my pair
18d0: 20 62 79 20 6f 74 68 65 72 20 70 61 69 72 20 65 by other pair e
18e0: 6e 64 0a 09 09 09 09 09 09 23 20 20 20 6d 2e 6d nd.......# m.m
18f0: 2d 6d 0a 09 09 09 09 09 09 23 20 6f 2d 2d 2d 6f -m.......# o---o
1900: 0a 09 09 09 09 09 09 6f 74 68 65 72 5f 70 61 69 .......other_pai
1910: 72 20 3d 20 6f 74 68 65 72 2e 70 6f 70 28 29 0a r = other.pop().
1920: 09 09 09 09 09 09 23 20 74 6f 73 73 69 6e 67 20 ......# tossing
1930: 6f 75 74 20 6f 74 68 65 72 20 70 61 69 72 0a 09 out other pair..
1940: 09 09 09 09 09 69 66 20 6f 74 68 65 72 5f 70 61 .....if other_pa
1950: 69 72 5b 30 5d 20 3d 3d 20 4e 6f 6e 65 3a 0a 09 ir[0] == None:..
1960: 09 09 09 09 09 23 20 74 68 69 73 20 77 61 73 20 .....# this was
1970: 6c 61 73 74 20 6f 6e 65 20 2d 20 6d 79 20 70 61 last one - my pa
1980: 69 72 20 67 6f 65 73 20 74 6f 20 72 65 73 75 6c ir goes to resul
1990: 74 0a 09 09 09 09 09 09 09 6e 65 77 5b 6d 79 5f t........new[my_
19a0: 70 61 69 72 5b 30 5d 5d 20 3d 20 6d 79 5f 70 61 pair[0]] = my_pa
19b0: 69 72 5b 31 5d 0a 09 09 09 09 09 09 09 61 6c 6c ir[1]........all
19c0: 5f 70 61 72 74 73 5f 66 6f 75 6e 64 20 3d 20 54 _parts_found = T
19d0: 72 75 65 0a 09 09 09 09 09 65 6c 73 65 3a 0a 09 rue......else:..
19e0: 09 09 09 09 09 23 20 77 68 65 6e 20 6d 79 20 70 .....# when my p
19f0: 61 69 72 20 65 6e 64 73 20 62 65 66 6f 72 65 20 air ends before
1a00: 6f 74 68 65 72 20 70 61 69 72 20 65 6e 64 73 0a other pair ends.
1a10: 09 09 09 09 09 09 23 20 20 6d 2d 2d 2d 6d 0a 09 ......# m---m..
1a20: 09 09 09 09 09 23 20 6f 2d 2d 2d 2d 2d 6f 0a 09 .....# o-----o..
1a30: 09 09 09 09 09 6d 79 5f 70 61 69 72 20 3d 20 73 .....my_pair = s
1a40: 65 6c 66 2e 70 6f 70 28 29 0a 09 09 09 09 09 09 elf.pop().......
1a50: 23 20 74 6f 73 73 69 6e 67 20 6f 75 74 20 6d 79 # tossing out my
1a60: 20 70 61 69 72 0a 09 09 09 09 09 09 69 66 20 6d pair.......if m
1a70: 79 5f 70 61 69 72 5b 30 5d 20 3d 3d 20 4e 6f 6e y_pair[0] == Non
1a80: 65 3a 0a 09 09 09 09 09 09 09 61 6c 6c 5f 70 61 e:........all_pa
1a90: 72 74 73 5f 66 6f 75 6e 64 20 3d 20 54 72 75 65 rts_found = True
1aa0: 0a 09 09 09 65 6c 69 66 20 6d 79 5f 70 61 69 72 ....elif my_pair
1ab0: 5b 30 5d 20 3c 20 6f 74 68 65 72 5f 70 61 69 72 [0] < other_pair
1ac0: 5b 30 5d 3a 0a 09 09 09 09 23 20 77 68 65 6e 20 [0]:.....# when
1ad0: 6d 79 20 70 61 69 72 20 73 74 61 72 74 73 20 62 my pair starts b
1ae0: 65 66 6f 72 65 20 6f 74 68 65 72 20 6f 6e 65 0a efore other one.
1af0: 09 09 09 09 23 20 6d 2d 2d 2d 0a 09 09 09 09 23 ....# m---.....#
1b00: 20 20 6f 2d 2d 2d 0a 09 09 09 09 69 66 20 6d 79 o---.....if my
1b10: 5f 70 61 69 72 5b 31 5d 20 3c 20 6f 74 68 65 72 _pair[1] < other
1b20: 5f 70 61 69 72 5b 30 5d 3a 0a 09 09 09 09 09 23 _pair[0]:......#
1b30: 20 77 68 65 6e 20 6d 79 20 70 61 69 72 20 65 6e when my pair en
1b40: 64 73 20 62 65 66 6f 72 65 20 6f 74 68 65 72 20 ds before other
1b50: 70 61 69 72 20 73 74 61 72 74 73 0a 09 09 09 09 pair starts.....
1b60: 09 23 20 6d 2d 2d 2d 6d 0a 09 09 09 09 09 23 20 .# m---m......#
1b70: 20 20 20 20 20 20 6f 2d 2d 2d 0a 09 09 09 09 09 o---......
1b80: 6e 65 77 5b 6d 79 5f 70 61 69 72 5b 30 5d 5d 20 new[my_pair[0]]
1b90: 3d 20 6d 79 5f 70 61 69 72 5b 31 5d 0a 09 09 09 = my_pair[1]....
1ba0: 09 09 23 20 6d 79 20 70 61 69 72 20 69 73 20 6e ..# my pair is n
1bb0: 6f 74 20 63 6f 76 65 72 65 64 20 61 6e 64 20 73 ot covered and s
1bc0: 68 6f 75 6c 64 20 62 65 20 61 64 64 65 64 20 74 hould be added t
1bd0: 6f 20 72 65 73 75 6c 74 0a 09 09 09 09 09 6d 79 o result......my
1be0: 5f 70 61 69 72 20 3d 20 73 65 6c 66 2e 70 6f 70 _pair = self.pop
1bf0: 28 29 0a 09 09 09 09 09 23 20 74 6f 73 73 69 6e ()......# tossin
1c00: 67 20 6f 75 74 20 6d 79 20 70 61 69 72 0a 09 09 g out my pair...
1c10: 09 09 09 69 66 20 6d 79 5f 70 61 69 72 5b 30 5d ...if my_pair[0]
1c20: 20 3d 3d 20 4e 6f 6e 65 3a 0a 09 09 09 09 09 09 == None:.......
1c30: 61 6c 6c 5f 70 61 72 74 73 5f 66 6f 75 6e 64 20 all_parts_found
1c40: 3d 20 54 72 75 65 0a 09 09 09 09 65 6c 73 65 3a = True.....else:
1c50: 0a 09 09 09 09 09 23 20 77 68 65 6e 20 6d 79 20 ......# when my
1c60: 70 61 69 72 20 65 6e 64 73 20 62 65 66 6f 72 65 pair ends before
1c70: 20 6f 74 68 65 72 20 70 61 69 72 20 73 74 61 72 other pair star
1c80: 74 73 0a 09 09 09 09 09 23 20 6d 2d 2d 2d 6d 0a ts......# m---m.
1c90: 09 09 09 09 09 23 20 20 20 6f 2d 2d 2d 0a 09 09 .....# o---...
1ca0: 09 09 09 6e 65 77 5b 6d 79 5f 70 61 69 72 5b 30 ...new[my_pair[0
1cb0: 5d 5d 20 3d 20 6f 74 68 65 72 5f 70 61 69 72 5b ]] = other_pair[
1cc0: 30 5d 0a 09 09 09 09 09 23 20 73 74 61 72 74 20 0]......# start
1cd0: 6f 66 20 6d 79 20 70 61 69 72 20 69 73 20 6e 6f of my pair is no
1ce0: 74 20 63 6f 76 65 72 65 64 20 61 6e 64 20 73 68 t covered and sh
1cf0: 6f 75 6c 64 20 62 65 20 61 64 64 65 64 20 74 6f ould be added to
1d00: 20 72 65 73 75 6c 74 0a 09 09 09 09 09 6d 79 5f result......my_
1d10: 70 61 69 72 5b 30 5d 20 3d 20 6f 74 68 65 72 5f pair[0] = other_
1d20: 70 61 69 72 5b 30 5d 0a 09 09 09 09 09 23 20 74 pair[0]......# t
1d30: 72 69 6d 6d 69 6e 67 20 6d 79 20 70 61 69 72 20 rimming my pair
1d40: 62 79 20 6f 74 68 65 72 20 70 61 69 72 20 73 74 by other pair st
1d50: 61 72 74 0a 09 09 09 09 09 23 20 6d 2e 6d 2d 6d art......# m.m-m
1d60: 0a 09 09 09 09 09 23 20 20 20 6f 2d 2d 2d 0a 09 ......# o---..
1d70: 09 09 65 6c 73 65 3a 0a 09 09 09 09 23 20 77 68 ..else:.....# wh
1d80: 65 6e 20 62 6f 74 68 20 70 61 69 72 73 20 73 74 en both pairs st
1d90: 61 72 74 73 20 73 69 6d 75 6c 74 61 6e 65 6f 75 arts simultaneou
1da0: 73 6c 79 0a 09 09 09 09 23 20 6d 2d 2d 2d 0a 09 sly.....# m---..
1db0: 09 09 09 23 20 6f 2d 2d 2d 0a 09 09 09 09 69 66 ...# o---.....if
1dc0: 20 6d 79 5f 70 61 69 72 5b 31 5d 20 3c 20 6f 74 my_pair[1] < ot
1dd0: 68 65 72 5f 70 61 69 72 5b 31 5d 3a 0a 09 09 09 her_pair[1]:....
1de0: 09 09 23 20 77 68 65 6e 20 6d 79 20 70 61 69 72 ..# when my pair
1df0: 20 65 6e 64 73 20 62 65 66 6f 72 65 20 6f 74 68 ends before oth
1e00: 65 72 20 70 61 69 72 0a 09 09 09 09 09 23 20 6d er pair......# m
1e10: 2d 2d 2d 6d 0a 09 09 09 09 09 23 20 6f 2d 2d 2d ---m......# o---
1e20: 2d 2d 6f 0a 09 09 09 09 09 6d 79 5f 70 61 69 72 --o......my_pair
1e30: 20 3d 20 73 65 6c 66 2e 70 6f 70 28 29 0a 09 09 = self.pop()...
1e40: 09 09 09 23 20 74 6f 73 73 69 6e 67 20 6f 75 74 ...# tossing out
1e50: 20 6d 79 20 70 61 69 72 0a 09 09 09 09 09 69 66 my pair......if
1e60: 20 6d 79 5f 70 61 69 72 5b 30 5d 20 3d 3d 20 4e my_pair[0] == N
1e70: 6f 6e 65 3a 0a 09 09 09 09 09 09 61 6c 6c 5f 70 one:.......all_p
1e80: 61 72 74 73 5f 66 6f 75 6e 64 20 3d 20 54 72 75 arts_found = Tru
1e90: 65 0a 09 09 09 09 65 6c 73 65 3a 0a 09 09 09 09 e.....else:.....
1ea0: 09 23 20 77 68 65 6e 20 6d 79 20 70 61 69 72 20 .# when my pair
1eb0: 65 6e 64 73 20 61 66 74 65 72 20 6f 74 68 65 72 ends after other
1ec0: 20 70 61 69 72 0a 09 09 09 09 09 23 20 6d 2d 2d pair......# m--
1ed0: 2d 2d 2d 6d 0a 09 09 09 09 09 23 20 6f 2d 2d 2d ---m......# o---
1ee0: 6f 0a 09 09 09 09 09 6d 79 5f 70 61 69 72 5b 30 o......my_pair[0
1ef0: 5d 20 3d 20 6f 74 68 65 72 5f 70 61 69 72 5b 31 ] = other_pair[1
1f00: 5d 0a 09 09 09 09 09 23 20 74 72 69 6d 6d 69 6e ]......# trimmin
1f10: 67 20 6d 79 20 70 61 69 72 20 62 79 20 6f 74 68 g my pair by oth
1f20: 65 72 20 70 61 69 72 20 65 6e 64 0a 09 09 09 09 er pair end.....
1f30: 09 23 20 6d 2e 2e 2e 6d 2d 6d 0a 09 09 09 09 09 .# m...m-m......
1f40: 23 20 6f 2d 2d 2d 6f 0a 09 09 09 09 09 6f 74 68 # o---o......oth
1f50: 65 72 5f 70 61 69 72 20 3d 20 6f 74 68 65 72 2e er_pair = other.
1f60: 70 6f 70 28 29 0a 09 09 09 09 09 23 20 74 6f 73 pop()......# tos
1f70: 73 69 6e 67 20 6f 75 74 20 6f 74 68 65 72 20 70 sing out other p
1f80: 61 69 72 0a 09 09 09 09 09 69 66 20 6f 74 68 65 air......if othe
1f90: 72 5f 70 61 69 72 5b 30 5d 20 3d 3d 20 4e 6f 6e r_pair[0] == Non
1fa0: 65 3a 0a 09 09 09 09 09 09 23 20 74 68 69 73 20 e:.......# this
1fb0: 77 61 73 20 6c 61 73 74 20 6f 6e 65 20 2d 20 6d was last one - m
1fc0: 79 20 70 61 69 72 20 67 6f 65 73 20 74 6f 20 72 y pair goes to r
1fd0: 65 73 75 6c 74 0a 09 09 09 09 09 09 6e 65 77 5b esult.......new[
1fe0: 6d 79 5f 70 61 69 72 5b 30 5d 5d 20 3d 20 6d 79 my_pair[0]] = my
1ff0: 5f 70 61 69 72 5b 31 5d 0a 09 09 09 09 09 09 61 _pair[1].......a
2000: 6c 6c 5f 70 61 72 74 73 5f 66 6f 75 6e 64 20 3d ll_parts_found =
2010: 20 54 72 75 65 0a 09 09 77 68 69 6c 65 20 54 72 True...while Tr
2020: 75 65 3a 0a 09 09 09 23 20 63 6f 70 79 20 61 6e ue:....# copy an
2030: 79 20 6c 65 66 74 6f 76 65 72 20 69 6e 20 41 20 y leftover in A
2040: 74 6f 20 6e 65 77 20 53 70 61 63 65 4d 61 70 0a to new SpaceMap.
2050: 09 09 09 6d 79 5f 70 61 69 72 20 3d 20 73 65 6c ...my_pair = sel
2060: 66 2e 70 6f 70 28 29 0a 09 09 09 69 66 20 6d 79 f.pop()....if my
2070: 5f 70 61 69 72 5b 30 5d 20 3d 3d 20 4e 6f 6e 65 _pair[0] == None
2080: 3a 0a 09 09 09 09 62 72 65 61 6b 0a 09 09 09 65 :.....break....e
2090: 6c 73 65 3a 0a 09 09 09 09 6e 65 77 5b 6d 79 5f lse:.....new[my_
20a0: 70 61 69 72 5b 30 5d 5d 20 3d 20 6d 79 5f 70 61 pair[0]] = my_pa
20b0: 69 72 5b 31 5d 0a 09 09 73 65 6c 66 2e 63 6c 65 ir[1]...self.cle
20c0: 61 72 28 29 0a 09 09 6f 74 68 65 72 2e 63 6c 65 ar()...other.cle
20d0: 61 72 28 29 0a 09 09 72 65 74 75 72 6e 28 53 70 ar()...return(Sp
20e0: 61 63 65 4d 61 70 28 6e 65 77 2c 20 73 65 6c 66 aceMap(new, self
20f0: 2e 5f 5f 62 6f 74 74 6f 6d 2c 20 73 65 6c 66 2e .__bottom, self.
2100: 5f 5f 74 6f 70 29 29 0a 0a 09 64 65 66 20 5f 5f __top))...def __
2110: 65 71 5f 5f 28 73 65 6c 66 2c 20 6f 74 68 65 72 eq__(self, other
2120: 29 3a 0a 09 09 27 27 27 43 6f 6d 70 61 72 65 73 ):...'''Compares
2130: 20 74 77 6f 20 73 70 61 63 65 20 6d 61 70 73 2e two space maps.
2140: 27 27 27 0a 09 09 69 66 20 74 79 70 65 28 6f 74 '''...if type(ot
2150: 68 65 72 29 20 21 3d 20 53 70 61 63 65 4d 61 70 her) != SpaceMap
2160: 3a 0a 09 09 09 72 65 74 75 72 6e 28 46 61 6c 73 :....return(Fals
2170: 65 29 0a 09 09 73 65 6c 66 2e 72 65 77 69 6e 64 e)...self.rewind
2180: 28 29 0a 09 09 6f 74 68 65 72 2e 72 65 77 69 6e ()...other.rewin
2190: 64 28 29 0a 09 09 72 65 73 75 6c 74 20 3d 20 4e d()...result = N
21a0: 6f 6e 65 0a 09 09 77 68 69 6c 65 20 54 72 75 65 one...while True
21b0: 3a 0a 09 09 09 74 68 69 73 20 3d 20 73 65 6c 66 :....this = self
21c0: 2e 70 6f 70 28 29 0a 09 09 09 74 68 61 74 20 3d .pop()....that =
21d0: 20 6f 74 68 65 72 2e 70 6f 70 28 29 0a 09 09 09 other.pop()....
21e0: 69 66 20 74 68 69 73 20 21 3d 20 74 68 61 74 3a if this != that:
21f0: 0a 09 09 09 09 72 65 73 75 6c 74 20 3d 20 46 61 .....result = Fa
2200: 6c 73 65 0a 09 09 09 09 62 72 65 61 6b 0a 09 09 lse.....break...
2210: 09 69 66 20 74 68 69 73 20 3d 3d 20 5b 4e 6f 6e .if this == [Non
2220: 65 2c 20 4e 6f 6e 65 5d 20 61 6e 64 20 74 68 61 e, None] and tha
2230: 74 20 3d 3d 20 5b 4e 6f 6e 65 2c 20 4e 6f 6e 65 t == [None, None
2240: 5d 3a 0a 09 09 09 09 72 65 73 75 6c 74 20 3d 20 ]:.....result =
2250: 54 72 75 65 0a 09 09 09 09 62 72 65 61 6b 0a 09 True.....break..
2260: 09 73 65 6c 66 2e 63 6c 65 61 72 28 29 0a 09 09 .self.clear()...
2270: 6f 74 68 65 72 2e 63 6c 65 61 72 28 29 0a 09 09 other.clear()...
2280: 72 65 74 75 72 6e 28 72 65 73 75 6c 74 29 0a 0a return(result)..
2290: 09 64 65 66 20 65 6e 64 28 73 65 6c 66 29 3a 0a .def end(self):.
22a0: 09 09 27 27 27 52 65 74 75 72 6e 73 20 6c 61 73 ..'''Returns las
22b0: 74 20 6b 6e 6f 77 6e 20 70 6f 69 6e 74 2e 27 27 t known point.''
22c0: 27 0a 09 09 65 6e 64 20 3d 20 4e 6f 6e 65 0a 09 '...end = None..
22d0: 09 73 65 6c 66 2e 72 65 77 69 6e 64 28 29 0a 09 .self.rewind()..
22e0: 09 77 68 69 6c 65 20 54 72 75 65 3a 0a 09 09 09 .while True:....
22f0: 74 68 69 73 20 3d 20 73 65 6c 66 2e 70 6f 70 28 this = self.pop(
2300: 29 0a 09 09 09 69 66 20 74 68 69 73 20 3d 3d 20 )....if this ==
2310: 5b 4e 6f 6e 65 2c 20 4e 6f 6e 65 5d 3a 0a 09 09 [None, None]:...
2320: 09 09 62 72 65 61 6b 0a 09 09 09 65 6c 69 66 20 ..break....elif
2330: 65 6e 64 20 3d 3d 20 4e 6f 6e 65 20 6f 72 20 74 end == None or t
2340: 68 69 73 5b 31 5d 20 3e 20 65 6e 64 3a 0a 09 09 his[1] > end:...
2350: 09 09 65 6e 64 20 3d 20 74 68 69 73 5b 31 5d 0a ..end = this[1].
2360: 09 09 73 65 6c 66 2e 63 6c 65 61 72 28 29 0a 09 ..self.clear()..
2370: 09 72 65 74 75 72 6e 28 65 6e 64 29 0a 0a 09 64 .return(end)...d
2380: 65 66 20 5f 5f 6c 65 6e 5f 5f 28 73 65 6c 66 29 ef __len__(self)
2390: 3a 0a 09 09 72 65 74 75 72 6e 28 6c 65 6e 28 73 :...return(len(s
23a0: 65 6c 66 2e 5f 5f 70 61 69 72 73 29 29 0a elf.__pairs)).