Class: RangeSet

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

Overview

RangeSet 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.0-RC3-SNAPSHOT'

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(range_map = TreeMap.new) ⇒ RangeSet

Returns an empty instance of RangeSet.


28
29
30
31
32
33
34
35
36
# File 'lib/rangeset/range_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) ⇒ RangeSet

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

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

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

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

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

Instance Method Details

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

Adds the other object's elements to this RangeSet. The result is stored in this RangeSet.

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

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

299
300
301
302
303
304
305
306
307
308
# File 'lib/rangeset/range_set.rb', line 299

def add(other)
  case other
    when Range
      add_range(other)
    when RangeSet
      add_range_set(other)
    else
      raise ArgumentError.new("unexpected object #{other}")
  end
end

#boundsRange

Returns the bounds of this RangeSet.

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

69
70
71
# File 'lib/rangeset/range_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 RangeSet.

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

217
218
219
220
221
# File 'lib/rangeset/range_set.rb', line 217

def bounds_intersected_by?(range)
  return false if RangeSet::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 RangeSet.

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

231
232
233
234
235
# File 'lib/rangeset/range_set.rb', line 231

def bounds_intersected_or_touched_by?(range)
  return false if RangeSet::range_empty?(range)

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

#buffer(range) ⇒ RangeSet

Buffers this RangeSet by the given range. The result is stored in a new RangeSet.

The values of each range will be shifted by the values specified by the given range.

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

# reverse ranges will remove buffer
RangeSet[0...4].buffer!(1...-2)      # -> [1...2]
RangeSet[1...2].buffer!(0.5...-0.5)  # -> []

544
545
546
# File 'lib/rangeset/range_set.rb', line 544

def buffer(range)
  clone.buffer!(range)
end

#buffer!(range) ⇒ RangeSet

Buffers this RangeSet by the given range. The result is stored in this RangeSet.

The values of each range will be shifted by the values specified by the given range.

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

# reverse ranges will remove buffer
RangeSet[0...4].buffer(1...-2)      # -> [1...2]
RangeSet[1...2].buffer(0.5...-0.5)  # -> []

526
527
528
# File 'lib/rangeset/range_set.rb', line 526

def buffer!(range)
  convolve_range!(range)
end

#clearRangeSet

Removes all elements from this RangeSet.


550
551
552
553
554
555
556
# File 'lib/rangeset/range_set.rb', line 550

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

  self
end

#cloneRangeSet

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


568
569
570
# File 'lib/rangeset/range_set.rb', line 568

def clone
  RangeSet.new.copy(self)
end

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

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

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 singleton (effectively shifts the set)
RangeSet[0...1] * 1         # -> [1...2]

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

# Convolving with reversed ranges is also possible.  However,
# the definition above doesn't apply anymore. Unfortunately,
# I didn't come up with a better definition yet :(
RangeSet[1...2] * (-1...2)  # -> [0...4]
RangeSet[0...4] * (1...-2)  # -> [1...2]

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

478
479
480
# File 'lib/rangeset/range_set.rb', line 478

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

#convolve!(other) ⇒ RangeSet

Convolves the other object's elements with this RangeSet. The result is stored in this RangeSet.

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 singleton (effectively shifts the set)
RangeSet[0...1].convolve!(1)      # -> [1...2]

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

# Convolving with reversed ranges is also possible.
RangeSet[1...2].convolve!(-1...2) # -> [0...4]
RangeSet[0...4].convolve!(1...-2) # -> [1...2]

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

445
446
447
448
449
450
451
452
453
454
# File 'lib/rangeset/range_set.rb', line 445

def convolve!(other)
  case other
    when Range
      convolve_range!(other)
    when RangeSet
      convolve_range_set!(other)
    else
      convolve_element!(other)
  end
end

#copy(range_set) ⇒ RangeSet

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


575
576
577
578
579
580
581
582
# File 'lib/rangeset/range_set.rb', line 575

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

  self
end

#countInteger

Counts the number of ranges contained by this RangeSet.

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

281
282
283
# File 'lib/rangeset/range_set.rb', line 281

def count
  @range_map.count
end

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

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

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

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


411
412
413
414
415
416
417
418
419
420
# File 'lib/rangeset/range_set.rb', line 411

