segments.py 35.9 KB
Newer Older
1
# Copyright (C) 2006  Kipp Cannon
kipp's avatar
kipp committed
2 3 4
#
# This program is free software; you can redistribute it and/or modify it
# under the terms of the GNU General Public License as published by the
duncan's avatar
duncan committed
5
# Free Software Foundation; either version 3 of the License, or (at your
kipp's avatar
kipp committed
6 7 8 9 10 11 12 13 14 15
# option) any later version.
#
# This program is distributed in the hope that it will be useful, but
# WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General
# Public License for more details.
#
# You should have received a copy of the GNU General Public License along
# with this program; if not, write to the Free Software Foundation, Inc.,
# 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
kipp's avatar
kipp committed
16

17

kipp's avatar
kipp committed
18 19 20 21 22 23 24 25
#
# =============================================================================
#
#                                   Preamble
#
# =============================================================================
#

26

27 28 29 30
#
# NOTE:  the logic in this code is unintuitively complicated.  Small,
# apparently irrelevant, changes to conditionals can have subtly unexpected
# consequences to the behaviour of the class methods.  ALWAYS make sure that
31
# the test suite returns OK on ALL tests after any changes you make.
32 33
#

34

35 36 37
"""
This module defines the segment and segmentlist objects, as well as the
infinity object used to define semi-infinite and infinite segments.
Kipp Cannon's avatar
Kipp Cannon committed
38 39 40 41

See also:

glue.segmentsUtils
42 43
"""

kipp's avatar
kipp committed
44

45 46 47
from bisect import bisect_left as _bisect_left
from bisect import bisect_right as _bisect_right
from copy import copy as _shallowcopy
kipp's avatar
kipp committed
48

49

50 51
import six
from six.moves import range
52 53 54


__author__ = "Kipp Cannon <kipp.cannon@ligo.org>"
55
__version__ = '1.0.0'
56 57 58


#
kipp's avatar
kipp committed
59 60 61 62 63
# =============================================================================
#
#                                   infinity
#
# =============================================================================
64 65
#

66

kipp's avatar
kipp committed
67
class infinity(object):
68
	"""
69 70
	The infinity object possess the algebraic properties necessary for
	use as a bound on semi-infinite and infinite segments.
71

kipp's avatar
kipp committed
72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
	This class uses comparison-by-identity rather than
	comparison-by-value.  What this means, is there are only ever two
	instances of this class, representing positive and negative
	infinity respectively.  All other "instances" of this class are
	infact simply references to one of these two, and comparisons are
	done by checking which one you've got.  This improves speed and
	reduces memory use, and is similar in implementation to Python's
	boolean True and False objects.

	The normal way to obtain references to positive or negative
	infinity is to do infinity() or -infinity() respectively.  It is
	also possible to select the sign by passing a single numeric
	argument to the constructor.  The sign of the argument causes a
	reference to either positive or negative infinity to be returned,
	respectively.  For example infinity(-1) is equivalent to
	-infinity().  However, this feature is a little slower and not
	recommended for normal use;  it is provided only to simplify the
	pickling and unpickling of instances of the class.

kipp's avatar
kipp committed
91 92 93 94 95
	Example:

	>>> x = infinity()
	>>> x > 0
	True
kipp's avatar
kipp committed
96 97
	>>> x + 10 == x
	True
kipp's avatar
kipp committed
98 99
	>>> segment(-10, 10) - segment(-x, 0)
	segment(0, 10)
100 101 102
	>>> import math
	>>> math.isinf(x)
	True
103
	"""
kipp's avatar
kipp committed
104 105 106 107 108 109 110 111 112 113
	__slots__ = []

	def __new__(cls, *args):
		if args:
			# pickle support
			(sign,) = args
			if sign > 0:
				return PosInfinity
			if sign < 0:
				return NegInfinity
114
			raise ValueError(sign)
kipp's avatar
kipp committed
115
		return PosInfinity
116 117

	def __repr__(self):
kipp's avatar
kipp committed
118 119 120 121
		"""
		Returns a string.
		"""
		if self is PosInfinity:
122 123
			return "infinity"
		return "-infinity"
kipp's avatar
kipp committed
124

125
	__str__ = __repr__
