Rux

Ruby binding to antirez/rax, a Radix tree implementation in C.

Rux::Tree is a key-value enumerable like Hash, but its keys must be strings. Its sweet spot is when:

  • The keys are large in size or many in number, but they share some prefixes
  • You need to iterate over the keyspace lexicographically (it's stored in alphabetical order) (not supported, see todos)

Installation

Add this line to your application's Gemfile:

# not on rubygems ... yet?
# gem 'rux'
gem 'rux', github: 'rmosolgo/rux'

Usage

require "rux"
tree = Rux::Tree.new
tree["a"] = 1
tree["ab"] = 2
tree.each { |k, v| puts(k, v) }
# a
# 1
# ab
# 2
tree.size         # => 2
tree["ab"]        # => 2
tree.delete("a")  # => 1
tree.size         # => 1
# fallbacks:
tree.get("x", :not_found)     # => :not_found
tree.delete("x", :not_found)  # => :not_found
tree.set("x", 1, :not_found)  # => :not_found
# previous value:
tree.set("x", 2, :not_found)  # => 1
tree.delete("x")              # => 2

Todo

  • Support cool lexicographical slices via raxIter
  • Expose rax's lazy enumeration
  • Learn how CRuby handles argument errors for variadic methods and do that
  • Implement a rax-backed Set for strings

Development

  • bundle exec rake compile
  • bundle exec rake test

License