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:

  • range (Array<Integer>) —

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

Returns:

Raises:



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:

  • element (Integer)

Returns:

  • (Boolean)

Raises:



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:

  • range (Array<Integer>) —

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

Returns:

Raises:



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