ArrayTrie
Trie-like, prefix-tree data structures. First, a prefix-tree based on Arrays, which differs from a traditional trie, which maps strings to values. Second, a more general prefix-tree data structure that works for any type of keys, provided those keys can be transformed to and from an array.
Both of these data structures are implemented in terms of hashes.
Installation
Add this line to your application's Gemfile:
gem 'array_trie'
And then execute:
$ bundle
Or install it yourself as:
$ gem install array_trie
Usage
Use the base ArrayTrie
class if you want to work with an array-keyed trie.
The more general ArrayTrie::PrefixTrie
class can be used with any sort of
ordered key.
require 'array_trie/prefix_trie'
# You can store any sort of ordered key in a PrefixTrie, provided you can
# convert to and from arrays in a stable way.
path_to_a = -> (path) { path.split('/') }
a_to_path = -> (array) { array.join('/') }
paths = ArrayTrie::PrefixTrie.new(path_to_a, a_to_path)
# Store some keys in the trie
paths['/usr/local/bin/ruby'] = 'executable'
paths['/usr/local/etc/nginx/nginx.cfg'] = 'config file'
paths['/bin/bash'] = 'executable'
# Tries have efficient prefix queries
paths.include_prefix?('/usr/local')
# => true
paths.count_prefix('/usr/local')
# => 2
# You can obtain a subtrie to operate on a subsection of your trie
usr_local = paths.subtrie('/usr/local')
usr_local['bin/ruby']
# => "executable"
usr_local['bin/fish'] = 'executable'
paths['/usr/local/bin/fish']
# => "executable"
# Use #breadth_first and #depth_first to enumarate your keys and values
paths.breadth_first do |k, v|
puts "Path #{k} is of type #{v}"
end
# STDOUT: Path /bin/bash is of type executable
# STDOUT: Path /usr/local/bin/ruby is of type executable
# STDOUT: Path /usr/local/etc/nginx/nginx.cfg is of type config file
# These methods return Enumerators, so you can use them with #map, etc.
enum = paths.depth_first
as_hash = Hash[enum.to_a]
# => {
# ... "/usr/local/bin/ruby"=>"executable",
# ... "/usr/local/etc/nginx/nginx.cfg"=>"config file",
# ... "/bin/bash"=>"executable"
# ... }
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. Finally, use bin/test
to run the tests.
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 tags, and push the .gem
file to rubygems.org.
Contributing
Bug reports and pull requests are welcome on GitHub at https://github.com/justjake/array_trie.