/*
 * Sortable CONtainer Elements.
 *
 * Summary:
 *
 *   Functions for adding and removing html fragments from html elements,
 *   associating object data with elements, and optionally establishing and
 *   maintaining a sort order for elements. Particulary useful with tmpl.js.
 *
 * Justification for existence: (i.e. why not just use the DOM + innerHTML?)
 *
 *  * Capable of working around (some of) IE's innerHTML restrictions and so
 *    can be used to efficiently sort and modify rows within a table body.
 *
 *  * An item can consist of multiple elements; this is particularly useful
 *    in tables. There's no need for each element to have an id, either.
 *
 *  * Being able to associate objects with items relieves the programmer of
 *    the need to maintain separate hash tables all over the place.
 *
 *  * Has special support for nested containers; scone_cut() + scone_paste()
 *    allows the representation of an object to be re-generated without the
 *    need to re-generate all of its (potentially complex) child elements.
 *
 *  * If used with tmpl.js, allows HTML supplied by 3rd-party designers to
 *    be made dynamic with very few modifications (unlike re-writing it all
 *    as JS DOM calls!).
 *
 */

// ensure CVS revision number survives minification
var dummy = '$Id: scone.js,v 1.1.6.3 2010-03-26 17:18:19 cmontoya Exp $';

/* -------- Private static variables. ------ */

var _scones            = {};
var _scone_for         = {};
var _scone_dummy_elem  = null;


/* -------- Public functions. -------- */


// Create a scone backed by an HTML element.
//
// The HTML element can be almost any element APART from:
//   TABLE : Explictly define a TBODY with an id and use that instead.
//
// Params:
//   sconeElemId = The "id" attribute of existing HTML element.
//   info        = Arbitrary information which the caller wants to associate
//                 with the scone. Retrieve with scone_get_info().
//   cmpFn       = Function when sorting to compare object representations of
//                 items. If cmpFn is null, items are always added at the end
//                 of the scone and scone_sort() has no effect.
//   cmpMode     = Passed as first argument to cmpFn. Typically used to control
//                 the type of sorting performed.
//
// Notes:
//   * Any existing contents of the HTML element given by sconeElemId will be
//     deleted.
//   * The cmpFn must have signature f(cmpMode, itemObjA, itemObjB) and return
//     -1, 0 or +1 for A < B, A == B and A > B respectively.
//
// Returns sconeElemId, or throws an error if the scone could not be created.
//
function scone_create(sconeElemId, info, cmpFn, cmpMode) {

	if (_scones[sconeElemId] != undefined) {
			throw("Scone \"" + sconeElemId + "\" already exists.");
	}

	var scone_elem = document.getElementById(sconeElemId);
	if (!scone_elem) {
			throw("Element \"" + sconeElemId + "\" not found.");
	}

	var elem_type = scone_elem.nodeName.toLowerCase();
	if (elem_type == "table") {
			throw("Element \"" + sconeElemId + "\" cannot be used since it is a " +
			       elem_type + "; use a tbody instead.");
	}

	while (scone_elem.lastChild) {
		scone_elem.removeChild(scone_elem.lastChild);
	}

	var scone = {
			info:               info,
			cmpFn:              cmpFn,
			cmpMode:            cmpMode,
			elemType:           elem_type,
			parentSconeItemId:  null,
			items:              [],
			itemIdHash:         {}
	};

	// Check if this scone is an item in another scone, or if it has been created
	// within an item of another scone.

	var elem = scone_elem;
	var pscone_id      = null;
	var pscone_item_id = null;
	while (elem) {
			if (elem.id) {
				if (_scone_for[elem.id] != undefined) {
					pscone_id      = _scone_for[elem.id];
					pscone_item_id = elem.id;
					break;
				}
			}
			elem = elem.parentNode;
	}
	if (pscone_item_id) {
			scone.parentSconeItemId = pscone_item_id;
			var pitem = _scones[pscone_id].itemIdHash[pscone_item_id];
			// mark our scone as a child of the parent item
			pitem.childSconeIdHash[sconeElemId] = true;
	}

	_scones[sconeElemId] = scone;
	return sconeElemId;
}


// Does a scone exist?
function scone_exists(sconeElemId) {
	return (_scones[sconeElemId] != undefined);
}


// Get the info object associated with a scone, or null if the scone
// does not exist.
function scone_get_info(sconeElemId) {
	var scone = _scones[sconeElemId];
	if (scone == undefined) {
			return null;
	}
	return scone.info;
}