kipp's avatar
kipp committed
126 127 128 129 130 131 132 133 134 135 136 137 138 139

	# pickle support

	def __reduce__(self):
		"""
		Pickle support.
		"""
		if self is PosInfinity:
			return (infinity, (1,))
		# self is NegInfinity
		return (infinity, (-1,))

	# tests

140 141 142 143 144 145 146 147 148 149 150 151
	def __cmp__(self, other):
		"""
		Positive infinity compares as greater than everything
		except itself, negative infinity compares as less than
		everything except itself.
		"""
		if self is other:
			return 0
		if self is PosInfinity:
			return 1
		# self is NegInfinity
		return -1
kipp's avatar
kipp committed
152

153
	def __nonzero__(self):
kipp's avatar
kipp committed
154 155 156
		"""
		Returns True.
		"""
157
		return True
kipp's avatar
kipp committed
158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175

	# arithmetic

	def __neg__(self):
		"""
		Returns -self.
		"""
		if self is PosInfinity:
			return NegInfinity
		# self is NegInfinity
		return PosInfinity

	def __pos__(self):
		"""
		Returns self.
		"""
		return self

176
	def __add__(self, other):
kipp's avatar
kipp committed
177 178 179
		"""
		Returns self.
		"""
180
		return self
kipp's avatar
kipp committed
181

182
	def __radd__(self, other):
kipp's avatar
kipp committed
183 184 185
		"""
		Returns self.
		"""
186
		return self
kipp's avatar
kipp committed
187

188
	def __sub__(self, other):
kipp's avatar
kipp committed
189 190 191 192
		"""
		Returns self.
		"""
		return self
193

kipp's avatar
kipp committed
194 195 196 197 198 199 200 201
	def __rsub__(self, other):
		"""
		Returns -self.
		"""
		if self is PosInfinity:
			return NegInfinity
		# self is NegInfinity
		return PosInfinity
202

203 204 205 206 207 208 209 210 211
	def __float__(self):
		"""
		Returns +/-inf (allows math.isinf() to work).
		"""
		if self is PosInfinity:
			return float("+inf")
		# self is NegInfinity
		return float("-inf")

212

kipp's avatar
kipp committed
213 214
PosInfinity = object.__new__(infinity)
NegInfinity = object.__new__(infinity)
215

216 217

#
kipp's avatar
kipp committed
218 219 220 221 222
# =============================================================================
#
#                                   segment
#
# =============================================================================
223 224
#

225

226
class segment(tuple):
227
	"""
228 229
	The segment class defines objects that represent a range of values.
	A segment has a start and an end, and is taken to represent the
230
	range of values in the semi-open interval [start, end).  Some
231 232 233 234 235 236 237
	limited arithmetic operations are possible with segments, but
	because the set of (single) segments is not closed under the
	sensible definitions of the standard arithmetic operations, the
	behaviour of the arithmetic operators on segments may not be as you
	would expect.  For general arithmetic on segments, use segmentlist
	objects.  The methods for this class exist mostly for purpose of
	simplifying the implementation of the segmentlist class.
238

239 240 241 242 243 244 245 246 247 248 249
	The segment class is a subclass of the tuple built-in class
	provided by Python.  This means segments are immutable --- you
	cannot modify a segment object after creating it, to change the
	boundaries of a segment you must create a new segment object with
	the desired boundaries.  Like tuples, segments can be used as
	dictionary keys, and like tuples the comparison used to find a
	segment in the dictionary is done by value not by ID.  And, like
	tuples, a segment can be created from any sequence-like object by
	passing it to the constructor (the sequence must have exactly two
	elements in it).

kipp's avatar
kipp committed
250 251 252 253 254 255 256 257 258 259 260 261
	Example:

	>>> segment(0, 10) & segment(5, 15)
	segment(5, 10)
	>>> segment(0, 10) | segment(5, 15)
	segment(0, 15)
	>>> segment(0, 10) - segment(5, 15)
	segment(0, 5)
	>>> segment(0, 10) < segment(5, 15)
	True
	>>> segment(1, 2) in segment(0, 10)
	True
262 263 264 265 266 267 268 269
	>>> segment(1, 11) in segment(0, 10)
	False
	>>> segment(0, 1)
	segment(0, 1)
	>>> segment(1, 0)
	segment(0, 1)
	>>> bool(segment(0, 1))
	True
kipp's avatar
kipp committed
270 271
	>>> bool(segment(0, 0))
	False
272 273
	>>> segment("AAA Towing", "York University") & segment("Pool", "Zoo")
	segment('Pool', 'York University')
274
	>>> x = [0, 1]	# a list
kipp's avatar
kipp committed
275 276
	>>> segment(x)
	segment(0, 1)
277 278 279 280 281
	>>> y = segment(0, 1)
	>>> y == x
	True
	>>> y is x
	False
282 283
	>>> x in y
	True
284 285 286 287 288
	>>> z = {x: ["/path/to/file1", "/path/to/file2"]}
	>>> y in z
	True
	>>> z[y]
	['/path/to/file1', '/path/to/file2']
289 290 291 292
	"""

	# basic class methods

