1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 """
36 This module defines the segment and segmentlist objects, as well as the
37 infinity object used to define semi-infinite and infinite segments.
38
39 See also:
40
41 glue.segmentsUtils
42 """
43
44
45 from bisect import bisect_left as _bisect_left
46 from bisect import bisect_right as _bisect_right
47 from copy import copy as _shallowcopy
48
49
50 from glue import git_version
51 import six
52 from six.moves import range
53
54
55 __author__ = "Kipp Cannon <kipp.cannon@ligo.org>"
56 __version__ = "git id %s" % git_version.id
57 __date__ = git_version.date
58
59
60
61
62
63
64
65
66
67
68
70 """
71 The infinity object possess the algebraic properties necessary for
72 use as a bound on semi-infinite and infinite segments.
73
74 This class uses comparison-by-identity rather than
75 comparison-by-value. What this means, is there are only ever two
76 instances of this class, representing positive and negative
77 infinity respectively. All other "instances" of this class are
78 infact simply references to one of these two, and comparisons are
79 done by checking which one you've got. This improves speed and
80 reduces memory use, and is similar in implementation to Python's
81 boolean True and False objects.
82
83 The normal way to obtain references to positive or negative
84 infinity is to do infinity() or -infinity() respectively. It is
85 also possible to select the sign by passing a single numeric
86 argument to the constructor. The sign of the argument causes a
87 reference to either positive or negative infinity to be returned,
88 respectively. For example infinity(-1) is equivalent to
89 -infinity(). However, this feature is a little slower and not
90 recommended for normal use; it is provided only to simplify the
91 pickling and unpickling of instances of the class.
92
93 Example:
94
95 >>> x = infinity()
96 >>> x > 0
97 True
98 >>> x + 10 == x
99 True
100 >>> segment(-10, 10) - segment(-x, 0)
101 segment(0, 10)
102 >>> import math
103 >>> math.isinf(x)
104 True
105 """
106 __slots__ = []
107
109 if args:
110
111 (sign,) = args
112 if sign > 0:
113 return PosInfinity
114 if sign < 0:
115 return NegInfinity
116 raise ValueError(sign)
117 return PosInfinity
118
120 """
121 Returns a string.
122 """
123 if self is PosInfinity:
124 return "infinity"
125 return "-infinity"
126
127 __str__ = __repr__
128
129
130
139
140
141
143 """
144 Positive infinity compares as greater than everything
145 except itself, negative infinity compares as less than
146 everything except itself.
147 """
148 if self is other:
149 return 0
150 if self is PosInfinity:
151 return 1
152
153 return -1
154
156 """
157 Returns True.
158 """
159 return True
160
161
162
171
173 """
174 Returns self.
175 """
176 return self
177
179 """
180 Returns self.
181 """
182 return self
183
185 """
186 Returns self.
187 """
188 return self
189
191 """
192 Returns self.
193 """
194 return self
195
204
206 """
207 Returns +/-inf (allows math.isinf() to work).
208 """
209 if self is PosInfinity:
210 return float("+inf")
211
212 return float("-inf")
213
214
215 PosInfinity = object.__new__(infinity)
216 NegInfinity = object.__new__(infinity)
217
218
219
220
221
222
223
224
225
226
227
229 """
230 The segment class defines objects that represent a range of values.
231 A segment has a start and an end, and is taken to represent the
232 range of values in the semi-open interval [start, end). Some
233 limited arithmetic operations are possible with segments, but
234 because the set of (single) segments is not closed under the
235 sensible definitions of the standard arithmetic operations, the
236 behaviour of the arithmetic operators on segments may not be as you
237 would expect. For general arithmetic on segments, use segmentlist
238 objects. The methods for this class exist mostly for purpose of
239 simplifying the implementation of the segmentlist class.
240
241 The segment class is a subclass of the tuple built-in class
242 provided by Python. This means segments are immutable --- you
243 cannot modify a segment object after creating it, to change the
244 boundaries of a segment you must create a new segment object with
245 the desired boundaries. Like tuples, segments can be used as
246 dictionary keys, and like tuples the comparison used to find a
247 segment in the dictionary is done by value not by ID. And, like
248 tuples, a segment can be created from any sequence-like object by
249 passing it to the constructor (the sequence must have exactly two
250 elements in it).
251
252 Example:
253
254 >>> segment(0, 10) & segment(5, 15)
255 segment(5, 10)
256 >>> segment(0, 10) | segment(5, 15)
257 segment(0, 15)
258 >>> segment(0, 10) - segment(5, 15)
259 segment(0, 5)
260 >>> segment(0, 10) < segment(5, 15)
261 True
262 >>> segment(1, 2) in segment(0, 10)
263 True
264 >>> segment(1, 11) in segment(0, 10)
265 False
266 >>> segment(0, 1)
267 segment(0, 1)
268 >>> segment(1, 0)
269 segment(0, 1)
270 >>> bool(segment(0, 1))
271 True
272 >>> bool(segment(0, 0))
273 False
274 >>> segment("AAA Towing", "York University") & segment("Pool", "Zoo")
275 segment('Pool', 'York University')
276 >>> x = [0, 1] # a list
277 >>> segment(x)
278 segment(0, 1)
279 >>> y = segment(0, 1)
280 >>> y == x
281 True
282 >>> y is x
283 False
284 >>> x in y
285 True
286 >>> z = {x: ["/path/to/file1", "/path/to/file2"]}
287 >>> y in z
288 True
289 >>> z[y]
290 ['/path/to/file1', '/path/to/file2']
291 """
292
293
294
296 if len(args) == 1:
297 args = args[0]
298 if len(args) != 2:
299 raise TypeError("__new__() takes 2 arguments, or 1 argument when it is a sequence of length 2")
300 if args[0] <= args[1]:
301 return tuple.__new__(cls, args)
302 else:
303 return tuple.__new__(cls, (args[1], args[0]))
304
306 return "segment(%s, %s)" % (repr(self[0]), repr(self[1]))
307
309 return "[%s ... %s)" % (str(self[0]), str(self[1]))
310
311
312
314 """
315 Returns the length of the interval represented by the
316 segment. Requires the bounds to support the subtract
317 operation.
318 """
319 return self[1] - self[0]
320
321
322
324 """
325 Return True if the segment's boudaries are not equal, False
326 if they are equal.
327 """
328 return self[0] != self[1]
329
331 """
332 Returns >0 if self covers an interval above other's
333 interval, <0 if self covers an interval below other's, or 0
334 if the two intervals are not disjoint (intersect or touch).
335 A return value of 0 indicates the two segments would
336 coalesce.
337 """
338 if self[0] > other[1]:
339 return 1
340 if self[1] < other[0]:
341 return -1
342 return 0
343
345 if isinstance(other, tuple):
346 return tuple.__lt__(self, other)
347 return self[0] < other
348
350 if isinstance(other, tuple):
351 return tuple.__le__(self, other)
352 return self[0] <= other
353
355 if isinstance(other, tuple):
356 return tuple.__eq__(self, other)
357 return self[0] == other
358
360 if isinstance(other, tuple):
361 return tuple.__ne__(self, other)
362 return self[0] != other
363
365 if isinstance(other, tuple):
366 return tuple.__gt__(self, other)
367 return self[0] > other
368
370 if isinstance(other, tuple):
371 return tuple.__ge__(self, other)
372 return self[0] >= other
373
374
375
376
377
378
379
380
381
382
383 __hash__ = tuple.__hash__
384
385
386
388 """
389 Return the segment that is the intersection of the given
390 segments. Raises ValueError if the result cannot be
391 presented as a single segment.
392 """
393 if (self[1] <= other[0]) or (self[0] >= other[1]):
394
395 raise ValueError(other)
396 return tuple.__new__(self.__class__, (max(self[0], other[0]), min(self[1], other[1])))
397
399 """
400 Return the segment that is the union of the given segments.
401 Raises ValueError if the result cannot be represented as a
402 single segment.
403 """
404 if (self[1] < other[0]) or (self[0] > other[1]):
405
406 raise ValueError(other)
407 return tuple.__new__(self.__class__, (min(self[0], other[0]), max(self[1], other[1])))
408
409
410 __add__ = __or__
411
413 """
414 Return the segment that is that part of self which is not
415 contained in other. Raises ValueError if the result cannot
416 be represented as a single segment.
417 """
418 if (self[1] <= other[0]) or (self[0] >= other[1]):
419
420 return self
421 if (self in other) or ((self[0] < other[0]) and (self[1] > other[1])):
422
423 raise ValueError(other)
424 if self[0] < other[0]:
425 return tuple.__new__(self.__class__, (self[0], other[0]))
426 return tuple.__new__(self.__class__, (other[1], self[1]))
427
428
429
431 """
432 Return True if the intersection of self and other is not a
433 null segment.
434 """
435 return (self[1] > other[0]) and (self[0] < other[1])
436
438 """
439 Return True if other is wholly contained in self. If other
440 is an instance of the segment class or an instance of a
441 subclass of segment then it is treated as an interval whose
442 upper and lower bounds must not be outside of self,
443 otherwise other is compared to the bounds of self as a
444 scalar.
445 """
446 try:
447 a, b = other
448 except ValueError:
449 return self[0] <= other < self[1]
450 else:
451 return (self[0] <= a) and (self[1] >= b)
452
453
454
456 """
457 Return a new segment whose bounds are given by subtracting
458 x from the segment's lower bound and adding x to the
459 segment's upper bound.
460 """
461 return self.__class__(self[0] - x, self[1] + x)
462
464 """
465 Return a new segment whose bounds are given by adding x to
466 the segment's lower bound and subtracting x from the
467 segment's upper bound.
468 """
469 return self.__class__(self[0] + x, self[1] - x)
470
472 """
473 Return a new segment whose bounds are given by adding x to
474 the segment's upper and lower bounds.
475 """
476 return tuple.__new__(self.__class__, (self[0] + x, self[1] + x))
477
478
479
480
481
482
483
484
485
486
487
489 """
490 The segmentlist class defines a list of segments, and is an
491 extension of the built-in list class. This class provides
492 addtional methods that assist in the manipulation of lists of
493 segments. In particular, arithmetic operations such as union and
494 intersection are provided. Unlike the segment class, the
495 segmentlist class is closed under all supported arithmetic
496 operations.
497
498 All standard Python sequence-like operations are supported, like
499 slicing, iteration and so on, including arithmetic operations.
500 However, the arithmetic and other methods for this class generally
501 require the segmentlist to be in what is refered to as a
502 "coalesced" state --- consisting solely of disjoint segments listed
503 in ascending order. Using the standard Python sequence-like
504 operations, a segmentlist can be easily constructed that is not in
505 this state; for example by simply appending a segment to the end
506 of the list that overlaps some other segment already in the list.
507 The use of methods that require coalesced lists with lists that are
508 not coalesced has undefined results. The class provides the
509 .coalesce() method that can be called to put a segmentlist in the
510 coalesced state. All arithmetic methods return coalesced results,
511 so typically the .coalesce() method will be executed once after
512 importing a segmentlist from an untrusted source, then there is
513 never a need to call the .coalesce() method again as long as the
514 segmentlists are manipulated exclusively via the arithmetic
515 operators.
516
517 Example:
518
519 >>> x = segmentlist([segment(-10, 10)])
520 >>> x |= segmentlist([segment(20, 30)])
521 >>> x -= segmentlist([segment(-5, 5)])
522 >>> print(x)
523 [segment(-10, -5), segment(5, 10), segment(20, 30)]
524 >>> print(~x)
525 [segment(-infinity, -10), segment(-5, 5), segment(10, 20), segment(30, infinity)]
526 """
527
528
529
531 """
532 Returns True if the given object is wholly contained within
533 the segments in self. If self has length n, then if item
534 is a scalar or a segment this operation is O(log n), if
535 item is a segmentlist of m segments this operation is O(m
536 log n).
537
538 Note the difference between this operator and the standard
539 Python "in" operator for sequence-like objects: in the
540 case of standard sequence-like objects the in operator
541 checks for an exact match between the given item and one of
542 the contents of the list; for segmentlists, the in operator
543 checks if the given item is contained within any of the
544 segments in the segmentlist.
545 """
546 if isinstance(item, self.__class__):
547 return all(seg in self for seg in item)
548 i = _bisect_left(self, item)
549 return ((i != 0) and (item in self[i-1])) or ((i != len(self)) and (item in self[i]))
550
551
552
554 """
555 Return the sum of the durations of all segments in self.
556 Does not require the segmentlist to be coalesced.
557 """
558 return sum(abs(seg) for seg in self)
559
561 """
562 Return the segment whose end-points denote the maximum and
563 minimum extent of the segmentlist. Does not require the
564 segmentlist to be coalesced.
565 """
566 if not len(self):
567 raise ValueError("empty list")
568 min, max = self[0]
569 for lo, hi in self:
570 if min > lo:
571 min = lo
572 if max < hi:
573 max = hi
574 return segment(min, max)
575
576 - def find(self, item):
577 """
578 Return the smallest i such that i is the index of an
579 element that wholly contains item. Raises ValueError if no
580 such element exists. Does not require the segmentlist to
581 be coalesced.
582 """
583 for i, seg in enumerate(self):
584 if item in seg:
585 return i
586 raise ValueError(item)
587
588
589
591 """
592 Replace the segmentlist with the intersection of itself and
593 another. If the two lists have lengths n and m
594 respectively, this operation is O(n + m).
595 """
596 return self.__isub__(~other)
597
599 """
600 Return the intersection of the segmentlist and another. If
601 the two lists have lengths n and m respectively, this
602 operation is O(n + m).
603 """
604 if len(self) >= len(other):
605 return self.__class__(self).__iand__(other)
606 return self.__class__(other).__iand__(self)
607
609 """
610 Replace the segmentlist with the union of itself and
611 another. If the two lists have numbers of elements n and m
612 respectively, then for m << n the algorithm is O(m log n),
613 otherwise it is O((n + m) log (n + m)).
614 """
615 if len(other) > len(self) / 2:
616 self.extend(other)
617 return self.coalesce()
618 if other is self:
619 return self
620 i = 0
621 for seg in other:
622 i = j = _bisect_right(self, seg, i)
623 lo, hi = seg
624 if i and self[i - 1][1] >= lo:
625 i -= 1
626 lo = self[i][0]
627 n = len(self)
628 while j < n and self[j][0] <= hi:
629 j += 1
630 if j > i:
631 self[i] = segment(lo, max(hi, self[j - 1][1]))
632 del self[i + 1 : j]
633 else:
634 self.insert(i, seg)
635 i += 1
636 return self
637
639 """
640 Return the union of the segment list and another. The
641 algorithm has the same scaling as in the
642 segmentlist.__ior__() method, except that the lists are
643 reordered to attempt to use the O(m log n) case.
644 """
645 if len(self) >= len(other):
646 return self.__class__(self).__ior__(other)
647 return self.__class__(other).__ior__(self)
648
650 """
651 Return the segmentlist that is the list of all intervals
652 contained in exactly one of this and another list. This
653 operation is O(n log n).
654 """
655 l = self - other
656 l.extend(other - self)
657 l.sort()
658 return l
659
660
661 __iadd__ = __ior__
662 __add__ = __or__
663
665 """
666 Replace the segmentlist with the difference between itself
667 and another. For lists of length m and n respectively,
668 this operation is O(n + m).
669 """
670 if not other:
671 return self
672 if other is self:
673 del self[:]
674 return self
675 i = j = 0
676 other_lo, other_hi = other[j]
677 while i < len(self):
678 self_lo, self_hi = self[i]
679 while other_hi <= self_lo:
680 j += 1
681 if j >= len(other):
682 return self
683 other_lo, other_hi = other[j]
684 if self_hi <= other_lo:
685 i += 1
686 elif other_lo <= self_lo:
687 if other_hi >= self_hi:
688 del self[i]
689 else:
690 self[i] = segment(other_hi, self_hi)
691 else:
692 self[i] = segment(self_lo, other_lo)
693 i += 1
694 if other_hi < self_hi:
695 self.insert(i, segment(other_hi, self_hi))
696 return self
697
699 """
700 Return the difference between the segmentlist and another.
701 This operation is O(n).
702 """
703 return self.__class__(self).__isub__(other)
704
722
723
724
726 """
727 Returns True if the intersection of self and the segment
728 other is not the null set, otherwise returns False. The
729 algorithm is O(log n). Requires the list to be coalesced.
730 """
731 i = _bisect_left(self, other)
732 return ((i != 0) and (other[0] < self[i-1][1])) or ((i != len(self)) and (other[1] > self[i][0]))
733
735 """
736 Returns True if the intersection of self and the
737 segmentlist other is not the null set, otherwise returns
738 False. The algorithm is O(n), but faster than explicit
739 calculation of the intersection, i.e. by testing bool(self
740 & other). Requires both lists to be coalesced.
741 """
742
743 if not (self and other):
744 return False
745
746 i = j = 0
747 seg = self[0]
748 otherseg = other[0]
749 while True:
750 if seg[1] <= otherseg[0]:
751 i += 1
752 if i >= len(self):
753 return False
754 seg = self[i]
755 elif otherseg[1] <= seg[0]:
756 j += 1
757 if j >= len(other):
758 return False
759 otherseg = other[j]
760 else:
761 return True
762
764 """
765 Sort the elements of the list into ascending order, and merge
766 continuous segments into single segments. Segmentlist is
767 modified in place. This operation is O(n log n).
768 """
769 self.sort()
770 i = j = 0
771 n = len(self)
772 while j < n:
773 lo, hi = self[j]
774 j += 1
775 while j < n and hi >= self[j][0]:
776 hi = max(hi, self[j][1])
777 j += 1
778 if lo != hi:
779 self[i] = segment(lo, hi)
780 i += 1
781 del self[i : ]
782 return self
783
785 """
786 Execute the .protract() method on each segment in the list
787 and coalesce the result. Segmentlist is modified in place.
788 """
789 self[:] = (seg.protract(x) for seg in self)
790 return self.coalesce()
791
793 """
794 Execute the .contract() method on each segment in the list
795 and coalesce the result. Segmentlist is modified in place.
796 """
797 self[:] = (seg.contract(x) for seg in self)
798 return self.coalesce()
799
801 """
802 Execute the .shift() method on each segment in the list.
803 The algorithm is O(n) and does not require the list to be
804 coalesced nor does it coalesce the list. Segmentlist is
805 modified in place.
806 """
807 self[:] = (seg.shift(x) for seg in self)
808 return self
809
810
811
812
813
814
815
816
817
818
819
821 """
822 Implements the segmentlist offset book-keeping in the
823 segmentlistdict class. Not intended for use outside of the
824 segmentlistdict class.
825 """
828
830 dict.__init__(self)
831 self.__parent = parent
832
834 return _offsets, (self.__parent,), None, None, iter(self.items())
835
837 """
838 Set an offset. If the new offset is identical to the
839 current offset this is a no-op, otherwise the corresponding
840 segmentlist object is shifted.
841 """
842 try:
843 delta = value - self[key]
844 except KeyError:
845 dict.__setitem__(self, key, value)
846 return
847 if delta:
848 self.__parent[key].shift(delta)
849 dict.__setitem__(self, key, self[key] + delta)
850
852 """
853 From a dictionary of offsets, apply each offset to the
854 corresponding segmentlist. NOTE: it is acceptable for the
855 offset dictionary to contain entries for which there is no
856 matching segmentlist; no error will be raised, but the
857 offset will be ignored. This simplifies the case of
858 updating several segmentlistdict objects from a common
859 offset dictionary, when one or more of the segmentlistdicts
860 contains only a subset of the keys.
861 """
862 for key, value in six.iteritems(d):
863 if key in self:
864 self[key] = value
865
867 """
868 Remove the offsets from all segmentlists.
869 """
870 for key in self:
871 self[key] = 0.0
872
873
875 raise NotImplementedError
877 raise NotImplementedError
879 raise NotImplementedError
881 raise NotImplementedError
882
883
885 """
886 A dictionary associating a unique label and numeric offset with
887 each of a set of segmentlist objects.
888
889 This class implements a standard mapping interface, with additional
890 features added to assist with the manipulation of a collection of
891 segmentlist objects. In particular, methods for taking unions and
892 intersections of the lists in the dictionary are available, as well
893 as the ability to record and apply numeric offsets to the
894 boundaries of the segments in each list.
895
896 The numeric offsets are stored in the "offsets" attribute, which
897 itself is a dictionary, associating a number with each key in the
898 main dictionary. Assigning to one of the entries of the offsets
899 attribute has the effect of shifting the corresponding segmentlist
900 from its original position (not its current position) by the given
901 amount.
902
903 Example:
904
905 >>> x = segmentlistdict()
906 >>> x["H1"] = segmentlist([segment(0, 10)])
907 >>> print(x)
908 {'H1': [segment(0, 10)]}
909 >>> x.offsets["H1"] = 6
910 >>> print(x)
911 {'H1': [segment(6.0, 16.0)]}
912 >>> x.offsets.clear()
913 >>> print(x)
914 {'H1': [segment(0.0, 10.0)]}
915 >>> x["H2"] = segmentlist([segment(5, 15)])
916 >>> x.intersection(["H1", "H2"])
917 [segment(5, 10.0)]
918 >>> x.offsets["H1"] = 6
919 >>> x.intersection(["H1", "H2"])
920 [segment(6.0, 15)]
921 >>> c = x.extract_common(["H1", "H2"])
922 >>> c.offsets.clear()
923 >>> c
924 {'H2': [segment(6.0, 15)], 'H1': [segment(0.0, 9.0)]}
925 """
927 self = dict.__new__(cls, *args)
928 self.offsets = _offsets(self)
929 return self
930
932 dict.__init__(self, *args)
933 dict.clear(self.offsets)
934 for key in self:
935 dict.__setitem__(self.offsets, key, 0.0)
936 if args and isinstance(args[0], self.__class__):
937 dict.update(self.offsets, args[0].offsets)
938
939 - def copy(self, keys = None):
940 """
941 Return a copy of the segmentlistdict object. The return
942 value is a new object with a new offsets attribute, with
943 references to the original keys, and shallow copies of the
944 segment lists. Modifications made to the offset dictionary
945 or segmentlists in the object returned by this method will
946 not affect the original, but without using much memory
947 until such modifications are made. If the optional keys
948 argument is not None, then should be an iterable of keys
949 and only those segmentlists will be copied (KeyError is
950 raised if any of those keys are not in the
951 segmentlistdict).
952
953 More details. There are two "built-in" ways to create a
954 copy of a segmentlist object. The first is to initialize a
955 new object from an existing one with
956
957 >>> old = segmentlistdict()
958 >>> new = segmentlistdict(old)
959
960 This creates a copy of the dictionary, but not of its
961 contents. That is, this creates new with references to the
962 segmentlists in old, therefore changes to the segmentlists
963 in either new or old are reflected in both. The second
964 method is
965
966 >>> new = old.copy()
967
968 This creates a copy of the dictionary and of the
969 segmentlists, but with references to the segment objects in
970 the original segmentlists. Since segments are immutable,
971 this effectively creates a completely independent working
972 copy but without the memory cost of a full duplication of
973 the data.
974 """
975 if keys is None:
976 keys = self
977 new = self.__class__()
978 for key in keys:
979 new[key] = _shallowcopy(self[key])
980 dict.__setitem__(new.offsets, key, self.offsets[key])
981 return new
982
984 """
985 Set the segmentlist associated with a key. If key is not
986 already in the dictionary, the corresponding offset is
987 initialized to 0.0, otherwise it is left unchanged.
988 """
989 dict.__setitem__(self, key, value)
990 if key not in self.offsets:
991 dict.__setitem__(self.offsets, key, 0.0)
992
996
997
998
999 - def map(self, func):
1000 """
1001 Return a dictionary of the results of func applied to each
1002 of the segmentlist objects in self.
1003
1004 Example:
1005
1006 >>> x = segmentlistdict()
1007 >>> x["H1"] = segmentlist([segment(0, 10)])
1008 >>> x["H2"] = segmentlist([segment(5, 15)])
1009 >>> x.map(lambda l: 12 in l)
1010 {'H2': True, 'H1': False}
1011 """
1012 return dict((key, func(value)) for key, value in six.iteritems(self))
1013
1015 """
1016 Return a dictionary of the results of running .abs() on
1017 each of the segmentlists.
1018 """
1019 return self.map(abs)
1020
1022 """
1023 Return a dictionary of the results of running .extent() on
1024 each of the segmentlists.
1025 """
1026 return self.map(segmentlist.extent)
1027
1029 """
1030 Return the result of running .extent() on the union of all
1031 lists in the dictionary.
1032 """
1033 segs = tuple(seglist.extent() for seglist in self.values() if seglist)
1034 if not segs:
1035 raise ValueError("empty list")
1036 return segment(min(seg[0] for seg in segs), max(seg[1] for seg in segs))
1037
1038 - def find(self, item):
1039 """
1040 Return a dictionary of the results of running .find() on
1041 each of the segmentlists.
1042
1043 Example:
1044
1045 >>> x = segmentlistdict()
1046 >>> x["H1"] = segmentlist([segment(0, 10)])
1047 >>> x["H2"] = segmentlist([segment(5, 15)])
1048 >>> x.find(7)
1049 {'H2': 0, 'H1': 0}
1050
1051 NOTE: all segmentlists must contain the item or KeyError
1052 is raised.
1053 """
1054 return self.map(lambda x: x.find(item))
1055
1057 """
1058 Return a list of the keys for the segment lists that
1059 contain x.
1060
1061 Example:
1062
1063 >>> x = segmentlistdict()
1064 >>> x["H1"] = segmentlist([segment(0, 10)])
1065 >>> x["H2"] = segmentlist([segment(5, 15)])
1066 >>> x.keys_at(12)
1067 ['H2']
1068 """
1069 return [key for key, segs in self.items() if x in segs]
1070
1071
1072
1074 for key, value in six.iteritems(other):
1075 if key in self:
1076 self[key] &= value
1077 else:
1078 self[key] = segmentlist()
1079 return self
1080
1082 if sum(len(s) for s in self.values()) <= sum(len(s) for s in other.values()):
1083 return self.copy().__iand__(other)
1084 return other.copy().__iand__(self)
1085
1087 for key, value in six.iteritems(other):
1088 if key in self:
1089 self[key] |= value
1090 else:
1091 self[key] = _shallowcopy(value)
1092 return self
1093
1095 if sum(len(s) for s in self.values()) >= sum(len(s) for s in other.values()):
1096 return self.copy().__ior__(other)
1097 return other.copy().__ior__(self)
1098
1099 __iadd__ = __ior__
1100 __add__ = __or__
1101
1103 for key, value in six.iteritems(other):
1104 if key in self:
1105 self[key] -= value
1106 return self
1107
1110
1112 for key, value in six.iteritems(other):
1113 if key in self:
1114 self[key] ^= value
1115 else:
1116 self[key] = _shallowcopy(value)
1117 return self
1118
1120 if sum(len(s) for s in self.values()) <= sum(len(s) for s in other.values()):
1121 return self.copy().__ixor__(other)
1122 return other.copy().__ixor__(self)
1123
1129
1130
1131
1133 """
1134 Returns True if any segmentlist in self intersects the
1135 segment, otherwise returns False.
1136 """
1137 return any(value.intersects_segment(seg) for value in six.itervalues(self))
1138
1140 """
1141 Returns True if there exists a segmentlist in self that
1142 intersects the corresponding segmentlist in other; returns
1143 False otherwise.
1144
1145 See also:
1146
1147 .intersects_all(), .all_intersects(), .all_intersects_all()
1148 """
1149 return any(key in self and self[key].intersects(value) for key, value in six.iteritems(other))
1150
1152 """
1153 Returns True if each segmentlist in other intersects the
1154 corresponding segmentlist in self; returns False
1155 if this is not the case, or if other is empty.
1156
1157 See also:
1158
1159 .intersects(), .all_intersects(), .all_intersects_all()
1160 """
1161 return all(key in self and self[key].intersects(value) for key, value in six.iteritems(other)) and bool(other)
1162
1164 """
1165 Returns True if each segmentlist in self intersects the
1166 corresponding segmentlist in other; returns False
1167 if this is not the case or if self is empty.
1168
1169 See also:
1170
1171 .intersects, .intersects_all(), .all_intersects_all()
1172 """
1173 return all(key in other and other[key].intersects(value) for key, value in six.iteritems(self)) and bool(self)
1174
1176 """
1177 Returns True if self and other have the same keys, and each
1178 segmentlist intersects the corresponding segmentlist in the
1179 other; returns False if this is not the case or if either
1180 dictionary is empty.
1181
1182 See also:
1183
1184 .intersects(), .all_intersects(), .intersects_all()
1185 """
1186 return set(self) == set(other) and all(other[key].intersects(value) for key, value in six.iteritems(self)) and bool(self)
1187
1189 """
1190 Appends the segmentlists from other to the corresponding
1191 segmentlists in self, adding new segmentslists to self as
1192 needed.
1193 """
1194 for key, value in six.iteritems(other):
1195 if key not in self:
1196 self[key] = _shallowcopy(value)
1197 else:
1198 self[key].extend(value)
1199
1201 """
1202 Run .coalesce() on all segmentlists.
1203 """
1204 for value in six.itervalues(self):
1205 value.coalesce()
1206 return self
1207
1209 """
1210 Run .contract(x) on all segmentlists.
1211 """
1212 for value in six.itervalues(self):
1213 value.contract(x)
1214 return self
1215
1217 """
1218 Run .protract(x) on all segmentlists.
1219 """
1220 for value in six.itervalues(self):
1221 value.protract(x)
1222 return self
1223
1225 """
1226 Return a new segmentlistdict containing only those
1227 segmentlists associated with the keys in keys, with each
1228 set to their mutual intersection. The offsets are
1229 preserved.
1230 """
1231 keys = set(keys)
1232 new = self.__class__()
1233 intersection = self.intersection(keys)
1234 for key in keys:
1235 dict.__setitem__(new, key, _shallowcopy(intersection))
1236 dict.__setitem__(new.offsets, key, self.offsets[key])
1237 return new
1238
1239
1240
1242 """
1243 Return True if any segment in any list in self intersects
1244 any segment in any list in other. If the optional keys
1245 argument is not None, then it should be an iterable of keys
1246 and only segment lists for those keys will be considered in
1247 the test (instead of raising KeyError, keys not present in
1248 both segment list dictionaries will be ignored). If keys
1249 is None (the default) then all segment lists are
1250 considered.
1251
1252 This method is equivalent to the intersects() method, but
1253 without requiring the keys of the intersecting segment
1254 lists to match.
1255 """
1256 if keys is not None:
1257 keys = set(keys)
1258 self = tuple(self[key] for key in set(self) & keys)
1259 other = tuple(other[key] for key in set(other) & keys)
1260 else:
1261 self = tuple(self.values())
1262 other = tuple(other.values())
1263
1264 if len(self) < len(other):
1265 self, other = other, self
1266 return any(a.intersects(b) for a in self for b in other)
1267
1269 """
1270 Return the intersection of the segmentlists associated with
1271 the keys in keys.
1272 """
1273 keys = set(keys)
1274 if not keys:
1275 return segmentlist()
1276 seglist = _shallowcopy(self[keys.pop()])
1277 for key in keys:
1278 seglist &= self[key]
1279 return seglist
1280
1282 """
1283 Return the union of the segmentlists associated with the
1284 keys in keys.
1285 """
1286 keys = set(keys)
1287 if not keys:
1288 return segmentlist()
1289 seglist = _shallowcopy(self[keys.pop()])
1290 for key in keys:
1291 seglist |= self[key]
1292 return seglist
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304 try:
1305 from .__segments import *
1306 except ImportError:
1307 pass
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319 import six.moves.copyreg
1320
1321 six.moves.copyreg.pickle(segment, lambda x: (segment, tuple(x)))
1322 six.moves.copyreg.pickle(segmentlist, lambda x: (segmentlist, (), None, iter(x)))
1323