define(function(){
// Асинхронные функции
var Async = {};
// Асинхронный цикл For
function asyncFor (parameters) {
parameters = parameters || {}; // Параметры цикла
parameters.initializationParameters = parameters.initializationParameters || {}; // Начальные значения счетчиков цикла
parameters.testConditionFunction = parameters.testConditionFunction || function () {return true;}; // Условие выхода из цикла
parameters.incrementFunction = parameters.incrementFunction || function () {}; // Приращение счетчиков цикла
parameters.bodyStatementFunction = parameters.bodyStatementFunction || function () {}; // Тело цикла
parameters.doneFunction = parameters.doneFunction || function () {}; // Функция, выполняющаяся после завершения цикла
parameters.breakFunction = function () {}; // Функция, выполняющаясь при прерывания цикла
parameters.continueFunction = function () {}; // Функция, выполняющаясь при перепрыгивании на следующий шаг цикла
parameters.break = function (labelFunction) { // Определение типа перепрыгивания на следующий шаг цикла
if (labelFunction === undefined) {
return 'break';
} else {
parameters.breakFunction = labelFunction;
return 'break label';
}
};
parameters.continue = function (labelFunction) { // Определение типа прерывания цикла
if (labelFunction === undefined) {
return 'continue';
} else {
parameters.continueFunction = labelFunction;
return 'continue label';
}
};
parameters.counter = 0; // Счетчик числа выполненных шагов цикла
parameters.nextIterationStep = function () { // Выполнить шаг цикла
if (parameters.counter > 0) {
parameters.incrementFunction(parameters); // Произвести приращение счетчиков цикла при выполнении следующего шага
}
parameters.counter++;
if (parameters.testConditionFunction(parameters)) { // Проверить тестовое условие цикла
setTimeout(function(){
var breakOrContinueAsyncFor = parameters.bodyStatementFunction(parameters); // Выполнить тело цикла
if (breakOrContinueAsyncFor === 'break') { // Завершить цикл
parameters.doneFunction(parameters);
} else if (breakOrContinueAsyncFor === 'break label') { // Прервать цикл и выполнить функцию, в которой описан переход во внешний цикл
parameters.breakFunction(parameters);
} else if (breakOrContinueAsyncFor === 'continue') { // Перепрыгнуть на следующий шаг цикла
parameters.nextIterationStep();
} else if (breakOrContinueAsyncFor === 'continue label') { // Выполнить функцию, в которой описан переход во внешний цикл
parameters.continueFunction(parameters);
}
}, 0); // В общем случае для выполнения маленьких задержек рекомендуется использовать значение не менее 25 мс,
// потому что меньшие задержки оставляют слишком короткие интервалы времени для обновления пользовательского интерфейса.
// Однако для ускорения выполнения цикла оставлена задержка 0 мс.
} else {
parameters.doneFunction(parameters); // Выполнить завершающую функцию в конце работы цикла
}
};
parameters.nextIterationStep(); // Выполнить проверку тестового условия цикла и сделать первый шаг
}
/*= Примеры кода асинхронных циклов asyncFor =*\
// Одиночный асинхронный цикл
asyncFor ({
initializationParameters: {i: 0}
, testConditionFunction: function (asyncForLoop) {
if (asyncForLoop.initializationParameters.i < 10) {return true;} else {return false;}
}
, incrementFunction: function (asyncForLoop) {
asyncForLoop.initializationParameters.i = asyncForLoop.initializationParameters.i + 1;
}
, bodyStatementFunction: function (asyncForLoop) {
console.log(asyncForLoop.initializationParameters.i);
asyncForLoop.nextIterationStep(); // Переход на следующий шаг цикла
}
, doneFunction: function (asyncForLoop) {
console.log('The End. Last index: ' + asyncForLoop.initializationParameters.i);
}
});
// Вложенные асинхронные циклы
// Внешний цикл - начало
asyncFor ({
initializationParameters: {i: 0}
, testConditionFunction: function (outerLoop) {
if (outerLoop.initializationParameters.i < 2) {return true;} else {return false;}
}
, incrementFunction: function (outerLoop) {
outerLoop.initializationParameters.i = outerLoop.initializationParameters.i + 1;
}
, bodyStatementFunction: function (outerLoop) {
// Внутренний цикл - начало
asyncFor ({
initializationParameters: {j: 0}
, testConditionFunction: function (innerLoop) {
if (innerLoop.initializationParameters.j < 2) {return true;} else {return false;}
}
, incrementFunction: function (innerLoop) {
innerLoop.initializationParameters.j = innerLoop.initializationParameters.j + 1;
}
, bodyStatementFunction: function (innerLoop) {
console.log(outerLoop.initializationParameters.i + ' ' + innerLoop.initializationParameters.j);
innerLoop.nextIterationStep(); // Переход на следующий шаг внутреннего цикла
}
, doneFunction: function (innerLoop) {
outerLoop.nextIterationStep(); // После завершения внутреннего цикла осуществляется переход на следующий шаг внешнего цикла
}
});
// Внутренний цикл - конец
}
, doneFunction: function (outerLoop) {
console.log('All cycles done');
}
});
// Внешний цикл - конец
// Прерывание одиночного асинхронного цикла
asyncFor ({
initializationParameters: {i: 0}
, testConditionFunction: function (asyncForLoop) {
if (asyncForLoop.initializationParameters.i < 10) {return true;} else {return false;}
}
, incrementFunction: function (asyncForLoop) {
asyncForLoop.initializationParameters.i = asyncForLoop.initializationParameters.i + 1;
}
, bodyStatementFunction: function (asyncForLoop) {
if (asyncForLoop.initializationParameters.i === 3) {
// Перепрыгивание на следующий шаг цикла
return asyncForLoop.continue(
// Если в качестве метки label будет передана функция, то будет выполнен её код
// function(asyncForLoop) {
// console.log('Continue label. Current index: ' + asyncForLoop.initializationParameters.i);
// asyncForLoop.doneFunction(asyncForLoop); // В результате перепрыгивания шага можно просто завершить выполнение цикла
// }
);
}
if (asyncForLoop.initializationParameters.i === 5) {
// Прерывание цикла
return asyncForLoop.break(
// function(asyncForLoop) {
// console.log('Break label. Current index: ' + asyncForLoop.initializationParameters.i);
// asyncForLoop.doneFunction(asyncForLoop); // В результате прерывания цикла можно просто завершить выполнение цикла
// }
);
}
console.log(asyncForLoop.initializationParameters.i);
asyncForLoop.nextIterationStep(); // Обычный переход на следующий шаг цикла
}
, doneFunction: function (asyncForLoop) {
console.log('The End. Last index: ' + asyncForLoop.initializationParameters.i);
}
});
// Прерывание вложенных асинхронных циклов
// Внешний цикл - начало
asyncFor ({
initializationParameters: {i: 0}
, testConditionFunction: function (outerLoop) {
if (outerLoop.initializationParameters.i < 5) {return true;} else {return false;}
}
, incrementFunction: function (outerLoop) {
outerLoop.initializationParameters.i = outerLoop.initializationParameters.i + 1;
}
, bodyStatementFunction: function (outerLoop) {
// Внутренний цикл - начало
asyncFor ({
initializationParameters: {j: 0}
, testConditionFunction: function (innerLoop) {
if (innerLoop.initializationParameters.j < 5) {return true;} else {return false;}
}
, incrementFunction: function (innerLoop) {
innerLoop.initializationParameters.j = innerLoop.initializationParameters.j + 1;
}
, bodyStatementFunction: function (innerLoop) {
if (innerLoop.initializationParameters.j === 2) {
// Перепрыгивание на следующий шаг цикла
return innerLoop.continue(
// Если в качестве метки label будет передана функция, то будет выполнен её код
// function(outerLoop){
// console.log('Continue label. Current index: ' + innerLoop.initializationParameters.j);
// innerLoop.doneFunction(); // В результате перепрыгивания шага можно просто завершить выполнение внутреннего цикла
// }
);
}
if (innerLoop.initializationParameters.j === 2) {
// Прерывание цикла
return innerLoop.break(
// function(innerLoop){
// console.log('Break label. Current index: ' + innerLoop.initializationParameters.j);
// outerLoop.doneFunction(outerLoop); // В результате прерывания цикла можно просто завершить выполнение внешнего цикла
// }
);
}
console.log(outerLoop.initializationParameters.i + ' ' + innerLoop.initializationParameters.j);
innerLoop.nextIterationStep(); // Обычный переход на следующий шаг внутреннего цикла
}
, doneFunction: function (innerLoop) {
outerLoop.nextIterationStep(); // После завершения внутреннего цикла осуществляется переход на следующий шаг внешнего цикла
}
});
// Внутренний цикл - конец
}
, doneFunction: function (outerLoop) {
console.log('All cycles done');
}
});
// Внешний цикл - конец
\*================================ */
// Асинхронный цикл forEach
function asyncForEachInArray (array, process, callback) {
if (array.length === 0) {
callback(array);
return;
}
var tempArray = array.slice()
, currentTempArrayIndex = 0
, breakProcess;
function startIterationProcess () {
var startTime = +new Date();
do {
breakProcess = process(tempArray.shift(), currentTempArrayIndex);
if (breakProcess === 'break') {
tempArray.length = 0;
} else {
currentTempArrayIndex++;
}
} while (
tempArray.length > 0
&& ((+new Date() - startTime) < 50) // Установить таймаут, если цикл выполняется дольше 50 мс
);
if (tempArray.length > 0) {
setTimeout(startIterationProcess, 0); // В общем случае для выполнения маленьких задержек рекомендуется использовать значение не менее 25 мс,
// потому что меньшие задержки оставляют слишком короткие интервалы времени для обновления пользовательского интерфейса.
} else {
callback(array);
}
}
startIterationProcess();
}
/*= Пример кода асинхронного цикла asyncForEachInArray =*\
var array = new Array(5000);
asyncForEachInArray (
array
, function (item, index) {
array[index] = item + '-' + index;
if (index === 2000) {
// Прервать выполнение итераций
return 'break';
}
}
, function (array) {
console.log('All done');
console.log(array);
}
);
\*====================================== */
/*= Описание алгоритма сортировки массивов =*\
Алгоритм сортировки массивов merge sort используют браузеры Firefox и Safari в своей реализации Array.prototype.sort()
Алгоритм merge sort быстр в работе и легок в реализации.
Он базируется на идее, что легче сравнить и слить два уже отсортированных списка,
нежели разбираться с одним несортированным списком.
Реализация алгоритма merge sort начинается с создания некоторого числа N одноэлементных массивов,
где N - общее число элементов в оригинальном массиве, который требуется отсортировать.
Затем эти одноэлементные массивы объединяются обратно в единый отсортированный массив.
Сравнение и слияние двух уже отсортированных списков представляет собой довольной простой алгоритм.
Представим, что у нас есть два списка: список A и список B.
Мы начинаем с самого начала каждого списка и сравниваем два их значения.
Меньшее из двух сравниваемых значений вставляется в итоговый массив.
Пусть к примеру меньшим окажется значение из списка A, тогда это значение будет помещено в итоговый массив.
Далее второе значение из списка A сравнивается с первым значением из списка B.
Снова меньшее из двух значений вставляется в итоговый массив.
Теперь для примера меньшим пусть будет число из списка B, тогда на следующем шаге будут сравниваться второй элемент из
списка A и второй элемент из списка B.
Код такого сравнения будет следующим:
function merge (leftArray, rightArray) {
var resultArray = []
, leftArrayLength = leftArray.length
, rightArrayLength = rightArray.length
, indexLeft = 0,
, indexRight = 0;
while (
indexLeft < leftArrayLength
&& indexRight < rightArrayLength
) {
if (leftArray[indexLeft] < rightArray[indexRight]) {
result.push(leftArray[indexLeft]);
indexLeft++;
} else {
result.push(rightArray[indexRight]);
indexRight++;
}
}
return resultArray.concat(leftArray.slice(indexLeft)).concat(rightArray.slice(indexRight));
}
В приведенной выше функции сравнивается и сливается два массива: левый и правый.
Переменная indexLeft хранит в себе индекс сравниваемого элемента из списка leftArray,
в то время как переменная indexRight хранит в себе индекс сравниваемого элемента из списка rightArray.
Кажлый раз, когда значение из одного массива добавляется в итоговый массив,
его соотвествующий индекс элемента увеличивается на единицу.
Как только один из массивов закончится, то оставшиеся значания будут добавлены в конец итогового массива
посредством операции concat().
Функция merge() работает просто, но теперь необходимо объединить два отсортированных списка.
Как было замечено ранее, это делается путем разделения массива на несколько одноэлементных массивов,
которые затем объединяются в списки.
Это можно легко сделать, применив рекурсию:
function mergeSort (array) {
var arrayLength = array.length;
// Условие выхода из функции
// Если число элементов в сортируемом массиве 0 или 1, то такой массив не требует сортировки
if (arrayLength < 2) {
return array;
}
var middle = Math.floor(arrayLength / 2) // определяем середину исходного массива
, leftArray = items.slice(0, middle) // левая половина исходного массива
, rightArray = items.slice(middle); // правая половина исходного массива
return merge(mergeSort(leftArray), mergeSort(rightArray)); // Рекурсивно сравниваем и сливаем два массива,
// периодически разделяя их пополам на более мелкие составляющие
}
Сперва стоит отметить, что если в сортируемом массивке 0 или 1 элемент, то такой массив не требует сортировки.
Если массив содержит в себе 2 или более значений, то он разделяется пополам на левый и правый массивы.
Каждый из этих массивов затем опять разделяется пополам, помещаясь обратно в функцию mergeSort(), после завершения которой
результат помещается в функцию merge(), где происходит сравнение и слияние двух маленьких массивов с
последующим помещением их в итоговый отсортированный массив.
Таким образом сортируется сначала левая половина массива, а затем сортируется правая часть массива,
после чего итоговые результаты сравниваются и объединяются.
Благодаря рекурсии вы в конечно итоге доходите до точки, где два одноэлементных массива сравниваются и сливаются в итоговы массив.
Имплементация алгоритма merge sort возвращает другой массив, отличающийся от того, который был передан для сортировки,
то есть это не сортировка массива на месте. Если вам требуется отсортировать исходный массив на месте,
то в этом случае вы можете очистить оригинальный массив и заполнить его отсортированным содержимым следующим образом:
function mergeSort (array) {
var arrayLength = array.length;
// Условие выхода из функции
// Если число элементов в сортируемом массиве 0 или 1, то такой массив не требует сортировки
if (arrayLength < 2) {
return array;
}
var middle = Math.floor(arrayLength / 2) // определяем середину исходного массива
, leftArray = array.slice(0, middle) // левая половина исходного массива
, rightArray = array.slice(middle) // правая половина исходного массива
, params = merge(mergeSort(leftArray), mergeSort(rightArray));
// Добавляем аргументы для замены всего, начиная с 0 и до последнего элемента в массиве
params.unshift(0, arrayLength);
array.splice.apply(array, params);
return array;
}
Эта версия функции mergeSort() хранит результат сортировки в переменной params.
Самый лучший способ заменить элементы в массиве - это использовать метод splice(), который принимает два и более аргументов.
Первый аргумент - это индекс первого заменяемого значения, а второй аргумент - это число элементов, которые надо заменить.
Каждый последующий аргумент - это значение, которое надо вставить на соотвествующщую позицию.
Посокольку нет способа передать значения в метод splice(), то необходимо использовать метод apply(),
в который передать первые два аргумента объединенные с отсортированным массивом.
Таким образом 0 и array.length добавляются в начало массива, используя метод unshift() так,
что apply() может быть использован совместно со splice().
После этого исходный массив возвращается из функции.
// Функция arrayMergeSort сортирует массив синхронно
// По умолчанию сортировка производится по возрастанию
// Параметр array - массив требующий сортировки
// Необязательный параметр compareFunction - функция, задающая порядок сравнения элементов массива
// Функция compareFunction должна возвращать:
// 1 - если первый сравниваемый элемент массива больше второго сравниваемого элемента
// -1 - если первый сравниваемый элемент массива меньше второго сравниваемого элемента
// 0 - если сравниваемые элементы массива равны друг другу
// Функция возвращает отсортированный массив
function arrayMergeSort (array, compareFunction) {
// для примера array = [5, 4, 6]
var work = []
, arrayLength = array.length // для примера arrayLength = 3
, limit
, i
, j
, k;
// Для массивов с числом элементов 0 или 1 сортировка не требуется
if (arrayLength < 2) {return array;}
// Фомируем массив, состоящий из одноэлементных массивов, для примера work = [[5], [4], [6]]
for (i = 0; i < arrayLength; i++){
work.push([array[i]]);
}
work.push([]); // на случай, если в массиве нечетное число элементов work = [[5], [4], [6], []]
// для примера изначально limit = 3, на каждом шаге цикла limit = Math.floor( (3 + 1) / 2 )), поскольку мы добавили пустой массив []
for (limit = arrayLength; limit > 1; limit = Math.floor( (limit + 1) / 2 )) {
for (j = 0, k = 0; k < limit; j++, k += 2) {
work[j] = merge(work[k], work[k + 1], compareFunction);
}
work[j] = []; // на случай, если в массиве нечетное число элементов
}
return work[0];
}
\*============================== */
// Асинхронная сортировка массивов sort
function asyncArraySort (array, callback, compareFunction) {
// для примера array = [5, 4, 6]
var work = []
, arrayLength = array.length; // для примера arrayLength = 3
// Для массивов с числом элементов 0 или 1 сортировка не требуется
if (arrayLength < 2) {return array;}
if (callback === undefined) {
callback = function(){};
}
// Асинхронно фомируем массив, состоящий из одноэлементных массивов, для примера work = [[5], [4], [6]]
asyncForEachInArray(array, addElementsToWorkArray, startMergeProcess);
function addElementsToWorkArray (item) {
work.push([item]);
}
function startMergeProcess () {
work.push([]); // на случай, если в массиве нечетное число элементов work = [[5], [4], [6], []]
// для примера изначально limit = 3, на каждом шаге цикла limit = Math.floor( (3 + 1) / 2 )), поскольку мы добавили пустой массив []
var limit = arrayLength;
asyncFor ({
initializationParameters: {limit: limit}
, testConditionFunction: function (outerLoop) {
if (outerLoop.initializationParameters.limit > 1) {return true;} else {return false;}
}
, incrementFunction: function (outerLoop) {
outerLoop.initializationParameters.limit = Math.floor( (outerLoop.initializationParameters.limit + 1) / 2 );
}
, bodyStatementFunction: function (outerLoop) {
asyncFor ({
initializationParameters: {j: 0, k: 0}
, testConditionFunction: function (innerLoop) {
if (innerLoop.initializationParameters.k < outerLoop.initializationParameters.limit) {return true;} else {return false;}
}
, incrementFunction: function (innerLoop) {
innerLoop.initializationParameters.j = innerLoop.initializationParameters.j + 1;
innerLoop.initializationParameters.k = innerLoop.initializationParameters.k + 2;
}
, bodyStatementFunction: function (innerLoop) {
work[innerLoop.initializationParameters.j] = merge(work[innerLoop.initializationParameters.k], work[innerLoop.initializationParameters.k + 1], compareFunction);
innerLoop.nextIterationStep(); // Переход на следующий шаг внутреннего цикла
}
, doneFunction: function (innerLoop) {
work[innerLoop.initializationParameters.j] = []; // на случай, если в массиве нечетное число элементов
outerLoop.nextIterationStep(); // Переход на следующий шаг внешнего цикла
}
});
}
, doneFunction: function () { // Завершение внешнего цикла
callback(work[0]); // Возвращение отсортированного массива
}
});
}
}
// Функция merge производит сравнение и слияние двух массивов по естесвенному порядку расположения чисел и строк в них
// Параметр leftArray - первый массив для сравнение и слияния
// Параметр rightArray - второй массив для сравнение и слияния
// Необязательный параметр compareFunction - функция, задающая порядок сравнения элементов массива
// Функция compareFunction должна возвращать:
// 1 - если первый сравниваемый элемент массива больше второго сравниваемого элемента
// -1 - если первый сравниваемый элемент массива меньше второго сравниваемого элемента
// 0 - если сравниваемые элементы массива равны друг другу
// Функция возвращает слитый массив
function merge (leftArray, rightArray, compareFunction) {
var resultArray = [];
if (compareFunction === undefined) {
compareFunction = function (a, b) {
if (a > b) {
return 1;
} else if (a < b) {
return -1;
} else if (a === b) {
return 0;
}
};
}
while (leftArray.length > 0 && rightArray.length > 0) {
if (compareFunction(leftArray[0], rightArray[0]) === -1) {
resultArray.push(leftArray.shift());
} else {
resultArray.push(rightArray.shift());
}
}
resultArray = resultArray.concat(leftArray).concat(rightArray);
// Убедимся, что оставшиеся массивы пусты
leftArray.splice(0, leftArray.length);
rightArray.splice(0, rightArray.length);
return resultArray;
}
/*= Примеры кода асинхронной сортировки массива asyncArraySort =*\
// Асинхронная сортировка обычного массива
var array = []
, len = 999;
for (;len--;) {
array.push(len);
}
asyncArraySort(
array
, function(result){
array = result;
console.log(array);
}
);
// Асинхронная сортировка массива, содержащего объекты, по убыванию
var array = [
{n: 5}
, {n: 4}
, {n: 1}
, {n: 3}
, {n: 2}
];
asyncArraySort(
array
, function(result){
array = result;
console.dir(array);
}
, function (a, b) {
if (a.n < b.n) {
return 1;
} else if (a.n > b.n) {
return -1;
} else if (a.n === b.n) {
return 0;
}
}
);
\*=========================================== */
Async.asyncFor = asyncFor;
Async.asyncForEachInArray = asyncForEachInArray;
Async.asyncArraySort = asyncArraySort;
return Async;
});
Комментариев нет:
Отправить комментарий