indexer.js

define([
	'jquery',
	'underscore',
	'backbone'
], function ($,
             _,
             Backbone) {

	/**
	 * options
	 * @type {string}
	 */

	var itemIdFieldName = 'id'; // поле в котором хранится id одного элемента
	var numberGroupPrefix = '_'; // разделитель для числовых групп
	var maxNumberGroupItemsLength = 3; // максимальное количество уникальных элементов в числовой группе


	/**
	 * костыль для индекса
	 * поля, которые хранят свое значение в разных местах (а должны учитыватся вместе)
	 */

	var magicFields = {
		minPrice:{
			field:'maxPrice',
			type:'min',
			index:[]
		},
		maxPrice:{
			field:'minPrice',
			type:'max',
			index:[]
		}
	};


	var getInserterObjectByKeyString = function(key, parentObject){
		if(!parentObject[key]) parentObject[key] = {};
		return parentObject[key];
	};


	// создает вложенный объект, abcdef = {a:{b:{c:{d:{e:{f:{}}
	var createIndexObjHierarchy = function(key, indexObj, type){

		key = key.toLowerCase();

		if(!indexObj[key]){
			indexObj[key] = {};
			indexObj[key]['type'] = type;
		}

		return indexObj[key];
	};

	// создает числовую группу по значениям
	var createGroupByValue = function(start, end, index, type){

		if(!index[start + numberGroupPrefix + end]){
			index[start + numberGroupPrefix + end] = {
				items:[],
				start:start,
				end:end,
				type:type,
				sorted:false
			}
		}

		return index[start + numberGroupPrefix + end];
	};

	// создает группы для группировки числовых значений
	var createIndexNumberGroups = function(value, indexObj, type){

		var start;
		var end;

		if(_.isEmpty(indexObj.index)){
			start = 0;
			end = value;
			return createGroupByValue(start, end, indexObj.index, type);
		}

		// получаю все существующие числовые группы

		// пытаюсь найти подходящую группу
		for(var g1 in indexObj.index){

			if(value >= indexObj.index[g1].start
				&& value <= indexObj.index[g1].end
				&& indexObj.index[g1].items.length < maxNumberGroupItemsLength){
				indexObj.index[g1].sorted = false;
				return indexObj.index[g1];
			}
		}

		// группа не была найдена, или её размер слишком велик
		// надо проверить размер всех групп
		// найти подходящую (или создать)
		// и вернуть
		for(var g in indexObj.index){


			// группа стала слишком большой, её надо разбить
			if(indexObj.index[g].items.length >= maxNumberGroupItemsLength ){

				// дальше по коду я могу резать группы,
				// поэтому все они должны быть отсортированы
				//if(!indexObj.index[g].sorted){
				//	//indexObj.index[g].sorted = true;
				//}
				// сортировка каждый раз - уменьшает скорость работы
				// надо сделать более интеллектуальное добавление значений, что бы не приходилось всегда сортировать
				if(!indexObj.index[g].sorted){
					indexObj.index[g].items.sort(function(a, b){
						if(a.value > b.value) return 1;
						if(a.value < b.value) return -1;
						return 0;
					});
					indexObj.index[g].sorted = true;
				}

				// теперь надо проверить не состоит ли группа из одинаковых значений
				// если в ней все значения одинаковые - я не могу её разрезать
				var uniq = _.uniq(indexObj.index[g].items, function(item){
					return item.value;
				});

				// нужно резать массив только, если уникальных элементов больше maxNumberGroupItemsLength
				if(uniq.length > maxNumberGroupItemsLength){

					var length = Math.ceil(indexObj.index[g].items.length / 2);

					var items1 = indexObj.index[g].items.slice(0, length);
					var items2 = indexObj.index[g].items.slice(length);

					var firstGroup = createGroupByValue(items1[0].value, items1[items1.length -1].value, indexObj.index, type);
					var secondGroup = createGroupByValue(items2[0].value, items2[items2.length -1].value, indexObj.index, type);

					firstGroup.items = firstGroup.items.concat(items1);
					secondGroup.items = secondGroup.items.concat(items2);

					delete indexObj.index[g];
				}
			}

		}

		// снова пытаюсь найти подходящую группу
		// теперь уже без проверки на максимальное количество элементов
		// т.к. группы были ранее разбиты и если одна из них слишком большая - значит в ней повторения (одинаковые значения)
		// а их я ложу в одну группу даже, если размер превышает допустимый
		for(var g2 in indexObj.index){
			if(value >= indexObj.index[g2].start && value <= indexObj.index[g2].end){
				indexObj.index[g2].sorted = false;
				return indexObj.index[g2];
			}
		}

		// группа для числа не была найдена
		// значит надо расширить одну из существующих групп до текущего числа
		// тоесть имея 2 группы 1-3 и 6-7,  и добавляя число "5" нужно группу 6-7 (именно 6-7 т.к. она ближе)
		// рассширить и сделать вместо 6-7 5-7 (в следующих интерациях эта группа будет наполнена и разбита в случае необходимости)
		// magicData определяет какую группу надо модифицировать
		var magicData = {
			groupName:false,
			create:{
				start:false,
				end:false
			},
			start:false,
			end:false,
			type:'number',
			extType:false,
			diff:false
		};

		var diff;
		var extType;

		for(var group in indexObj.index) {

			var gStart = indexObj.index[group].start;
			var gEnd = indexObj.index[group].end;

			if(gStart > value){
				extType = 1;
				diff = gStart - value;
			}
			if(gEnd < value){
				extType = 2;
				diff = value - gEnd;
			}

			// если разница меньше, чем рассчитанная ранее - записываю инфу
			// переделать используя continue
			if(!magicData.diff || diff < magicData.diff){
				magicData.diff = diff;
				magicData.extType = extType;
				magicData.start = gStart;
				magicData.end = gEnd;
				magicData.groupName = group;
			}
		}

		switch(magicData.extType){
			case 1:
				magicData.create.start = value;
				magicData.create.end = magicData.end;
				break;

			case 2:
				magicData.create.start = magicData.start;
				magicData.create.end = value;
				break;
		}

		var newGroup = createGroupByValue(magicData.create.start, magicData.create.end, indexObj.index, type);
		var cloneItemsOldGroup = indexObj.index[magicData.groupName].items.slice(0);

		delete indexObj.index[magicData.groupName]; // удаляю группу которая не нужна

		newGroup.items = newGroup.items.concat(cloneItemsOldGroup);

		return newGroup;
	};


	// создает группу для индекса сложных значений (из двух полей)
	var createIndexComplexNumberGroups = function(value, valueother, indexObj, typeofValue) {

		//typeofValue  -- тип записываемых данных
		// typeofValue = min/max

		var type = 'number-complex';
		var valueMin = (typeofValue == 'min')? value : valueother;
		var valueMax = (typeofValue == 'min')? valueother : value;

		var start;

		if(_.isEmpty(indexObj.index)){
			start = 0;
			return createGroupByValue(start, valueMax, indexObj.index, 'number-complex');
		}

		// пытаюсь найти подходящую группу
		for(var g1 in indexObj.index){

			if(valueMin >= indexObj.index[g1].start
				&& valueMax <= indexObj.index[g1].end
				&& indexObj.index[g1].items.length < maxNumberGroupItemsLength){

				return indexObj.index[g1];
			}
		}


		// группа не была найдена, или её размер слишком велик
		// надо проверить размер всех групп
		// найти подходящую (или создать)
		// и вернуть
		//for(var g in indexObj.index){
		//
		//
		//	// группа стала слишком большой, её надо разбить
		//	if(indexObj.index[g].items.length >= maxNumberGroupItemsLength ){
		//
		//		// дальше по коду я могу резать группы,
		//		// поэтому все они должны быть отсортированы
		//		//if(!indexObj.index[g].sorted){
		//		//	//indexObj.index[g].sorted = true;
		//		//}
		//		// сортировка каждый раз - уменьшает скорость работы, убрать (сейчас баг поэтому пока оставить)
		//		indexObj.index[g].items.sort(function(a, b){
		//			if(a.value > b.value) return 1;
		//			if(a.value < b.value) return -1;
		//			return 0;
		//		});
		//		indexObj.index[g].sorted = true;
		//
		//
		//		// теперь надо проверить не состоит ли группа из одинаковых значений
		//		// если в ней все значения одинаковые - я не могу её разрезать
		//		var uniq = _.uniq(indexObj.index[g].items, function(item){
		//			return item.value;
		//		});
		//
		//		// нужно резать массив только, если уникальных элементов больше maxNumberGroupItemsLength
		//		if(uniq.length > maxNumberGroupItemsLength){
		//
		//			var length = Math.ceil(indexObj.index[g].items.length / 2);
		//
		//			var items1 = indexObj.index[g].items.slice(0, length);
		//			var items2 = indexObj.index[g].items.slice(length);
		//
		//			var firstGroup = createGroupByValue(items1[0].value, items1[items1.length -1].value, indexObj.index, type);
		//			var secondGroup = createGroupByValue(items2[0].value, items2[items2.length -1].value, indexObj.index, type);
		//
		//			firstGroup.items = firstGroup.items.concat(items1);
		//			secondGroup.items = secondGroup.items.concat(items2);
		//
		//			delete indexObj.index[g];
		//		}
		//	}
		//
		//}

		// снова пытаюсь найти подходящую группу
		// теперь уже без проверки на максимальное количество элементов
		// т.к. группы были ранее разбиты и если одна из них слишком большая - значит в ней повторения (одинаковые значения)
		// а их я ложу в одну группу даже, если размер превышает допустимый
		for(var g2 in indexObj.index){
			if(valueMin >= indexObj.index[g2].start && valueMax <= indexObj.index[g2].end){
				return indexObj.index[g2];
			}
		}

		//// группа для числа не была найдена
		//// значит надо расширить одну из существующих групп до текущего числа
		//// тоесть имея 2 группы 1-3 и 6-7,  и добавляя число "5" нужно группу 6-7 (именно 6-7 т.к. она ближе)
		//// рассширить и сделать вместо 6-7 5-7 (в следующих интерациях эта группа будет наполнена и разбита в случае необходимости)
		//// magicData определяет какую группу надо модифицировать
		var magicData = {
			groupName:false,
			create:{
				start:false,
				end:false
			},
			start:false,
			end:false,
			type:'number',
			extType:false,
			diff:false
		};

		var diff;
		var extType;

		for(var group in indexObj.index) {

			var gStart = indexObj.index[group].start;
			var gEnd = indexObj.index[group].end;

			if(gStart > valueMin){
				extType = 1;
				diff = gStart - valueMin;
			}
			if(gEnd < valueMax){
				extType = 2;
				diff = valueMax - gEnd;
			}

			// если разница меньше, чем рассчитанная ранее - записываю инфу
			// переделать используя continue
			if(!magicData.diff || diff < magicData.diff){
				magicData.diff = diff;
				magicData.extType = extType;
				magicData.start = gStart;
				magicData.end = gEnd;
				magicData.groupName = group;
			}
		}

		switch(magicData.extType){
			case 1:
				magicData.create.start = valueMin;
				magicData.create.end = magicData.end;
				break;

			case 2:
				magicData.create.start = magicData.start;
				magicData.create.end = valueMax;
				break;
		}

		var newGroup = createGroupByValue(magicData.create.start, magicData.create.end, indexObj.index, type);
		var cloneItemsOldGroup = indexObj.index[magicData.groupName].items.slice(0);

		delete indexObj.index[magicData.groupName]; // удаляю группу которая не нужна

		newGroup.items = newGroup.items.concat(cloneItemsOldGroup);

		return newGroup;

	};

	// context -indexer
	var createIndexObjByItem = function(item, indexObj){

		var readyIndexObj = indexObj;

		for(var n in item){

			if(this.fields.ignore.indexOf(n) >= 0) continue;
			if(this.fields.index.length && this.fields.index.indexOf(n) < 0) continue;

			var typeOfValue = typeof item[n];

			var indexItem = createIndexObjHierarchy.call(this, n, readyIndexObj);

			if(!indexItem.index) indexItem.index = {};

			// сохраняю в index значения типа string
			if(typeOfValue == 'string'){
				var indexValue = item[n].split(' ').join('');
				var indexValueItem = createIndexObjHierarchy(indexValue, indexItem.index, 'string');
				if(!indexValueItem.items) indexValueItem.items = [];
				indexValueItem.items.push({id:item[itemIdFieldName], value:item[n]});
				continue;
			}

			if(typeOfValue == 'number'){
				// тут значения должны быть сгруппированы по промежуткам
				// index:{0_100:{start:0,end:5,sorted:false,items:[]},101_200:{start:0,end:5,sorted:false,items:[]}}
				if(!magicFields[n]){
					var indexNumberGroup = createIndexNumberGroups(item[n], indexItem, 'number');
					if(!indexNumberGroup.items) indexNumberGroup.items = [];
					var pushItemNumber = {id:item[itemIdFieldName], value:item[n], key:n};
					indexNumberGroup.items.push(pushItemNumber);
					continue;
				}

				// создаю индекс для "магической группы"
				// значения которая хранит в разных полях
				var indexNumberCompGroup = createIndexComplexNumberGroups(item[n], item[magicFields[n].field], indexItem, magicFields[n].type);
				if(!indexNumberCompGroup.items) indexNumberCompGroup.items = [];
				var pushItemCompNumber = {id:item[itemIdFieldName], value:item[n], key:n};
				pushItemCompNumber.values = {};
				pushItemCompNumber.values[magicFields[n].type] = item[n];
				pushItemCompNumber.values[magicFields[magicFields[n].field].type] = item[magicFields[n].field];
				indexNumberCompGroup.items.push(pushItemCompNumber);
			}

			//todo если в массиве лежат объекты - будет ошибка
			if(_.isArray(item[n])){
				for(var s in item[n]){
					var indexArrValue = item[n][s].split(' ').join('');
					var indexArrValueItem = createIndexObjHierarchy(indexArrValue, indexItem.index, 'array');
					if(!indexArrValueItem.items) indexArrValueItem.items = [];
					indexArrValueItem.items.push({id:item[itemIdFieldName], value:item[n][s]});
				}
				continue;
			}

			//if(item[n] === null){
			//	var indexNullValue = 'null';
			//	var indexNullValueItem = createIndexObjHierarchy(indexNullValue, indexItem.index, 'null');
			//	if(!indexNullValueItem.items) indexNullValueItem.items = [];
			//	indexNullValueItem.items.push({id:item[itemIdFieldName], value:null});
			//	continue;
			//}

			if(typeOfValue === 'boolean'){
				var indexBooleanValue = item[n].toString();
				var indexBooleanValueItem = createIndexObjHierarchy(indexBooleanValue, indexItem.index, 'boolean');
				if(!indexBooleanValueItem.items) indexBooleanValueItem.items = [];
				indexBooleanValueItem.items.push({id:item[itemIdFieldName], value:item[n]});
				continue;
			}

			// TODO if isObject - нужно сделать обработку для объекта

		}

		return readyIndexObj;

	};


	// выбрать элементы по правилу меньше или равно
	var getLessOrEqualItems = function(options, context){

		// контекст public methods

		var out = [];
		var ctx = context; // context cache
		var min;
		var max;

		var index = this.getIndexByKey(options.key);

		for(var i in index){

			// если группа начинается с большего числа, чем мне нужно - continue
			if(index[i].start > options.value) continue;

			// если группа заканчивается на подходящем числе - группа подходит целиком
			if(index[i].end <= options.value){
				out = out.concat(index[i].items);
				continue;
			}

			// подходит лишь часть группы
			if(index[i].start <= options.value){
				var tmpItems;
				tmpItems = _.filter(index[i].items, function(item){
					return (index[i].type !== 'number-complex')
						? item.value <= options.value
						: (item.values.max <= options.value || item.values.min <= options.value);
				});
				if(tmpItems && tmpItems.length){
					out = out.concat(tmpItems);
				}
			}
		}
		var resultItems = _.map(out, function(item){
			return item.id;
		});

		// возвращаю id объектов + данные по выборке
		return {
			items:resultItems,
			min:min,
			max:max
		}

	};

	// выбрать элементы по правилу больше или равно
	var getOverOrEqualItems = function(options, context){

		// контекст public methods

		var out = [];
		var ctx = context; // context cache
		var min;
		var max;

		var index = this.getIndexByKey(options.key);

		for(var i in index){

			// если группа заканчивается с меньшего числа - continue
			if(index[i].end < options.value) continue;

			// если группа начинается на подходящем числе - группа подходит целиком
			if(index[i].start >= options.value){
				out = out.concat(index[i].items);
				continue;
			}

			// подходит лишь часть группы
			if(index[i].end >= options.value){
				var tmpItems;
				tmpItems = _.filter(index[i].items, function(item){
					return (index[i].type !== 'number-complex')
						? item.value >= options.value
						: (item.values.min >= options.value || item.values.max >= options.value);
				});
				if(tmpItems && tmpItems.length){
					out = out.concat(tmpItems);
				}
			}
		}

		var resultItems = _.map(out, function(item){
			return item.id;
		});

		// возвращаю id объектов + данные по выборке
		return {
			items:resultItems,
			min:min,
			max:max
		}
	};


	// получить кеш
	var getCache = function(attrs, options){

		if(!this.cache.length) return false;

		for(var i=0; i<this.cache.length;i++){

			if(this.cache[i].attrs.length !== attrs.length) continue;

			var correct = _.every(this.cache[i].attrs, function(attrItem, num){
				return attrItem.key == attrs[num].key && attrItem.value == attrs[num].value && attrItem.pattern == attrs[num].pattern;
			});

			if(correct) return this.cache[i];
		}

		return false;
	};

	/**
	 * основная функция для выборки элементов (where)
	 * её "smart" заключается вот в чем
	 * (внимание формат реальных данных иной, сделал так для простоты)
	 * если attrs = {a,b,c,d} а в кеше уже есть выборка для {a,b}
	 * то мне нужно выбрать только {c,d} и найти "схождение"
	 *
	 * но, сделаю это потом (сейчас не критично)
	 * @param attrs
	 * @param options
	 */
	var smartPick = function(attrs, options, context){

		//var t = Date.now();

		var result;
		var allIds = [];
		var ctx = context;
		attrs = attrs || [];
		options = options || {};

		//var attrsKeys = [];
		//var cacheCut;

		/**
		 * нахожу самый подходящший подходящий элемент из кеша
		 *
		 */
		//if(ctx.cache.length){
		//
		//	for(var a in attrs){
		//		attrsKeys.push(attrs[a].key + ':' + attrs[a].value);
		//	}
		//
		//	cacheFor:
		//	for(var c in ctx.cache){
		//		for(var b in ctx.cache.attrs){
		//			if(attrsKeys.indexOf(ctx.cache.attrs[b].key + ':' + ctx.cache.attrs[b].value) < 0) {
		//				continue cacheFor;
		//			}
		//		}
		//		if(!cacheCut || cacheCut.attrs.length < ctx.cache[c].attrs.length){
		//			cacheCut = ctx.cache[c];
		//		}
		//	}
		//}

		for(var f in attrs){

			attrs[f].key = attrs[f].key.toLowerCase();
			if(attrs[f].value && typeof attrs[f].value == 'string') attrs[f].value = attrs[f].value.toLowerCase();

			// получаю элементы для каждого ключа pattern "="
			if(!attrs[f].pattern || attrs[f].pattern == '='){
				allIds.push(this.getIndexIdsByKeyValue(attrs[f].key, attrs[f].value));
			}
			//// получаю элементы по паттерная больше/меньше
			//if(attrs[f].pattern &&  attrs[f].pattern == '<'){
			//
			//}
			if(attrs[f].pattern &&  attrs[f].pattern == '<='){
				var lessOrEqualItems = getLessOrEqualItems.call(this, attrs[f], self);
				allIds.push(lessOrEqualItems.items);
			}
			//if(attrs[f].pattern &&  attrs[f].pattern == '>'){
			//
			//}
			if(attrs[f].pattern &&  attrs[f].pattern == '>='){
				var overOrEqualItems = getOverOrEqualItems.call(this, attrs[f], self);
				allIds.push(overOrEqualItems.items);
			}
		}


		allIds = _.compact(allIds);
		result = _.intersection.apply(_, allIds);

		//var e = Date.now();
		//var p = e - t;
		//console.log('!!!! indexer process', p + '.ms');

		return result;
	};

	// сохранить кеш
	var saveCache = function(attrs, options, items){
		this.cache.push({
			items:items,
			attrs:attrs,
			options:options
		});
	};

	/**
	 * Class SortIndexer
	 * @param options
	 * @returns {{indexerClass: Function, getIndex: Function, getIndexByKey: Function, getIndexByKeyValue: Function, getIndexIdsByKeyValue: Function, where: Function, resetIndex: Function}}
	 * @constructor
	 */
	var SortIndexer = function(options){

		var self = this;

		options = options || {};

		this.app = options.app || false;
		this.fields = options.fields || {index:[], ignore:[]};
		this.items = {};
		this.cache = [];
		this.index = {};
		//this.attrs = false;


		var createIndexByItems = function(items, callback){
			for(var o in items){
				createIndexObjByItem.call(this, items[o], this.index);
			}

			if(callback) callback.apply(self);
		};

		return {

			indexerClass:SortIndexer,

			// вернуть index всех ключей
			getIndex:function(){
				return self.index;
			},
			getIndexFields:function(){
				return (self.fields && self.fields.index)? self.fields.index : false;
			},
			getLastQueryAttributes:function(){
				return this.attrs;
			},

			// вернуть объект index по ключу
			getIndexByKey:function(key){
				key = key.toLowerCase();
				var obj = getInserterObjectByKeyString(key, this.getIndex.apply(this));
				return (obj && obj.index)? obj.index : false;
			},

			getIndexByKeyValue:function(key, value){
				key = key.toLowerCase();
				if(value && typeof value == 'string') value = value.toLowerCase();

				var obj = getInserterObjectByKeyString(key, this.getIndex.apply(this));
				if(!obj || !obj.index) return false;

				var out = getInserterObjectByKeyString(value, obj.index);
				return (out && out.items)? out.items : false;
			},

			getIndexIdsByKeyValue:function(key, value){

				key = key.toLowerCase();
				if(value && typeof value == 'string') value = value.toLowerCase();

				var items = this.getIndexByKeyValue(key, value);

				if(items){
					return _.map(items, function(item){
						return item.id;
					});
				}
				return false;
			},

			// получить список id по входящим атрибутам
			where: function(attrs, options){

				this.attrs = attrs;

				options = options || {};
				var result;

				result = getCache.call(self, attrs, options);
				if(result){
					return result.items;
				}

				result = smartPick.call(this, attrs, options, self);
				saveCache.call(self, attrs, options, result);
				return result;
			},

			// обновить index
			resetIndex:function(items, callback){

				self.cache = []; // киляю кеш
				self.index = {}; // киляю индекс
				self.items = items; // киляю элементы
				this.attrs = false; // киляю текущие атрибуты выборки
				// все по килял - можно сделать новый индекс
				createIndexByItems.call(self, items, callback);
			}
		}

	};

	return SortIndexer;

});