Class: IntervalSet

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/interval_set.rb,
lib/interval_set/version.rb

Overview

IntervalSet implements a set of sorted non-overlapping ranges. A range’s start is always interpreted as inclusive while the end is exclusive

Constant Summary collapse

VERSION = 
'0.2.3'

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ IntervalSet

Returns an empty instance of IntervalSet.



27
28
29
 
# File 'lib/interval_set.rb', line 27

def initialize
  @range_map = TreeMap.new
end

Class Method Details

.[](*ranges) ⇒ IntervalSet

Builds a new IntervalSet from the supplied ranges. Overlapping ranges will be merged.

IntervalSet[]               # -> []
IntervalSet[0...1]          # -> [0...1]
IntervalSet[0...1, 2...3]   # -> [0...1, 2...3]
IntervalSet[0...1, 1...2]   # -> [0...2]

array = [0...1, 2...3]
IntervalSet[*array]         # -> [0...1, 2...3]

Parameters:

  • ranges (Range[]) —

    a list of ranges to be added to the new IntervalSet

Returns:

  • (IntervalSet) —

    a new IntervalSet containing the supplied ranges.



20
21
22
23
24
 
# File 'lib/interval_set.rb', line 20

def self.[](*ranges)
  IntervalSet.new.tap do |interval_set|
    ranges.each {|range| interval_set << range}
  end
end

Instance Method Details

#add(other) ⇒ IntervalSet Also known as: <<, union!

Adds the other object’s elements to this IntervalSet. The result is stored in this IntervalSet.

IntervalSet.new.add(0...1)  # -> [0...1]
IntervalSet.new << (0...1)  # -> [0...1]

i = IntervalSet.new         # -> []
i << (0...1)                # -> [0...1]
i << (2...3)                # -> [0...1, 2...3]
i << (1...2)                # -> [0...3]
i << (-1...4)               # -> [-1...4]

Parameters:

Returns:



324
325
326
327
328
329
330
331
332
333
 
# File 'lib/interval_set.rb', line 324

def add(other)
  case other
    when Range
      add_range(other)
    when IntervalSet
      add_interval_set(other)
    else
      IntervalSet.unexpected_object(other)
  end
end

#bounds ⇒ Range

Returns the bounds of this IntervalSet.

IntervalSet[0...1, 2...3].bounds # -> 0...3
IntervalSet[].bounds             # -> nil

Returns:

  • (Range) —

    a range from lower to upper bound or nil if empty.



71
72
73
 
# File 'lib/interval_set.rb', line 71

def bounds
  empty? ? nil : min...max
end

#bounds_intersected_by?(range) ⇒ Boolean

Returns true if the given range has common elements with the bounding range of this IntervalSet.

IntervalSet[1...2].bounds_intersected_by?(2...3)         # -> false
IntervalSet[1...2, 5...6].bounds_intersected_by?(3...4)  # -> true

Parameters:

  • range (Range)

Returns:

  • (Boolean) 


247
248
249
250
251
 
# File 'lib/interval_set.rb', line 247

def bounds_intersected_by?(range)
  return false if IntervalSet.range_empty?(range)

  !empty? && range.first < max && range.last > min
end

#bounds_intersected_or_touched_by?(range) ⇒ Boolean

Returns true if the given range has common elements with the bounding range or the bounds of this IntervalSet.

IntervalSet[1...2].bounds_intersected_or_touched_by?(2...3)        # -> true
IntervalSet[1...2].bounds_intersected_or_touched_by?(3...4)        # -> false
IntervalSet[1...2, 5...6].bounds_intersected_or_touched_by?(3...4) # -> true

Parameters:

  • range (Range)

Returns:

  • (Boolean) 


261
262
263
264
265
 
# File 'lib/interval_set.rb', line 261

def bounds_intersected_or_touched_by?(range)
  return false if IntervalSet.range_empty?(range)

  !empty? && range.first <= max && range.last >= min
end

#buffer(left, right) ⇒ IntervalSet

Buffers this IntervalSet by adding a left and right margin to each range. The result is stored in a new IntervalSet.

