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/avl_tree/rbtree_adapter.rb,
lib/range_list/avl_tree/abstract_adapter.rb

Defined Under Namespace

Classes: ArgumentError, Error

Constant Summary collapse

VERSION = 
"1.3.1"

Instance Method Summary collapse

Constructor Details

#initialize ⇒ RangeList

Returns a new instance of RangeList.



9
10
11
 
# File 'lib/range_list.rb', line 9

def initialize
  @avl_tree = AvlTree::RBTreeAdapter.new
end

Instance Method Details

#add(range) ⇒ RangeList

Add range into current range list.

Parameters:

  • range (Array<Integer>) —

    the range, first element is range start, second is range end. Range end need be greater or equal than range start.

Returns:

Raises:



18
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 18

def add(range)
  validate_range!(range)
  return self if empty_range?(range)

  # Get real range start.
  start_lower_range = avl_tree.lower_entry(range[0])
  range_start = if !start_lower_range.nil? && start_lower_range[1] >= range[0]
    start_lower_range[0]
  else
    range[0]
  end

  # Get real range end.
  end_lower_range = avl_tree.lower_entry(range[1])
  range_end = if !end_lower_range.nil? && end_lower_range[1] >= range[1]
    end_lower_range[1]
  else
    range[1]
  end

  # Insert or replace new range.
  avl_tree.put(range_start, range_end)

  # Remove keys between range, exclude start, include end.
  sub_range = avl_tree.sub_map(range[0] + 1, range[1])
  sub_range.each { |range_start, _range_end| avl_tree.remove(range_start) }

  self
end

#contains?(element) ⇒ Boolean

Returns true if current ranges contains the element.

Parameters:

  • element (Integer) —

    the range element

Returns:

  • (Boolean)

Raises:



113
114
115
116
117
118
 
# File 'lib/range_list.rb', line 113

def contains?(element)
  validate_element!(element)

  lower_entry = avl_tree.lower_entry(element)
  !lower_entry.nil? && lower_entry[1] > element
end

#contains_all?(range) ⇒ Boolean

Note:

return false if the argument range is empty

Returns true if current ranges contains all elements of the range.

Parameters:

  • range (Array<Integer>) —

    the range, first element is range start, second is range end. Range end need be greater or equal than range start.

Returns:

  • (Boolean)

Raises:



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

def contains_all?(range)
  validate_range!(range)
  return false if empty_range?(range)

  start_lower_range = avl_tree.lower_entry(range[0])
  !start_lower_range.nil? && start_lower_range[1] >= range[1]
end

#contains_any?(range) ⇒ Boolean

Note:

return false if the argument range is empty

Returns true if current ranges contains any element of the range.

Parameters:

  • range (Array<Integer>) —

    the range, first element is range start, second is range end. Range end need be greater or equal than range start.

Returns:

  • (Boolean)

Raises:



100
101
102
103
104
105
106
107
 
# File 'lib/range_list.rb', line 100

def contains_any?(range)
  validate_range!(range)
  return false if empty_range?(range)

  # `-1` means not include.
  end_lower_range = avl_tree.lower_entry(range[1] - 1)
  !end_lower_range.nil? && end_lower_range[1] > range[0]
end

#each {|range_start, range_end| ... } ⇒ RangeList, Enumerator

Give RangeList iterative ability.

Yields:

  • (range_start, range_end) —

    give the range element to the block

Returns:



123
124
125
126
127
128
129
130
 
# File 'lib/range_list.rb', line 123

def each(&block)
  if block
    avl_tree.each(&block)
    self
  else
    enum_for(:each)
  end
end

#print ⇒ void

This method returns an undefined value.

Print current range list.



77
78
79
80
 
# File 'lib/range_list.rb', line 77

def print
  info = map { |k, v| "[#{k}, #{v})" }.join(" ")
  puts info
end

#remove(range) ⇒ RangeList

Remove range from current range list.

Parameters:

  • range (Array<Integer>) —

    the range, first element is range start, second is range end. Range end need be greater or equal than range start.

Returns:

Raises:



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

def remove(range)
  validate_range!(range)
  return self if empty_range?(range)

  # Insert end lower range, `-1` means not include.
  end_lower_range = avl_tree.lower_entry(range[1] - 1)
  if !end_lower_range.nil? && end_lower_range[1] > range[1]
    avl_tree.put(range[1], end_lower_range[1])
  end

  # Relace start lower range, `-1` means not include.
  start_lower_range = avl_tree.lower_entry(range[0] - 1)
  if !start_lower_range.nil? && start_lower_range[1] > range[0]
    avl_tree.put(start_lower_range[0], range[0])
  end

  # Remove keys between range, include start, exclude end
  sub_range = avl_tree.sub_map(range[0], range[1] - 1)
  sub_range.each { |range_start, _range_end| avl_tree.remove(range_start) }

  self
end