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
Returns the number of key-value pairs in the trie.
Public Class Methods
# File lib/erlang/trie.rb, line 30 def self.[](pairs) result = self.new(0) pairs.each { |key, val| result.put!(key, val) } result end
# 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
# 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
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
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
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
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
Returns true
if the trie contains no key-value pairs.
# File lib/erlang/trie.rb, line 47 def empty? size == 0 end
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
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
# File lib/erlang/trie.rb, line 273 def include?(key, value) entry = get(key) entry && value.eql?(entry[1]) end
Returns true
if the given key is present in the trie.
# File lib/erlang/trie.rb, line 52 def key?(key) !!get(key) end
@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
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
# File lib/erlang/trie.rb, line 81 def reduce(memo) each { |entry| memo = yield(memo, entry) } memo end
# 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
# 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
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
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
# File lib/erlang/trie.rb, line 357 def copy_size(copy) copy ? copy.size : 0 end
# File lib/erlang/trie.rb, line 353 def index_for(key) (key.hash.abs >> @significant_bits) & 31 end