293 294 295 296
	def __new__(cls, *args):
		if len(args) == 1:
			args = args[0]
		if len(args) != 2:
297
			raise TypeError("__new__() takes 2 arguments, or 1 argument when it is a sequence of length 2")
298 299
		if args[0] <= args[1]:
			return tuple.__new__(cls, args)
300
		else:
301
			return tuple.__new__(cls, (args[1], args[0]))
302 303

	def __repr__(self):
304
		return "segment(%s, %s)" % (repr(self[0]), repr(self[1]))
305 306

	def __str__(self):
307
		return "[%s ... %s)" % (str(self[0]), str(self[1]))
308 309 310

	# accessors

311
	def __abs__(self):
312
		"""
313
		Returns the length of the interval represented by the
314 315
		segment.  Requires the bounds to support the subtract
		operation.
316
		"""
317
		return self[1] - self[0]
318 319 320 321 322

	# comparisons

	def __nonzero__(self):
		"""
323 324
		Return True if the segment's boudaries are not equal, False
		if they are equal.
325
		"""
326
		return self[0] != self[1]
327

328
	def disjoint(self, other):
329 330 331 332 333 334 335 336 337 338 339 340 341
		"""
		Returns >0 if self covers an interval above other's
		interval, <0 if self covers an interval below other's, or 0
		if the two intervals are not disjoint (intersect or touch).
		A return value of 0 indicates the two segments would
		coalesce.
		"""
		if self[0] > other[1]:
			return 1
		if self[1] < other[0]:
			return -1
		return 0

342
	def __lt__(self, other):
343
		if isinstance(other, tuple):
344 345 346 347
			return tuple.__lt__(self, other)
		return self[0] < other

	def __le__(self, other):
348
		if isinstance(other, tuple):
349 350 351 352
			return tuple.__le__(self, other)
		return self[0] <= other

	def __eq__(self, other):
353
		if isinstance(other, tuple):
354 355 356 357
			return tuple.__eq__(self, other)
		return self[0] == other

	def __ne__(self, other):
358
		if isinstance(other, tuple):
359 360 361 362
			return tuple.__ne__(self, other)
		return self[0] != other

	def __gt__(self, other):
363
		if isinstance(other, tuple):
364 365 366 367
			return tuple.__gt__(self, other)
		return self[0] > other

	def __ge__(self, other):
368
		if isinstance(other, tuple):
369 370 371
			return tuple.__ge__(self, other)
		return self[0] >= other

372 373 374 375 376 377 378 379 380 381 382
	#
	# From <https://docs.python.org/3/reference/datamodel.html#object.__hash__>:
	#
	# "if [a class] defines __eq__() but not __hash__(), its instances will not
	# be usable as items in hashable collections... If a class that overrides
	# __eq__() needs to retain the implementation of __hash__() from a parent
	# class, the interpreter must be told this explicitly by setting __hash__ =
	# <ParentClass>.__hash__."
	#
	__hash__ = tuple.__hash__

383 384 385 386 387
	# some arithmetic operations that (mostly) make sense for segments

	def __and__(self, other):
		"""
		Return the segment that is the intersection of the given
388 389
		segments.  Raises ValueError if the result cannot be
		presented as a single segment.
390
		"""
391 392
		if (self[1] <= other[0]) or (self[0] >= other[1]):
			# self and other don't intersect
393
			raise ValueError(other)
394
		return tuple.__new__(self.__class__, (max(self[0], other[0]), min(self[1], other[1])))
395 396 397

	def __or__(self, other):
		"""
398 399 400
		Return the segment that is the union of the given segments.
		Raises ValueError if the result cannot be represented as a
		single segment.
401
		"""
