Class: Recluse::HashTree

Inherits:
Object
  • Object
show all
Defined in:
lib/recluse/hashtree.rb

Overview

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.

Instance Method Summary collapse

Constructor Details

#initialize(&block) ⇒ HashTree

Create a hash tree.



9
10
11
12
13
 
# File 'lib/recluse/hashtree.rb', line 9

def initialize(&block)
  @parent_keys = {}
  @child_keys = {}
  @equivalence = block.nil? ? (proc { |a, b| a == b }) : block
end

Instance Method Details

#add(child, parents) ⇒ Object

Add child associated with parent(s).



17
18
19
20
21
22
23
24
25
26
27
28
29
 
# 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) ⇒ Object

Add child with no value and no parents.



41
42
43
44
45
46
47
48
49
 
# 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) ⇒ Object

Add parent with no children.



33
34
35
36
37
 
# 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) ⇒ Boolean

Is element a child?

Returns:

  • (Boolean) 


105
106
107
 
# File 'lib/recluse/hashtree.rb', line 105

def child?(element)
  @child_keys.keys.any? { |key| @equivalence.call(key, element) }
end

#childless ⇒ Object

Finds parents without children. Returned as hash.



154
155
156
 
# File 'lib/recluse/hashtree.rb', line 154

def childless
  @parent_keys.select { |_key, children| children.empty? }
end

#children ⇒ Object

Get children hash.



93
94
95
 
# File 'lib/recluse/hashtree.rb', line 93

def children
  @child_keys.dup
end

#delete(element) ⇒ Object

Delete from parents and children. Essentially removes all known references.



141
142
143
144
 
# File 'lib/recluse/hashtree.rb', line 141

def delete(element)
  delete_child(element)
  delete_parent(element)
end

#delete_child(element) ⇒ Object

Delete child. Removes references to child in associated parents.



117
118
119
120
121
122
123
124
125
 
# 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) ⇒ Object

Delete parent. Removes references to parent in associated children.



129
130
131
132
133
134
135
136
137
 
# 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) ⇒ Object

Get value of child.



59
60
61
 
# File 'lib/recluse/hashtree.rb', line 59

def get_child_value(child)
  @child_keys[get_child_key(child)][:value]
end

#get_children(parent) ⇒ Object

Get parent’s children



71
72
73
 
# File 'lib/recluse/hashtree.rb', line 71

def get_children(parent)
  @parent_keys[get_parent_key(parent)]
end

#get_parents(child) ⇒ Object

Get child’s parents



65
66
67
 
# File 'lib/recluse/hashtree.rb', line 65

def get_parents(child)
  @child_keys[get_child_key(child)][:parents]
end

#get_values(parent) ⇒ Object

Collect values of children for parent.



77
78
79
80
81
82
83
 
# 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) ⇒ Boolean

Does element exist as a child and/or parent key?

Returns:

  • (Boolean) 


99
100
101
 
# File 'lib/recluse/hashtree.rb', line 99

def has?(element)
  child?(element) || parent?(element)
end

#orphans ⇒ Object

Finds children without parents. Returned as hash.



148
149
150
 
# File 'lib/recluse/hashtree.rb', line 148

def orphans
  @child_keys.select { |_key, info| info[:parents].empty? }
end

#parent?(element) ⇒ Boolean

Is element a parent?

Returns:

  • (Boolean) 


111
112
113
 
# File 'lib/recluse/hashtree.rb', line 111

def parent?(element)
  @parent_keys.keys.any? { |key| @equivalence.call(key, element) }
end

#parents ⇒ Object

Get parents hash.



87
88
89
 
# File 'lib/recluse/hashtree.rb', line 87

def parents
  @parent_keys.dup
end

#set_child_value(child, value) ⇒ Object

Set value of child.



53
54
55
 
# File 'lib/recluse/hashtree.rb', line 53

def set_child_value(child, value)
  @child_keys[get_child_key(child)][:value] = value
end