IntervalSet[1...2].buffer(1, 2)       # -> [0...4]

# negative values will shrink the ranges
IntervalSet[0...4].buffer(-1, -2)     # -> [1...2]
IntervalSet[1...2].buffer(-0.5, -0.5) # -> []

Parameters:

  • left (Object) —

    margin added to the left side of each range.

  • right (Object) —

    margin added to the right side of each range.

Returns:

  • (IntervalSet) —

    a new IntervalSet containing the buffered ranges.



607
608
609
 
# File 'lib/interval_set.rb', line 607

def buffer(left, right)
  clone.buffer!(left, right)
end

#buffer!(left, right) ⇒ IntervalSet

Buffers this IntervalSet by adding a left and right margin to each range. The result is stored in this IntervalSet.

IntervalSet[1...2].buffer!(1, 2) # -> [0...4]

# negative values will shrink the ranges
IntervalSet[0...4].buffer!(-1, -2) # -> [1...2]
IntervalSet[1...2].buffer!(-0.5, -0.5) # -> []

Parameters:

  • left (Object) —

    margin added to the left side of each range.

  • right (Object) —

    margin added to the right side of each range.

Returns:



582
583
584
585
586
587
588
589
590
591
592
593
 
# File 'lib/interval_set.rb', line 582

def buffer!(left, right)
  ranges = map do |range|
    range.first - left...range.last + right
  end.select do |range|
    range.first < range.last
  end

  clear
  ranges.each {|r| add_range(r)}

  self
end

#clear ⇒ IntervalSet

Removes all elements from this IntervalSet.

Returns:



613
614
615
616
617
618
619
 
# File 'lib/interval_set.rb', line 613

def clear
  @range_map.clear
  @min = nil
  @max = nil

  self
end

#clone ⇒ IntervalSet

Returns a new IntervalSet instance containing all ranges of this IntervalSet.

Returns:



631
632
633
 
# File 'lib/interval_set.rb', line 631

def clone
  IntervalSet.new.copy(self)
end

#convolve(other) ⇒ IntervalSet Also known as: *

Convolves the other object’s elements with this IntervalSet. The result is stored in a new IntervalSet.

The result will contain all elements which can be obtained by adding any pair of elements from both sets. A ∗ B = { a + b | a ∈ A ∧ b ∈ B }

# Convolve with a range (effectively buffers the set)
IntervalSet[0...4] * (-1...2) # -> [-1...6]

# Convolving with empty or reversed ranges result in an empty set.
IntervalSet[0...4] * (0...0)  # -> []
IntervalSet[0...4] * (1...0)  # -> []

# Convolve with a interval set
IntervalSet[0...1, 10...12] * IntervalSet[-2...1, 1...2]  # -> [-2...3, 8...14]

Parameters:

Returns:

  • (IntervalSet) —

    a new IntervalSet containing the convolution.



531
532
533
 
# File 'lib/interval_set.rb', line 531

def convolve(other)
  clone.convolve!(other)
end

#convolve!(other) ⇒ IntervalSet

Convolves the other object’s elements with this IntervalSet. The result is stored in this IntervalSet.

The result will contain all elements which can be obtained by adding any pair of elements from both sets. A ∗ B = { a + b | a ∈ A ∧ b ∈ B }

# Convolve with a range (effectively buffers the set)
IntervalSet[0...4].convolve!(-1...2) # -> [-1...6]

# Convolving with empty or reversed ranges result in an empty set.
IntervalSet[0...4].convolve!(0...0)  # -> []
IntervalSet[0...4].convolve!(1...0)  # -> []

# Convolve with a interval set
IntervalSet[0...1, 10...12].convolve!(IntervalSet[-2...1, 1...2]) # -> [-2...3, 8...14]

Parameters:

Returns:



502
503
504
505
506
507
508
509
510
511
 
# File 'lib/interval_set.rb', line 502

def convolve!(other)
  case other
    when Range
      convolve_range!(other)
    when IntervalSet
      convolve_interval_set!(other)
    else
      IntervalSet.unexpected_object(other)
  end