402 403
		if (self[1] < other[0]) or (self[0] > other[1]):
			# self and other are disjoint
404
			raise ValueError(other)
405
		return tuple.__new__(self.__class__, (min(self[0], other[0]), max(self[1], other[1])))
406

407
	# addition is union
408 409 410 411 412
	__add__ = __or__

	def __sub__(self, other):
		"""
		Return the segment that is that part of self which is not
413 414
		contained in other.  Raises ValueError if the result cannot
		be represented as a single segment.
415
		"""
416 417
		if (self[1] <= other[0]) or (self[0] >= other[1]):
			# self and other do not intersect
418
			return self
419
		if (self in other) or ((self[0] < other[0]) and (self[1] > other[1])):
kipp's avatar
kipp committed
420
			# result is not exactly 1 segment
421
			raise ValueError(other)
422
		if self[0] < other[0]:
423 424
			return tuple.__new__(self.__class__, (self[0], other[0]))
		return tuple.__new__(self.__class__, (other[1], self[1]))
425

kipp's avatar
kipp committed
426
	# check for proper intersection and subsetness
427 428 429

	def intersects(self, other):
		"""
430 431
		Return True if the intersection of self and other is not a
		null segment.
432
		"""
433
		return (self[1] > other[0]) and (self[0] < other[1])
434

435 436 437 438 439 440
	def connects(self, other):
		"""
		Returns True if ths segment and other touch but do not overlap
		"""
		return (self[1] == other[0]) or (self[0] == other[1])

441 442
	def __contains__(self, other):
		"""
443 444 445 446 447 448
		Return True if other is wholly contained in self.  If other
		is an instance of the segment class or an instance of a
		subclass of segment then it is treated as an interval whose
		upper and lower bounds must not be outside of self,
		otherwise other is compared to the bounds of self as a
		scalar.
449
		"""
450 451
		try:
			a, b = other
452
		except ValueError:
453
			return self[0] <= other < self[1]
454 455
		else:
			return (self[0] <= a) and (self[1] >= b)
456

457
	# protraction and contraction and shifting
458 459 460

	def protract(self, x):
		"""
Kipp Cannon's avatar
Kipp Cannon committed
461 462 463
		Return a new segment whose bounds are given by subtracting
		x from the segment's lower bound and adding x to the
		segment's upper bound.
464
		"""
465
		return self.__class__(self[0] - x, self[1] + x)
466 467 468

	def contract(self, x):
		"""
Kipp Cannon's avatar
Kipp Cannon committed
469 470 471
		Return a new segment whose bounds are given by adding x to
		the segment's lower bound and subtracting x from the
		segment's upper bound.
472
		"""
473
		return self.__class__(self[0] + x, self[1] - x)
474

475 476
	def shift(self, x):
		"""
Kipp Cannon's avatar
Kipp Cannon committed
477 478
		Return a new segment whose bounds are given by adding x to
		the segment's upper and lower bounds.
479
		"""
480
		return tuple.__new__(self.__class__, (self[0] + x, self[1] + x))
481

482 483

#
kipp's avatar
kipp committed
484 485 486 487 488
# =============================================================================
#
#                                 segmentlist
#
# =============================================================================
489 490
#

491

