Class: RubySprites::Packer::BothSplit::Heap

Inherits:
Object
  • Object
show all
Defined in:
lib/lash-sprites/packer/both_split.rb

Instance Method Summary collapse

Constructor Details

#initialize(&comparer) ⇒ Heap

Returns a new instance of Heap.



114
115
116
117
# File 'lib/lash-sprites/packer/both_split.rb', line 114

def initialize(&comparer)
  @comparer = comparer
  @heap = [0]
end

Instance Method Details

#empty?Boolean

Returns:

  • (Boolean)


161
162
163
# File 'lib/lash-sprites/packer/both_split.rb', line 161

def empty?
  return @heap.length == 1
end

#insert(el) ⇒ Object



119
120
121
122
123
124
125
126
127
128
129
130
131
132
# File 'lib/lash-sprites/packer/both_split.rb', line 119

def insert(el)
  pos = @heap.length
  @heap.push(el)
  new_pos = pos
  while new_pos != 1 &&  @comparer.call(el, @heap[new_pos / 2]) < 0
    new_pos /= 2
  end

  while(pos > new_pos)
    @heap[pos] = @heap[pos / 2]
    pos /= 2
  end
  @heap[pos] = el
end

#inspectObject



165
166
167
# File 'lib/lash-sprites/packer/both_split.rb', line 165

def inspect
  return @heap.to_s
end

#peekObject



156
157
158
159
# File 'lib/lash-sprites/packer/both_split.rb', line 156

def peek
  return nil if @heap.length == 1
  return @heap[1]
end

#removeObject



134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
# File 'lib/lash-sprites/packer/both_split.rb', line 134

def remove
  return nil if @heap.length == 1
  el = @heap[1]
  shifter = @heap.pop
  if @heap.length != 1
    pos = 1
    while(!@heap[pos * 2].nil?)
      lesser_pos = pos * 2
      lesser_pos += 1 if !@heap[pos * 2 + 1].nil? && @comparer.call(@heap[pos * 2 + 1], @heap[pos * 2]) < 0
      if(@comparer.call(@heap[lesser_pos], shifter) < 0)
        @heap[pos] = @heap[lesser_pos]
        pos = lesser_pos
      else
        break
      end
    end

    @heap[pos] = shifter
  end
  return el
end