// Add a new child item to a scone.
//
// Params:
//  itemElemId = The id attribute of the "main" element for this item.
//  html       = The HTML representation of the item. Must contain an element
//               with the id given by itemElemId (doesn't matter where).
//  info       = The object to associate with the item (used for sorting).
//  noOrder    = If true, the item will be added to the end of the scone.
//               Otherwise, the item will be inserted as determined by using
//               the scone's cmpFn and cmpMode to compare the info with that
//               of the existing items.
//
// Returns itemElemId, or throws an error if the item could not be added.
//
// Notes:
//   * Text nodes (and comments) at the top level of the HTML will be
//     discarded. If you want to insert straight text, use e.g. a <span>.
//   * The top-level elements in the HTML must be suitable for insertion into
//     the element backing the scone (e.g. rows for a tbody scone).
//   * An item with the given id must not already exist in any scone.
//   * The id atrributes of elements in the html must not already exist in the
//     document (this error may not always be detected by this function).
//   * The HTML must not contain any existing scones (corrolary of previous
//     rule really).
//   * If the scone's cmpFn is null, noOrder will be ignored.
//
function scone_add_item(sconeElemId, itemElemId, html, info, noOrder) {

	// Locate scone.

	var scone = _scones[sconeElemId];
	if (scone == undefined) {
			throw("No such scone \"" + sconeElemId + "\"");
	}
	var scone_elem = document.getElementById(sconeElemId);
	if (!scone_elem) {
			throw("Element \"" + sconeElemId + "\" not found.");
	}

	// Duplicate check.

	if (document.getElementById(itemElemId)) {
			throw("Item with id \"" + itemElemId +
			      "\" already exists in the document.");
	}
	if (_scone_for[itemElemId] != undefined) {
			throw("Item with id \"" + itemElemId +
			      "\" already exists in \"" + _scone_for[itemElemId] + "\"");
	}

	// Determine insert position.

	var idx;
	if (noOrder || scone.cmpFn == null) {
			idx = scone.items.length;
	} else {
			idx = _scone_find_ipos(scone, info);
	}

	var before_elem;
	if (idx == scone.items.length) {
			before_elem = null;
	} else {
			before_elem = _scone_first_item_elem(scone.items[idx]);
	}

	// Add HTML to a dummy element.

	if (!_scone_dummy_elem) {
			_scone_dummy_elem = document.createElement("div");
	}
	var holder_elem = null;
	var e = "unknown";
	try {
			if (scone.elemType == "tbody") {
				_scone_dummy_elem.innerHTML =
				  "<table><tbody>"
				  + html + "</tbody></table>";
				holder_elem = _scone_dummy_elem.getElementsByTagName("tbody")[0];
			} else if (scone.elemType == "tr") {
				_scone_dummy_elem.innerHTML =
				  "<table><tbody><tr>"
				  + html + "</tr></tbody></table>";
				holder_elem = _scone_dummy_elem.getElementsByTagName("tr")[0];
			} else {
				_scone_dummy_elem.innerHTML = html;
				holder_elem = _scone_dummy_elem;
			}
	} catch (e) {
	}
	if (!holder_elem) {
			throw("Failed to add \"" + html + "\" to \"" + sconeElemId + "\"" +
			      " due to: " + e);
	}

	// Copy elements to correct position.

	var num_elems = 0;
	var first_elem = null;
	var new_elem = holder_elem.firstChild;
	while (new_elem) {
			var next_elem = new_elem.nextSibling;
			holder_elem.removeChild(new_elem);
			if (new_elem.nodeType == 1) {
				scone_elem.insertBefore(new_elem, before_elem);
				num_elems++;
				if (!first_elem) {
					first_elem = new_elem;
				}
			}
			new_elem = next_elem;
	}

	_scone_dummy_elem.innerHTML = "";

	// Check id of main element in item now present.

	var item_elem = document.getElementById(itemElemId);
	if (!item_elem) {
			// If not, rollback addition of elements.
			var j = 0;
			if (before_elem) {
				while (before_elem.previousSibling && j < num_elems) {
					if (before_elem.previousSibling.nodeType == 1) {
						j++;
					}
					scone_elem.removeChild(before_elem.previousSibling);
				}
			} else {
				while (scone_elem.lastChild && j < num_elems) {
					if (scone_elem.lastChild.nodeType == 1) {
						j++;
					}
					scone_elem.removeChild(scone_elem.lastChild);
				}
			}
			throw("Element with id \"" + itemElemId + "\" not found in \"" +
			      html + "\", or html is invalid.");
	}

	// Determine position of first top-level element of the item relative to
	// the main element within the item (i.e. the one with the id).

	var elem = item_elem.parentNode;
	var top_elem_above = item_elem;
	var offset_up = 0;
	while (elem && elem != scone_elem) {
			top_elem_above = elem;
			elem = elem.parentNode;
			offset_up++;
	}
	var elem = first_elem;
	var offset_left = 0;
	while (elem && elem != top_elem_above) {
			if (elem.nodeType == 1) {
				offset_left++;
			}
			elem = elem.nextSibling;
	}

	// Store details about the item in hashes / arrays.

	var item = {
			id               : itemElemId,
			info             : info,
			offsetLeft       : offset_left,
			offsetUp         : offset_up,
			numElems         : num_elems,
			childSconeIdHash : {}
	};

	scone.items.splice(idx, 0, item);
	scone.itemIdHash[itemElemId] = item;
	_scone_for[itemElemId] = sconeElemId;

	return itemElemId;
}