492 493
class segmentlist(list):
	"""
494 495 496 497 498 499 500
	The segmentlist class defines a list of segments, and is an
	extension of the built-in list class.  This class provides
	addtional methods that assist in the manipulation of lists of
	segments.  In particular, arithmetic operations such as union and
	intersection are provided.  Unlike the segment class, the
	segmentlist class is closed under all supported arithmetic
	operations.
501 502

	All standard Python sequence-like operations are supported, like
Kipp Cannon's avatar
Kipp Cannon committed
503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519
	slicing, iteration and so on, including arithmetic operations.
	However, the arithmetic and other methods for this class generally
	require the segmentlist to be in what is refered to as a
	"coalesced" state --- consisting solely of disjoint segments listed
	in ascending order.  Using the standard Python sequence-like
	operations, a segmentlist can be easily constructed that is not in
	this state;  for example by simply appending a segment to the end
	of the list that overlaps some other segment already in the list.
	The use of methods that require coalesced lists with lists that are
	not coalesced has undefined results.  The class provides the
	.coalesce() method that can be called to put a segmentlist in the
	coalesced state.  All arithmetic methods return coalesced results,
	so typically the .coalesce() method will be executed once after
	importing a segmentlist from an untrusted source, then there is
	never a need to call the .coalesce() method again as long as the
	segmentlists are manipulated exclusively via the arithmetic
	operators.
520

kipp's avatar
kipp committed
521 522 523 524 525
	Example:

	>>> x = segmentlist([segment(-10, 10)])
	>>> x |= segmentlist([segment(20, 30)])
	>>> x -= segmentlist([segment(-5, 5)])
526
	>>> print(x)
kipp's avatar
kipp committed
527
	[segment(-10, -5), segment(5, 10), segment(20, 30)]
528
	>>> print(~x)
kipp's avatar
kipp committed
529
	[segment(-infinity, -10), segment(-5, 5), segment(10, 20), segment(30, infinity)]
530 531 532 533 534 535
	"""

	# container method over-rides.

	def __contains__(self, item):
		"""
kipp's avatar
kipp committed
536
		Returns True if the given object is wholly contained within
Kipp Cannon's avatar
Kipp Cannon committed
537 538 539
		the segments in self.  If self has length n, then if item
		is a scalar or a segment this operation is O(log n), if
		item is a segmentlist of m segments this operation is O(m
540
		log n).
541

kipp's avatar
kipp committed
542
		Note the difference between this operator and the standard
kipp's avatar
kipp committed
543 544 545 546 547 548
		Python "in" operator for sequence-like objects:  in the
		case of standard sequence-like objects the in operator
		checks for an exact match between the given item and one of
		the contents of the list; for segmentlists, the in operator
		checks if the given item is contained within any of the
		segments in the segmentlist.
549
		"""
550
		if isinstance(item, self.__class__):
Kipp Cannon's avatar
Kipp Cannon committed
551
			return all(seg in self for seg in item)
552
		i = _bisect_left(self, item)
553
		return ((i != 0) and (item in self[i-1])) or ((i != len(self)) and (item in self[i]))
554

555
	# supplementary accessors
556

557
	def __abs__(self):
558
		"""
559 560
		Return the sum of the durations of all segments in self.
		Does not require the segmentlist to be coalesced.
561
		"""
562
		return sum(abs(seg) for seg in self)
563

564 565 566
	def extent(self):
		"""
		Return the segment whose end-points denote the maximum and
567 568
		minimum extent of the segmentlist.  Does not require the
		segmentlist to be coalesced.
569
		"""
570
		if not len(self):
571
			raise ValueError("empty list")
572
		min, max = self[0]
573 574 575 576 577
		for lo, hi in self:
			if min > lo:
				min = lo
			if max < hi:
				max = hi
578
		return segment(min, max)
579

580 581
	def find(self, item):
		"""
582
		Return the smallest i such that i is the index of an
583 584 585
		element that wholly contains item.  Raises ValueError if no
		such element exists.  Does not require the segmentlist to
		be coalesced.
586
		"""
587 588
		for i, seg in enumerate(self):
			if item in seg:
589
				return i
590
		raise ValueError(item)
591

592 593 594 595 596
	# arithmetic operations that are sensible with segment lists

	def __iand__(self, other):
		"""
		Replace the segmentlist with the intersection of itself and
597 598
		another.  If the two lists have lengths n and m
		respectively, this operation is O(n + m).
599
		"""
600
		return self.__isub__(~other)
601 602 603

	def __and__(self, other):
		"""
604 605 606
		Return the intersection of the segmentlist and another.  If
		the two lists have lengths n and m respectively, this
		operation is O(n + m).
607
		"""
608
		if len(self) >= len(other):
609 610
			return self.__class__(self).__iand__(other)
		return self.__class__(other).__iand__(self)
611 612 613

	def __ior__(self, other):
		"""
614
		Replace the segmentlist with the union of itself and
615 616 617 618 619 620 621
		another.  If the two lists have numbers of elements n and m
		respectively, then for m << n the algorithm is O(m log n),
		otherwise it is O((n + m) log (n + m)).
		"""
		if len(other) > len(self) / 2:
			self.extend(other)
			return self.coalesce()
Kipp Cannon's avatar
Kipp Cannon committed
622 623
		if other is self:
			return self
