Artifact
6e71065e5d4adba8bdd0af08580d686956703471da61990044aa754eb584d933:
0000: 63 6c 61 73 73 20 53 70 61 63 65 4d 61 70 3a 0a class SpaceMap:.
0010: 09 27 27 27 20 48 65 72 65 20 77 65 20 68 61 76 .''' Here we hav
0020: 65 3a 0a 09 5f 5f 62 6f 74 74 6f 6d 20 2d 20 6d e:..__bottom - m
0030: 69 6e 69 6d 75 6d 20 73 70 61 63 65 20 61 64 64 inimum space add
0040: 72 65 73 73 20 70 6f 73 73 69 62 6c 65 3b 0a 09 ress possible;..
0050: 5f 5f 74 6f 70 20 2d 20 6d 61 78 69 6d 75 6d 20 __top - maximum
0060: 73 70 61 63 65 20 61 64 64 72 65 73 73 20 70 6f space address po
0070: 73 73 69 62 6c 65 3b 0a 09 5f 5f 70 61 69 72 73 ssible;..__pairs
0080: 20 2d 20 69 6e 74 65 72 6e 61 6c 20 6c 69 73 74 - internal list
0090: 20 6f 66 20 72 61 6e 67 65 73 3b 0a 09 5f 5f 77 of ranges;..__w
00a0: 61 6c 6b 5f 6c 69 73 74 20 2d 20 69 6e 74 65 72 alk_list - inter
00b0: 6e 61 6c 20 6c 69 73 74 20 6f 66 20 6b 65 79 73 nal list of keys
00c0: 2e 27 27 27 0a 0a 09 5f 5f 73 6c 6f 74 73 5f 5f .'''...__slots__
00d0: 20 3d 20 66 72 6f 7a 65 6e 73 65 74 28 28 27 5f = frozenset(('_
00e0: 5f 62 6f 74 74 6f 6d 27 2c 20 27 5f 5f 70 61 69 _bottom', '__pai
00f0: 72 73 27 2c 20 27 5f 5f 74 6f 70 27 2c 20 27 5f rs', '__top', '_
0100: 5f 77 61 6c 6b 5f 6c 69 73 74 27 29 29 0a 0a 09 _walk_list'))...
0110: 64 65 66 20 5f 5f 69 6e 69 74 5f 5f 28 73 65 6c def __init__(sel
0120: 66 2c 20 73 6f 75 72 63 65 20 3d 20 4e 6f 6e 65 f, source = None
0130: 2c 20 62 6f 74 74 6f 6d 20 3d 20 30 2c 20 74 6f , bottom = 0, to
0140: 70 20 3d 20 4e 6f 6e 65 29 3a 0a 09 09 27 27 27 p = None):...'''
0150: 20 54 68 69 73 20 6f 6e 65 20 63 61 6e 20 62 65 This one can be
0160: 20 62 6f 6f 74 73 74 72 61 70 70 65 64 20 62 79 bootstrapped by
0170: 20 67 69 76 69 6e 67 20 61 20 64 69 63 74 20 69 giving a dict i
0180: 6e 20 66 6f 72 6d 61 74 20 7b 78 3a 79 2c 20 78 n format {x:y, x
0190: 3a 79 7d 2e 27 27 27 0a 09 09 73 65 6c 66 2e 5f :y}.'''...self._
01a0: 5f 70 61 69 72 73 20 3d 20 7b 7d 0a 09 09 73 65 _pairs = {}...se
01b0: 6c 66 2e 5f 5f 77 61 6c 6b 5f 6c 69 73 74 20 3d lf.__walk_list =
01c0: 20 4e 6f 6e 65 0a 09 09 73 65 6c 66 2e 5f 5f 62 None...self.__b
01d0: 6f 74 74 6f 6d 20 3d 20 62 6f 74 74 6f 6d 0a 09 ottom = bottom..
01e0: 09 73 65 6c 66 2e 5f 5f 74 6f 70 20 3d 20 74 6f .self.__top = to
01f0: 70 0a 09 09 69 66 20 74 79 70 65 28 73 6f 75 72 p...if type(sour
0200: 63 65 29 20 3d 3d 20 64 69 63 74 3a 0a 09 09 09 ce) == dict:....
0210: 66 6f 72 20 6b 65 79 20 69 6e 20 73 6f 75 72 63 for key in sourc
0220: 65 3a 0a 09 09 09 09 73 65 6c 66 2e 5f 5f 73 65 e:.....self.__se
0230: 74 28 6b 65 79 2c 20 73 6f 75 72 63 65 5b 6b 65 t(key, source[ke
0240: 79 5d 29 0a 09 09 09 73 65 6c 66 2e 66 6f 6c 64 y])....self.fold
0250: 28 29 0a 0a 09 64 65 66 20 5f 5f 67 65 74 69 74 ()...def __getit
0260: 65 6d 5f 5f 28 73 65 6c 66 2c 20 6e 61 6d 65 29 em__(self, name)
0270: 3a 0a 09 09 27 27 27 52 65 74 75 72 6e 73 20 6c :...'''Returns l
0280: 61 73 74 20 72 61 6e 67 65 20 61 64 64 72 65 73 ast range addres
0290: 73 20 62 79 20 66 69 72 73 74 20 72 61 6e 67 65 s by first range
02a0: 20 61 64 64 72 65 73 73 2e 27 27 27 0a 09 09 69 address.'''...i
02b0: 66 20 6e 61 6d 65 20 69 6e 20 73 65 6c 66 2e 5f f name in self._
02c0: 5f 70 61 69 72 73 3a 0a 09 09 09 72 65 74 75 72 _pairs:....retur
02d0: 6e 28 73 65 6c 66 2e 5f 5f 70 61 69 72 73 5b 6e n(self.__pairs[n
02e0: 61 6d 65 5d 29 0a 09 09 65 6c 73 65 3a 0a 09 09 ame])...else:...
02f0: 09 72 65 74 75 72 6e 28 4e 6f 6e 65 29 0a 0a 09 .return(None)...
0300: 64 65 66 20 5f 5f 73 65 74 28 73 65 6c 66 2c 20 def __set(self,
0310: 6e 61 6d 65 2c 20 76 61 6c 75 65 29 3a 0a 09 09 name, value):...
0320: 27 27 27 49 6e 74 65 72 6e 61 6c 20 66 75 6e 63 '''Internal func
0330: 74 69 6f 6e 20 74 6f 20 61 64 64 20 72 61 6e 67 tion to add rang
0340: 65 73 20 77 69 74 68 6f 75 74 20 66 6f 6c 64 69 es without foldi
0350: 6e 67 2e 20 41 6c 73 6f 20 63 68 65 63 6b 73 20 ng. Also checks
0360: 66 6f 72 20 72 61 6e 67 65 20 63 6f 72 72 65 63 for range correc
0370: 74 6e 65 73 73 2e 27 27 27 0a 09 09 69 66 20 74 tness.'''...if t
0380: 79 70 65 28 6e 61 6d 65 29 20 21 3d 20 69 6e 74 ype(name) != int
0390: 20 6f 72 20 74 79 70 65 28 76 61 6c 75 65 29 20 or type(value)
03a0: 21 3d 20 69 6e 74 20 6f 72 20 6e 61 6d 65 20 3e != int or name >
03b0: 3d 20 76 61 6c 75 65 3a 0a 09 09 09 72 65 74 75 = value:....retu
03c0: 72 6e 28 46 61 6c 73 65 29 0a 09 09 69 66 20 6e rn(False)...if n
03d0: 6f 74 20 73 65 6c 66 2e 5f 5f 62 6f 74 74 6f 6d ot self.__bottom
03e0: 20 3d 3d 20 4e 6f 6e 65 3a 0a 09 09 09 69 66 20 == None:....if
03f0: 6e 61 6d 65 20 3c 20 73 65 6c 66 2e 5f 5f 62 6f name < self.__bo
0400: 74 74 6f 6d 20 6f 72 20 76 61 6c 75 65 20 3c 20 ttom or value <
0410: 73 65 6c 66 2e 5f 5f 62 6f 74 74 6f 6d 3a 0a 09 self.__bottom:..
0420: 09 09 09 72 65 74 75 72 6e 28 46 61 6c 73 65 29 ...return(False)
0430: 0a 09 09 69 66 20 6e 6f 74 20 73 65 6c 66 2e 5f ...if not self._
0440: 5f 74 6f 70 20 3d 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 6e 6f 74 20 74 79 70 65 28 6f 74 68 65 72 29 not type(other)
09e0: 20 3d 3d 20 53 70 61 63 65 4d 61 70 3a 0a 09 09 == SpaceMap:...
09f0: 09 72 65 74 75 72 6e 28 46 61 6c 73 65 29 0a 09 .return(False)..
0a00: 09 6e 65 77 20 3d 20 7b 7d 0a 09 09 73 65 6c 66 .new = {}...self
0a10: 2e 72 65 77 69 6e 64 28 29 0a 09 09 6f 74 68 65 .rewind()...othe
0a20: 72 2e 72 65 77 69 6e 64 28 29 0a 09 09 6d 79 5f r.rewind()...my_
0a30: 70 61 69 72 20 3d 20 73 65 6c 66 2e 70 6f 70 28 pair = self.pop(
0a40: 29 0a 09 09 6f 74 68 65 72 5f 70 61 69 72 20 3d )...other_pair =
0a50: 20 6f 74 68 65 72 2e 70 6f 70 28 29 0a 09 09 23 other.pop()...#
0a60: 20 69 66 20 74 68 65 72 65 20 61 72 65 20 6e 6f if there are no
0a70: 20 70 61 69 72 73 20 69 6e 20 42 20 2d 20 77 65 pairs in B - we
0a80: 20 68 61 76 65 20 6e 6f 74 68 69 6e 67 20 74 6f have nothing to
0a90: 20 64 6f 0a 09 09 69 66 20 6f 74 68 65 72 5f 70 do...if other_p
0aa0: 61 69 72 5b 30 5d 20 3d 3d 20 4e 6f 6e 65 20 6f air[0] == None o
0ab0: 72 20 6d 79 5f 70 61 69 72 5b 30 5d 20 3d 3d 20 r my_pair[0] ==
0ac0: 4e 6f 6e 65 3a 0a 09 09 09 61 6c 6c 5f 70 61 72 None:....all_par
0ad0: 74 73 5f 66 6f 75 6e 64 20 3d 20 54 72 75 65 0a ts_found = True.
0ae0: 09 09 65 6c 73 65 3a 0a 09 09 09 61 6c 6c 5f 70 ..else:....all_p
0af0: 61 72 74 73 5f 66 6f 75 6e 64 20 3d 20 46 61 6c arts_found = Fal
0b00: 73 65 0a 09 09 77 68 69 6c 65 20 6e 6f 74 20 61 se...while not a
0b10: 6c 6c 5f 70 61 72 74 73 5f 66 6f 75 6e 64 3a 0a ll_parts_found:.
0b20: 09 09 09 69 66 20 6d 79 5f 70 61 69 72 5b 30 5d ...if my_pair[0]
0b30: 20 3e 20 6f 74 68 65 72 5f 70 61 69 72 5b 30 5d > other_pair[0]
0b40: 3a 0a 09 09 09 09 23 20 77 68 65 6e 20 6d 79 20 :.....# when my
0b50: 70 61 69 72 20 73 74 61 72 74 73 20 61 66 74 65 pair starts afte
0b60: 72 20 6f 74 68 65 72 20 70 61 69 72 20 73 74 61 r other pair sta
0b70: 72 74 73 0a 09 09 09 09 23 20 20 6d 2d 2d 2d 0a rts.....# m---.
0b80: 09 09 09 09 23 20 6f 2d 2d 2d 0a 09 09 09 09 69 ....# o---.....i
0b90: 66 20 6d 79 5f 70 61 69 72 5b 30 5d 20 3e 20 6f f my_pair[0] > o
0ba0: 74 68 65 72 5f 70 61 69 72 5b 31 5d 3a 0a 09 09 ther_pair[1]:...
0bb0: 09 09 09 23 20 77 68 65 6e 20 6d 79 20 70 61 69 ...# when my pai
0bc0: 72 20 73 74 61 72 74 73 20 61 66 74 65 72 20 6f r starts after o
0bd0: 74 68 65 72 20 70 61 69 72 20 65 6e 64 73 0a 09 ther pair ends..
0be0: 09 09 09 09 23 20 20 20 20 20 20 20 6d 2d 2d 2d ....# m---
0bf0: 0a 09 09 09 09 09 23 20 6f 2d 2d 2d 6f 0a 09 09 ......# o---o...
0c00: 09 09 09 6f 74 68 65 72 5f 70 61 69 72 20 3d 20 ...other_pair =
0c10: 6f 74 68 65 72 2e 70 6f 70 28 29 0a 09 09 09 09 other.pop().....
0c20: 09 23 20 74 6f 73 73 69 6e 67 20 6f 75 74 20 6f .# tossing out o
0c30: 74 68 65 72 20 70 61 69 72 0a 09 09 09 09 09 69 ther pair......i
0c40: 66 20 6f 74 68 65 72 5f 70 61 69 72 5b 30 5d 20 f other_pair[0]
0c50: 3d 3d 20 4e 6f 6e 65 3a 0a 09 09 09 09 09 09 61 == None:.......a
0c60: 6c 6c 5f 70 61 72 74 73 5f 66 6f 75 6e 64 20 3d ll_parts_found =
0c70: 20 54 72 75 65 0a 09 09 09 09 65 6c 73 65 3a 0a True.....else:.
0c80: 09 09 09 09 09 23 20 77 68 65 6e 20 6d 79 20 70 .....# when my p
0c90: 61 69 72 20 73 74 61 72 74 73 20 62 65 66 6f 72 air starts befor
0ca0: 65 20 6f 74 68 65 72 20 70 61 69 72 20 65 6e 64 e other pair end
0cb0: 73 0a 09 09 09 09 09 23 20 20 20 20 6d 2d 2d 2d s......# m---
0cc0: 20 7c 20 20 20 20 20 6d 2d 2d 2d 0a 09 09 09 09 | m---.....
0cd0: 09 23 20 6f 2d 2d 2d 6f 20 20 20 7c 20 6f 2d 2d .# o---o | o--
0ce0: 2d 6f 0a 09 09 09 09 09 69 66 20 6d 79 5f 70 61 -o......if my_pa
0cf0: 69 72 5b 31 5d 20 3e 20 6f 74 68 65 72 5f 70 61 ir[1] > other_pa
0d00: 69 72 5b 31 5d 3a 0a 09 09 09 09 09 09 23 20 77 ir[1]:.......# w
0d10: 68 65 6e 20 6d 79 20 70 61 69 72 20 65 6e 64 73 hen my pair ends
0d20: 20 61 66 74 65 72 20 6f 74 68 65 72 20 70 61 69 after other pai
0d30: 72 20 65 6e 64 73 0a 09 09 09 09 09 09 23 20 20 r ends.......#
0d40: 20 20 6d 2d 2d 2d 6d 20 7c 20 20 20 20 20 6d 2d m---m | m-
0d50: 2d 2d 6d 0a 09 09 09 09 09 09 23 20 6f 2d 2d 2d --m.......# o---
0d60: 6f 20 20 20 20 7c 20 6f 2d 2d 2d 6f 0a 09 09 09 o | o---o....
0d70: 09 09 09 6f 74 68 65 72 5f 70 61 69 72 5b 30 5d ...other_pair[0]
0d80: 20 3d 20 6d 79 5f 70 61 69 72 5b 30 5d 0a 09 09 = my_pair[0]...
0d90: 09 09 09 09 23 20 74 72 69 6d 6d 69 6e 67 20 6f ....# trimming o
0da0: 74 68 65 72 20 70 61 69 72 20 62 79 20 6d 79 20 ther pair by my
0db0: 70 61 69 72 20 73 74 61 72 74 0a 09 09 09 09 09 pair start......
0dc0: 09 23 20 20 20 6d 2d 2d 2d 6d 0a 09 09 09 09 09 .# m---m......
0dd0: 09 23 20 6f 2e 6f 2d 6f 0a 09 09 09 09 09 65 6c .# o.o-o......el
0de0: 73 65 3a 0a 09 09 09 09 09 09 23 20 77 68 65 6e se:.......# when
0df0: 20 6d 79 20 70 61 69 72 20 65 6e 64 73 20 62 65 my pair ends be
0e00: 66 6f 72 65 20 6f 74 68 65 72 20 70 61 69 72 20 fore other pair
0e10: 65 6e 64 73 0a 09 09 09 09 09 09 23 20 20 6d 2d ends.......# m-
0e20: 2d 2d 6d 0a 09 09 09 09 09 09 23 20 6f 2d 2d 2d --m.......# o---
0e30: 2d 2d 6f 0a 09 09 09 09 09 09 6e 65 77 5b 6d 79 --o.......new[my
0e40: 5f 70 61 69 72 5b 30 5d 5d 20 3d 20 6d 79 5f 70 _pair[0]] = my_p
0e50: 61 69 72 5b 31 5d 0a 09 09 09 09 09 09 23 20 6d air[1].......# m
0e60: 79 20 70 61 69 72 20 69 73 20 63 6f 76 65 72 65 y pair is covere
0e70: 64 20 61 6e 64 20 73 68 6f 75 6c 64 20 62 65 20 d and should be
0e80: 61 64 64 65 64 20 74 6f 20 72 65 73 75 6c 74 0a added to result.
0e90: 09 09 09 09 09 09 6d 79 5f 70 61 69 72 20 3d 20 ......my_pair =
0ea0: 73 65 6c 66 2e 70 6f 70 28 29 0a 09 09 09 09 09 self.pop()......
0eb0: 09 23 20 74 6f 73 73 69 6e 67 20 6f 75 74 20 6d .# tossing out m
0ec0: 79 20 70 61 69 72 0a 09 09 09 09 09 09 69 66 20 y pair.......if
0ed0: 6d 79 5f 70 61 69 72 5b 30 5d 20 3d 3d 20 4e 6f my_pair[0] == No
0ee0: 6e 65 3a 0a 09 09 09 09 09 09 09 61 6c 6c 5f 70 ne:........all_p
0ef0: 61 72 74 73 5f 66 6f 75 6e 64 20 3d 20 54 72 75 arts_found = Tru
0f00: 65 0a 09 09 09 65 6c 69 66 20 6d 79 5f 70 61 69 e....elif my_pai
0f10: 72 5b 30 5d 20 3c 20 6f 74 68 65 72 5f 70 61 69 r[0] < other_pai
0f20: 72 5b 30 5d 3a 0a 09 09 09 09 23 20 77 68 65 6e r[0]:.....# when
0f30: 20 6d 79 20 70 61 69 72 20 73 74 61 72 74 73 20 my pair starts
0f40: 62 65 66 6f 72 65 20 6f 74 68 65 72 20 6f 6e 65 before other one
0f50: 0a 09 09 09 09 23 20 6d 2d 2d 2d 0a 09 09 09 09 .....# m---.....
0f60: 23 20 20 6f 2d 2d 2d 0a 09 09 09 09 69 66 20 6d # o---.....if m
0f70: 79 5f 70 61 69 72 5b 31 5d 20 3c 20 6f 74 68 65 y_pair[1] < othe
0f80: 72 5f 70 61 69 72 5b 30 5d 3a 0a 09 09 09 09 09 r_pair[0]:......
0f90: 23 20 77 68 65 6e 20 6d 79 20 70 61 69 72 20 65 # when my pair e
0fa0: 6e 64 73 20 62 65 66 6f 72 65 20 6f 74 68 65 72 nds before other
0fb0: 20 70 61 69 72 20 73 74 61 72 74 73 0a 09 09 09 pair starts....
0fc0: 09 09 23 20 6d 2d 2d 2d 6d 0a 09 09 09 09 09 23 ..# m---m......#
0fd0: 20 20 20 20 20 20 20 6f 2d 2d 2d 0a 09 09 09 09 o---.....
0fe0: 09 6d 79 5f 70 61 69 72 20 3d 20 73 65 6c 66 2e .my_pair = self.
0ff0: 70 6f 70 28 29 0a 09 09 09 09 09 23 20 74 6f 73 pop()......# tos
1000: 73 69 6e 67 20 6f 75 74 20 6d 79 20 70 61 69 72 sing out my pair
1010: 0a 09 09 09 09 09 69 66 20 6d 79 5f 70 61 69 72 ......if my_pair
1020: 5b 30 5d 20 3d 3d 20 4e 6f 6e 65 3a 0a 09 09 09 [0] == None:....
1030: 09 09 09 61 6c 6c 5f 70 61 72 74 73 5f 66 6f 75 ...all_parts_fou
1040: 6e 64 20 3d 20 54 72 75 65 0a 09 09 09 09 65 6c nd = True.....el
1050: 73 65 3a 0a 09 09 09 09 09 23 20 77 68 65 6e 20 se:......# when
1060: 6d 79 20 70 61 69 72 20 65 6e 64 73 20 62 65 66 my pair ends bef
1070: 6f 72 65 20 6f 74 68 65 72 20 70 61 69 72 20 73 ore other pair s
1080: 74 61 72 74 73 0a 09 09 09 09 09 23 20 6d 2d 2d tarts......# m--
1090: 2d 6d 0a 09 09 09 09 09 23 20 20 20 6f 2d 2d 2d -m......# o---
10a0: 0a 09 09 09 09 09 6d 79 5f 70 61 69 72 5b 30 5d ......my_pair[0]
10b0: 20 3d 20 6f 74 68 65 72 5f 70 61 69 72 5b 30 5d = other_pair[0]
10c0: 0a 09 09 09 09 09 23 20 74 72 69 6d 6d 69 6e 67 ......# trimming
10d0: 20 6d 79 20 70 61 69 72 20 62 79 20 6f 74 68 65 my pair by othe
10e0: 72 20 70 61 69 72 20 73 74 61 72 74 0a 09 09 09 r pair start....
10f0: 09 09 23 20 6d 2e 6d 2d 6d 0a 09 09 09 09 09 23 ..# m.m-m......#
1100: 20 20 20 6f 2d 2d 2d 0a 09 09 09 65 6c 73 65 3a o---....else:
1110: 0a 09 09 09 09 23 20 77 68 65 6e 20 62 6f 74 68 .....# when both
1120: 20 70 61 69 72 73 20 73 74 61 72 74 73 20 73 69 pairs starts si
1130: 6d 75 6c 74 61 6e 65 6f 75 73 6c 79 0a 09 09 09 multaneously....
1140: 09 23 20 6d 2d 2d 2d 0a 09 09 09 09 23 20 6f 2d .# m---.....# o-
1150: 2d 2d 0a 09 09 09 09 69 66 20 6d 79 5f 70 61 69 --.....if my_pai
1160: 72 5b 31 5d 20 3c 20 6f 74 68 65 72 5f 70 61 69 r[1] < other_pai
1170: 72 5b 31 5d 3a 0a 09 09 09 09 09 23 20 77 68 65 r[1]:......# whe
1180: 6e 20 6d 79 20 70 61 69 72 20 65 6e 64 73 20 62 n my pair ends b
1190: 65 66 6f 72 65 20 6f 74 68 65 72 20 70 61 69 72 efore other pair
11a0: 0a 09 09 09 09 09 23 20 6d 2d 2d 2d 6d 0a 09 09 ......# m---m...
11b0: 09 09 09 23 20 6f 2d 2d 2d 2d 2d 6f 0a 09 09 09 ...# o-----o....
11c0: 09 09 6e 65 77 5b 6d 79 5f 70 61 69 72 5b 30 5d ..new[my_pair[0]
11d0: 5d 20 3d 20 6d 79 5f 70 61 69 72 5b 31 5d 0a 09 ] = my_pair[1]..
11e0: 09 09 09 09 23 20 6d 79 20 70 61 69 72 20 69 73 ....# my pair is
11f0: 20 63 6f 76 65 72 65 64 20 61 6e 64 20 73 68 6f covered and sho
1200: 75 6c 64 20 62 65 20 61 64 64 65 64 20 74 6f 20 uld be added to
1210: 72 65 73 75 6c 74 0a 09 09 09 09 09 6d 79 5f 70 result......my_p
1220: 61 69 72 20 3d 20 73 65 6c 66 2e 70 6f 70 28 29 air = self.pop()
1230: 0a 09 09 09 09 09 23 20 74 6f 73 73 69 6e 67 20 ......# tossing
1240: 6f 75 74 20 6d 79 20 70 61 69 72 0a 09 09 09 09 out my pair.....
1250: 09 69 66 20 6d 79 5f 70 61 69 72 5b 30 5d 20 3d .if my_pair[0] =
1260: 3d 20 4e 6f 6e 65 3a 0a 09 09 09 09 09 09 61 6c = None:.......al
1270: 6c 5f 70 61 72 74 73 5f 66 6f 75 6e 64 20 3d 20 l_parts_found =
1280: 54 72 75 65 0a 09 09 09 09 65 6c 73 65 3a 0a 09 True.....else:..
1290: 09 09 09 09 23 20 77 68 65 6e 20 6d 79 20 70 61 ....# when my pa
12a0: 69 72 20 65 6e 64 73 20 61 66 74 65 72 20 6f 74 ir ends after ot
12b0: 68 65 72 20 70 61 69 72 0a 09 09 09 09 09 23 20 her pair......#
12c0: 6d 2d 2d 2d 2d 2d 6d 0a 09 09 09 09 09 23 20 6f m-----m......# o
12d0: 2d 2d 2d 6f 0a 09 09 09 09 09 6e 65 77 5b 6d 79 ---o......new[my
12e0: 5f 70 61 69 72 5b 30 5d 5d 20 3d 20 6f 74 68 65 _pair[0]] = othe
12f0: 72 5f 70 61 69 72 5b 31 5d 0a 09 09 09 09 09 23 r_pair[1]......#
1300: 20 70 61 72 74 20 6f 66 20 6d 79 20 70 61 69 72 part of my pair
1310: 20 69 73 20 63 6f 76 65 72 65 64 20 61 6e 64 20 is covered and
1320: 73 68 6f 75 6c 64 20 62 65 20 61 64 64 65 64 20 should be added
1330: 74 6f 20 72 65 73 75 6c 74 0a 09 09 09 09 09 6f to result......o
1340: 74 68 65 72 5f 70 61 69 72 20 3d 20 6f 74 68 65 ther_pair = othe
1350: 72 2e 70 6f 70 28 29 0a 09 09 09 09 09 23 20 74 r.pop()......# t
1360: 6f 73 73 69 6e 67 20 6f 75 74 20 6f 74 68 65 72 ossing out other
1370: 20 70 61 69 72 0a 09 09 09 09 09 69 66 20 6f 74 pair......if ot
1380: 68 65 72 5f 70 61 69 72 5b 30 5d 20 3d 3d 20 4e her_pair[0] == N
1390: 6f 6e 65 3a 0a 09 09 09 09 09 09 61 6c 6c 5f 70 one:.......all_p
13a0: 61 72 74 73 5f 66 6f 75 6e 64 20 3d 20 54 72 75 arts_found = Tru
13b0: 65 0a 09 09 73 65 6c 66 2e 63 6c 65 61 72 28 29 e...self.clear()
13c0: 0a 09 09 6f 74 68 65 72 2e 63 6c 65 61 72 28 29 ...other.clear()
13d0: 0a 09 09 72 65 74 75 72 6e 28 53 70 61 63 65 4d ...return(SpaceM
13e0: 61 70 28 6e 65 77 2c 20 73 65 6c 66 2e 5f 5f 62 ap(new, self.__b
13f0: 6f 74 74 6f 6d 2c 20 73 65 6c 66 2e 5f 5f 74 6f ottom, self.__to
1400: 70 29 29 0a 0a 09 64 65 66 20 5f 5f 73 75 62 5f p))...def __sub_
1410: 5f 28 73 65 6c 66 2c 20 6f 74 68 65 72 29 3a 0a _(self, other):.
1420: 09 09 27 27 27 52 65 74 75 72 6e 73 20 6e 65 77 ..'''Returns new
1430: 20 73 70 61 63 65 20 6d 61 70 20 77 69 74 68 20 space map with
1440: 72 61 6e 67 65 73 20 69 6e 20 41 20 6e 6f 74 20 ranges in A not
1450: 63 6f 76 65 72 65 64 20 62 79 20 42 2e 27 27 27 covered by B.'''
1460: 0a 09 09 69 66 20 6e 6f 74 20 74 79 70 65 28 6f ...if not type(o
1470: 74 68 65 72 29 20 3d 3d 20 53 70 61 63 65 4d 61 ther) == SpaceMa
1480: 70 3a 0a 09 09 09 72 65 74 75 72 6e 28 46 61 6c p:....return(Fal
1490: 73 65 29 0a 09 09 6e 65 77 20 3d 20 7b 7d 0a 09 se)...new = {}..
14a0: 09 73 65 6c 66 2e 72 65 77 69 6e 64 28 29 0a 09 .self.rewind()..
14b0: 09 6f 74 68 65 72 2e 72 65 77 69 6e 64 28 29 0a .other.rewind().
14c0: 09 09 6d 79 5f 70 61 69 72 20 3d 20 73 65 6c 66 ..my_pair = self
14d0: 2e 70 6f 70 28 29 0a 09 09 6f 74 68 65 72 5f 70 .pop()...other_p
14e0: 61 69 72 20 3d 20 6f 74 68 65 72 2e 70 6f 70 28 air = other.pop(
14f0: 29 0a 09 09 23 20 69 66 20 74 68 65 72 65 20 61 )...# if there a
1500: 72 65 20 6e 6f 20 70 61 69 72 73 20 69 6e 20 42 re no pairs in B
1510: 20 2d 20 63 6f 70 79 20 74 68 69 73 20 6f 6e 65 - copy this one
1520: 20 74 6f 20 6e 65 77 20 53 70 61 63 65 4d 61 70 to new SpaceMap
1530: 0a 09 09 69 66 20 6f 74 68 65 72 5f 70 61 69 72 ...if other_pair
1540: 5b 30 5d 20 3d 3d 20 4e 6f 6e 65 3a 0a 09 09 09 [0] == None:....
1550: 6e 65 77 5b 6d 79 5f 70 61 69 72 5b 30 5d 5d 20 new[my_pair[0]]
1560: 3d 20 6d 79 5f 70 61 69 72 5b 31 5d 0a 09 09 09 = my_pair[1]....
1570: 61 6c 6c 5f 70 61 72 74 73 5f 66 6f 75 6e 64 20 all_parts_found
1580: 3d 20 54 72 75 65 0a 09 09 65 6c 69 66 20 6d 79 = True...elif my
1590: 5f 70 61 69 72 5b 30 5d 20 3d 3d 20 4e 6f 6e 65 _pair[0] == None
15a0: 3a 0a 09 09 09 61 6c 6c 5f 70 61 72 74 73 5f 66 :....all_parts_f
15b0: 6f 75 6e 64 20 3d 20 54 72 75 65 0a 09 09 65 6c ound = True...el
15c0: 73 65 3a 0a 09 09 09 61 6c 6c 5f 70 61 72 74 73 se:....all_parts
15d0: 5f 66 6f 75 6e 64 20 3d 20 46 61 6c 73 65 0a 09 _found = False..
15e0: 09 77 68 69 6c 65 20 6e 6f 74 20 61 6c 6c 5f 70 .while not all_p
15f0: 61 72 74 73 5f 66 6f 75 6e 64 3a 0a 09 09 09 69 arts_found:....i
1600: 66 20 6d 79 5f 70 61 69 72 5b 30 5d 20 3e 20 6f f my_pair[0] > o
1610: 74 68 65 72 5f 70 61 69 72 5b 30 5d 3a 0a 09 09 ther_pair[0]:...
1620: 09 09 23 20 77 68 65 6e 20 6d 79 20 70 61 69 72 ..# when my pair
1630: 20 73 74 61 72 74 73 20 61 66 74 65 72 20 6f 74 starts after ot
1640: 68 65 72 20 70 61 69 72 20 73 74 61 72 74 73 0a her pair starts.
1650: 09 09 09 09 23 20 20 6d 2d 2d 2d 0a 09 09 09 09 ....# m---.....
1660: 23 20 6f 2d 2d 2d 0a 09 09 09 09 69 66 20 6d 79 # o---.....if my
1670: 5f 70 61 69 72 5b 30 5d 20 3e 20 6f 74 68 65 72 _pair[0] > other
1680: 5f 70 61 69 72 5b 31 5d 3a 0a 09 09 09 09 09 23 _pair[1]:......#
1690: 20 77 68 65 6e 20 6d 79 20 70 61 69 72 20 73 74 when my pair st
16a0: 61 72 74 73 20 61 66 74 65 72 20 6f 74 68 65 72 arts after other
16b0: 20 70 61 69 72 20 65 6e 64 73 0a 09 09 09 09 09 pair ends......
16c0: 23 20 20 20 20 20 20 20 6d 2d 2d 2d 0a 09 09 09 # m---....
16d0: 09 09 23 20 6f 2d 2d 2d 6f 0a 09 09 09 09 09 6f ..# o---o......o
16e0: 74 68 65 72 5f 70 61 69 72 20 3d 20 6f 74 68 65 ther_pair = othe
16f0: 72 2e 70 6f 70 28 29 0a 09 09 09 09 09 23 20 74 r.pop()......# t
1700: 6f 73 73 69 6e 67 20 6f 75 74 20 6f 74 68 65 72 ossing out other
1710: 20 70 61 69 72 0a 09 09 09 09 09 69 66 20 6f 74 pair......if ot
1720: 68 65 72 5f 70 61 69 72 5b 30 5d 20 3d 3d 20 4e her_pair[0] == N
1730: 6f 6e 65 3a 0a 09 09 09 09 09 09 23 20 74 68 69 one:.......# thi
1740: 73 20 77 61 73 20 6c 61 73 74 20 6f 6e 65 20 2d s was last one -
1750: 20 6d 79 20 70 61 69 72 20 67 6f 65 73 20 74 6f my pair goes to
1760: 20 72 65 73 75 6c 74 0a 09 09 09 09 09 09 6e 65 result.......ne
1770: 77 5b 6d 79 5f 70 61 69 72 5b 30 5d 5d 20 3d 20 w[my_pair[0]] =
1780: 6d 79 5f 70 61 69 72 5b 31 5d 0a 09 09 09 09 09 my_pair[1]......
1790: 09 61 6c 6c 5f 70 61 72 74 73 5f 66 6f 75 6e 64 .all_parts_found
17a0: 20 3d 20 54 72 75 65 0a 09 09 09 09 65 6c 73 65 = True.....else
17b0: 3a 0a 09 09 09 09 09 23 20 77 68 65 6e 20 6d 79 :......# when my
17c0: 20 70 61 69 72 20 73 74 61 72 74 73 20 62 65 66 pair starts bef
17d0: 6f 72 65 20 6f 74 68 65 72 20 70 61 69 72 20 65 ore other pair e
17e0: 6e 64 73 0a 09 09 09 09 09 23 20 20 20 20 6d 2d nds......# m-
17f0: 2d 2d 20 7c 20 20 20 20 20 6d 2d 2d 2d 0a 09 09 -- | m---...
1800: 09 09 09 23 20 6f 2d 2d 2d 6f 20 20 20 7c 20 6f ...# o---o | o
1810: 2d 2d 2d 6f 0a 09 09 09 09 09 69 66 20 6d 79 5f ---o......if my_
1820: 70 61 69 72 5b 31 5d 20 3e 20 6f 74 68 65 72 5f pair[1] > other_
1830: 70 61 69 72 5b 31 5d 3a 0a 09 09 09 09 09 09 23 pair[1]:.......#
1840: 20 77 68 65 6e 20 6d 79 20 70 61 69 72 20 65 6e when my pair en
1850: 64 73 20 61 66 74 65 72 20 6f 74 68 65 72 20 70 ds after other p
1860: 61 69 72 20 65 6e 64 73 0a 09 09 09 09 09 09 23 air ends.......#
1870: 20 20 20 20 6d 2d 2d 2d 6d 20 7c 20 20 20 20 20 m---m |
1880: 6d 2d 2d 2d 6d 0a 09 09 09 09 09 09 23 20 6f 2d m---m.......# o-
1890: 2d 2d 6f 20 20 20 20 7c 20 6f 2d 2d 2d 6f 0a 09 --o | o---o..
18a0: 09 09 09 09 09 6d 79 5f 70 61 69 72 5b 30 5d 20 .....my_pair[0]
18b0: 3d 20 6f 74 68 65 72 5f 70 61 69 72 5b 31 5d 0a = other_pair[1].
18c0: 09 09 09 09 09 09 23 20 74 72 69 6d 6d 69 6e 67 ......# trimming
18d0: 20 6d 79 20 70 61 69 72 20 62 79 20 6f 74 68 65 my pair by othe
18e0: 72 20 70 61 69 72 20 65 6e 64 0a 09 09 09 09 09 r pair end......
18f0: 09 23 20 20 20 6d 2e 6d 2d 6d 0a 09 09 09 09 09 .# m.m-m......
1900: 09 23 20 6f 2d 2d 2d 6f 0a 09 09 09 09 09 09 6f .# o---o.......o
1910: 74 68 65 72 5f 70 61 69 72 20 3d 20 6f 74 68 65 ther_pair = othe
1920: 72 2e 70 6f 70 28 29 0a 09 09 09 09 09 09 23 20 r.pop().......#
1930: 74 6f 73 73 69 6e 67 20 6f 75 74 20 6f 74 68 65 tossing out othe
1940: 72 20 70 61 69 72 0a 09 09 09 09 09 09 69 66 20 r pair.......if
1950: 6f 74 68 65 72 5f 70 61 69 72 5b 30 5d 20 3d 3d other_pair[0] ==
1960: 20 4e 6f 6e 65 3a 0a 09 09 09 09 09 09 23 20 74 None:.......# t
1970: 68 69 73 20 77 61 73 20 6c 61 73 74 20 6f 6e 65 his was last one
1980: 20 2d 20 6d 79 20 70 61 69 72 20 67 6f 65 73 20 - my pair goes
1990: 74 6f 20 72 65 73 75 6c 74 0a 09 09 09 09 09 09 to result.......
19a0: 09 6e 65 77 5b 6d 79 5f 70 61 69 72 5b 30 5d 5d .new[my_pair[0]]
19b0: 20 3d 20 6d 79 5f 70 61 69 72 5b 31 5d 0a 09 09 = my_pair[1]...
19c0: 09 09 09 09 09 61 6c 6c 5f 70 61 72 74 73 5f 66 .....all_parts_f
19d0: 6f 75 6e 64 20 3d 20 54 72 75 65 0a 09 09 09 09 ound = True.....
19e0: 09 65 6c 73 65 3a 0a 09 09 09 09 09 09 23 20 77 .else:.......# w
19f0: 68 65 6e 20 6d 79 20 70 61 69 72 20 65 6e 64 73 hen my pair ends
1a00: 20 62 65 66 6f 72 65 20 6f 74 68 65 72 20 70 61 before other pa
1a10: 69 72 20 65 6e 64 73 0a 09 09 09 09 09 09 23 20 ir ends.......#
1a20: 20 6d 2d 2d 2d 6d 0a 09 09 09 09 09 09 23 20 6f m---m.......# o
1a30: 2d 2d 2d 2d 2d 6f 0a 09 09 09 09 09 09 6d 79 5f -----o.......my_
1a40: 70 61 69 72 20 3d 20 73 65 6c 66 2e 70 6f 70 28 pair = self.pop(
1a50: 29 0a 09 09 09 09 09 09 23 20 74 6f 73 73 69 6e ).......# tossin
1a60: 67 20 6f 75 74 20 6d 79 20 70 61 69 72 0a 09 09 g out my pair...
1a70: 09 09 09 09 69 66 20 6d 79 5f 70 61 69 72 5b 30 ....if my_pair[0
1a80: 5d 20 3d 3d 20 4e 6f 6e 65 3a 0a 09 09 09 09 09 ] == None:......
1a90: 09 09 61 6c 6c 5f 70 61 72 74 73 5f 66 6f 75 6e ..all_parts_foun
1aa0: 64 20 3d 20 54 72 75 65 0a 09 09 09 65 6c 69 66 d = True....elif
1ab0: 20 6d 79 5f 70 61 69 72 5b 30 5d 20 3c 20 6f 74 my_pair[0] < ot
1ac0: 68 65 72 5f 70 61 69 72 5b 30 5d 3a 0a 09 09 09 her_pair[0]:....
1ad0: 09 23 20 77 68 65 6e 20 6d 79 20 70 61 69 72 20 .# when my pair
1ae0: 73 74 61 72 74 73 20 62 65 66 6f 72 65 20 6f 74 starts before ot
1af0: 68 65 72 20 6f 6e 65 0a 09 09 09 09 23 20 6d 2d her one.....# m-
1b00: 2d 2d 0a 09 09 09 09 23 20 20 6f 2d 2d 2d 0a 09 --.....# o---..
1b10: 09 09 09 69 66 20 6d 79 5f 70 61 69 72 5b 31 5d ...if my_pair[1]
1b20: 20 3c 20 6f 74 68 65 72 5f 70 61 69 72 5b 30 5d < other_pair[0]
1b30: 3a 0a 09 09 09 09 09 23 20 77 68 65 6e 20 6d 79 :......# when my
1b40: 20 70 61 69 72 20 65 6e 64 73 20 62 65 66 6f 72 pair ends befor
1b50: 65 20 6f 74 68 65 72 20 70 61 69 72 20 73 74 61 e other pair sta
1b60: 72 74 73 0a 09 09 09 09 09 23 20 6d 2d 2d 2d 6d rts......# m---m
1b70: 0a 09 09 09 09 09 23 20 20 20 20 20 20 20 6f 2d ......# o-
1b80: 2d 2d 0a 09 09 09 09 09 6e 65 77 5b 6d 79 5f 70 --......new[my_p
1b90: 61 69 72 5b 30 5d 5d 20 3d 20 6d 79 5f 70 61 69 air[0]] = my_pai
1ba0: 72 5b 31 5d 0a 09 09 09 09 09 23 20 6d 79 20 70 r[1]......# my p
1bb0: 61 69 72 20 69 73 20 6e 6f 74 20 63 6f 76 65 72 air is not cover
1bc0: 65 64 20 61 6e 64 20 73 68 6f 75 6c 64 20 62 65 ed and should be
1bd0: 20 61 64 64 65 64 20 74 6f 20 72 65 73 75 6c 74 added to result
1be0: 0a 09 09 09 09 09 6d 79 5f 70 61 69 72 20 3d 20 ......my_pair =
1bf0: 73 65 6c 66 2e 70 6f 70 28 29 0a 09 09 09 09 09 self.pop()......
1c00: 23 20 74 6f 73 73 69 6e 67 20 6f 75 74 20 6d 79 # tossing out my
1c10: 20 70 61 69 72 0a 09 09 09 09 09 69 66 20 6d 79 pair......if my
1c20: 5f 70 61 69 72 5b 30 5d 20 3d 3d 20 4e 6f 6e 65 _pair[0] == None
1c30: 3a 0a 09 09 09 09 09 09 61 6c 6c 5f 70 61 72 74 :.......all_part
1c40: 73 5f 66 6f 75 6e 64 20 3d 20 54 72 75 65 0a 09 s_found = True..
1c50: 09 09 09 65 6c 73 65 3a 0a 09 09 09 09 09 23 20 ...else:......#
1c60: 77 68 65 6e 20 6d 79 20 70 61 69 72 20 65 6e 64 when my pair end
1c70: 73 20 62 65 66 6f 72 65 20 6f 74 68 65 72 20 70 s before other p
1c80: 61 69 72 20 73 74 61 72 74 73 0a 09 09 09 09 09 air starts......
1c90: 23 20 6d 2d 2d 2d 6d 0a 09 09 09 09 09 23 20 20 # m---m......#
1ca0: 20 6f 2d 2d 2d 0a 09 09 09 09 09 6e 65 77 5b 6d o---......new[m
1cb0: 79 5f 70 61 69 72 5b 30 5d 5d 20 3d 20 6f 74 68 y_pair[0]] = oth
1cc0: 65 72 5f 70 61 69 72 5b 30 5d 0a 09 09 09 09 09 er_pair[0]......
1cd0: 23 20 73 74 61 72 74 20 6f 66 20 6d 79 20 70 61 # start of my pa
1ce0: 69 72 20 69 73 20 6e 6f 74 20 63 6f 76 65 72 65 ir is not covere
1cf0: 64 20 61 6e 64 20 73 68 6f 75 6c 64 20 62 65 20 d and should be
1d00: 61 64 64 65 64 20 74 6f 20 72 65 73 75 6c 74 0a added to result.
1d10: 09 09 09 09 09 6d 79 5f 70 61 69 72 5b 30 5d 20 .....my_pair[0]
1d20: 3d 20 6f 74 68 65 72 5f 70 61 69 72 5b 30 5d 0a = other_pair[0].
1d30: 09 09 09 09 09 23 20 74 72 69 6d 6d 69 6e 67 20 .....# trimming
1d40: 6d 79 20 70 61 69 72 20 62 79 20 6f 74 68 65 72 my pair by other
1d50: 20 70 61 69 72 20 73 74 61 72 74 0a 09 09 09 09 pair start.....
1d60: 09 23 20 6d 2e 6d 2d 6d 0a 09 09 09 09 09 23 20 .# m.m-m......#
1d70: 20 20 6f 2d 2d 2d 0a 09 09 09 65 6c 73 65 3a 0a o---....else:.
1d80: 09 09 09 09 23 20 77 68 65 6e 20 62 6f 74 68 20 ....# when both
1d90: 70 61 69 72 73 20 73 74 61 72 74 73 20 73 69 6d pairs starts sim
1da0: 75 6c 74 61 6e 65 6f 75 73 6c 79 0a 09 09 09 09 ultaneously.....
1db0: 23 20 6d 2d 2d 2d 0a 09 09 09 09 23 20 6f 2d 2d # m---.....# o--
1dc0: 2d 0a 09 09 09 09 69 66 20 6d 79 5f 70 61 69 72 -.....if my_pair
1dd0: 5b 31 5d 20 3c 20 6f 74 68 65 72 5f 70 61 69 72 [1] < other_pair
1de0: 5b 31 5d 3a 0a 09 09 09 09 09 23 20 77 68 65 6e [1]:......# when
1df0: 20 6d 79 20 70 61 69 72 20 65 6e 64 73 20 62 65 my pair ends be
1e00: 66 6f 72 65 20 6f 74 68 65 72 20 70 61 69 72 0a fore other pair.
1e10: 09 09 09 09 09 23 20 6d 2d 2d 2d 6d 0a 09 09 09 .....# m---m....
1e20: 09 09 23 20 6f 2d 2d 2d 2d 2d 6f 0a 09 09 09 09 ..# o-----o.....
1e30: 09 6d 79 5f 70 61 69 72 20 3d 20 73 65 6c 66 2e .my_pair = self.
1e40: 70 6f 70 28 29 0a 09 09 09 09 09 23 20 74 6f 73 pop()......# tos
1e50: 73 69 6e 67 20 6f 75 74 20 6d 79 20 70 61 69 72 sing out my pair
1e60: 0a 09 09 09 09 09 69 66 20 6d 79 5f 70 61 69 72 ......if my_pair
1e70: 5b 30 5d 20 3d 3d 20 4e 6f 6e 65 3a 0a 09 09 09 [0] == None:....
1e80: 09 09 09 61 6c 6c 5f 70 61 72 74 73 5f 66 6f 75 ...all_parts_fou
1e90: 6e 64 20 3d 20 54 72 75 65 0a 09 09 09 09 65 6c nd = True.....el
1ea0: 73 65 3a 0a 09 09 09 09 09 23 20 77 68 65 6e 20 se:......# when
1eb0: 6d 79 20 70 61 69 72 20 65 6e 64 73 20 61 66 74 my pair ends aft
1ec0: 65 72 20 6f 74 68 65 72 20 70 61 69 72 0a 09 09 er other pair...
1ed0: 09 09 09 23 20 6d 2d 2d 2d 2d 2d 6d 0a 09 09 09 ...# m-----m....
1ee0: 09 09 23 20 6f 2d 2d 2d 6f 0a 09 09 09 09 09 6d ..# o---o......m
1ef0: 79 5f 70 61 69 72 5b 30 5d 20 3d 20 6f 74 68 65 y_pair[0] = othe
1f00: 72 5f 70 61 69 72 5b 31 5d 0a 09 09 09 09 09 23 r_pair[1]......#
1f10: 20 74 72 69 6d 6d 69 6e 67 20 6d 79 20 70 61 69 trimming my pai
1f20: 72 20 62 79 20 6f 74 68 65 72 20 70 61 69 72 20 r by other pair
1f30: 65 6e 64 0a 09 09 09 09 09 23 20 6d 2e 2e 2e 6d end......# m...m
1f40: 2d 6d 0a 09 09 09 09 09 23 20 6f 2d 2d 2d 6f 0a -m......# o---o.
1f50: 09 09 09 09 09 6f 74 68 65 72 5f 70 61 69 72 20 .....other_pair
1f60: 3d 20 6f 74 68 65 72 2e 70 6f 70 28 29 0a 09 09 = other.pop()...
1f70: 09 09 09 23 20 74 6f 73 73 69 6e 67 20 6f 75 74 ...# tossing out
1f80: 20 6f 74 68 65 72 20 70 61 69 72 0a 09 09 09 09 other pair.....
1f90: 09 69 66 20 6f 74 68 65 72 5f 70 61 69 72 5b 30 .if other_pair[0
1fa0: 5d 20 3d 3d 20 4e 6f 6e 65 3a 0a 09 09 09 09 09 ] == None:......
1fb0: 09 23 20 74 68 69 73 20 77 61 73 20 6c 61 73 74 .# this was last
1fc0: 20 6f 6e 65 20 2d 20 6d 79 20 70 61 69 72 20 67 one - my pair g
1fd0: 6f 65 73 20 74 6f 20 72 65 73 75 6c 74 0a 09 09 oes to result...
1fe0: 09 09 09 09 6e 65 77 5b 6d 79 5f 70 61 69 72 5b ....new[my_pair[
1ff0: 30 5d 5d 20 3d 20 6d 79 5f 70 61 69 72 5b 31 5d 0]] = my_pair[1]
2000: 0a 09 09 09 09 09 09 61 6c 6c 5f 70 61 72 74 73 .......all_parts
2010: 5f 66 6f 75 6e 64 20 3d 20 54 72 75 65 0a 09 09 _found = True...
2020: 77 68 69 6c 65 20 54 72 75 65 3a 0a 09 09 09 23 while True:....#
2030: 20 63 6f 70 79 20 61 6e 79 20 6c 65 66 74 6f 76 copy any leftov
2040: 65 72 20 69 6e 20 41 20 74 6f 20 6e 65 77 20 53 er in A to new S
2050: 70 61 63 65 4d 61 70 0a 09 09 09 6d 79 5f 70 61 paceMap....my_pa
2060: 69 72 20 3d 20 73 65 6c 66 2e 70 6f 70 28 29 0a ir = self.pop().
2070: 09 09 09 69 66 20 6d 79 5f 70 61 69 72 5b 30 5d ...if my_pair[0]
2080: 20 3d 3d 20 4e 6f 6e 65 3a 0a 09 09 09 09 62 72 == None:.....br
2090: 65 61 6b 0a 09 09 09 65 6c 73 65 3a 0a 09 09 09 eak....else:....
20a0: 09 6e 65 77 5b 6d 79 5f 70 61 69 72 5b 30 5d 5d .new[my_pair[0]]
20b0: 20 3d 20 6d 79 5f 70 61 69 72 5b 31 5d 0a 09 09 = my_pair[1]...
20c0: 73 65 6c 66 2e 63 6c 65 61 72 28 29 0a 09 09 6f self.clear()...o
20d0: 74 68 65 72 2e 63 6c 65 61 72 28 29 0a 09 09 72 ther.clear()...r
20e0: 65 74 75 72 6e 28 53 70 61 63 65 4d 61 70 28 6e eturn(SpaceMap(n
20f0: 65 77 2c 20 73 65 6c 66 2e 5f 5f 62 6f 74 74 6f ew, self.__botto
2100: 6d 2c 20 73 65 6c 66 2e 5f 5f 74 6f 70 29 29 0a m, self.__top)).
2110: 0a 09 64 65 66 20 5f 5f 65 71 5f 5f 28 73 65 6c ..def __eq__(sel
2120: 66 2c 20 6f 74 68 65 72 29 3a 0a 09 09 27 27 27 f, other):...'''
2130: 43 6f 6d 70 61 72 65 73 20 74 77 6f 20 73 70 61 Compares two spa
2140: 63 65 20 6d 61 70 73 2e 27 27 27 0a 09 09 69 66 ce maps.'''...if
2150: 20 74 79 70 65 28 6f 74 68 65 72 29 20 21 3d 20 type(other) !=
2160: 53 70 61 63 65 4d 61 70 3a 0a 09 09 09 72 65 74 SpaceMap:....ret
2170: 75 72 6e 28 46 61 6c 73 65 29 0a 09 09 73 65 6c urn(False)...sel
2180: 66 2e 72 65 77 69 6e 64 28 29 0a 09 09 6f 74 68 f.rewind()...oth
2190: 65 72 2e 72 65 77 69 6e 64 28 29 0a 09 09 72 65 er.rewind()...re
21a0: 73 75 6c 74 20 3d 20 4e 6f 6e 65 0a 09 09 77 68 sult = None...wh
21b0: 69 6c 65 20 54 72 75 65 3a 0a 09 09 09 74 68 69 ile True:....thi
21c0: 73 20 3d 20 73 65 6c 66 2e 70 6f 70 28 29 0a 09 s = self.pop()..
21d0: 09 09 74 68 61 74 20 3d 20 6f 74 68 65 72 2e 70 ..that = other.p
21e0: 6f 70 28 29 0a 09 09 09 69 66 20 74 68 69 73 20 op()....if this
21f0: 21 3d 20 74 68 61 74 3a 0a 09 09 09 09 72 65 73 != that:.....res
2200: 75 6c 74 20 3d 20 46 61 6c 73 65 0a 09 09 09 09 ult = False.....
2210: 62 72 65 61 6b 0a 09 09 09 69 66 20 74 68 69 73 break....if this
2220: 20 3d 3d 20 5b 4e 6f 6e 65 2c 20 4e 6f 6e 65 5d == [None, None]
2230: 20 61 6e 64 20 74 68 61 74 20 3d 3d 20 5b 4e 6f and that == [No
2240: 6e 65 2c 20 4e 6f 6e 65 5d 3a 0a 09 09 09 09 72 ne, None]:.....r
2250: 65 73 75 6c 74 20 3d 20 54 72 75 65 0a 09 09 09 esult = True....
2260: 09 62 72 65 61 6b 0a 09 09 73 65 6c 66 2e 63 6c .break...self.cl
2270: 65 61 72 28 29 0a 09 09 6f 74 68 65 72 2e 63 6c ear()...other.cl
2280: 65 61 72 28 29 0a 09 09 72 65 74 75 72 6e 28 72 ear()...return(r
2290: 65 73 75 6c 74 29 0a 0a 09 64 65 66 20 65 6e 64 esult)...def end
22a0: 28 73 65 6c 66 29 3a 0a 09 09 27 27 27 52 65 74 (self):...'''Ret
22b0: 75 72 6e 73 20 6c 61 73 74 20 6b 6e 6f 77 6e 20 urns last known
22c0: 70 6f 69 6e 74 2e 27 27 27 0a 09 09 65 6e 64 20 point.'''...end
22d0: 3d 20 4e 6f 6e 65 0a 09 09 73 65 6c 66 2e 72 65 = None...self.re
22e0: 77 69 6e 64 28 29 0a 09 09 77 68 69 6c 65 20 54 wind()...while T
22f0: 72 75 65 3a 0a 09 09 09 74 68 69 73 20 3d 20 73 rue:....this = s
2300: 65 6c 66 2e 70 6f 70 28 29 0a 09 09 09 69 66 20 elf.pop()....if
2310: 74 68 69 73 20 3d 3d 20 5b 4e 6f 6e 65 2c 20 4e this == [None, N
2320: 6f 6e 65 5d 3a 0a 09 09 09 09 62 72 65 61 6b 0a one]:.....break.
2330: 09 09 09 65 6c 69 66 20 65 6e 64 20 3d 3d 20 4e ...elif end == N
2340: 6f 6e 65 20 6f 72 20 74 68 69 73 5b 31 5d 20 3e one or this[1] >
2350: 20 65 6e 64 3a 0a 09 09 09 09 65 6e 64 20 3d 20 end:.....end =
2360: 74 68 69 73 5b 31 5d 0a 09 09 73 65 6c 66 2e 63 this[1]...self.c
2370: 6c 65 61 72 28 29 0a 09 09 72 65 74 75 72 6e 28 lear()...return(
2380: 65 6e 64 29 0a 0a 09 64 65 66 20 5f 5f 6c 65 6e end)...def __len
2390: 5f 5f 28 73 65 6c 66 29 3a 0a 09 09 72 65 74 75 __(self):...retu
23a0: 72 6e 28 6c 65 6e 28 73 65 6c 66 2e 5f 5f 70 61 rn(len(self.__pa
23b0: 69 72 73 29 29 0a irs)).