yet_another_range_list

YARL (Yet Another Range List)

YARL is a Ruby gem that provides efficient functionality for managing and manipulating range lists using a segment tree data structure.

Features

• Add and remove ranges with ease
• Efficient range manipulation using segment trees
• Configurable maximum and minimum values

Installation

Add this line to your application's Gemfile:

gem 'yet_another_range_list'

And then execute:

$ bundle install

Or install it yourself as:

$ gem install yet_another_range_list

Usage

Basic Operations

require 'yet_another_range_list'

rl = YARL::RangeList.new

# Add ranges
rl.add([1, 5])
rl.add([3, 8])
rl << [10, 20]

# Remove ranges
rl.remove([10, 11])
rl.delete([15, 17])

# Print the current range list (Left bound inclusive, and right bound exclusive)
rl.print
# => [1, 8) [11, 15) [17, 20)

# Get current ranges (Both bound inclusively)
rl.to_a
# => [[1, 7], [11, 14], [17, 19]]

Configuration

By default the support integer range is between 0 and 4294967295 (The max number for unsigned 32bit integer), you can customize the limit when initializing a RangeList:

rl = YARL::RangeList.new(-1000, 1000)

Performance and Complexity

YARL uses a segment tree data structure to efficiently manage range operations. This allows for better performance compared to naive implementations, especially for large datasets or frequent operations.

Time Complexity

• Initialization: O(1).
• Add/Remove Range: O(log n) per operation, where n is the range of possible values (max_n - min_n).
• Print/To Array: O(log n).

Space Complexity

• O(m), where m is the number of distinct intervals that have been added or removed. This is because new nodes in the tree are only created when a range is modified.

Development

After checking out the repo, run bin/setup to install dependencies. Then, run rake test to run the tests. 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.

License

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

Code of Conduct

Everyone interacting in the YARL project's codebases, issue trackers, chat rooms and mailing lists is expected to follow the code of conduct.