end

#copy(interval_set) ⇒ IntervalSet

Replaces the content of this IntervalSet by the content of the given IntervalSet.

Parameters:

  • interval_set (IntervalSet) —

    the other IntervalSet to be copied

Returns:



638
639
640
641
642
643
644
645
 
# File 'lib/interval_set.rb', line 638

def copy(interval_set)
  clear
  interval_set.each {|range| put(range)}
  @min = interval_set.min
  @max = interval_set.max

  self
end

#count ⇒ Fixnum

Counts the number of ranges contained by this IntervalSet.

i = IntervalSet[]           # -> []
i.count                     # -> 0
i << (0...1)                # -> [0...1]
i.count                     # -> 1
i << (2...3)                # -> [0...1, 2...3]
i.count                     # -> 2
i << (1...2)                # -> [0...3]
i.count                     # -> 1

Returns:

  • (Fixnum) —

    the number of ranges.



306
307
308
 
# File 'lib/interval_set.rb', line 306

def count
  @range_map.count
end

#difference(other) ⇒ IntervalSet Also known as: -

Subtracts the other object’s elements from this IntervalSet. The result is stored in a new IntervalSet.

IntervalSet[0...2, 3...5] - IntervalSet[1...4, 5...6] # -> [0...1, 4...5]

Note that using remove or difference! is more efficient than -=.

Parameters:

Returns:

  • (IntervalSet) —

    a new IntervalSet containing the difference.



436
437
438
439
440
441
442
443
444
445
 
# File 'lib/interval_set.rb', line 436

def difference(other)
  case other
    when Range
      difference_range(other)
    when IntervalSet
      difference_interval_set(other)
    else
      IntervalSet.unexpected_object(other)
  end
end

#each {|range.| ... } ⇒ void

This method returns an undefined value.

Iterates over all ranges of this set in ascending order.

Yields:

  • all ranges.

Yield Parameters:

  • range. (Range) 


625
626
627
 
# File 'lib/interval_set.rb', line 625

def each
  @range_map.each_node {|node| yield node.value}
end

#empty? ⇒ Boolean

Returns true if this IntervalSet contains no ranges.

Returns:

  • (Boolean) 


41
42
43
 
# File 'lib/interval_set.rb', line 41

def empty?
  @range_map.empty?
end

#eql?(other) ⇒ Boolean Also known as: ==

Returns true if two IntervalSets are equal.

IntervalSet[0...1] == IntervalSet[0...1]  # -> true
IntervalSet[0...1] == IntervalSet[1...2]  # -> false

Parameters:

  • other (Object) —

    the other object.

Returns:

  • (Boolean) 


81
82
83
84
85
86
87
88
 
# File 'lib/interval_set.rb', line 81

def eql?(other)
  return false if other.nil? || !other.is_a?(IntervalSet) || count != other.count || bounds != other.bounds

  lhs_iter = enum_for
  rhs_iter = other.enum_for

  count.times.all? {lhs_iter.next == rhs_iter.next}
end

#eql_set?(other) ⇒ Boolean

Returns true if the other object represents a equal set of ranges as this IntervalSet.

IntervalSet[1...2].eql_set?(1...2)           # -> true
IntervalSet[1...2].eql_set?(IntervalSet[1...2]) # -> true

Parameters:

Returns:

  • (Boolean) 


99
100
101
102
103
104
105
106
107
108
 
# File 'lib/interval_set.rb', line 99

def eql_set?(other)
  case other
    when Range
      eql_range?(other)
    when IntervalSet
      eql?(other)
    else
      IntervalSet.unexpected_object(other)
  end
end

#include?(element) ⇒ Boolean Also known as: ===

Returns true if this IntervalSet contains the given element.

i = IntervalSet[0...1]      # -> [0...1]

i.include?(0)               # -> true
i.include?(0.5)             # -> true
i.include?(1)               # -> false ; a range's end is exclusive

Note that the given element must be comparable to elements already in this set. Otherwise, the behavior is undefined.

