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.



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

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

Instance Method Details

#clearObject



392
393
394
395
# File 'lib/pwrake/queue/queue_array.rb', line 392

def clear
  @q.clear
  @size = 0
end

#delete(t) ⇒ Object



381
382
383
384
385
386
387
388
389
390
# File 'lib/pwrake/queue/queue_array.rb', line 381

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)


300
301
302
# File 'lib/pwrake/queue/queue_array.rb', line 300

def empty?
  @size == 0
end

#firstObject



361
362
363
364
365
366
367
368
369
# File 'lib/pwrake/queue/queue_array.rb', line 361

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

#lastObject



371
372
373
374
375
376
377
378
379
# File 'lib/pwrake/queue/queue_array.rb', line 371

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



344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
# File 'lib/pwrake/queue/queue_array.rb', line 344

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



286
287
288
289
290
291
292
293
294
# File 'lib/pwrake/queue/queue_array.rb', line 286

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

#shiftObject



304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
# File 'lib/pwrake/queue/queue_array.rb', line 304

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_weightedObject



321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
# File 'lib/pwrake/queue/queue_array.rb', line 321

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

#sizeObject



296
297
298
# File 'lib/pwrake/queue/queue_array.rb', line 296

def size
  @size
end