range_list_nxm

RangeList

RangeList is a quick Range Query Library

A pair of integers define a range, for example: [1, 5). This range includes integers: 1, 2, 3, and 4. A range list is an aggregate of these ranges: [10, 11), [100, 201). This range includes integers: 10, 100, 101, ... 200.

RangeList It uses red and black tree to ensure the operation efficiency and the use of additional memory

The time complexity of add() method and remove() method is log(n)

Gem

desc

pipeline

Installation

Install the gem and add to the application's Gemfile by executing:

$ bundle add range_list_nxm

If bundler is not being used to manage dependencies, install the gem by executing:

$ gem install range_list_nxm

Usage

require "range_list"

rl = RangeList.new
rl.add([1, 5])
rl.print ## Should display: [1, 5) 

rl.add([10, 20])
rl.print ## Should display: [1, 5) [10, 20)

rl.add([20, 20])
rl.print ## Should display: [1, 5) [10, 20) 

rl.add([20, 21])
rl.print ## Should display: [1, 5) [10, 21) 

rl.add([2, 4])
rl.print ## Should display: [1, 5) [10, 21) 

rl.add([3, 8])
rl.print ## Should display: [1, 8) [10, 21) 

rl.remove([10, 10])
rl.print ## Should display: [1, 8) [10, 21) 

rl.remove([10, 11])
rl.print ## Should display: [1, 8) [11, 21) 

rl.remove([15, 17])
rl.print ## Should display: [1, 8) [11, 15) [17, 21) 

rl.remove([3, 19])
rl.print ## Should display: [1, 3) [19, 21)

result = rl.query_all ## result: {1=>3, 19=>21}

Development

After checking out the repo, run bin/setup to install dependencies. You can also run bin/console for an interactive prompt that will allow you to experiment.

To install this gem onto your local machine, run bundle exec rake install. To release a new version, update the version number in version.rb, and then run bundle exec rake release, which will create a git tag for the version, push git commits and the created tag, and push the .gem file to rubygems.org.

Contributing

Bug reports and pull requests are welcome on GitLab at https://gitlab.com/ningxiaoming/range_list

License

The gem is available as open source under the terms of the MIT License.