Parameters:

  • element (Object)

Returns:

  • (Boolean) 


122
123
124
125
126
127
128
 
# File 'lib/interval_set.rb', line 122

def include?(element)
  return false if element.nil?

  floor_entry = @range_map.floor_entry(element)

  !floor_entry.nil? && floor_entry.value.last > element
end

#include_or_limit?(element) ⇒ Boolean

Returns true if the closure of this IntervalSet contains the given element.

The closure of a set S is defined as the set containing all elements of S but also its limit points.

It will always return true if #include? returns true but in addition it will also return true if the exclusive end of a range is included.

i = IntervalSet[0...1]      # -> [0...1]

i.include_or_limit?(0)      # -> true
i.include_or_limit?(0.5)    # -> true
i.include_or_limit?(1)      # -> true

Note that the given element must be comparable to elements already in this set. Otherwise, the behavior is undefined.

Parameters:

  • element (Object)

Returns:

  • (Boolean) 


150
151
152
153
154
155
156
 
# File 'lib/interval_set.rb', line 150

def include_or_limit?(element)
  return false if element.nil?

  floor_entry = @range_map.floor_entry(element)

  !floor_entry.nil? && floor_entry.value.last >= element
end

#intersect(other) ⇒ IntervalSet Also known as: intersection!

Intersects the other object’s elements with this IntervalSet. The result is stored in this IntervalSet.

i = IntervalSet[0...2, 3...5].intersect(1...5) # -> [1...2, 3...5]
i                                              # -> [1...2, 3...5]

Parameters:

Returns:



369
370
371
372
373
374
375
376
377
378
 
# File 'lib/interval_set.rb', line 369

def intersect(other)
  case other
    when Range
      intersect_range(other)
    when IntervalSet
      intersect_interval_set(other)
    else
      IntervalSet.unexpected_object(other)
  end
end

#intersect?(other) ⇒ Boolean

Returns true if the given object has any common elements with this IntervalSet.

i = IntervalSet[0...1]      # -> [0...1]

# Ranges only need a single common element with the interval set
i.intersect?(0...1)         # -> true
i.intersect?(0...2)         # -> true
i.intersect?(1...2)         # -> false ; the start of a range is inclusive but the end exclusive

# The same applies for interval sets
i.intersect?(IntervalSet[0...1])         # -> true
i.intersect?(IntervalSet[0...1, 2...3])  # -> true
i.intersect?(IntervalSet[2...3])         # -> false

Parameters:

Returns:

  • (Boolean) 


283
284
285
286
287
288
289
290
291
292
 
# File 'lib/interval_set.rb', line 283

def intersect?(other)
  case other
    when Range
      intersect_range?(other)
    when IntervalSet
      intersect_interval_set?(other)
    else
      IntervalSet.unexpected_object(other)
  end
end

#intersection(other) ⇒ IntervalSet Also known as: &

Intersects the other object’s elements with this IntervalSet. The result is stored in a new IntervalSet.

IntervalSet[0...2, 3...5] & IntervalSet[1...4, 5...6] # -> [1...2, 3...4]

Parameters:

Returns:

  • (IntervalSet) —

    a new IntervalSet containing the intersection.



389
390
391
392
393
394
395
396
397
398
 
# File 'lib/interval_set.rb', line 389

def intersection(other)
  case other
    when Range
      intersection_range(other)
    when IntervalSet
      intersection_interval_set(other)
    else
      IntervalSet.unexpected_object(other)
  end
end

#marshal_dump ⇒ Object 



31
32
33
 
# File 'lib/interval_set.rb', line 31

def marshal_dump
  to_a
end

#marshal_load(ranges) ⇒ Object 



35
36
37
38
 
# File 'lib/interval_set.rb', line 35

def marshal_load(ranges)
  initialize
  ranges.each {|range| add(range)}
end

#max ⇒ Object

Returns the upper bound of this IntervalSet.

IntervalSet[0...1, 2...3].max  # -> 3
IntervalSet[].max              # -> nil

Returns:

  • the upper bound or nil if empty.



