Source: IndexBinaryTree.js

"use strict";

/*
name
id
rebuild
state
match
lookup
*/

var Shared = require('./Shared'),
	Path = require('./Path'),
	BinaryTree = require('./BinaryTree'),
	treeInstance = new BinaryTree(),
	btree = function () {};

treeInstance.inOrder('hash');

/**
 * The index class used to instantiate hash map indexes that the database can
 * use to speed up queries on collections and views.
 * @constructor
 */
var IndexBinaryTree = function () {
	this.init.apply(this, arguments);
};

IndexBinaryTree.prototype.init = function (keys, options, collection) {
	this._btree = new (btree.create(2, this.sortAsc))();
	this._size = 0;
	this._id = this._itemKeyHash(keys, keys);

	this.unique(options && options.unique ? options.unique : false);

	if (keys !== undefined) {
		this.keys(keys);
	}

	if (collection !== undefined) {
		this.collection(collection);
	}

	this.name(options && options.name ? options.name : this._id);
};

Shared.addModule('IndexBinaryTree', IndexBinaryTree);
Shared.mixin(IndexBinaryTree.prototype, 'Mixin.ChainReactor');
Shared.mixin(IndexBinaryTree.prototype, 'Mixin.Sorting');

IndexBinaryTree.prototype.id = function () {
	return this._id;
};

IndexBinaryTree.prototype.state = function () {
	return this._state;
};

IndexBinaryTree.prototype.size = function () {
	return this._size;
};

Shared.synthesize(IndexBinaryTree.prototype, 'data');
Shared.synthesize(IndexBinaryTree.prototype, 'name');
Shared.synthesize(IndexBinaryTree.prototype, 'collection');
Shared.synthesize(IndexBinaryTree.prototype, 'type');
Shared.synthesize(IndexBinaryTree.prototype, 'unique');

IndexBinaryTree.prototype.keys = function (val) {
	if (val !== undefined) {
		this._keys = val;

		// Count the keys
		this._keyCount = (new Path()).parse(this._keys).length;
		return this;
	}

	return this._keys;
};

IndexBinaryTree.prototype.rebuild = function () {
	// Do we have a collection?
	if (this._collection) {
		// Get sorted data
		var collection = this._collection.subset({}, {
				$decouple: false,
				$orderBy: this._keys
			}),
			collectionData = collection.find(),
			dataIndex,
			dataCount = collectionData.length;

		// Clear the index data for the index
		this._btree = new (btree.create(2, this.sortAsc))();

		if (this._unique) {
			this._uniqueLookup = {};
		}

		// Loop the collection data
		for (dataIndex = 0; dataIndex < dataCount; dataIndex++) {
			this.insert(collectionData[dataIndex]);
		}
	}

	this._state = {
		name: this._name,
		keys: this._keys,
		indexSize: this._size,
		built: new Date(),
		updated: new Date(),
		ok: true
	};
};

IndexBinaryTree.prototype.insert = function (dataItem, options) {
	var uniqueFlag = this._unique,
		uniqueHash,
		dataItemHash = this._itemKeyHash(dataItem, this._keys),
		keyArr;

	if (uniqueFlag) {
		uniqueHash = this._itemHash(dataItem, this._keys);
		this._uniqueLookup[uniqueHash] = dataItem;
	}

	// We store multiple items that match a key inside an array
	// that is then stored against that key in the tree...

	// Check if item exists for this key already
	keyArr = this._btree.get(dataItemHash);

	// Check if the array exists
	if (keyArr === undefined) {
		// Generate an array for this key first
		keyArr = [];

		// Put the new array into the tree under the key
		this._btree.put(dataItemHash, keyArr);
	}

	// Push the item into the array
	keyArr.push(dataItem);

	this._size++;
};

