Class: BinarySearchTreeHash

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/binary_search_tree/binary_search_tree_hash.rb

Instance Method Summary collapse

Constructor Details

#initialize(logger = nil) ⇒ BinarySearchTreeHash

Returns a new instance of BinarySearchTreeHash.



4
5
6
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 4

def initialize logger=nil
  @bst = BinarySearchTree.new logger
end

Instance Method Details

#==(other_bst_hash) ⇒ Object 



180
181
182
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 180

def == other_bst_hash
  bst == other_bst_hash.send(:bst)
end

#[](key) ⇒ Object 



17
18
19
20
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 17

def [] key
  node = @bst.find key
  node.nil?? nil : node.value
end

#[]=(key, value) ⇒ Object 



22
23
24
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 22

def []=(key, value)
  @bst.insert key, value
end

#clear ⇒ Object 



8
9
10
11
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 8

def clear
  @bst.clear
  self
end

#delete(key) ⇒ Object 



26
27
28
29
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 26

def delete key
  @bst.remove key
  self
end

#delete_if ⇒ Object 



99
100
101
102
103
104
105
106
107
108
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 99

def delete_if
  nodes = @bst.nodes
  nodes.each_with_index do |node, i|
    if yield node.key, node.value
      @bst.remove node
      nodes[i] = nil
    end
  end
  nodes.compact.map{ |node| [node.key, node.value] }
end

#each ⇒ Object 



62
63
64
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 62

def each
  @bst.nodes.each { |node| yield [node.key, node.value] }
end

#each_key ⇒ Object 



66
67
68
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 66

def each_key
  @bst.nodes.each{ |node| yield node.key }
end

#each_pair ⇒ Object 



74
75
76
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 74

def each_pair
  @bst.nodes.each{ |node| yield node.key, node.value }
end

#each_value ⇒ Object 



70
71
72
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 70

def each_value
  @bst.nodes.each{ |node| yield node.value }
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


13
14
15
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 13

def empty?
  @bst.empty?
end

#has_key?(key) ⇒ Boolean

Returns:

  • (Boolean) 


115
116
117
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 115

def has_key? key
  !!@bst.find(key)
end

#has_value?(value) ⇒ Boolean

Returns:

  • (Boolean) 


131
132
133
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 131

def has_value? value
  !!@bst.find_value(value)
end

#include?(key) ⇒ Boolean

Returns:

  • (Boolean) 


119
120
121
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 119

def include? key
  has_key? key
end

#invert ⇒ Object 



153
154
155
156
157
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 153

def invert
  inverted_bst_hash = BinarySearchTreeHash.new
  each{ |key, value| inverted_bst_hash[value] = key }
  inverted_bst_hash
end

#key(value) ⇒ Object 



139
140
141
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 139

def key value
  @bst.find_value(value).key
end

#key?(key) ⇒ Boolean

Returns:

  • (Boolean) 


123
124
125
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 123

def key? key
  has_key? key
end

#keys ⇒ Object 



38
39
40
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 38

def keys
  map{ |node| node.first }
end

#max ⇒ Object 



58
59
60
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 58

def max
  [@bst.max.key, @bst.max.value]
end

#member?(key) ⇒ Boolean

Returns:

  • (Boolean) 


127
128
129
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 127

def member? key
  has_key? key
end

#merge(other_bst_hash) ⇒ Object 



164
165
166
167
168
169
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 164

def merge other_bst_hash
  merged_hash = BinarySearchTreeHash.new
  each{ |key, value| merged_hash[key] = value}
  other_bst_hash.each{ |key, value| merged_hash[key] = value }
  merged_hash
end

#merge!(other_bst_hash) ⇒ Object 



171
172
173
174
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 171

def merge! other_bst_hash
  other_bst_hash.each{ |key, value| self[key] = value }
  self
end

#min ⇒ Object 



54
55
56
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 54

def min
  [@bst.min.key, @bst.min.value]
end

#reject ⇒ Object 



82
83
84
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 82

def reject
  @bst.nodes.reject{ |node| yield node.key, node.value }.map{ |node| [node.key, node.value] }
end

#reject! ⇒ Object 



86
87
88
89
90
91
92
93
94
95
96
97
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 86

def reject!
  changed = false
  nodes = @bst.nodes
  nodes.each_with_index do |node, i|
    if yield node.key, node.value
      changed = true
      @bst.remove node
      nodes[i] = nil
    end
  end
  changed ? nodes.compact.map{ |node| [node.key, node.value] } : nil
end

#replace(other_bst_hash) ⇒ Object 



159
160
161
162
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 159

def replace other_bst_hash
  clear
  merge! other_bst_hash
end

#select ⇒ Object 



78
79
80
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 78

def select
  @bst.nodes.select{ |node| yield node.key, node.value }.map{ |node| [node.key, node.value] }
end

#shift ⇒ Object 



148
149
150
151
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 148

def shift
  deleted_node = @bst.remove_min
  deleted_node.nil?? nil : [deleted_node.key, deleted_node.value]
end

#size ⇒ Object Also known as: length 



110
111
112
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 110

def size
  @bst.size
end

#to_a ⇒ Object 



46
47
48
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 46

def to_a
  map{ |node| [node.first, node.last] }
end

#to_hash ⇒ Object Also known as: to_h 



31
32
33
34
35
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 31

def to_hash
  h = {}
  each{ |key, value| h[key] = value }
  h
end

#to_s ⇒ Object 



50
51
52
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 50

def to_s
  '{' + map{ |node| "#{node.first} => #{node.last}" }.join(', ') + '}'
end

#update(other_bst_hash) ⇒ Object 



176
177
178
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 176

def update other_bst_hash
  merge! other_bst_hash
end

#value?(value) ⇒ Boolean

Returns:

  • (Boolean) 


135
136
137
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 135

def value? value
  has_value? value
end

#values ⇒ Object 



42
43
44
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 42

def values
  map{ |node| node.last }
end

#values_at(key, *extra_keys) ⇒ Object 



143
144
145
146
 
# File 'lib/binary_search_tree/binary_search_tree_hash.rb', line 143

def values_at key, *extra_keys
  #TODO: optimize this so that only one tree traversal occurs
  ([key] + extra_keys).map{ |key| @bst.find(key).value }
end