Class: Pwrake::RankQueueArray

Inherits:
Object
  • Object
show all
Defined in:
lib/pwrake/queue/queue_array.rb

Overview

Rank-Even Last In First Out

Instance Method Summary collapse

Constructor Details

#initialize(n) ⇒ RankQueueArray

Returns a new instance of RankQueueArray.



266
267
268
269
270
 
# File 'lib/pwrake/queue/queue_array.rb', line 266

def initialize(n)
  @q = []
  @size = 0
  @n = (n>0) ? n : 1
end

Instance Method Details

#clear ⇒ Object 



378
379
380
381
 
# File 'lib/pwrake/queue/queue_array.rb', line 378

def clear
  @q.clear
  @size = 0
end

#delete(t) ⇒ Object 



367
368
369
370
371
372
373
374
375
376
 
# File 'lib/pwrake/queue/queue_array.rb', line 367

def delete(t)
  n = 0
  @q.each do |a|
    if a
      a.delete(t)
      n += a.size
    end
  end
  @size = n
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


286
287
288
 
# File 'lib/pwrake/queue/queue_array.rb', line 286

def empty?
  @size == 0
end

#first ⇒ Object 



347
348
349
350
351
352
353
354
355
 
# File 'lib/pwrake/queue/queue_array.rb', line 347

def first
  return nil if empty?
  @q.size.times do |i|
    a = @q[i]
    unless a.nil? || a.empty?
      return a.first
    end
  end
end

#last ⇒ Object 



357
358
359
360
361
362
363
364
365
 
# File 'lib/pwrake/queue/queue_array.rb', line 357

def last
  return nil if empty?
  @q.size.times do |i|
    a = @q[-i-1]
    unless a.nil? || a.empty?
      return a.last
    end
  end
end

#pop_last_max(a) ⇒ Object 



330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
 
# File 'lib/pwrake/queue/queue_array.rb', line 330

def pop_last_max(a)
  if a.size < 2
    return a.pop
  end
  y_max = nil
  i_max = nil
  n = [@n, a.size].min
  (-n..-1).each do |i|
    y = a[i].input_file_size
    if y_max.nil? || y > y_max
      y_max = y
      i_max = i
    end
  end
  a.delete_at(i_max)
end

#push(t) ⇒ Object 



272
273
274
275
276
277
278
279
280
 
# File 'lib/pwrake/queue/queue_array.rb', line 272

def push(t)
  r = t ? t.rank : 0
  a = @q[r]
  if a.nil?
    @q[r] = a = []
  end
  @size += 1
  a.push(t)
end

#shift ⇒ Object 



290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
 
# File 'lib/pwrake/queue/queue_array.rb', line 290

def shift
  if empty?
    return nil
  end
  (@q.size-1).downto(0) do |i|
    a = @q[i]
    next if a.nil? || a.empty?
    @size -= 1
    if a.size <= @n
      return pop_last_max(a)
    else
      return shift_weighted
    end
  end
  raise "ELIFO: @q=#{@q.inspect}"
end

#shift_weighted ⇒ Object 



307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
 
# File 'lib/pwrake/queue/queue_array.rb', line 307

def shift_weighted
  weight, weight_avg = RANK_STAT.rank_weight
  wsum = 0.0
  q = []
  @q.each_with_index do |a,i|
    next if a.nil? || a.empty?
    w = weight[i]
    w = weight_avg if w.nil?
    # w *= a.size
    wsum += w
    q << [a,wsum]
  end
  #
  x = rand() * wsum
  Log.debug "shift_weighted x=#{x} wsum=#{wsum} weight=#{weight.inspect}"
  q.each do |a,w|
    if w > x
      return a.pop
    end
  end
  raise "ELIFO: wsum=#{wsum} x=#{x}"
end

#size ⇒ Object 



282
283
284
 
# File 'lib/pwrake/queue/queue_array.rb', line 282

def size
  @size
end