class Erlang::Trie

Licensing

Portions taken and modified from github.com/hamstergem/hamster

Copyright (c) 2009-2014 Simon Harris

Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

@private

Attributes

size[R]

Returns the number of key-value pairs in the trie.

Public Class Methods

[](pairs) click to toggle source
# File lib/erlang/trie.rb, line 30
def self.[](pairs)
  result = self.new(0)
  pairs.each { |key, val| result.put!(key, val) }
  result
end
new(significant_bits, size = 0, entries = [], children = []) click to toggle source
# File lib/erlang/trie.rb, line 39
def initialize(significant_bits, size = 0, entries = [], children = [])
  @significant_bits = significant_bits
  @entries = entries
  @children = children
  @size = size
end

Public Instance Methods

==(other)
Alias for: eql?
at(index) click to toggle source
# File lib/erlang/trie.rb, line 278
def at(index)
  @entries.each do |entry|
    if entry
      return entry if index == 0
      index -= 1
    end
  end
  @children.each do |child|
    if child
      if child.size >= index+1
        return child.at(index)
      else
        index -= child.size
      end
    end
  end
  nil
end
bulk_delete(keys) click to toggle source

Delete multiple elements from a Trie. This is more efficient than several calls to `#delete`.

@param keys [Enumerable] The keys to delete @return [Trie]

# File lib/erlang/trie.rb, line 230
def bulk_delete(keys)
  new_entries = nil
  new_children = nil
  new_size = @size

  keys.each do |key|
    index = index_for(key)
    entry = (new_entries || @entries)[index]
    if !entry
      next
    elsif entry[0].eql?(key)
      new_entries ||= @entries.dup
      child = (new_children || @children)[index]
      if child
        # Bring up the first entry from the child into entries
        new_children ||= @children.dup
        new_children[index] = child.delete_at do |child_entry|
          new_entries[index] = child_entry
        end
      else
        new_entries[index] = nil
      end
      new_size -= 1
    else
      child = (new_children || @children)[index]
      if child
        copy = child.find_and_delete(key)
        unless copy.equal?(child)
          new_children ||= @children.dup
          new_children[index] = copy
          new_size -= (child.size - copy_size(copy))
        end
      end
    end
  end

  if new_entries || new_children
    Trie.new(@significant_bits, new_size, new_entries || @entries, new_children || @children)
  else
    self
  end
end
bulk_put(key_value_pairs) click to toggle source

Put multiple elements into a Trie. This is more efficient than several calls to `#put`.

@param key_value_pairs Enumerable of pairs (`[key, value]`) @return [Trie] A copy of `self` after associated the given keys and

values (or `self` if no modifications where needed).
# File lib/erlang/trie.rb, line 139
def bulk_put(key_value_pairs)
  new_entries = nil
  new_children = nil
  new_size = @size

  key_value_pairs.each do |key, value|
    index = index_for(key)
    entry = (new_entries || @entries)[index]

    if !entry
      new_entries ||= @entries.dup
      key = key.dup.freeze if key.is_a?(String) && !key.frozen?
      new_entries[index] = [key, value].freeze
      new_size += 1
    elsif entry[0].eql?(key)
      if !entry[1].equal?(value)
        new_entries ||= @entries.dup
        key = key.dup.freeze if key.is_a?(String) && !key.frozen?
        new_entries[index] = [key, value].freeze
      end
    else
      child = (new_children || @children)[index]
      if child
        new_child = child.put(key, value)
        if !new_child.equal?(child)
          new_children ||= @children.dup
          new_children[index] = new_child
          new_size += new_child.size - child.size
        end
      else
        new_children ||= @children.dup
        new_children[index] = Trie.new(@significant_bits + 5).put!(key, value)
        new_size += 1
      end
    end
  end

  if new_entries || new_children
    Trie.new(@significant_bits, new_size, new_entries || @entries, new_children || @children)
  else
    self
  end
end
delete(key) click to toggle source

Returns a copy of self with the given key (and associated value) deleted. If not found, returns self.

# File lib/erlang/trie.rb, line 221
def delete(key)
  find_and_delete(key) || Trie.new(@significant_bits)
end
each(&block) click to toggle source

Calls block once for each entry in the trie, passing the key-value pair as parameters.

# File lib/erlang/trie.rb, line 57
def each(&block)
  # TODO: Using block.call here is slower than using yield by 5-10%, but
  # the latter segfaults on ruby 2.2 and above. Once that is fixed and
  # broken versions are sufficiently old, we should revert back to yield
  # with a warning that the broken versions are unsupported.
  #
  # For more context:
  # * https://bugs.ruby-lang.org/issues/11451
  # * https://github.com/hamstergem/hamster/issues/189
  @entries.each { |entry| block.call(entry) if entry }
  @children.each do |child|
    child.each(&block) if child
  end
  nil
end
empty?() click to toggle source

Returns true if the trie contains no key-value pairs.

# File lib/erlang/trie.rb, line 47
def empty?
  size == 0
end
eql?(other) click to toggle source

Returns true if . eql? is synonymous with ==

# File lib/erlang/trie.rb, line 298
def eql?(other)
  return true if equal?(other)
  return false unless instance_of?(other.class) && size == other.size
  each do |entry|
    return false unless other.include?(entry[0], entry[1])
  end
  true
