Class: Lite::Containers::AvlTree

Inherits:
Object
  • Object
show all
Includes:
Enumerable, Lite::Containers::Abstract::Collection, Lite::Containers::Abstract::Deque, Lite::Containers::Abstract::SortedMap
Defined in:
lib/lite/containers/avl_tree.rb,
lib/lite/containers/avl_tree/find.rb,
lib/lite/containers/avl_tree/node.rb,
lib/lite/containers/avl_tree/delete.rb,
lib/lite/containers/avl_tree/insert.rb,
lib/lite/containers/avl_tree/balance.rb,
lib/lite/containers/avl_tree/traversal.rb,
lib/lite/containers/avl_tree/implementation.rb,
lib/lite/containers/avl_tree/interfaces/bracket_assign.rb,
lib/lite/containers/avl_tree/interfaces/key_extraction_strategy/abstract.rb,
lib/lite/containers/avl_tree/interfaces/key_extraction_strategy/explicit.rb,
lib/lite/containers/avl_tree/interfaces/key_extraction_strategy/implicit.rb

Overview

rubocop:disable Metrics/ClassLength

Direct Known Subclasses

ExplicitKey, ImplicitKey

Defined Under Namespace

Modules: Balance, Delete, Find, Implementation, Insert, Interfaces, Traversal Classes: Error, ExplicitKey, ImplicitKey, Node

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Lite::Containers::Abstract::Collection

#count, #empty?, #length

Constructor Details

#initialize(impl, merge) ⇒ AvlTree

Returns a new instance of AvlTree.



37
38
39
40
41
 
# File 'lib/lite/containers/avl_tree.rb', line 37

def initialize(impl, merge)
  @impl = impl
  @merge = merge
  reset!
end

Instance Attribute Details

#size ⇒ Object (readonly)

Returns the value of attribute size.



27
28
29
 
# File 'lib/lite/containers/avl_tree.rb', line 27

def size
  @size
end

Class Method Details

.instance(type, merge: nil, **opts) ⇒ Object 



29
30
31
32
33
 
# File 'lib/lite/containers/avl_tree.rb', line 29

def self.instance(type, merge: nil, **opts)
  impl = Implementation.instance(type)
  merge = Helpers::Merge.instance(merge)
  new(impl, merge, **opts)
end

Instance Method Details

#[](key) ⇒ Object 



52
53
54
 
# File 'lib/lite/containers/avl_tree.rb', line 52

def [](key)
  find_with_finder(key, @impl::Exact)&.value
end

#back ⇒ Object 



116
117
118
 
# File 'lib/lite/containers/avl_tree.rb', line 116

def back
  fetch_back&.out
end

#delete(key) ⇒ Object 



68
69
70
71
72
 
# File 'lib/lite/containers/avl_tree.rb', line 68

def delete(key)
  deleted, @root = @impl.delete(key, @root)
  @size -= 1 if deleted
  deleted&.out
end

#drain! ⇒ Object 



128
129
130
131
132
 
# File 'lib/lite/containers/avl_tree.rb', line 128

def drain!
  array = reverse_traverse.to_a
  reset!
  array
end

#each(&block) ⇒ Object 



74
75
76
77
78
79
80
81
 
# File 'lib/lite/containers/avl_tree.rb', line 74

def each(&block)
  if block
    traverse.each(&block)
    self
  else
    traverse
  end
end

#find(key) ⇒ Object 



56
57
58
 
# File 'lib/lite/containers/avl_tree.rb', line 56

def find(key)
  find_with_finder(key, @impl::Exact)&.out
end

#find_or_nearest_backwards(key) ⇒ Object 



60
61
62
 
# File 'lib/lite/containers/avl_tree.rb', line 60

def find_or_nearest_backwards(key)
  find_with_finder(key, @impl::ExactOrNearestBackwards)&.out
end

#find_or_nearest_forwards(key) ⇒ Object 



64
65
66
 
# File 'lib/lite/containers/avl_tree.rb', line 64

def find_or_nearest_forwards(key)
  find_with_finder(key, @impl::ExactOrNearestForwards)&.out
end

#front ⇒ Object 



104
105
106
 
# File 'lib/lite/containers/avl_tree.rb', line 104

def front
  fetch_front&.out
end

#key?(key) ⇒ Boolean

Returns:

  • (Boolean) 


48
49
50
 
# File 'lib/lite/containers/avl_tree.rb', line 48

def key?(key)
  !find_with_finder(key, @impl::Exact).nil?
end

#pop_back ⇒ Object 



120
121
122
123
124
125
126
 
# File 'lib/lite/containers/avl_tree.rb', line 120

def pop_back
  node = fetch_back
  return unless node

  delete(node.key)
  node.out
end

#pop_front ⇒ Object 



108
109
110
111
112
113
114
 
# File 'lib/lite/containers/avl_tree.rb', line 108

def pop_front
  node = fetch_front
  return unless node

  delete(node.key)
  node.out
end

#reset! ⇒ Object 



43
44
45
46
 
# File 'lib/lite/containers/avl_tree.rb', line 43

def reset!
  @root = nil
  @size = 0
end

#reverse_each(&block) ⇒ Object 



83
84
85
86
87
88
89
90
 
# File 'lib/lite/containers/avl_tree.rb', line 83

def reverse_each(&block)
  if block
    reverse_traverse.each(&block)
    self
  else
    reverse_traverse
  end
end

#reverse_traverse(from: nil, to: nil) ⇒ Object 



98
99
100
101
102
 
# File 'lib/lite/containers/avl_tree.rb', line 98

def reverse_traverse(from: nil, to: nil)
  Enumerator.new do |yielder|
    @impl.reverse_traverse @root, yielder, from: from, to: to
  end
end

#traverse(from: nil, to: nil) ⇒ Object 



92
93
94
95
96
 
# File 'lib/lite/containers/avl_tree.rb', line 92

def traverse(from: nil, to: nil)
  Enumerator.new do |yielder|
    @impl.traverse @root, yielder, from: from, to: to
  end
end