Class: RangeList

Inherits:
Object
  • Object
show all
Defined in:
lib/range_list.rb

Overview

RangeList is a quick Range Query Library

Instance Method Summary collapse

Constructor Details

#initialize ⇒ RangeList

Returns a new instance of RangeList.



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

def initialize
  @red_black_tree_impl = RedBlackTreeImpl.new
end

Instance Method Details

#add(range) ⇒ Object

Add range to rangeList range must be less than or equal to range

Parameters:

  • range (Array<Integer>) —

    is a range.range.length must be 2，the range is range start,range is range end

Returns:

  • nil

Raises:

  • ArgumentError



17
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
 
# File 'lib/range_list.rb', line 17

def add(range)
  validate_param(range)
  return if range[0] == range[1]

  start_floor_range = @red_black_tree_impl.floor_range(range[0])
  return if !start_floor_range.nil? && start_floor_range[1] >= range[1]

  # find start
  start = if !start_floor_range.nil? && start_floor_range[1] >= range[0]
            start_floor_range[0]
          else
            range[0]
          end
  # find last
  last_floor_range = @red_black_tree_impl.floor_range(range[1])
  last = if !last_floor_range.nil? && last_floor_range[1] >= range[1]
           last_floor_range[1]
         else
           range[1]
         end
  # delete old range
  @red_black_tree_impl.sub_hash_key(start + 1, last).each do |k|
    @red_black_tree_impl.delete(k)
  end
  # add new range
  @red_black_tree_impl.put(start, last)
  nil
end

#print ⇒ Object 



72
73
74
75
76
77
78
79
 
# File 'lib/range_list.rb', line 72

def print
  item = ''
  # splicing range
  @red_black_tree_impl.each do |k, v|
    item += "[#{k}, #{v}) "
  end
  puts item[0, item.length - 1]
end

#query_all ⇒ Object 



81
82
83
84
85
86
87
 
# File 'lib/range_list.rb', line 81

def query_all
  res_hash = {}
  @red_black_tree_impl.each do |k,v|
    res_hash[k] = v
  end
  res_hash
end

#remove(range) ⇒ Object

Remove range to rangeList range must be less than or equal to range

Parameters:

  • range (Array<Integer>) —

    is a range. range length must be 2，the range is range start,range is range end

Returns:

  • nil

Raises:

  • ArgumentError



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

def remove(range)
  validate_param(range)
  return if range[0] == range[1]

  #  find add add ranges greater than range[0]
  end_floor_range = @red_black_tree_impl.floor_range(range[1] - 1)
  return if end_floor_range.nil?

  @red_black_tree_impl.put(range[1], end_floor_range[1]) if !end_floor_range.nil? && end_floor_range[1] > range[1]

  #  find add add ranges less than range[0]
  start_floor_range = @red_black_tree_impl.floor_range(range[0] - 1)
  @red_black_tree_impl.put(start_floor_range[0], range[0]) if !start_floor_range.nil? && start_floor_range[1] > range[0]

  # delete range
  @red_black_tree_impl.sub_hash_key(range[0], range[1] - 1).each do |k|
    @red_black_tree_impl.delete(k)
  end
  nil
end