// Get the ids of the items in a scone.
function scone_get_items(sconeElemId) {
	var scone = _scones[sconeElemId];
	if (scone == undefined) {
			throw("No such scone \"" + sconeElemId + "\"");
	}
	var itemElemIds = new Array(scone.items.length);
	for (var i = 0; i < scone.items.length; i++) {
			itemElemIds[i] = scone.items[i].id;
	}
	return itemElemIds;
}


// Does an item exist in any scone?
function scone_item_exists(itemElemId) {
	return _scone_for[itemElemId] != undefined;
}


// Get the info object for a child item in a scone, or null if there
// is no such item in any scone.
function scone_get_item_info(itemElemId) {
	var sconeElemId = _scone_for[itemElemId];
	if (!sconeElemId) {
			return null;
	}
	var scone = _scones[sconeElemId];
	if (scone == undefined) {
			return null;
	}
	if (scone.itemIdHash[itemElemId] == undefined) {
			return null;
	}
	return scone.itemIdHash[itemElemId].info;
}


// Returns the id of the scone to which a child item with the given id
// belongs, or null if the item has not been added to a scone.
function scone_get_item_owner(itemElemId) {
	return _scone_for[itemElemId] ? _scone_for[itemElemId] : null;
}


// Get array of any child scones within an item.
function scone_get_item_children(itemElemId) {

	var child_scone_ids = [];

	var sconeElemId = _scone_for[itemElemId];
	if (!sconeElemId) {
			return child_scone_ids;
	}
	var scone = _scones[sconeElemId];
	if (scone == undefined) {
			return child_scone_ids;
	}
	var item = scone.itemIdHash[itemElemId];
	if (item == undefined) {
			return child_scone_ids;
	}

	for (var childSconeId in item.childSconeIdHash) {
		child_scone_ids.push(childSconeId);
	}

	return child_scone_ids;
}

// If the given scone has been added as a child item in another scone,
// or created in HTML within an item in another scone, return the id of
// that item, or null otherwise.
// Notes:
//   * scone_get_item_owner(scone_get_parent_item(sconeElemId)) can be used
//     to find the containing scone of a given scone.
//   * If a scone actually is an item in another scone (as opposed to being
//     within it), scone_parent_item() will return sconeElemId itself.
function scone_get_parent_item(sconeElemId) {
	var scone = _scones[sconeElemId];
	if (scone == undefined) {
			return null;
	}
	return scone.parentSconeItemId;
}


// Remove an item from its scone.
// Returns nothing.
function scone_remove_item(itemElemId) {

	// Locate the scone.

	var sconeElemId = _scone_for[itemElemId];
	if (!sconeElemId) {
			throw("Item \"" + itemElemId + "\" has not been added to a scone.");
	}
	var scone = _scones[sconeElemId];
	if (!scone) {
			throw("Internal error: scone in _scone_for but not in _scones.");
	}
	var scone_elem = document.getElementById(sconeElemId);
	if (!scone_elem) {
			throw("Element \"" + sconeElemId + "\" not found.");
	}

	// Locate the item (slow since we need the index).

	var idx = -1;
	for (var i = 0; i < scone.items.length; i++) {
			if (scone.items[i].id == itemElemId) {
				idx = i;
				break;
			}
	}
	if (idx < 0) {
			throw("Internal error: item in _scone_for but not in scone items.");
	}
	var item = scone.items[idx];

	// Remove the HTML elements.

	var num_elems = item.numElems;
	var elem = _scone_first_item_elem(item);
	var j = 0;
	while (elem && j < num_elems) {
			var next_elem = elem.nextSibling;
			if (elem.nodeType == 1) {
				j++;
			}
			scone_elem.removeChild(elem);
			elem = next_elem;
	}

	// Remove the item entry.

	scone.items.splice(idx, 1);
	delete scone.itemIdHash[itemElemId];
	delete _scone_for[itemElemId];

	// Free child scones.

	for (var childSconeId in item.childSconeIdHash) {
			_scone_delete(childSconeId, true, true);
	}

	return;
}