61
62
63
 
# File 'lib/interval_set.rb', line 61

def max
  @max
end

#min ⇒ Object

Returns the lower bound of this IntervalSet.

IntervalSet[0...1, 2...3].min  # -> 0
IntervalSet[].min              # -> nil

Returns:

  • the lower bound or nil if empty.



51
52
53
 
# File 'lib/interval_set.rb', line 51

def min
  @min
end

#proper_subset?(other) ⇒ Boolean Also known as: <

Return true if this IntervalSet is a proper subset of the other.

IntervalSet[0...1] < IntervalSet[0...2] # -> true
IntervalSet[1...3] < IntervalSet[0...2] # -> false
IntervalSet[1...3] < IntervalSet[0...2] # -> false

# Compare to ranges
IntervalSet[1...2].subset?(0...3)    # -> false

Parameters:

Returns:

  • (Boolean) 


234
235
236
 
# File 'lib/interval_set.rb', line 234

def proper_subset?(other)
  !eql_set?(other) && subset?(other)
end

#proper_superset?(other) ⇒ Boolean Also known as: >

Returns true if this IntervalSet is a proper superset of the other.

IntervalSet[0...2] > IntervalSet[0...1] # -> true
IntervalSet[0...2] > IntervalSet[0...2] # -> false
IntervalSet[0...2] > IntervalSet[1...3] # -> false

# Compare to ranges
IntervalSet[0...3].superset?(1...2)  # -> true

Parameters:

Returns:

  • (Boolean) 


218
219
220
 
# File 'lib/interval_set.rb', line 218

def proper_superset?(other)
  !eql_set?(other) && superset?(other)
end

#remove(other) ⇒ IntervalSet Also known as: >>, difference!

Removes the other object’s elements from this IntervalSet. The result is stored in this IntervalSet.

i = IntervalSet[0...10]     # -> [0...10]
i.remove(0...2)             # -> [8...10]
i >> (2...8)                # -> [0...2, 8...10]

Parameters:

Returns:



347
348
349
350
351
352
353
354
355
356
 
# File 'lib/interval_set.rb', line 347

def remove(other)
  case other
    when Range
      remove_range(other)
    when IntervalSet
      remove_interval_set(other)
    else
      IntervalSet.unexpected_object(other)
  end
end

#shift(amount) ⇒ IntervalSet

Shifts this IntervalSet by the given amount. The result is stored in a new IntervalSet.

IntervalSet[0...1].shift!(1)  # -> [1...2]

Note that shift!(0) will not be optimized since IntervalSet does not assume numbers as element type.

Parameters:

  • amount (Object)

Returns:

  • (IntervalSet) —

    a new IntervalSet shifted by amount.



566
567
568
 
# File 'lib/interval_set.rb', line 566

def shift(amount)
  clone.shift!(amount)
end

#shift!(amount) ⇒ IntervalSet

Shifts this IntervalSet by the given amount. The result is stored in this IntervalSet.

IntervalSet[0...1].shift(1)   # -> [1...2]

Note that shift(0) will not be optimized since IntervalSet does not assume numbers as element type.

Parameters:

  • amount (Object)

Returns:



547
548
549
550
551
552
553
554
 
# File 'lib/interval_set.rb', line 547

def shift!(amount)
  ranges = map {|range| range.first + amount...range.last + amount}
  clear
  ranges.each {|range| put(range)}
  update_bounds

  self
end

#subset?(other) ⇒ Boolean Also known as: <=

Returns true if all elements of this IntervalSet are included by the other object.

IntervalSet[0...1] <= IntervalSet[0...1]        # -> true
IntervalSet[0...1] <= IntervalSet[0...1, 2...3] # -> true
IntervalSet[0...1, 2...3] <= IntervalSet[0...1] # -> false
IntervalSet[0...1, 2...3] <= IntervalSet[0...3] # -> true

# You can also supply ranges
IntervalSet[0...1, 2...3].subset?(0...3)    # -> true

Parameters:

Returns:

  • (Boolean) 


195
196
197
198
199
200
201
202
203
204
 