624
		i = 0
625
		for seg in other:
626
			i = j = _bisect_right(self, seg, i)
627 628
			lo, hi = seg
			if i and self[i - 1][1] >= lo:
629
				i -= 1
630
				lo = self[i][0]
631
			n = len(self)
632
			while j < n and self[j][0] <= hi:
633 634
				j += 1
			if j > i:
635 636
				self[i] = segment(lo, max(hi, self[j - 1][1]))
				del self[i + 1 : j]
637 638 639
			else:
				self.insert(i, seg)
			i += 1
640 641 642 643
		return self

	def __or__(self, other):
		"""
644
		Return the union of the segment list and another.  The
645 646 647
		algorithm has the same scaling as in the
		segmentlist.__ior__() method, except that the lists are
		reordered to attempt to use the O(m log n) case.
648
		"""
649
		if len(self) >= len(other):
650 651
			return self.__class__(self).__ior__(other)
		return self.__class__(other).__ior__(self)
652 653 654 655

	def __xor__(self, other):
		"""
		Return the segmentlist that is the list of all intervals
656
		contained in exactly one of this and another list.  This
657
		operation is O(n log n).
658
		"""
659 660 661 662
		l = self - other
		l.extend(other - self)
		l.sort()
		return l
663

664
	# addition is union
665 666 667 668 669
	__iadd__ = __ior__
	__add__ = __or__

	def __isub__(self, other):
		"""
670
		Replace the segmentlist with the difference between itself
kipp's avatar
kipp committed
671 672
		and another.  For lists of length m and n respectively,
		this operation is O(n + m).
673
		"""
674 675
		if not other:
			return self
Kipp Cannon's avatar
Kipp Cannon committed
676 677 678
		if other is self:
			del self[:]
			return self
679
		i = j = 0
680
		other_lo, other_hi = other[j]
681
		while i < len(self):
682 683
			self_lo, self_hi = self[i]
			while other_hi <= self_lo:
684
				j += 1
685 686
				if j >= len(other):
					return self
687 688
				other_lo, other_hi = other[j]
			if self_hi <= other_lo:
689
				i += 1
690 691
			elif other_lo <= self_lo:
				if other_hi >= self_hi:
692 693
					del self[i]
				else:
694
					self[i] = segment(other_hi, self_hi)
695
			else:
696
				self[i] = segment(self_lo, other_lo)
697
				i += 1
698 699
				if other_hi < self_hi:
					self.insert(i, segment(other_hi, self_hi))
700 701 702 703 704
		return self

	def __sub__(self, other):
		"""
		Return the difference between the segmentlist and another.
705
		This operation is O(n).
706
		"""
707
		return self.__class__(self).__isub__(other)
708 709 710

	def __invert__(self):
		"""
711 712
		Return the segmentlist that is the inversion of the given
		list.  This operation is O(n).
713
		"""
kipp's avatar
kipp committed
714
		if not len(self):
715 716
			return self.__class__([segment(NegInfinity, PosInfinity)])
		l = self.__class__()
717 718 719
		if self[0][0] > NegInfinity:
			l.append(segment(NegInfinity, self[0][0]))
		last = self[0][1]
720
		for i in range(1, len(self)):
kipp's avatar
kipp committed
721
			l.append(segment(last, self[i][0]))
kipp's avatar
kipp committed
722
			last = self[i][1]
723 724 725
		if last < PosInfinity:
			l.append(segment(last, PosInfinity))
		return l
726

727 728
	# other operations

729 730 731 732 733 734
	def intersects_segment(self, other):
		"""
		Returns True if the intersection of self and the segment
		other is not the null set, otherwise returns False.  The
		algorithm is O(log n).  Requires the list to be coalesced.
		"""
735
		i = _bisect_left(self, other)
736 737
		return ((i != 0) and (other[0] < self[i-1][1])) or ((i != len(self)) and (other[1] > self[i][0]))

kipp's avatar
kipp committed
738 739
	def intersects(self, other):
		"""
740 741 742
		Returns True if the intersection of self and the
		segmentlist other is not the null set, otherwise returns
		False.  The algorithm is O(n), but faster than explicit
743 744
		calculation of the intersection, i.e. by testing bool(self
		& other).  Requires both lists to be coalesced.
kipp's avatar
kipp committed
745
		"""