// Replace an item within a scone with new html and info.
//
// If keepChildren is true, any child scones within the item will
// be preserved (provided their ids still exist in the new html).
//
// Returns nothing.
//
function scone_replace_item(itemElemId, html, info, keepChildren) {

	var sconeElemId = scone_get_item_owner(itemElemId);

	var saved_child_ids    = [];
	var saved_child_scones = [];
	if (keepChildren) {
		saved_child_ids    = scone_get_item_children(itemElemId);
		saved_child_scones = new Array(saved_child_ids.length);
		for (var i = 0; i < saved_child_ids.length; i++) {
			saved_child_scones[i] = scone_cut(saved_child_ids[i]);
		}
	}

	scone_remove_item(itemElemId);
	scone_add_item(sconeElemId, itemElemId, html, info);

	for (var i = 0; i < saved_child_ids.length; i++) {
		if (document.getElementById(saved_child_ids[i])) {
			scone_paste(saved_child_ids[i], saved_child_scones[i]);
		}
	}

	return;
}


// Change the info associated with an item and re-position it accordingly
// within the scone if needed.
function scone_set_item_info(itemElemId, new_info, info_only) {

	var sconeElemId = scone_get_item_owner(itemElemId);
	var scone = _scones[sconeElemId];
	if (!scone) {
		throw("Could not find scone for item \"" + itemElemId + "\"");
	}

	var item = scone.itemIdHash[itemElemId];
	if (!item) {
		throw("Could not find item \"" + itemElemId + 
		      "\" in scone \"" + sconeElemId + "\"");
	}

	// If this score is not sorted, just store the new info and we're done.

	if (scone.cmpFn == null) {
		item.info = new_info;
		return;
	}

	// Figure out:
	//   old position
	//   new position if old entry was still there
	//   new position with old entry gone

	var old_idx;
	for (var i = 0; i < scone.items.length; i++) {
			if (scone.items[i].id == itemElemId) {
				old_idx = i;
				break;
			}
	}
	var new_idx_pre  = _scone_find_ipos(scone, new_info);
	var new_idx_post = (old_idx < new_idx_pre) ? new_idx_pre - 1 : new_idx_pre;

	// Store the new info (note that we had to wait until we'd found the
	// new position before doing this, or else our search would have been
	// confused by the old item appearing to have the new info).

	item.info = new_info;

	// Finished if no change in position.

	if ( old_idx == new_idx_post ) return;

	// Before which element must the item now be positioned?

	var before_elem;
	if (new_idx_pre == scone.items.length) {
			before_elem = null;
	} else {
			before_elem = _scone_first_item_elem(scone.items[new_idx_pre]);
	}

	var scone_elem = document.getElementById(sconeElemId);
	if (!scone_elem) {
			throw("Element \"" + sconeElemId + "\" not found.");
	}

	// Remove and re-add item elements within the DOM.

	if (info_only != true) {
		var num_elems = item.numElems;
		var elem = _scone_first_item_elem(item);
		var j = 0;
		while (elem && j < num_elems) {
				var next_elem = elem.nextSibling;
				if (elem.nodeType == 1) {
					j++;
				}
				scone_elem.removeChild(elem);
				scone_elem.insertBefore(elem, before_elem);
				elem = next_elem;
		}
	}

	// Remove and re-add the item entry.

	scone.items.splice(old_idx, 1);
	scone.items.splice(new_idx_post, 0, item);

	return;
}

