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

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:



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

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) 


221
222
223
224
225
 
# File 'lib/interval_set.rb', line 221

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) 


235
236
237
238
239
 
# File 'lib/interval_set.rb', line 235

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.



581
582
583
 
# File 'lib/interval_set.rb', line 581

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:



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

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:



587
588
589
590
591
592
593
 
# File 'lib/interval_set.rb', line 587

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:



605
606
607
 
# File 'lib/interval_set.rb', line 605

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.



505
506
507
 
# File 'lib/interval_set.rb', line 505

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:



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

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:



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

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.



280
281
282
 
# File 'lib/interval_set.rb', line 280

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.



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

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) 


599
600
601
 
# File 'lib/interval_set.rb', line 599

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

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



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

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) 


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

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.



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

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) 


208
209
210
 
# File 'lib/interval_set.rb', line 208

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) 


192
193
194
 
# File 'lib/interval_set.rb', line 192

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:



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

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.



540
541
542
 
# File 'lib/interval_set.rb', line 540

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:



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

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) 


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

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) 


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

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.



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

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.



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

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.



434
435
436
 
# File 'lib/interval_set.rb', line 434

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.



452
453
454
455
456
 
# File 'lib/interval_set.rb', line 452

def xor!(other)
  intersection = self & other

  add(other).remove(intersection)
end