Class: RangeList

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/range_list.rb,
lib/range_list/errors.rb,
lib/range_list/version.rb,
lib/range_list/map/tree_map.rb,
lib/range_list/map/sorted_map.rb

Overview

errors in RangeList

Defined Under Namespace

Modules: Map Classes: Error, IllegalArgumentError

Constant Summary collapse

VERSION = 
"0.3.0"

Instance Method Summary collapse

Constructor Details

#initialize ⇒ RangeList

Returns a new instance of RangeList.



11
12
13
 
# File 'lib/range_list.rb', line 11

def initialize
  @tree_map = Map::TreeMap.new
end

Instance Method Details

#add(range) ⇒ RangeList

Add specified range into current RangeList

Parameters:

  • Two integer element such as [left, right], include left, exclude right.

Returns:

Raises:

  • when range is invalid



19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/range_list.rb', line 19

def add(range)
  validate_range!(range)
  self if validate_empty_range?(range)

  # 1. Compute the range of the merged interval
  left_bound = range[0]
  left_floor_range = @tree_map.floor_entry(range[0])
  if !left_floor_range.nil? && left_floor_range[1] >= range[0]
    # left_floor_range and range has overlapping interval
    left_bound = left_floor_range[0]
  end

  right_bound = range[1]
  right_floor_range = @tree_map.floor_entry(range[1])
  if !right_floor_range.nil? && right_floor_range[1] >= range[1]
    # right_floor_range and range has overlapping interval
    right_bound = right_floor_range[1]
  end

  # 2. Remove overlapping intervals
  overlapping_ranges = @tree_map.sub_map(left_bound, right_bound)
  overlapping_ranges.each { |left, _right| @tree_map.remove(left) }

  # 3. Insert new range
  @tree_map.put(left_bound, right_bound)

  self
end

#contains?(element) ⇒ Boolean

Returns true if range list contains input element, or false if not contains.

Parameters:

Returns:

Raises:

  • when element is invalid



88
89
90
91
92
93
 
# File 'lib/range_list.rb', line 88

def contains?(element)
  validate_element!(element)

  floor_range = @tree_map.floor_entry(element)
  !floor_range.nil? && floor_range[1] > element
end

#each(&block) ⇒ Object 



95
96
97
 
# File 'lib/range_list.rb', line 95

def each(&block)
  @tree_map.each(&block)
end

#print ⇒ Object

Print RangeList to stdout



80
81
82
 
# File 'lib/range_list.rb', line 80

def print
  Kernel.print to_s
end

#remove(range) ⇒ RangeList

Remove specified range from current range

Parameters:

  • Two integer element such as [left, right], include left, exclude right.

Returns:

Raises:

  • when range is invalid



52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
 
# File 'lib/range_list.rb', line 52

def remove(range)
  validate_range!(range)
  self if validate_empty_range?(range)

  # 1. Remove overlapping intervals
  right_lower_range = @tree_map.floor_entry(range[1] - 1)
  if !right_lower_range.nil? && right_lower_range[1] > range[1]
    # right_lower_range and range has overlapping interval
    # insert new range after remove overlapping interval
    @tree_map.put(range[1], right_lower_range[1])
  end

  left_lower_range = @tree_map.floor_entry(range[0] - 1)
  if !left_lower_range.nil? && left_lower_range[1] > range[0]
    # left_lower_range and range has overlapping interval
    # insert new range after remove overlapping interval
    @tree_map.put(left_lower_range[0], range[0])
  end

  # 2. Remove ranges completely covered by input range
  # to_key is range[1] - 1 because right bound is exclusive
  overlapping_ranges = @tree_map.sub_map(range[0], range[1] - 1)
  overlapping_ranges.each { |left, _right| @tree_map.remove(left) }

  self
end

#to_s ⇒ Object 



99
100
101
 
# File 'lib/range_list.rb', line 99

def to_s
  map { |k, v| "[#{k}, #{v})" }.join(" ")
end