class ColumnPack::BinPacker

Arranges elements into bins using a simple one dimensional bin packing algorithm.

Public Class Methods

new(total_bins, options = {}) click to toggle source

Uses a fixed number of bins (total_bins).

Options: :algorithm specify a different bin packing algorithm (default :best_fit_decreasing)

available algorithms are :best_fit_decreasing, :best_fit_increasing

:shuffle_in_col after packing columns, shuffle the elements in each column (defaults to true)

# File lib/column_pack/bin_packer.rb, line 14
def initialize(total_bins, options = {})
  raise ArgumentError.new("Must choose a number of bins greater than zero") if total_bins <= 0

  @total_bins = total_bins
  @algorithm  = options[:algorithm] || :best_fit_decreasing

  if options.has_key? :shuffle_in_col
    @shuffle_in_col = options[:shuffle_in_col]
  else
    @shuffle_in_col = true
  end

  @elements       = []
  @needs_packing  = true
end

Public Instance Methods

add(size, content) click to toggle source

Adds element to be packed.

# File lib/column_pack/bin_packer.rb, line 31
def add(size, content)
  raise ArgumentError.new("Bin size must be greater than zero") if size <= 0

  @elements << {:size => size.to_i, :content => content}
  @needs_packing = true
end
bins() click to toggle source

Returns a packed multi-dimensional array of elements.

# File lib/column_pack/bin_packer.rb, line 39
def bins
  pack_all if @needs_packing
  @bins
end
empty_space() click to toggle source

Total empty space left over by uneven packing.

# File lib/column_pack/bin_packer.rb, line 45
def empty_space
  pack_all if @needs_packing
  max = @sizes.each.max
  space = 0

  @sizes.each { |size| space += max - size }

  space
end

Private Instance Methods

best_fit() click to toggle source
# File lib/column_pack/bin_packer.rb, line 78
def best_fit
  @elements.each do |element|
    _, col = @sizes.each_with_index.min
    pack(col, element)
  end
end
best_fit_decreasing() click to toggle source
# File lib/column_pack/bin_packer.rb, line 67
def best_fit_decreasing
  @elements.sort_by! { |e| e[:size] }
  @elements.reverse!
  best_fit
end
best_fit_increasing() click to toggle source
# File lib/column_pack/bin_packer.rb, line 73
def best_fit_increasing
  @elements.sort_by! { |e| e[:size] }
  best_fit
end
pack(col, element) click to toggle source
# File lib/column_pack/bin_packer.rb, line 101
def pack(col, element)
  @bins[col] << element[:content]
  @sizes[col] += element[:size].to_i
end
pack_all() click to toggle source
# File lib/column_pack/bin_packer.rb, line 56
def pack_all
  @bins   = Array.new(@total_bins) {Array.new}
  @sizes  = Array.new(@total_bins, 0)

  self.send(@algorithm)
  tall_to_middle
  shuffle_within_cols if @shuffle_in_col

  @needs_packing = false
end
shuffle_within_cols() click to toggle source
# File lib/column_pack/bin_packer.rb, line 85
def shuffle_within_cols
  @bins.each { |bin| bin.shuffle! }
end
tall_to_middle() click to toggle source

moves the tallest bin to the middle

# File lib/column_pack/bin_packer.rb, line 90
def tall_to_middle
  if (@total_bins > 1) && ((@total_bins % 2) != 0)
    _, max_col = @sizes.each_with_index.max
    mid_col = @total_bins / 2

    temp = @bins[mid_col].clone
    @bins[mid_col] = @bins[max_col]
    @bins[max_col] = temp
  end
end