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

new(&block) click to toggle source

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, parents) click to toggle source

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(children) click to toggle source

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(parents) click to toggle source

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
child?(element) click to toggle source

Is element a child?

# File lib/recluse/hashtree.rb, line 105
def child?(element)
  @child_keys.keys.any? { |key| @equivalence.call(key, element) }
end
childless() click to toggle source

Finds parents without children. Returned as hash.

# File lib/recluse/hashtree.rb, line 154
def childless
  @parent_keys.select { |_key, children| children.empty? }
end
children() click to toggle source

Get children hash.

# File lib/recluse/hashtree.rb, line 93
def children
  @child_keys.dup
end
delete(element) click to toggle source

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(element) click to toggle source

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(element) click to toggle source

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_child_value(child) click to toggle source

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_children(parent) click to toggle source

Get parent's children

# File lib/recluse/hashtree.rb, line 71
def get_children(parent)
  @parent_keys[get_parent_key(parent)]
end
get_parents(child) click to toggle source

Get child's parents

# File lib/recluse/hashtree.rb, line 65
def get_parents(child)
  @child_keys[get_child_key(child)][:parents]
end
get_values(parent) click to toggle source

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
has?(element) click to toggle source

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
orphans() click to toggle source

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
parent?(element) click to toggle source

Is element a parent?

# File lib/recluse/hashtree.rb, line 111
def parent?(element)
  @parent_keys.keys.any? { |key| @equivalence.call(key, element) }
end
parents() click to toggle source

Get parents hash.

# File lib/recluse/hashtree.rb, line 87
def parents
  @parent_keys.dup
end
set_child_value(child, value) click to toggle source

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_child_key(child) click to toggle source

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_parent_key(parent) click to toggle source

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