Class: Lite::Containers::Heap

Inherits:
Object
  • Object
show all
Includes:
Abstract::Collection, Abstract::ImplicitKey, Abstract::Queue
Defined in:
lib/lite/containers/heap.rb

Overview

rubocop:disable Metrics/ClassLength

Defined Under Namespace

Classes: Error

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Abstract::ImplicitKey

#<<

Methods included from Abstract::Collection

#count, #empty?, #length

Constructor Details

#initialize(comparison) ⇒ Heap

Returns a new instance of Heap.



28
29
30
31
32
 
# File 'lib/lite/containers/heap.rb', line 28

def initialize(comparison)
  @comparison = comparison
  reset!
  freeze
end

Class Method Details

.instance(type, key_extractor: nil) ⇒ Object 



17
18
19
20
 
# File 'lib/lite/containers/heap.rb', line 17

def self.instance(type, key_extractor: nil)
  comparison = Helpers::Comparison.instance(type, key_extractor: key_extractor)
  with_comparison(comparison)
end

.with_comparison(comparison) ⇒ Object 



22
23
24
 
# File 'lib/lite/containers/heap.rb', line 22

def self.with_comparison(comparison)
  new(comparison)
end

Instance Method Details

#drain! ⇒ Object 



72
73
74
75
76
 
# File 'lib/lite/containers/heap.rb', line 72

def drain!
  result = []
  result << pop while length.positive?
  result
end

#front ⇒ Object 



42
43
44
 
# File 'lib/lite/containers/heap.rb', line 42

def front
  top
end

#pop ⇒ Object 



56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/lite/containers/heap.rb', line 56

def pop
  return if length.zero?

  if length == 1
    @array.pop
  else
    value = top
    sift_down(0, @array.pop)
    value
  end
end

#pop_front ⇒ Object 



68
69
70
 
# File 'lib/lite/containers/heap.rb', line 68

def pop_front
  pop
end

#push(value) ⇒ Object 



46
47
48
49
50
 
# File 'lib/lite/containers/heap.rb', line 46

def push(value)
  @array.push value
  sift_up(length - 1)
  self
end

#replace_top(value) ⇒ Object 



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

def replace_top(value)
  sift_down(0, value)
end

#reset! ⇒ Object 



78
79
80
81
82
83
84
 
# File 'lib/lite/containers/heap.rb', line 78

def reset!
  if frozen?
    @array.clear
  else
    @array = []
  end
end

#size ⇒ Object 



34
35
36
 
# File 'lib/lite/containers/heap.rb', line 34

def size
  @array.size
end

#top ⇒ Object 



38
39
40
 
# File 'lib/lite/containers/heap.rb', line 38

def top
  @array.first
end