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.1.1'

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(range_map = TreeMap.new) ⇒ IntervalSet

Returns an empty instance of IntervalSet.

Parameters:

  • range_map (TreeMap) (defaults to: TreeMap.new) —

    a TreeMap of ranges. For internal use only.



28
29
30
31
32
33
34
35
36
 
# File 'lib/interval_set.rb', line 28

def initialize(range_map = TreeMap.new)
  unless range_map.instance_of?(TreeMap) || range_map.instance_of?(TreeMap::BoundedMap)
    raise ArgumentError.new("invalid range_map #{range_map}")
  end

  @range_map = range_map

  update_bounds
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:



296
297
298
299
300
301
302
303
304
305
 
# File 'lib/interval_set.rb', line 296

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.



69
70
71
 
# File 'lib/interval_set.rb', line 69

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) 


219
220
221
222
223
 
# File 'lib/interval_set.rb', line 219

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) 


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

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.



579
580
581
 
# File 'lib/interval_set.rb', line 579

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:



554
555
556
557
558
559
560
561
562
563
564
565
 
# File 'lib/interval_set.rb', line 554

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:



585
586
587
588
589
590
591
 
# File 'lib/interval_set.rb', line 585

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:



603
604
605
 
# File 'lib/interval_set.rb', line 603

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.



503
504
505
 
# File 'lib/interval_set.rb', line 503

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:



474
475
476
477
478
479
480
481
482
483
 
# File 'lib/interval_set.rb', line 474

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:



610
611
612
613
614
615
616
617
 
# File 'lib/interval_set.rb', line 610

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.



278
279
280
 
# File 'lib/interval_set.rb', line 278

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.



408
409
410
411
412
413
414
415
416
417
 
# File 'lib/interval_set.rb', line 408

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) 


597
598
599
 
# File 'lib/interval_set.rb', line 597

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

#empty? ⇒ Boolean

Returns true if this IntervalSet contains no ranges.

Returns:

  • (Boolean) 


39
40
41
 
# File 'lib/interval_set.rb', line 39

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) 


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

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) 


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

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) 


120
121
122
123
124
125
126
 
# File 'lib/interval_set.rb', line 120

def include?(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:



341
342
343
344
345
346
347
348
349
350
 
# File 'lib/interval_set.rb', line 341

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) 


255
256
257
258
259
260
261
262
263
264
 
# File 'lib/interval_set.rb', line 255

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.



361
362
363
364
365
366
367
368
369
370
 
# File 'lib/interval_set.rb', line 361

def intersection(other)
  case other
    when Range
      intersection_range(other)
    when IntervalSet
      intersection_interval_set(other)
    else
      IntervalSet.unexpected_object(other)
  end
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.



59
60
61
 
# File 'lib/interval_set.rb', line 59

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.



49
50
51
 
# File 'lib/interval_set.rb', line 49

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) 


206
207
208
 
# File 'lib/interval_set.rb', line 206

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) 


190
191
192
 
# File 'lib/interval_set.rb', line 190

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:



319
320
321
322
323
324
325
326
327
328
 
# File 'lib/interval_set.rb', line 319

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.



538
539
540
 
# File 'lib/interval_set.rb', line 538

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:



519
520
521
522
523
524
525
526
 
# File 'lib/interval_set.rb', line 519

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) 


167
168
169
170
171
172
173
174
175
176
 
# File 'lib/interval_set.rb', line 167

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) 


142
143
144
145
146
147
148
149
150
151
 
# File 'lib/interval_set.rb', line 142

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.



626
627
628
629
630
631
632
633
634
635
636
637
638
639
 
# File 'lib/interval_set.rb', line 626

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.



384
385
386
387
388
389
390
391
392
393
 
# File 'lib/interval_set.rb', line 384

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.



432
433
434
 
# File 'lib/interval_set.rb', line 432

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.



450
451
452
453
454
 
# File 'lib/interval_set.rb', line 450

def xor!(other)
  intersection = self & other

  add(other).remove(intersection)
end