end
Also aliased as: ==
get(key) click to toggle source

Retrieves the entry corresponding to the given key. If not found, returns nil.

# File lib/erlang/trie.rb, line 209
def get(key)
  index = index_for(key)
  entry = @entries[index]
  if entry && entry[0].eql?(key)
    entry
  else
    child = @children[index]
    child.get(key) if child
  end
end
include?(key, value) click to toggle source
# File lib/erlang/trie.rb, line 273
def include?(key, value)
  entry = get(key)
  entry && value.eql?(entry[1])
end
key?(key) click to toggle source

Returns true if the given key is present in the trie.

# File lib/erlang/trie.rb, line 52
def key?(key)
  !!get(key)
end
put(key, value) click to toggle source

@return [Trie] A copy of `self` with the given value associated with the

key (or `self` if no modification was needed because an identical
key-value pair wes already stored
# File lib/erlang/trie.rb, line 95
def put(key, value)
  index = index_for(key)
  entry = @entries[index]

  if !entry
    entries = @entries.dup
    key = key.dup.freeze if key.is_a?(String) && !key.frozen?
    entries[index] = [key, value].freeze
    Trie.new(@significant_bits, @size + 1, entries, @children)
  elsif entry[0].eql?(key)
    if entry[1].equal?(value)
      self
    else
      entries = @entries.dup
      key = key.dup.freeze if key.is_a?(String) && !key.frozen?
      entries[index] = [key, value].freeze
      Trie.new(@significant_bits, @size, entries, @children)
    end
  else
    child = @children[index]
    if child
      new_child = child.put(key, value)
      if new_child.equal?(child)
        self
      else
        children = @children.dup
        children[index] = new_child
        new_self_size = @size + (new_child.size - child.size)
        Trie.new(@significant_bits, new_self_size, @entries, children)
      end
    else
      children = @children.dup
      children[index] = Trie.new(@significant_bits + 5).put!(key, value)
      Trie.new(@significant_bits, @size + 1, @entries, children)
    end
  end
end
put!(key, value) click to toggle source

Returns self after overwriting the element associated with the specified key.

# File lib/erlang/trie.rb, line 184
def put!(key, value)
  index = index_for(key)
  entry = @entries[index]
  if !entry
    @size += 1
    key = key.dup.freeze if key.is_a?(String) && !key.frozen?
    @entries[index] = [key, value].freeze
  elsif entry[0].eql?(key)
    key = key.dup.freeze if key.is_a?(String) && !key.frozen?
    @entries[index] = [key, value].freeze
  else
    child = @children[index]
    if child
      old_child_size = child.size
      @children[index] = child.put!(key, value)
      @size += child.size - old_child_size
    else
      @children[index] = Trie.new(@significant_bits + 5).put!(key, value)
      @size += 1
    end
  end
  self
end
reduce(memo) { |memo, entry| ... } click to toggle source
# File lib/erlang/trie.rb, line 81
def reduce(memo)
  each { |entry| memo = yield(memo, entry) }
  memo
end
reverse_each() { |entry| ... } click to toggle source
# File lib/erlang/trie.rb, line 73
def reverse_each(&block)
  @children.reverse_each do |child|
    child.reverse_each(&block) if child
  end
  @entries.reverse_each { |entry| yield(entry) if entry }
  nil
end
select() { |entry| ... } click to toggle source
# File lib/erlang/trie.rb, line 86
def select
  keys_to_delete = []
  each { |entry| keys_to_delete << entry[0] unless yield(entry) }
  bulk_delete(keys_to_delete)
end

Protected Instance Methods

delete_at(index = @entries.index { |e| e }) { |entries| ... } click to toggle source

Returns a replacement instance after removing the specified entry. If empty, returns nil

# File lib/erlang/trie.rb, line 334
def delete_at(index = @entries.index { |e| e })
  yield(@entries[index]) if block_given?
  if size > 1
    entries = @entries.dup
    child = @children[index]
    if child
      children = @children.dup
      children[index] = child.delete_at do |entry|
        entries[index] = entry
      end
    else
      entries[index] = nil
    end
    Trie.new(@significant_bits, @size - 1, entries, children || @children)
  end
end
find_and_delete(key) click to toggle source

Returns a replacement instance after removing the specified key. If not found, returns self. If empty, returns nil.

# File lib/erlang/trie.rb, line 313
def find_and_delete(key)
  index = index_for(key)
  entry = @entries[index]
  if entry && entry[0].eql?(key)
    return delete_at(index)
  else
    child = @children[index]
    if child
      copy = child.find_and_delete(key)
      unless copy.equal?(child)
        children = @children.dup
        children[index] = copy
        new_size = @size - (child.size - copy_size(copy))
        return Trie.new(@significant_bits, new_size, @entries, children)
      end
    end
  end
  self
end

Private Instance Methods

copy_size(copy) click to toggle source
# File lib/erlang/trie.rb, line 357
def copy_size(copy)
  copy ? copy.size : 0
end
index_for(key) click to toggle source
# File lib/erlang/trie.rb, line 353
def index_for(key)
  (key.hash.abs >> @significant_bits) & 31
end