def difference(other)
  case other
    when Range
      difference_range(other)
    when RangeSet
      difference_range_set(other)
    else
      raise ArgumentError.new("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)

562
563
564
# File 'lib/rangeset/range_set.rb', line 562

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

#empty?Boolean

Returns true if this RangeSet contains no ranges.


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

def empty?
  @range_map.empty?
end

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

Returns true if two RangeSets are equal.

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

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

def eql?(other)
  return false if count != other.count
  return false if 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 RangeSet. Singletons will always evaluate to false.

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

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

def eql_set?(other)
  case other
    when Range
      eql_range?(other)
    when RangeSet
      eql?(other)
    else
      false
  end
end

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

Returns true if this RangeSet contains all elements contained by the other object.

r = RangeSet[0...1]         # -> [0...1]

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

# You can also supply ranges
r.include?(0...1)           # -> true
r.include?(0...2)           # -> false ; the whole range must be included
r.include?(0...0.5)         # -> true

# ... and range sets as well
r.include?(RangeSet[0...1])               # -> true
r.include?(RangeSet[0...1, 2...3])        # -> false
r.include?(RangeSet[0...0.25, 0.75...1])  # -> true

130
131
132
133
134
135
136
137
138
139
# File 'lib/rangeset/range_set.rb', line 130

def include?(other)
  case other
    when Range
      include_range?(other)
    when RangeSet
      include_range_set?(other)
    else
      include_element?(other)
  end
end

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

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

RangeSet[0...1].included_by?(0...1)               # -> true
RangeSet[0...1, 2...3].included_by?(0...1)        # -> false
RangeSet[0...0.25, 0.75...1].included_by?(0...1)  # -> true

153
154
155
156
157
158
159
160
161
162
163
164
# File 'lib/rangeset/range_set.rb', line 153

def included_by?(other)
  return true if empty?

  case other
    when Range
      included_by_range?(other)
    when RangeSet
      other.include_range_set?(self)
    else
      false
  end
end

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

Intersects the other object's elements with this RangeSet. The result is stored in this RangeSet.

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

344
345
346
347
348
349
350
351
352
353
# File 'lib/rangeset/range_set.rb', line 344

def intersect(other)
  case other
    when Range
      intersect_range(other)
    when RangeSet
      intersect_range_set(other)
    else
      raise ArgumentError.new("unexpected object #{other}")
  end
end

#intersect?(other) ⇒ Boolean

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

r = RangeSet[0...1]         # -> [0...1]

# For a single element intersect? behaves exactly like include?
r.intersect?(0)             # -> true
r.intersect?(0.5)           # -> true
r.intersect?(1)             # -> false

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

# The same applies for range sets
r.intersect?(RangeSet[0...1])         # -> true
r.intersect?(RangeSet[0...1, 2...3])  # -> true
r.intersect?(RangeSet[2...3])         # -> false

258
259
260
261
262
263
264
265
266
267
# File 'lib/rangeset/range_set.rb', line 258

def intersect?(other)
  case other
    when Range
      intersect_range?(other)
    when RangeSet
      intersect_range_set?(other)
    else
      include_element?(other)
  end
end

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

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

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

364
365
366
367
368
369
370
371
372
373
# File 'lib/rangeset/range_set.rb', line 364

def intersection(other)
  case other
    when Range
      intersection_range(other)
    when RangeSet
      intersection_range_set(other)
    else
      raise ArgumentError.new("unexpected object #{other}")
  end
end

#maxObject

Returns the upper bound of this RangeSet.

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

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

def max
  @max
end

#minObject

Returns the lower bound of this RangeSet.

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

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

def min
  @min
end

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

Return true if this RangeSet is a proper subset of the other. The result for a singleton will only be true if this RangeSet is empty.

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

# Compare to singletons
RangeSet[0...1].subset?(0)        # -> false
RangeSet[].subset?(0)             # -> true

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

204
205
206
# File 'lib/rangeset/range_set.rb', line 204

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

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

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

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

# Compare to singletons
RangeSet[0...1].superset?(0)      # -> true
RangeSet[0...1].superset?(1)      # -> false ; a range's end is exclusive

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

183
184
185
# File 'lib/rangeset/range_set.rb', line 183

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

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

Removes the other object's elements from this RangeSet. The result is stored in this RangeSet.

r = RangeSet[0...10]        # -> [0...10]
r.remove(0...2)             # -> [8...10]
r >> (2...8)                # -> [0...2, 8...10]

322
323
324
325
326
327
328
329
330
331
# File 'lib/rangeset/range_set.rb', line 322

def remove(other)
  case other
    when Range
      remove_range(other)
    when RangeSet
      remove_range_set(other)
    else
      raise ArgumentError.new("unexpected object #{other}")
  end
end

#shift(amount) ⇒ RangeSet

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

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

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


508
509
510
# File 'lib/rangeset/range_set.rb', line 508

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

#shift!(amount) ⇒ RangeSet

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

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

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


494
495
496
# File 'lib/rangeset/range_set.rb', line 494

def shift!(amount)
  convolve_element!(amount)
end

#to_sString Also known as: inspect

Returns a String representation of this RangeSet.

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

591
592
593
594
595
596
597
598
599
600
601
602
603
604
# File 'lib/rangeset/range_set.rb', line 591

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) ⇒ RangeSet Also known as: |, +

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

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

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


387
388
389
390
391
392
393
394
395
396
# File 'lib/rangeset/range_set.rb', line 387

def union(other)
  case other
    when Range
      union_range(other)
    when RangeSet
      union_range_set(other)
    else
      raise ArgumentError.new("unexpected object #{other}")
  end
end