Untitled
By: a guest | May 19th, 2010 | Syntax:
JavaScript | Size: 1.97 KB | Hits: 188 | Expires: Never
// По-уму этот алгоритм называется "one-dimensional bin packing"
// Я на скорую руку реализовал второй по сложности с конца его вариант -- First fit :)
// src_data_array = ...
buffer_data_array = []; // массив буферов
buffer_data_array_sizes = []; // запоминаем посчитанные веса буферов, чтобы не пересчитывать каждый раз
tmp_data_array = src_data_array.slice(0); // содаем копию для разборки на буферы
while( tmp_data_array.length > 0 ){ // каждый елемент...
var __item = tmp_data_array.pop(); // запоминаем, вытаскивая из исходного массива
//
if( buffer_data_array.length == 0){ // если нет ни одного буфера...
buffer_data_array[0] = []; // создаем новый
buffer_data_array[0].push(__item); // пихаем в него елемент. предполагается что елемент не больше макс. размера буфера.
buffer_data_array_sizes[0] = __item[1]; // запоминаем размер нового буфера
}else{ // если уже есть буфер
var __commited = false;
for ( j in buffer_data_array ) { // пробегаем по всем буферам, пытаясь засунуть наш елемент...
if( (buffer_data_array_sizes[j] + __item[1]) <= buffer_size ){ // лезит?
buffer_data_array[j].push(__item);
buffer_data_array_sizes[j] += __item[1];
__commited = true;
break;
}
}
if (__commited == false) { // если никуда не лезет -- создаем новый буффер
buffer_data_array.push([]);
buffer_data_array[buffer_data_array.length-1].push(__item);
buffer_data_array_sizes[buffer_data_array.length-1] = __item[1];
}
}
}