class Recluse::HashTree
Sorta like a node tree but using two hashes for easy searching for parents and/or children. This way, it should have similar performance whether you're iterating over parents or children. Additionally, not every child will need a parent or they might not need a parent at initialization.
Public Class Methods
Create a hash tree.
# File lib/recluse/hashtree.rb, line 9 def initialize(&block) @parent_keys = {} @child_keys = {} @equivalence = block.nil? ? (proc { |a, b| a == b }) : block end
Public Instance Methods
Add child associated with parent(s).
# File lib/recluse/hashtree.rb, line 17 def add(child, parents) unless child?(child) @child_keys[child] = { value: nil, parents: [] } end @child_keys[get_child_key(child)][:parents] += [*parents] [*parents].each do |parent| @parent_keys[parent] = [] unless parent?(parent) @parent_keys[get_parent_key(parent)] << get_child_key(child) end end
Add child with no value and no parents.
# File lib/recluse/hashtree.rb, line 41 def add_child(children) [*children].each do |child| next if child?(child) @child_keys[child] = { value: nil, parents: [] } end end
Add parent with no children.
# File lib/recluse/hashtree.rb, line 33 def add_parent(parents) [*parents].each do |parent| @parent_keys[parent] = [] unless parent?(parent) end end
Is element a child?
# File lib/recluse/hashtree.rb, line 105 def child?(element) @child_keys.keys.any? { |key| @equivalence.call(key, element) } end
Finds parents without children. Returned as hash.
# File lib/recluse/hashtree.rb, line 154 def childless @parent_keys.select { |_key, children| children.empty? } end
Get children hash.
# File lib/recluse/hashtree.rb, line 93 def children @child_keys.dup end
Delete from parents and children. Essentially removes all known references.
# File lib/recluse/hashtree.rb, line 141 def delete(element) delete_child(element) delete_parent(element) end
Delete child. Removes references to child in associated parents.
# File lib/recluse/hashtree.rb, line 117 def delete_child(element) return false unless child?(element) c_key = get_child_key(element) @child_keys[c_key][:parents].each do |parent| @parent_keys[parent] -= [c_key] end @child_keys.delete c_key true end
Delete parent. Removes references to parent in associated children.
# File lib/recluse/hashtree.rb, line 129 def delete_parent(element) return false unless parent?(element) p_key = get_parent_key(element) @parent_keys[p_key].each do |child| @child_keys[child][:parents] -= [p_key] end @parent_keys.delete p_key true end
Get value of child.
# File lib/recluse/hashtree.rb, line 59 def get_child_value(child) @child_keys[get_child_key(child)][:value] end
Get parent's children
# File lib/recluse/hashtree.rb, line 71 def get_children(parent) @parent_keys[get_parent_key(parent)] end
Get child's parents
# File lib/recluse/hashtree.rb, line 65 def get_parents(child) @child_keys[get_child_key(child)][:parents] end
Collect values of children for parent.
# File lib/recluse/hashtree.rb, line 77 def get_values(parent) vals = {} @parent_keys[get_parent_key(parent)].each do |child| vals[child] = @child_keys[child][:value] end vals end
Does element exist as a child and/or parent key?
# File lib/recluse/hashtree.rb, line 99 def has?(element) child?(element) || parent?(element) end
Finds children without parents. Returned as hash.
# File lib/recluse/hashtree.rb, line 148 def orphans @child_keys.select { |_key, info| info[:parents].empty? } end
Is element a parent?
# File lib/recluse/hashtree.rb, line 111 def parent?(element) @parent_keys.keys.any? { |key| @equivalence.call(key, element) } end
Get parents hash.
# File lib/recluse/hashtree.rb, line 87 def parents @parent_keys.dup end
Set value of child.
# File lib/recluse/hashtree.rb, line 53 def set_child_value(child, value) @child_keys[get_child_key(child)][:value] = value end
Private Instance Methods
Get the child key (in case of alternative equivalence testing)
# File lib/recluse/hashtree.rb, line 162 def get_child_key(child) @child_keys.keys.find { |key| @equivalence.call(key, child) } end
Get the parent key (in case of alternative equivalence testing)
# File lib/recluse/hashtree.rb, line 168 def get_parent_key(parent) @parent_keys.keys.find { |key| @equivalence.call(key, parent) } end