IndexBinaryTree.prototype.remove = function (dataItem, options) {
	var uniqueFlag = this._unique,
		uniqueHash,
		dataItemHash = this._itemKeyHash(dataItem, this._keys),
		keyArr,
		itemIndex;

	if (uniqueFlag) {
		uniqueHash = this._itemHash(dataItem, this._keys);
		delete this._uniqueLookup[uniqueHash];
	}

	// Try and get the array for the item hash key
	keyArr = this._btree.get(dataItemHash);

	if (keyArr !== undefined) {
		// The key array exits, remove the item from the key array
		itemIndex = keyArr.indexOf(dataItem);

		if (itemIndex > -1) {
			// Check the length of the array
			if (keyArr.length === 1) {
				// This item is the last in the array, just kill the tree entry
				this._btree.del(dataItemHash);
			} else {
				// Remove the item
				keyArr.splice(itemIndex, 1);
			}

			this._size--;
		}
	}
};

IndexBinaryTree.prototype.violation = function (dataItem) {
	// Generate item hash
	var uniqueHash = this._itemHash(dataItem, this._keys);

	// Check if the item breaks the unique constraint
	return Boolean(this._uniqueLookup[uniqueHash]);
};

IndexBinaryTree.prototype.hashViolation = function (uniqueHash) {
	// Check if the item breaks the unique constraint
	return Boolean(this._uniqueLookup[uniqueHash]);
};

IndexBinaryTree.prototype.lookup = function (query) {
	return this._data[this._itemHash(query, this._keys)] || [];
};

IndexBinaryTree.prototype.match = function (query, options) {
	// Check if the passed query has data in the keys our index
	// operates on and if so, is the query sort matching our order
	var pathSolver = new Path();
	var indexKeyArr = pathSolver.parseArr(this._keys),
		queryArr = pathSolver.parseArr(query),
		matchedKeys = [],
		matchedKeyCount = 0,
		i;

	// Loop the query array and check the order of keys against the
	// index key array to see if this index can be used
	for (i = 0; i < indexKeyArr.length; i++) {
		if (queryArr[i] === indexKeyArr[i]) {
			matchedKeyCount++;
			matchedKeys.push(queryArr[i]);
		} else {
			// Query match failed - this is a hash map index so partial key match won't work
			return {
				matchedKeys: [],
				totalKeyCount: queryArr.length,
				score: 0
			};
		}
	}

	return {
		matchedKeys: matchedKeys,
		totalKeyCount: queryArr.length,
		score: matchedKeyCount
	};

	//return pathSolver.countObjectPaths(this._keys, query);
};

IndexBinaryTree.prototype._itemHash = function (item, keys) {
	var path = new Path(),
		pathData,
		hash = '',
		k;

	pathData = path.parse(keys);

	for (k = 0; k < pathData.length; k++) {
		if (hash) { hash += '_'; }
		hash += path.value(item, pathData[k].path).join(':');
	}

	return hash;
};

IndexBinaryTree.prototype._itemKeyHash = function (item, keys) {
	var path = new Path(),
		pathData,
		hash = '',
		k;

	pathData = path.parse(keys);

	for (k = 0; k < pathData.length; k++) {
		if (hash) { hash += '_'; }
		hash += path.keyValue(item, pathData[k].path);
	}

	return hash;
};

IndexBinaryTree.prototype._itemHashArr = function (item, keys) {
	var path = new Path(),
		pathData,
		//hash = '',
		hashArr = [],
		valArr,
		i, k, j;

	pathData = path.parse(keys);

	for (k = 0; k < pathData.length; k++) {
		valArr = path.value(item, pathData[k].path);

		for (i = 0; i < valArr.length; i++) {
			if (k === 0) {
				// Setup the initial hash array
				hashArr.push(valArr[i]);
			} else {
				// Loop the hash array and concat the value to it
				for (j = 0; j < hashArr.length; j++) {
					hashArr[j] = hashArr[j] + '_' + valArr[i];
				}
			}
		}
	}

	return hashArr;
};

Shared.finishModule('IndexBinaryTree');
module.exports = IndexBinaryTree;