// Sort the items in a scone based on the cmpFn supplied at creation.
// If the given cmpMode is null, the existing cmpMode associated with the scone
// will be used; otherwise, the given cmpMode will be used for this sort and
// associated with the scone (replacing the existing cmpMode).
//
function scone_sort(sconeElemId, cmpMode) {

	var scone = _scones[sconeElemId];
	if (scone == undefined) {
			throw("No such scone \"" + sconeElemId + "\"");
	}
	var scone_elem = document.getElementById(sconeElemId);
	if (!scone_elem) {
			throw("Element \"" + sconeElemId + "\" not found.");
	}

	if (scone.cmpFn == null) {
			return;
	}

	if (cmpMode != null) {
			scone.cmpMode = cmpMode;
	} else {
			cmpMode = scone.cmpMode;
	}

	// Find elements.
	var elemsById = {};
	for (var i = 0; i < scone.items.length; i++) {
			var id = scone.items[i].id;
			var elem = _scone_first_item_elem(scone.items[i]);
			var num_elems = scone.items[i].numElems;
			var elems = new Array(num_elems);
			var j = 0;
			while (elem && j < num_elems) {
				if (elem.nodeType == 1) {
					elems[j++] = elem;
				}
				elem = elem.nextSibling;
			}
			elemsById[id] = elems;
	}

	// Sort items.
	var cmpFn = scone.cmpFn;
	var f = function (a, b) {
			return cmpFn(cmpMode, a.info, b.info);
	}
	scone.items.sort(f);

	// Remove elements.
	while (scone_elem.lastChild) scone_elem.removeChild(scone_elem.lastChild);

	// Re-insert elements.
	for (var i = 0; i < scone.items.length; i++) {
			var id = scone.items[i].id;
			var elems = elemsById[id];
			for (var j = 0; j < elems.length; j++) {
				scone_elem.appendChild(elems[j]);
			}
	}

	return;
}


// Save the state and items of a scone, then remove them.
//
// Returns a serialized copy of the scone, including its state, its items and
// the DOM / HTML representation of those items suitable for scone_restore().
//
//
// Notes:
//   * If the scone contains other scones (either as items, or within HTML
//     belonging to items), they will also be saved with the scone.
//   * Any styling or attributes applied to the scone HTML element itself
//     is NOT saved.
//   * The object returned should be treated as opaque - the format may
//     change.
//
function scone_cut(sconeElemId) {
	return _scone_cut(sconeElemId, false, false);
}


// Restore a scone saved with scone_extract.
//
// Replaces any existing contents of the element given by sconeElemId
// (which must exist).
//
// Returns nothing.
//
function scone_paste(sconeElemId, savedScone) {
	_scone_paste(sconeElemId, savedScone, false);
}


// Delete a scone and all its items (including nested scones), leaving only
// the scone HTML element itself (which will no longer be a scone).
//
// Returns nothing.
//
function scone_delete(sconeElemId) {
	_scone_delete(sconeElemId, false, false);
	return;
}


/* ------------ Private functions ----------- */


// As scone_delete, but with extra ignoreXXX params for efficiency when
// recursing.
function _scone_delete(sconeElemId, ignoreHTML, ignoreParent) {

	var scone = _scones[sconeElemId];
	if (scone == undefined) {
			throw("No such scone \"" + sconeElemId + "\"");
	}

	if (!ignoreHTML) {
			var scone_elem = document.getElementById(sconeElemId);
			if (scone_elem) {
				while (scone_elem.lastChild) {
					scone_elem.removeChild(scone_elem.lastChild);
				}
			}
	}

	if (!ignoreParent && scone.parentSconeItemId) {
			var parentSconeElemId = _scone_for[scone.parentSconeItemId];
			var parentScone = _scones[parentSconeElemId];
			var parentItem = parentScone.itemIdHash[scone.parentSconeItemId];
			delete parentItem.childSconeIdHash[sconeElemId];
	}

	for (var i = 0; i < scone.items.length; i++) {
			var item = scone.items[i];
			delete _scone_for[item.id];
			for (var childId in item.childSconeIdHash) {
				// no need to remove from doc or parent since
				// the top-level delete will have done this.
				_scone_delete(childId, true, true);
			}
	}

	delete _scones[sconeElemId];

	return;
}