kipp's avatar
kipp committed
746
		# if either has zero length, the answer is False
747 748
		if not (self and other):
			return False
kipp's avatar
kipp committed
749
		# walk through both lists in order, searching for a match
750
		i = j = 0
751 752 753 754
		seg = self[0]
		otherseg = other[0]
		while True:
			if seg[1] <= otherseg[0]:
755
				i += 1
756 757 758 759
				if i >= len(self):
					return False
				seg = self[i]
			elif otherseg[1] <= seg[0]:
760
				j += 1
761 762 763 764
				if j >= len(other):
					return False
				otherseg = other[j]
			else:
765
				return True
kipp's avatar
kipp committed
766

767 768
	def coalesce(self):
		"""
Kipp Cannon's avatar
Kipp Cannon committed
769 770 771
		Sort the elements of the list into ascending order, and merge
		continuous segments into single segments.  Segmentlist is
		modified in place.  This operation is O(n log n).
772 773
		"""
		self.sort()
774 775 776
		i = j = 0
		n = len(self)
		while j < n:
777
			lo, hi = self[j]
778
			j += 1
779 780
			while j < n and hi >= self[j][0]:
				hi = max(hi, self[j][1])
781
				j += 1
782 783 784
			if lo != hi:
				self[i] = segment(lo, hi)
				i += 1
785
		del self[i : ]
786 787 788 789
		return self

	def protract(self, x):
		"""
Kipp Cannon's avatar
Kipp Cannon committed
790 791
		Execute the .protract() method on each segment in the list
		and coalesce the result.  Segmentlist is modified in place.
792
		"""
793
		self[:] = (seg.protract(x) for seg in self)
794
		return self.coalesce()
795 796 797

	def contract(self, x):
		"""
Kipp Cannon's avatar
Kipp Cannon committed
798 799
		Execute the .contract() method on each segment in the list
		and coalesce the result.  Segmentlist is modified in place.
800
		"""
801
		self[:] = (seg.contract(x) for seg in self)
802
		return self.coalesce()
803 804 805

	def shift(self, x):
		"""
Kipp Cannon's avatar
Kipp Cannon committed
806 807 808 809
		Execute the .shift() method on each segment in the list.
		The algorithm is O(n) and does not require the list to be
		coalesced nor does it coalesce the list.  Segmentlist is
		modified in place.
810
		"""
811
		self[:] = (seg.shift(x) for seg in self)
812
		return self
kipp's avatar
kipp committed
813

814

kipp's avatar
kipp committed
815 816 817 818 819 820 821 822
#
# =============================================================================
#
#                               segmentlistdict
#
# =============================================================================
#

823 824 825 826 827 828 829 830 831 832 833

class _offsets(dict):
	"""
	Implements the segmentlist offset book-keeping in the
	segmentlistdict class.  Not intended for use outside of the
	segmentlistdict class.
	"""
	def __new__(cls, parent):
		return dict.__new__(cls)

	def __init__(self, parent):
834
		dict.__init__(self)
835
		self.__parent = parent
836 837 838

	def __reduce__(self):
		return _offsets, (self.__parent,), None, None, iter(self.items())
839 840 841 842 843 844 845

	def __setitem__(self, key, value):
		"""
		Set an offset.  If the new offset is identical to the
		current offset this is a no-op, otherwise the corresponding
		segmentlist object is shifted.
		"""
846 847 848 849 850
		try:
			delta = value - self[key]
		except KeyError:
			dict.__setitem__(self, key, value)
			return
851 852 853 854 855 856 857 858 859 860 861 862
		if delta:
			self.__parent[key].shift(delta)
			dict.__setitem__(self, key, self[key] + delta)

	def update(self, d):
		"""
		From a dictionary of offsets, apply each offset to the
		corresponding segmentlist.  NOTE:  it is acceptable for the
		offset dictionary to contain entries for which there is no
		matching segmentlist; no error will be raised, but the
		offset will be ignored.  This simplifies the case of
		updating several segmentlistdict objects from a common
kipp's avatar
kipp committed
863
		offset dictionary, when one or more of the segmentlistdicts
864 865
		contains only a subset of the keys.
		"""
866
		for key, value in six.iteritems(d):
867
			if key in self:
868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887
				self[key] = value

	def clear(self):
		"""
		Remove the offsets from all segmentlists.
		"""
		for key in self:
			self[key] = 0.0

	# stubs to prevent bugs
	def __delitem__(*args):
		raise NotImplementedError
	def fromkeys(*args):
		raise NotImplementedError
	def pop(*args):
		raise NotImplementedError
	def popitem(*args):
		raise NotImplementedError


kipp's avatar
kipp committed
888 889
class segmentlistdict(dict):
	"""
kipp's avatar
kipp committed
890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905
	A dictionary associating a unique label and numeric offset with
	each of a set of segmentlist objects.

	This class implements a standard mapping interface, with additional
	features added to assist with the manipulation of a collection of
	segmentlist objects.  In particular, methods for taking unions and
	intersections of the lists in the dictionary are available, as well
	as the ability to record and apply numeric offsets to the
	boundaries of the segments in each list.

	The numeric offsets are stored in the "offsets" attribute, which
	itself is a dictionary, associating a number with each key in the
	main dictionary.  Assigning to one of the entries of the offsets
	attribute has the effect of shifting the corresponding segmentlist
	from its original position (not its current position) by the given
	amount.
kipp's avatar
kipp committed
906 907 908 909 910

	Example:

	>>> x = segmentlistdict()
	>>> x["H1"] = segmentlist([segment(0, 10)])
911
	>>> print(x)
kipp's avatar
kipp committed
912 913
	{'H1': [segment(0, 10)]}
	>>> x.offsets["H1"] = 6
914
	>>> print(x)
kipp's avatar
kipp committed
915 916
	{'H1': [segment(6.0, 16.0)]}
	>>> x.offsets.clear()
917
	>>> print(x)
kipp's avatar
kipp committed
918 919 920 921 922 923
	{'H1': [segment(0.0, 10.0)]}
	>>> x["H2"] = segmentlist([segment(5, 15)])
	>>> x.intersection(["H1", "H2"])
	[segment(5, 10.0)]
	>>> x.offsets["H1"] = 6
	>>> x.intersection(["H1", "H2"])
924
	[segment(6.0, 15)]
kipp's avatar
kipp committed
925 926
	>>> c = x.extract_common(["H1", "H2"])
	>>> c.offsets.clear()
927
	>>> assert c == {'H2': [segment(6.0, 15)], 'H1': [segment(0.0, 9.0)]}
kipp's avatar
kipp committed
928
	"""
929 930 931 932 933
	def __new__(cls, *args):
		self = dict.__new__(cls, *args)
		self.offsets = _offsets(self)
		return self

kipp's avatar
kipp committed
934 935
	def __init__(self, *args):
		dict.__init__(self, *args)
936 937 938
		dict.clear(self.offsets)
		for key in self:
			dict.__setitem__(self.offsets, key, 0.0)
939
		if args and isinstance(args[0], self.__class__):
kipp's avatar
kipp committed
940 941
			dict.update(self.offsets, args[0].offsets)

942
	def copy(self, keys = None):
943
		"""
944
		Return a copy of the segmentlistdict object.  The return
945 946
		value is a new object with a new offsets attribute, with
		references to the original keys, and shallow copies of the
947 948 949
		segment lists.  Modifications made to the offset dictionary
		or segmentlists in the object returned by this method will
		not affect the original, but without using much memory
950 951 952 953 954
		until such modifications are made.  If the optional keys
		argument is not None, then should be an iterable of keys
		and only those segmentlists will be copied (KeyError is
		raised if any of those keys are not in the
		segmentlistdict).
955 956

		More details.  There are two "built-in" ways to create a
957 958
		copy of a segmentlist object.  The first is to initialize a
		new object from an existing one with
959

960
		>>> old = segmentlistdict()
961 962
		>>> new = segmentlistdict(old)

963 964 965 966 967
		This creates a copy of the dictionary, but not of its
		contents.  That is, this creates new with references to the
		segmentlists in old, therefore changes to the segmentlists
		in either new or old are reflected in both.  The second
		method is
968 969 970

		>>> new = old.copy()

971
		This creates a copy of the dictionary and of the
972 973 974 975 976
		segmentlists, but with references to the segment objects in
		the original segmentlists.  Since segments are immutable,
		this effectively creates a completely independent working
		copy but without the memory cost of a full duplication of
		the data.
977
		"""