u_GenericSet Data Structure
The set data type does not store duplicate elements. It offers the ability to perform unions, differences and intersections with other sets. Iterating the structure using getIterator is a little slow, so use toArray() as needed. It is "generic" in the spirit of Java generics (which have always seemed ironically named to me, since they make a data structure's element-type specific), meaning you permanently set the type of element at instantiation.
I have played around with it using data sets in the 1,000s of records range and the performance was satisfactory. Comments and criticisms are always welcomed.
// This data structure does not allow duplicates, thus re-adding the same value will simply ignore the 2nd value.
// Set the datatype when constructing the object:string, number, etc.
// Once the object is constructed, elements of different types cannot be used for operations add(), remove(), contains() otherwise the object will throw an exception
// Wrap code that uses this in a try/catch block and write code to handle exceptions.
var u_GenericSet = Class.create();
u_GenericSet.prototype = {
// Constructor creates a deep copy of the array parameter to avoid pass by reference mayhem.
// Array parameter is optional
initialize: function (elementType, array) {
if (JSUtil.nil(elementType)) {
throw "Mandatory constructor parameter 'elementType' was omitted when constructing object of type u_GenericSet";
}
if (!/number|string|object|boolean$/i.test(elementType)) {
throw "Constructor parameter 'elementType' must be number|string|object|boolean when constructing object of type u_GenericSet";
}
this.elementType = elementType.toLowerCase();
this.ary = [];
if (array) {
for (var i = 0; i < array.length; i++) {
if ((typeof array[i]) != this.elementType) {
throw "Could not construct the u_GenericSet object because array parameter elements were not all of type " + this.elementType;
}
this.add(array[i]);
}
}
},
// Ensures no duplicates. Param must be of type set at construction
add: function (element) {
var passedType = (typeof element).toLowerCase();
if (passedType != this.elementType) {
throw "u_GenericSet was constructed to contain only elements of type:" + this.elementType + " Attempted to add element of type:" + typeof element;
}
//First element
if (this.ary.length == 0) {
this.ary[0] = element;
return;
}
//If the element is bigger than last element, stick it at the end
if (element > this.ary[this.ary.length - 1]) {
this.ary[this.ary.length] = element;
return;
}
//If the element is smaller than first element, stick it at the beginning
if (element < this.ary[0]) {
this.ary.splice(0, 0, element);
return;
}
var finder = this._binaryIndexOf(element);
if (finder.foundIt) {
return;
} else {
this.ary.splice(finder.ndx, 0, element);
}
},
//Returns object with 2 properties: 1) foundIt (boolean), 2) ndx (integer)
_binaryIndexOf: function (searchElement) {
var minIndex = 0;
var maxIndex = (this.ary.length == 0) ? 0 : this.ary.length - 1;
var currentIndex;
var currentElement;
while (minIndex <= maxIndex) {
currentIndex = (minIndex + maxIndex) / 2 | 0;
currentElement = this.ary[currentIndex];
if (currentElement < searchElement) {
minIndex = currentIndex + 1;
}
else if (currentElement > searchElement) {
maxIndex = currentIndex - 1;
}
else if (currentElement == searchElement) {
return { foundIt: true, ndx: currentIndex };
}
}
return { foundIt: false, ndx: minIndex };
},
//Returns a boolean
_binaryExists: function (searchElement) {
var minIndex = 0;
var maxIndex = (this.ary.length == 0) ? 0 : this.ary.length - 1;
var currentIndex;
var currentElement;
while (minIndex <= maxIndex) {
currentIndex = (minIndex + maxIndex) / 2 | 0;
currentElement = this.ary[currentIndex];
if (currentElement < searchElement) {
minIndex = currentIndex + 1;
} else if (currentElement > searchElement) {
maxIndex = currentIndex - 1;
} else {
return true;
}
}
return false;
},
//Returns a boolean
contains: function (element) {
var passedType = (typeof element).toLowerCase();
if (passedType != this.elementType) {
throw "u_GenericSet was constructed to contain only elements of type:" + this.elementType + " Attempted to call contains for element of type:" + typeof element;
}
return this._binaryExists(element);
},
//Removes a value, not a value at an index
remove: function (element) {
var passedType = (typeof element).toLowerCase();
if (passedType != this.elementType) {
throw "u_GenericSet was constructed to contain only elements of type:" + this.elementType + " Attempted to call remove for element of type:" + typeof element;
}
var finder = this._binaryIndexOf(element);
if (finder.foundIt) {
this.ary.splice(finder.ndx, 1);
return true;
}
return false;
},
// Returns an int
size: function () { return this.ary.length; },
//Returns a new u_GenericSet containing the elements from both sets
union: function (otherSet) {
if (otherSet.type != "u_GenericSet") {
throw "Called union() on u_GenericSet with a parameter that was not a u_GenericSet type object.";
}
var otherAsArray = otherSet.toArray();
var oReturn = new u_GenericSet(this.elementType, this.ary);
for (var i = 0; i < otherAsArray.length; i++) {
oReturn.add(otherAsArray[i]);
}
return oReturn;
},
//Returns a new u_GenericSet containg the elements in this set that are not in the other
difference: function (otherSet) {
if (otherSet.type != "u_GenericSet") {
throw "Called difference() on u_GenericSet with a parameter that was not a u_GenericSet type object.";
}
var inThisSetButNotInOtherSet = [];
for (var i = 0; i < this.ary.length; i++) {
if (!otherSet.contains(this.ary[i])) {
inThisSetButNotInOtherSet.push(this.ary[i]);
}
}
return new u_GenericSet(this.elementType, inThisSetButNotInOtherSet);
},
//Returns a new u_GenericSet containing elements that are members of both sets
intersection: function (otherSet) {
if (otherSet.type != "u_GenericSet") {
throw "Called intersection() on u_GenericSet with a parameter that was not a u_GenericSet type object.";
}
var inBothSets = [];
var baseSet;
var foreignSet;
//Use the smallest set as the base set to minimize number of comparisons/iterations required
if (this.ary.size() < otherSet.size()) {
baseSet = this;
foreignSet = otherSet;
} else {
baseSet = otherSet;
foreignSet = this;
}
var baseIter = baseSet.getIterator();
while (baseIter.hasNext()) {
var val = baseIter.getValue();
if (foreignSet.contains(val)) {
inBothSets.push(val);
}
baseIter.next();
}
return new u_GenericSet(this.elementType, inBothSets);
},
// Returns a boolean
isEmpty: function () {
return this.ary.length == 0;
},
// Empties all elements
purgeAll: function () {
this.ary = [];
},
// Returns a comma separated list in a String
toString: function () {
return this.ary.toString();
},
//Creates a deep copy to avoid inadvertent modification of the original
toArray: function () {
var ret = [];
for (var i = 0; i < this.ary.length; i++) {
ret.push(this.ary[i]);
}
return ret;
},
getIterator: function () {
var current = undefined;
var store = this.ary;
function hasNext() {
if (store.length == 0) {
return false;
}
if (current == undefined) {
current = 0;
}
if (current < store.length) {
return true;
} else {
return false;
}
}
function next() {
var val = store[current];
current++;
return val;
}
function getValue() {
return store[current];
}
return { next: next, getValue: getValue, hasNext: hasNext };
},
type: 'u_GenericSet'
}
https://www.servicenow.com/community/north-texas-snug/u-genericset-data-structure/ba-p/2285361