Trie

A trie is a data structure for efficiently storing and retrieving strings with identical prefixes, like "meet" and "meek".

Installation

  1. Add the dependency to your shard.yml:

    dependencies:
  cadmium_trie:
    github: cadmiumcr/trie

  2. Run shards install

Usage

require "trie"
trie = Cadmium.trie.new

trie.add("meet")
trie.size
# => 5

trie.add("meek")
trie.size
# => 6

trie.contains?("meet")
# => true

trie.find_prefix("meeting")
# => {"meet", "ing"}
trie.find_prefix("meet")
# => {"meet", ""}
trie.find_prefix("me")
# => {nil, "me"}

trie.keys_with_prefix("me")
# => ["meet", "meek"]

trie.add(["m", "me"])
trie.matches_on_path("meeting")
# => ["m", "me", "meet"]

Contributing

  1. Fork it (https://github.com/cadmiumcr/trie/fork)
  2. Create your feature branch (git checkout -b my-new-feature)
  3. Commit your changes (git commit -am 'Add some feature')
  4. Push to the branch (git push origin my-new-feature)
  5. Create a new Pull Request

Contributors