//==============================================================================
// HashCompactor.js -- Storage and lookup of Key/Data combinations
// by SkewsMe.com
//
// HashCompactor is a container designed to allow for quick lookup of data given a
// set of keys (character strings) (in particular, peoples' names or IP Addresses).
// Each character in a key is a node with subsequent characters being stored in recursive sub-nodes.
// The keys' characters overlap for beginning sequences such as "Ab" in keys "Able" and "Abby".
// Multiple data entries are allowed for each key. The data may be any object.
//
// Optional data validation may be removed by a debugged client program (see DEBUG).
//
// Designed for porting to C++, currently realized in JavaScript.
// Comments for porting are included (see "C++").
// JavaScript has intermittent 15-16 millisecond bursts causing major lag for large data.
// For example, string.charAt(0) suffers from these lags.
// In JavaScript testing using website log files as input, these lags cause
// execution time to quadruple as the amount of data doubles.
//
// Join https://sourceforge.net/projects/hashcompactor if you'd like to help develop this project.
//
//
// See https://skewsme.com/code/HashCompactor/hashcompactor_trans.js for a working demo
//
// Uses global variable naming conventions HashCompactor- and -SM_HC_-
//
// Search: C++, DEBUG, ASSERT, VERIFY, UNDONE, KLUDGE
//
// Conceived: 1992 - (c) Skews_Me
// Created: 27 Nov 2004
// Updated: March 2012, see current working JavaScript code
// Updated: September 2015
//
// UNDONE:
//
// Optimize runs of characters.
// Optimize to only index array after some hardcoded nodes.
// Optimize with tail recursion and unwrapping.
// Stress test recursion with huge keys.
// Optimize loops.
// Array buffering.
// Which is faster? if (x == -1) and a do or (x != -1) and a jump do?
// for relevant functions. Currently assumes key doesn't exist for adding data
// and the key does exist for retrieving data.
// Would reversing the internal node sort decrease loop time?
// File load optimization -- remove comments, whitespace, debugging routines, etc.
// Use www.skewsme.com/remove.html to strip comments
//==============================================================================
function HashCompactor() // C++ class
{
// DO NOT CALL other HashCompactor routines from the callback functions of
// Compile() and CompileNames().
// Exceptions: MarkToDelete(), KeyCount(), DEBUG StartTime(), EndTime()
this.AddData = HashCompactorAddData; // AddData(key,datum); Add a data item to key.
// Multiple calls with same key creates multiple
// data entries for that key.
// Returns an array of data items allowing
// direct access to the data.
// The returned array may be altered in size.
// To remove all the data, use DeleteKey().
// Example:
// ... currentKey, sortFunction;
//
// var hc = new HashCompactor();
// var previousKey = null;
// var data = new Array();
// for (...) {
// if (previousKey != currentKey)
// data = hc.AddData(previousKey = currentKey, dataItem);
// else
// data.push(dataItem);
// }
// hc.CompileNames(); // sort
this.GetData = HashCompactorGetData; // GetData(key); Returns an array of data entries
// if the key exists, otherwise null.
// The array allows direct access to the data.
// The array may be altered in size.
// To remove all the data, use DeleteKey().
this.SetData = HashCompactorSetData; // SetData(key,data); Adds an array of data entries to the key.
// Creates the key if necessary.
// If the data array parameter is from a previously returned SetData(),
// AddData() or GetData() call, SetData() shouldn't be called
// for the same key.
// Returns an array of data items allowing
// direct access to the data.
// The returned array may be altered in size.
// To remove all the data, use DeletelKey().
this.DeleteKey = HashCompactorDeleteKey; // DeleteKey(key); Deletes the key and the data array
// associated with it.
// Invalidates the arrays returned from AddData(), GetData()
// and SetData().
this.SortNodes = HashCompactorSortNodes; // SortNodes(); Sort the nodes for all keys.
// Note: SortNodes() will order a numerical key
// 103 after 102-102999... and
// all capital letters will be sorted before lower-case.
// Use CompileNames() for retrieving keys in alphabetical order
// regardless of their case.
this.SortKey = HashCompactorSortKey; // SortKey(key); Sorts the nodes of one key that was
// created with AddData() or SetData()
this.KeyCount = HashCompactorKeyCount; // KeyCount(); Returns the number of unique keys.
// Returns the property this.numKeys
this.Compile = HashCompactorCompile; // Compile(keystr,callback_function,client_data); Iterates through every key
// containing the initial keystr and executes the provided
// callback function when data is found for those keys.
// Passes client_data to callback_function. client_data may be null.
// If keystr equals "", Compile() iterates through
// all keys.
// Example: hc.Compile("",SM_HC_PrintToScreen,null);
// The callback fuction should be of the form:
// function callback_fn_name(key_string,data_array,client_data)
// { return 1 to continue, 0 to stop }
// The data_array may be altered in size. To remove all the data,
// use DeleteKey() AFTER Compile().
// You may also use MarkToDelete(key) from within the
// callback_function to indicate multiple keys which you
// wish to delete and call DeleteMarked() after the the Compile
// to delete the keys.
// See "Sample sorting algorithm" below. See also CompileNames() source code below.
this.CompileNames = HashCompactorCompileNames; // CompileNames(keystr,callback_function,client_data);
// Creates a new HashCompactor object for sorting
// alphabetically. Internally, key strings are
// first converted to upper case and added to the new
// HashCompactor.
// CompileNames() then calls Compile()
// with keystr converted to upper case.
// If keystr equals "", CompileNames() iterates through
// all keys.
// Passes client_data to callback_function. client_data may be null.
// callback_function should be of the form:
// function callback_fn_name(key_string,data_array,client_data)
// { return 1 to continue, 0 to stop }
// The data_array may be altered in size. To remove all the data,
// use DeleteKey() AFTER CompileNames().
// You may also use MarkToDelete(key) from within the
// callback_function to indicate multiple keys which you
// wish to delete and call DeleteMarked() after the the Compile
// to delete the keys.
this.MarkKeyToDelete = HashCompactorMarkKeyToDelete;
this.DeleteMarkedKeys = HashCompactorDeleteMarkedKeys;
this.ClearMarkedKeys = HashCompactorClearMarkedKeys;
// MarkToDelete(key) is called from Compile callback functions to indicate deletion later by DeleteMarked()
// DeleteMarked() is called after the Compile routines to delete the keys that were indicated with MarkToDelete().
// ClearMarked() empties the marked array. DeleteMarked() also clears the array.
this.Copy = HashCompactorCopy; // Copy(hc); Copies another HashCompactor object
this.SetNodeFinder = HashCompactorSetNodeFinder;
// SetNodeFinder(function_name); Set the optimization for FindNode().
// Returns the previous function_name.
// Default function is SM_HC_LookupNode(node,character); See below.
// SM_HC_LookupNode() begins searching a
// node's this.nodes from its this.current value
// to end of array, then tries from the beginning of the array.
// SetNodeFinder() overrides the default function and should be in the form:
// function finder_routine(node,character) { set node.current to the index into node.nodes
// and return the index if the character is found, otherwise return -1 }.
// Use node.current and node.length for indexing node.nodes.
// node.nodes[index].c is the character to match against.
// The finder routine will not be called if this.current for the node equals -1
// and thus there are no nodes to search.
// The finder routine should update node.current only if a match is found.
// The finder routine should return -1 if node isn't found or there's an error.
// Default assumes keys are pre-sorted using SortNodes() (but isn't required).
// Sorted keys are more likely to share beginning characters (for example,
// adding people alphabetically by last name) and thus would be accessing
// the nodes already being referenced by the nodes' this.current values.
// DEBUGGING -- Include hashcompactordebug.js after hashcompactor.js to use debugging functions
//this.Dump // Dump(); Prints lines of "key : data.length" to page.
// Calls this.Compile("",SM_HC_PrintToScreen,null)
//this.Stats // Prints node statistics to page.
//this.StartTime // StartTime(); Set initial Date object
//this.EndTime // EndTime(); Returns time difference from
// previous call to StartTime() in milliseconds
// StartTime() and EndTime() may also be paired in subnodes
// INTERNAL
// Each object (subnode) in this.nodes is a HashCompactorNode that stores the
// character, reference count, additional subnodes and data
this.current = -1; // -1 indicates no nodes, otherwise an index into this.nodes
this.nodes = new Array();
this.numKeys = 0;
this.FindNode = HashCompactorFindNode;
// FindNode(character); Optimization to find the right this.nodes node
// for the given character. Returns -1 if node doesn't exist.
// FindNode() calls SM_HC_LookupNode() by default, overridden by SetNodeFinder().
// FindNode() won't call the node finder if this.current equals -1 and thus no nodes.
}
function SM_HC_LookupNode(node, character)
{
// Default routine for finding nodes. Overridden by SetNodeFinder(). See above.
// DO NOT set node.current to -1.
// ASSERT from FindNode() (node.current != -1 && node.nodes);
var i = node.current;
if (node.nodes[i].c == character)
return i;
else if (node.nodes.length == 1) // Skip loops if there is only one node (which didn't match)
return -1;
else
{
var nodes = node.nodes; // C++ aliases to eliminate dereferencing
var length = nodes.length;
for (++i; i<length; i++) // to end of array
if (nodes[i].c == character)
return node.current=i;
for (i=0, length=node.current; i<length; i++) // from beginning of array
if (nodes[i].c == character)
return node.current=i;
}
return -1;
}
/*==============================================================================
// Sample sorting algorithm
//
// user_defined_data may be of any type
function user_defined_data(key,data_array,value_to_sort) // Used for user_defined_process_sorted_function
{
this.key=key;
this.data_array=data_array;
this.value_to_sort=value_to_sort;
}
// Entry point
function user_defined_sort(keystr,hash_compactor_object)
{
var user_defined_sort_data = new Array(); // of type user_defined_data (data may be any type)
hash_compactor_object.Compile(keystr,user_defined_sort_data_builder,user_defined_sort_data); // Build user_defined_sort_data
user_defined_sort_data.sort(user_defined_sort_data_elements); // Sort the elements from data
for (var i=0, length=user_defined_sort_data.length; i<length; i++)
if (! user_defined_process_sorted_function(user_defined_sort_data[i].key, user_defined_sort_data[i].data_array, user_defined_sort_data[i].value_to_sort))
return;
}
function user_defined_sort_data_builder(key,data,user_defined_sort_data)
{
// Sample
var value_to_sort = user_defined_initialization;
for (var i=0, length=data.length; i<length; i++)
{
if (data[i].user_defined_test)
{
value_to_sort = data[i].user_defined_field;
}
}
user_defined_sort_data.push(new user_defined_data(key,data,value_to_sort));
return 1;
}
function user_defined_sort_data_elements(a,b)
{
return (a.user_defined_value > b.user_defined_value) ? -1 : 1; // Sorts highest value first
}
==============================================================================*/
//==============================================================================
function HashCompactorNode(character,refcount) // C++ class
{
this.c = character; // Sucessive characters in the key string
this.r = refcount; // Reference count to determine deletion
this.current = -1; // -1 indicates no nodes
this.nodes = null; // null indicates no nodes
this.data = null; // null indicates no data
this.AddData = HashCompactorNodeAddData;
this.AddDataItem = HashCompactorNodeAddDataItem;
this.SetData = HashCompactorNodeSetData;
this.SetDataItems = HashCompactorNodeSetDataItems;
this.SetNode = HashCompactorNodeSetNode;
this.SortNodes = HashCompactorNodeSortNodes;
this.SortKey = HashCompactorNodeSortKey;
this.GetData = HashCompactorNodeGetData;
this.Copy = HashCompactorNodeCopy;
this.CopyData = HashCompactorNodeCopyData;
this.DelKey = HashCompactorNodeDelKey;
this.DelNode = HashCompactorNodeDelNode;
this.FindNode = HashCompactorNodeFindNode;
this.Compile = HashCompactorNodeCompile;
this.CompileAll = HashCompactorNodeCompileAll;
this.Clear = HashCompactorNodeClear;
this.AddName = HashCompactorNodeAddName;
}
var _SM_HC_nodefinder = SM_HC_LookupNode;
var _SM_HC_todelete = new Array(); // Used by MarkToDelete() and it's sister functions.
var _SM_HC_sortarray = new Array(); // Used by SortNodes() and SortKey() in the SM_HC_SortAlpha() routine.
_SM_HC_sortarray.length = 2; // C++ allocate array length
function SM_HC_SortAlpha(a,b)
{
_SM_HC_sortarray[0] = a.c;
_SM_HC_sortarray[1] = b.c;
_SM_HC_sortarray.sort(); // C++ sort array
return (_SM_HC_sortarray[0] == b.c) ? 1 : -1;
}
function HashCompactorFindNode(character) // C++ inline
{
return (this.current != -1) ? _SM_HC_nodefinder (this, character) : -1;
}
function HashCompactorNodeFindNode(character) // C++ inline
{
return (this.current != -1) ? _SM_HC_nodefinder (this, character) : -1;
}
function HashCompactorKeyCount() // C++ inline
{
return this.numKeys;
}
//==============================================================================
// Optimization: Rather than call string.unshift() or string.substr() for recursive calls using key or keystr,
// pass indexes into the key. The key is converted to an array because charAt() is too slow.
function HashCompactorKeySubstrOp(key) // C++ struct (or class)
{
this.current = 0;
this.key = key.split(""); // C++ convert string into array of characters (may not be necessary step in C++)
// ASSERT (key.length > 0);
this.remaining = key.length;
this.InKey = HashCompactorKeySubstrOpInKey; // Returns this.remaining (characters in key).
this.Char = HashCompactorKeySubstrOpChar; // Returns the character at this.current.
// DO NOT call if InKey() returned 0.
this.Next = HashCompactorKeySubstrOpNext; // Point this.current to next character and update this.remaining.
// DO NOT call if InKey() returned 0.
}
function HashCompactorKeySubstrOpInKey() // C++ inline
{
return this.remaining; // ASSERT (this.remaining >= 0);
}
function HashCompactorKeySubstrOpChar() // C++ inline
{
// DO NOT call unless this.InKey() returns (this.remaining > 0).
return this.key[this.current];
}
function HashCompactorKeySubstrOpNext() // C++ inline
{
// DO NOT call unless this.InKey() returns (this.remaining > 0).
// JavaScript: post-increment faster, pre-decrement faster
this.current++
--this.remaining;
return this;
}
//==============================================================================
function HashCompactorAddData(key,datum)
{
// DEBUG: This may be removed if client guarantees no (key=="") calls
if (! key.length)
return;
var keyOp = new HashCompactorKeySubstrOp(key); // ASSERT (key.length > 0);
var character = keyOp.Char();
var inode = this.FindNode(character); // Sets this.current if character found in this.nodes
if (inode == -1)
{
inode = this.current = this.nodes.length;
this.nodes.push(new HashCompactorNode(character,1)); // C++ grow array
}
else
this.nodes[inode].r++; // ASSERT from FindNode() (inode == this.current != -1);
var data = this.nodes[inode].AddData(keyOp.Next(),datum);
if (data.length == 1)
this.numKeys++;
return data;
}
// Recursive
function HashCompactorNodeAddData(keyOp,datum)
{
if (keyOp.InKey())
{
this.SetNode(keyOp.Char()); // Updates this.current
return this.nodes[this.current].AddData(keyOp.Next(),datum);
}
else
return this.AddDataItem(datum);
}
function HashCompactorNodeSetNode(character)
{
// Called from AddData() and SetData() to reduce stack size due to recursion.
// Create node if necessary and update this.current.
if (! this.nodes)
{
this.nodes = new Array();
// this.nodes.length = 1; // C++ allocate array size
this.nodes[this.current = 0] = new HashCompactorNode(character,1); // C++ grow array
}
else
{
var inode = this.FindNode(character); // Sets this.current if found
if (inode == -1)
{
this.current = this.nodes.length;
this.nodes.push(new HashCompactorNode(character,1)); // C++ grow array
}
else
this.nodes[inode].r++; // ASSERT from FindNode() (inode == this.current != -1);
}
}
function HashCompactorNodeAddDataItem(datum)
{
// Called from AddData() to reduce stack size due to recursion.
if (! this.data)
this.data = new Array();
this.data.push(datum); // C++ grow array
return this.data;
}
//==============================================================================
function SM_HC_CompileData(callback_function,client_data)
{
this.callback=callback_function;
this.data=client_data;
this.status = 1; // Set to 0 to break out of search
}
function HashCompactorCompile(keystr,callback_function,client_data)
{
var compile_data = new SM_HC_CompileData(callback_function,client_data);
if (keystr.length)
{
// Only sort nodes present in keystr
var keystrOp = new HashCompactorKeySubstrOp(keystr);
var character=keystrOp.Char();
var inode=this.FindNode(character);
if (inode != -1)
this.nodes[inode].Compile(keystrOp.Next(),character,compile_data);
}
else
{
// (keystr == "") so sort all nodes
for (var i=0, length=this.nodes.length; compile_data.status && i<length; i++)
this.nodes[i].CompileAll(this.nodes[i].c,compile_data);
this.current = 0;
}
}
// Recursive
function HashCompactorNodeCompileAll(str,compile_data)
{
if (this.data) // If data, then it's a key so call the callback function supplied to Compile()
if (! (compile_data.status = compile_data.callback(str,this.data,compile_data.data)))
return;
if (this.nodes)
{
for (var i=0, length=this.nodes.length; compile_data.status && i<length; i++)
this.nodes[i].CompileAll(str+this.nodes[i].c,compile_data);
this.current = 0;
}
}
// Recursive
function HashCompactorNodeCompile(keystrOp,str,compile_data)
{
// keystrOp == HashCompactorKeySubstrOp
var inKeystr = keystrOp.InKey(); // DEBUG: C++ InKey() is inline so assignment may not be necessary
if (! inKeystr && this.data) // Only check if data once the end of keystr is determined
if (! (compile_data.status = compile_data.callback(str,this.data,compile_data.data)))
return;
if (this.nodes)
{
if (inKeystr)
{
// Continue recursing through keystr
var character=keystrOp.Char();
var inode=this.FindNode(character);
if (inode != -1)
this.nodes[inode].Compile(keystrOp.Next(),str+character,compile_data);
}
else
{
// At end of keystr so compile all nodes
for (var i=0, length=this.nodes.length; compile_data.status && i<length; i++)
this.nodes[i].CompileAll(str+this.nodes[i].c,compile_data);
this.current = 0;
}
}
}
//==============================================================================
// Used by AddNames() and SM_HC_NameCompiler() to store original key name with its data
function HashCompactorNodeCompileNamesNameData(name,data) // C++ struct
{
this.name=name;
this.data=data;
}
function HashCompactorCompileNamesCompileData(callback_function,client_data)
{
this.callback = callback_function;
this.client_data = client_data;
}
function SM_HC_CompileNamesCallback(key,namedata,compile_data) // C++ inline
{
// Pass the original key names back to client
return compile_data.callback(namedata[0].name,namedata[0].data,compile_data.client_data); // Execute the callback function
}
function HashCompactorCompileNames(keystr,callback_function,client_data)
{
var hc = new HashCompactor();
for (var i=0, length=this.nodes.length; i<length; i++)
this.nodes[i].AddName(this.nodes[i].c,hc);
hc.SortNodes(); // Keys are all upper-case
var compile_data = new HashCompactorCompileNamesCompileData(callback_function,client_data);
hc.Compile(keystr.toUpperCase(),SM_HC_CompileNamesCallback,compile_data); // C++ string.toUpperCase()
}
// Recursive
function HashCompactorNodeAddName(str,hc)
{
if (this.data)
hc.AddData(str.toUpperCase(),new HashCompactorNodeCompileNamesNameData(str,this.data)); // C++ string.toUpperCase()
if (this.nodes)
for (var i=0, length=this.nodes.length; i<length; i++)
this.nodes[i].AddName(str+this.nodes[i].c,hc);
}
//==============================================================================
// Optimazation to reduce paramaters in SetData() recursion
function HashCompactorNodeDataIO(dataIn) // C++ struct
{
this.dataIn = dataIn;
this.dataOut;
}
function HashCompactorSetData(key,dataIn)
{
// VERIFY dataIn isn't from a previous call to AddData(), GetData() or SetData()
// DEBUG: This may be removed if client guarantees (key != "") and (dataIn.length != 0).
if (! key.length || ! dataIn.length)
return;
var keyOp = new HashCompactorKeySubstrOp(key);
var character = keyOp.Char();
var inode = this.FindNode(character);
if (inode == -1)
{
inode = this.current = this.nodes.length;
this.nodes.push(new HashCompactorNode(character,1)); // C++ grow array
}
else
this.nodes[inode].r++;
// UNDONE: test whether directly incrementing numKeys from the return value of SetData()
// is faster. If key is always a new key, this might be the case.
var dataIO = new HashCompactorNodeDataIO(dataIn);
if (this.nodes[inode].SetData(keyOp.Next(),dataIO))
this.numKeys++;
// ASSERT (dataIO.dataOut != undefined)
return dataIO.dataOut;
}
// Recursive
function HashCompactorNodeSetData(keyOp,dataIO)
{
if (keyOp.InKey())
{
this.SetNode(keyOp.Char()); // Updates this.current
return this.nodes[this.current].SetData(keyOp.Next(),dataIO);
}
else // ASSERT (dataIO.dataIn.length > 0);
return this.SetDataItems(dataIO);
}
function HashCompactorNodeSetDataItems(dataIO)
{
// Called from SetData() to reduce stack size due to recursion.
// Create data item array if necessary and copy. Then set dataIO.dataOut.
// Returns 1 if a new data array (and thus key) was created, otherwise 0.
// ASSERT (dataIO.dataIn.length > 0);
var isNewData;
if (! this.data)
{
this.data = new Array();
isNewData = 1; // key didn't exist so increment hc.numKeys
}
else
isNewData = 0; // key already exists so don't increment hc.numKeys
var dataIn = dataIO.dataIn; // Alias to eliminate dereferencing
if (this.data != dataIn)
{
var length = dataIn.length;
this.data.length = length; // C++ reallocate array size
while (--length >= 0)
this.data[length] = dataIn[length];
// while (--length)
// this.data[length] = dataIn[length];
// this.data[0] = dataIn[0];
}
dataIO.dataOut = this.data;
return isNewData;
}
//==============================================================================
function HashCompactorMarkKeyToDelete(key) // C++ inline
{
_SM_HC_todelete.push(key); // C++ grow array
}
function HashCompactorClearMarkedKeys() // C++ inline
{
_SM_HC_todelete = new Array(); // C++ reallocate array
}
function HashCompactorDeleteMarkedKeys() // C++ inline
{
for (var i=0, length=_SM_HC_todelete.length; i<length; i++)
this.DeleteKey(_SM_HC_todelete[i]);
this.ClearMarked();
}
function HashCompactorSetNodeFinder(function_name) // C++ inline
{
var temp = _SM_HC_nodefinder;
_SM_HC_nodefinder = function_name;
return temp;
}
//==============================================================================
function HashCompactorDeleteKey(key)
{
if (! this.GetData(key)) // Invalid key? (semi-KLUDGE)
return;
var keyOp = new HashCompactorKeySubstrOp(key);
var inode = this.FindNode(keyOp.Char());
if (inode != -1)
{
this.nodes[inode].DelKey(keyOp.Next());
this.numKeys--;
// Remove node if no other subnode is using it
if (! --this.nodes[inode].r)
{
this.nodes.splice(inode,1); // C++ splice array
this.current = this.nodes.length ? 0 : -1; // UNDONE: optimize
}
}
}
// Recursive
function HashCompactorNodeDelKey(keyOp)
{
if (keyOp.InKey())
{
var inode = this.FindNode(keyOp.Char());
if (inode != -1)
{
this.nodes[inode].DelKey(keyOp.Next());
this.DelNode(inode);
}
}
else
this.data = null; // C++ delete[] array and assign
}
function HashCompactorNodeDelNode(inode)
{
// Called from Del(ete)Key() to reduce stack size due to recursion
// Remove inode's node if no other sub-node is using it
// ASSERT (inode != -1);
if (! --this.nodes[inode].r)
{
this.nodes.splice(inode,1); // C++ splice array
if (this.nodes.length)
this.current = 0;
else
{
this.nodes = null; // C++ delete[] array and assign
this.current = -1;
}
}
}
//==============================================================================
function HashCompactorGetData(key)
{
// DEBUG: This may be removed if client guarantees (key != "").
if (! key.length)
return;
var keyOp = new HashCompactorKeySubstrOp(key);
var inode = this.FindNode(keyOp.Char());
if (inode != -1)
return this.nodes[inode].GetData(keyOp.Next());
return null;
}
// Recursive
function HashCompactorNodeGetData(keyOp)
{
if (keyOp.InKey())
{
var inode = this.FindNode(keyOp.Char());
if (inode != -1)
return this.nodes[inode].GetData(keyOp.Next());
return null;
}
return this.data;
}
//==============================================================================
function HashCompactorSortNodes()
{
var length = this.nodes.length;
if (length)
{
this.nodes.sort(SM_HC_SortAlpha); // C++ sort array
this.current = 0;
for (var i=0; i<length; i++)
this.nodes[i].SortNodes();
}
}
// Recursive
function HashCompactorNodeSortNodes()
{
if (this.nodes) // ASSERT (this.nodes.length != 0);
{
this.nodes.sort(SM_HC_SortAlpha); // C++ sort array
this.current = 0;
for (var i=0, length=this.nodes.length; i<length; i++)
this.nodes[i].SortNodes();
}
}
function HashCompactorSortKey(key)
{
// DEBUG: This may be removed if client guarantees (key != "").
if (! key.length)
return;
if (this.nodes.length) // DEBUG: This may be removed if client guantees no empty HashCompactor
{
this.nodes.sort(SM_HC_SortAlpha); // C++ sort array
this.current = 0;
var keyOp = HashCompactorKeySubstrOp(key); // ASSERT (key.length);
var inode = this.FindNode(keyOp.Char());
if (inode != -1)
this.nodes[inode].SortKey(keyOp.Next()); // C++ string substr
}
}
// Recursive
function HashCompactorNodeSortKey(keyOp)
{
// ASSERT (this.nodes.length != 0);
if (this.nodes && keyOp.InKey())
{
this.nodes.sort(SM_HC_SortAlpha); // C++ sort array
this.current = 0;
var inode = this.FindNode(keyOp.Char());
if (inode != -1)
this.nodes[inode].SortKey(keyOp.Next()); // C++ string substr
}
}
//==============================================================================
function HashCompactorCopy(hc)
{
var i, length;
// Delete current nodes (C++ convention) then copy
for (i=0, length=this.nodes.length; i<length; i++)
this.nodes[i].Clear();
var newnode, thisnode;
this.nodes = new Array();
length = this.nodes.length = hc.nodes.length; // C++ allocate array size
for (i=0; i<length; i++)
{
newnode = hc.nodes[i]; // Alias to eliminate dereferencing
thisnode = this.nodes[i] = new HashCompactorNode(newnode.c,newnode.r);
thisnode.Copy(newnode);
}
this.current = length ? 0 : -1;
this.numKeys = hc.numKeys;
}
// Recursive
function HashCompactorNodeClear()
{
if (this.data)
this.data = null; // C++ delete[] array and assign
if (this.nodes)
{
for (var i=0, length=this.nodes.length; i<length; i++)
this.nodes[i].Clear();
this.nodes = null; // C++ delete[] array and assign
}
}
// Recursive
function HashCompactorNodeCopy(node)
{
if (node.data)
this.CopyData(node.data);
if (node.nodes)
{
this.nodes = new Array();
var length = this.nodes.length = node.nodes.length; // C++ allocate array size
var newnode, thisnode; // Aliases to eliminate dereferencing
for (var i=0; i<length; i++)
{
newnode = node.nodes[i];
thisnode = this.nodes[i] = new HashCompactorNode(newnode.c,newnode.r);
thisnode.Copy(newnode);
}
this.current = 0;
}
}
function HashCompactorNodeCopyData(data)
{
// Called from NodeCopy() to reduce stack size from recursion.
this.data = new Array();
var length = this.data.length = data.length; // C++ allocate array size
for (var i=0; i<length; i++)
this.data[i] = data[i];
}
//==============================================================================
// DEBUGGING functions for HashCompactor
// Save routines in hashcompactordebug.js and include after hashcompactor.js
function SM_HC_PrintToScreen(key,data)
{
document.write(key + ' : ' + data.length + '<br>');
return 1;
}
HashCompactor.prototype.Dump = function()
{
this.Compile("",SM_HC_PrintToScreen,null);
}
HashCompactor.prototype.StartTime = function()
{
this.time = new Date();
}
HashCompactor.prototype.EndTime = function()
{
var stamp = new Date();
return stamp - this.time;
}
HashCompactorNode.prototype.StartTime = function()
{
this.time = new Date();
}
HashCompactorNode.prototype.EndTime = function()
{
var stamp = new Date();
return stamp - this.time;
}
var _SM_HC_topidcount;
var _SM_HC_idcount;
var _SM_HC_idnodes;
var _SM_HC_avgcount;
var _SM_HC_maxcount;
var _SM_HC_datacount;
var _SM_HC_datanodes;
var _SM_HC_avgdata;
var _SM_HC_maxdata;
HashCompactor.prototype.Stats = function()
{
_SM_HC_topidcount=0;
_SM_HC_idcount=0;
_SM_HC_idnodes=0;
_SM_HC_avgcount=0;
_SM_HC_maxcount=0;
_SM_HC_datacount=0;
_SM_HC_datanodes=0;
_SM_HC_avgdata=0;
_SM_HC_maxdata=0;
for (var i=0;i<this.nodes.length; i++)
this.nodes[i].Stats();
_SM_HC_topidcount+=this.nodes.length;
// Don't count the top nodes in the sub-node stats
// _SM_HC_idcount+=this.nodes.length;
// _SM_HC_avgcount = (_SM_HC_avgcount + this.nodes.length) / (++_SM_HC_idnodes);
if (_SM_HC_maxcount < this.nodes.length)
_SM_HC_maxcount = this.nodes.length;
document.write('<br><br>Stats:<br>KeyCount = ' + this.KeyCount() + ', ' + _SM_HC_topidcount + ' top nodes, total=' + _SM_HC_idcount + ' non-top nodes in ' + _SM_HC_idnodes + ' sub-nodes containing ' + _SM_HC_datacount + ' data items in ' + _SM_HC_datanodes + ' data nodes<br>MAX=(' + _SM_HC_maxcount + ' sub-nodes, ' + _SM_HC_maxdata + ' data nodes) AVG=(' + _SM_HC_avgcount + ', ' + _SM_HC_avgdata + ')<br><br>');
}
HashCompactorNode.prototype.Stats = function()
{
if (this.data)
{
_SM_HC_datacount+=this.data.length;
_SM_HC_avgdata = (_SM_HC_avgdata + this.data.length) / (++_SM_HC_datanodes);
if (_SM_HC_maxdata < this.data.length)
_SM_HC_maxdata = this.data.length;
}
if (this.nodes)
{
for (var i=0;i<this.nodes.length; i++)
this.nodes[i].Stats();
_SM_HC_idcount+=this.nodes.length;
_SM_HC_avgcount = (_SM_HC_avgcount + this.nodes.length) / (++_SM_HC_idnodes);
}
}
//==============================================================================
|