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