Class Batfish::Trie
In: lib/data/trie.rb
Parent: Object

A Trie is a datastructure used to store key value pairs where the key is a string. It does so by through a tree-like structure where each edge as a character associated to it. To walk through the trie, you go down one character of the key at a time until you reach the end of the key.

Methods

[]   []=   add   delete   each   empty?   fetch   has_key?   has_value?   new  

Classes and Modules

Class Batfish::Trie::Node

Attributes

root  [R] 

Public Class methods

new()

Initialize a Trie

[Source]

# File lib/data/trie.rb, line 15
    def initialize
      @root = Node.new()
    end

Public Instance methods

[](key)

Alias for fetch

[]=(key, value)

Alias for add

add(key, value)

Adds a key value pair to the trie. Returns the trie itself so calls to add may be chained together.

[Source]

# File lib/data/trie.rb, line 23
    def add(key, value)
      @root.add(key.to_s.upcase.split(""), value)
      return self
    end
delete(key)

Deletes the given key value pair from the trie. Returns the trie itself so several delete may be chained.

[Source]

# File lib/data/trie.rb, line 33
    def delete(key)
      @root.delete(key.to_s.upcase.split(""))
      return self
    end
each() {|k, v| ...}

Calls block once for each key value pair in the trie.

[Source]

# File lib/data/trie.rb, line 68
    def each
      @root.each("") do |k, v|
        yield(k, v)
      end
    end
empty?()

Returns true if the trie is empty.

[Source]

# File lib/data/trie.rb, line 62
    def empty?
      return @root.children.empty? ? true : false
    end
fetch(key)

Returns the value associated with the given key. Returns nil if it is not found.

[Source]

# File lib/data/trie.rb, line 41
    def fetch(key)
      @root.fetch(key.upcase.split(""))
    end
has_key?(key)

Returns true if the trie contains the given key.

[Source]

# File lib/data/trie.rb, line 48
    def has_key?(key)
      return self.fetch(key) ? true : false
    end
has_value?(value)

Returns true if the trie contains the given value.

[Source]

# File lib/data/trie.rb, line 54
    def has_value?(value)
      self.each do |k, v|
        return true if v == value
      end
      return false
    end

[Validate]