// As scone_cut, but with extra params for recursive use.
function _scone_cut(sconeElemId, ignoreHTML, ignoreParent) {

	var scone = _scones[sconeElemId];
	if (scone == undefined) {
		throw("No such scone \"" + sconeElemId + "\"");
	}

	var saved_scone = {
		scone:         scone,
		elems:         [],
		childScones:   [],
		childSconeIds: []
	}

	if (!ignoreHTML) {
		var scone_elem = document.getElementById(sconeElemId);
		if (!scone_elem) {
				throw("Element \"" + sconeElemId + "\" not found.");
		}
		while (scone_elem.lastChild) {
			saved_scone.elems.splice(0,0, scone_elem.lastChild);
			scone_elem.removeChild(scone_elem.lastChild);
		}
	}

	if (!ignoreParent && scone.parentSconeItemId) {
			var parentSconeElemId = _scone_for[scone.parentSconeItemId];
			var parentScone = _scones[parentSconeElemId];
			var parentItem = parentScone.itemIdHash[scone.parentSconeItemId];
			delete parentItem.childSconeIdHash[sconeElemId];
	}

	for (var i = 0; i < scone.items.length; i++) {
		for (var childSconeId in scone.items[i].childSconeIdHash) {
			saved_scone.childSconeIds.push(childSconeId);
			// Recurse. There's no need to save any HTML this time.
			saved_scone.childScones.push(_scone_cut(childSconeId, true, true));
		}
		delete _scone_for[scone.items[i].id];
	}

	delete _scones[sconeElemId];

  return saved_scone;
}


// As scone_paste, but with extra param for recursion.
function _scone_paste(sconeElemId, savedScone, ignoreHTML) {

	if (_scones[sconeElemId] != undefined) {
			throw("Scone \"" + sconeElemId + "\" already exists.");
	}

	if (!ignoreHTML) {

		var scone_elem = document.getElementById(sconeElemId);
		if (!scone_elem) {
				throw("Element \"" + sconeElemId + "\" not found.");
		}
		// Remove existing contents
		while (scone_elem.lastChild) {
			scone_elem.removeChild(scone_elem.lastChild);
		}
		// Add saved elements
		for (var i = 0; i < savedScone.elems.length; i++) {
			scone_elem.appendChild(savedScone.elems[i]);
		}

		// Check if this scone is an item in another scone, or if it has been
		// pasted within an item of another scone.

		var elem = scone_elem;
		var pscone_id      = null;
		var pscone_item_id = null;
		while (elem) {
			if (elem.id) {
				if (_scone_for[elem.id] != undefined) {
					pscone_id      = _scone_for[elem.id];
					pscone_item_id = elem.id;
					break;
				}
			}
			elem = elem.parentNode;
		}
		if (pscone_item_id) {
			savedScone.scone.parentSconeItemId = pscone_item_id;
			var pitem = _scones[pscone_id].itemIdHash[pscone_item_id];
			// mark our scone as a child of the parent item
			pitem.childSconeIdHash[sconeElemId] = true;
		}

	}

	_scones[sconeElemId] = savedScone.scone;

	for (var i = 0; i < savedScone.scone.items.length; i++) {
		var item = savedScone.scone.items[i];
		_scone_for[item.id] = sconeElemId;
	}

	for (var i = 0; i < savedScone.childScones.length; i++) {
		var childScone   = savedScone.childScones[i];
		var childSconeId = savedScone.childSconeIds[i];
		// Recurse. There's no need to restore any HTML this time.
		_scone_paste(childSconeId, childScone, true);
	}

	return;
}


// Find the first top-level HTML element in an item.
function _scone_first_item_elem(item) {
	var item_key_elem = document.getElementById(item.id);
	if (!item_key_elem) {
			throw("Element \"" + item.id + "\" not found.");
	}
	var elem = item_key_elem;
	for (var i = 0; i < item.offsetUp; i++) {
			elem = elem.parentNode;
	}
	for (var i = 0; i < item.offsetLeft; i++) {
			elem = elem.previousSibling;
	}
	return elem;
}


// Find "insert before" position for a new item by comparing its info with
// that of the existing items using the scone's sort function and mode.
// Number of comparisons will be O(log2 n).
// Returns index in the range 0 to number of items (inclusive).
// Note that if the new_info compares equal to the info of an existing item,
// it will be considered to come after the existing item.
function _scone_find_ipos(scone, new_info) {
	var arr     = scone.items;
	var cmpFn   = scone.cmpFn;
	var cmpMode = scone.cmpMode;
	var h = arr.length, l = -1, m;
	while (h - l > 1) {
			if (cmpFn(cmpMode, arr[m = h + l >> 1].info, new_info) < 0) {
				l = m;
			} else {
				h = m;
			}
	}
	if (h < arr.length && cmpFn(cmpMode, arr[h].info, new_info) == 0) {
			return h + 1;
	} else {
			return h;
	}
}