# File 'lib/interval_set.rb', line 195

def subset?(other)
  case other
    when Range
      subset_range?(other)
    when IntervalSet
      other.superset_interval_set?(self)
    else
      IntervalSet.unexpected_object(other)
  end
end

#superset?(other) ⇒ Boolean Also known as: >=

Returns true if this IntervalSet includes all elements of the other object.

IntervalSet[0...1] >= IntervalSet[0...1]        # -> true
IntervalSet[0...2] >= IntervalSet[0...1]        # -> true
IntervalSet[0...1] >= IntervalSet[0...1, 2...3] # -> false
IntervalSet[0...3] >= IntervalSet[0...1, 2...3] # -> true

# You can also supply ranges
IntervalSet[0...2].superset?(0...1)  # -> true

Parameters:

Returns:

  • (Boolean) 


170
171
172
173
174
175
176
177
178
179
 
# File 'lib/interval_set.rb', line 170

def superset?(other)
  case other
    when Range
      superset_range?(other)
    when IntervalSet
      superset_interval_set?(other)
    else
      IntervalSet.unexpected_object(other)
  end
end

#to_s ⇒ String Also known as: inspect

Returns a String representation of this IntervalSet.

IntervalSet[].to_s             # -> "[]"
IntervalSet[0...1].to_s        # -> "[0...1]"
IntervalSet[0...1, 2...3].to_s # -> "[0...1, 2...3]"

Returns:

  • (String) —

    the String representation.



654
655
656
657
658
659
660
661
662
663
664
665
666
667
 
# File 'lib/interval_set.rb', line 654

def to_s
  string_io = StringIO.new

  last_index = count - 1

  string_io << '['
  each_with_index do |range, i|
    string_io << range
    string_io << ', ' if i < last_index
  end
  string_io << ']'

  string_io.string
end

#union(other) ⇒ IntervalSet Also known as: |, +

Joins the other object’s elements with this IntervalSet. The result is stored in a new IntervalSet.

IntervalSet[0...1, 2...3] | IntervalSet[1...2, 4...5] # -> [0...3, 4...5]

Note that using add or union! is more efficient than += or |=.

Parameters:

Returns:

  • (IntervalSet) —

    a new IntervalSet containing the union.



412
413
414
415
416
417
418
419
420
421
 
# File 'lib/interval_set.rb', line 412

def union(other)
  case other
    when Range
      union_range(other)
    when IntervalSet
      union_interval_set(other)
    else
      IntervalSet.unexpected_object(other)
  end
end

#xor(other) ⇒ IntervalSet Also known as: ^

Calculates a new IntervalSet which only contains elements exclusively from either this or the given object.

This operation is equivalent to (self | other) - (self & other)

IntervalSet[0...1] ^ IntervalSet[1...2]               # -> [0...2]
IntervalSet[0...2, 4...6] ^ IntervalSet[1...5, 7...8] # -> [0...1, 2...4, 5...6, 7...8]
IntervalSet[0...1] ^ IntervalSet[0...1]               # -> []

Parameters:

Returns:

  • (IntervalSet) —

    a new IntervalSet containing the exclusive set.



460
461
462
 
# File 'lib/interval_set.rb', line 460

def xor(other)
  clone.xor!(other)
end

#xor!(other) ⇒ IntervalSet

Calculates the set which contains elements exclusively from either this or the given object. The result of this operation is stored in this set.

The resulting set is equivalent to (self | other) - (self & other)

IntervalSet[0...1].xor!(IntervalSet[1...2])               # -> [0...2]
IntervalSet[0...2, 4...6].xor!(IntervalSet[1...5, 7...8]) # -> [0...1, 2...4, 5...6, 7...8]
IntervalSet[0...1].xor!(IntervalSet[0...1])               # -> []

Parameters:

Returns:

  • (IntervalSet) —

    a new IntervalSet containing the exclusive set.



478
479
480
481
482
 
# File 'lib/interval_set.rb', line 478

def xor!(other)
  intersection = self & other

  add(other).remove(intersection)
end