Javascript Data Structures, an argument for deprecating the ArrayUtil

treycarroll · ‎11-12-2015

I come from a Java and C# background so, as much as I love the power of Javascript, there are some significant gaps that leave me longing for those other languages. One of the "biggies" is the lack of data structures. Javascript arrays are these odd "everything" structures. After programming in Javascript for a while, we become accustomed to using arrays as: arrays (of course), lists, queues, stacks and sets. But implementations of those abstract data-types have some very specific characteristics and therefore should provide certain required operations, while very intentionally eschewing other operations.

But the real question is, "Are we missing out as Javascript programmers because our language doesn't natively support these ADTs?" I would give a pragmatic answer: "It depends." I don't really mind using the array functions to simulate Stacks and Queues, but some of the other ADTs are problematic. Let's walk through some examples to see how this plays out.

To create a Javascript Stack we can very easily do the following:

var stack = [];
stack.push('vanilla');
stack.push('chocolate');
stack.push('strawberry');
var sb = stack.pop();
alert(sb);   //this will output 'strawberry'

Stacks are LIFO (Last-in First-out) data structures, so pop() gives us back strawberry, which was added last. This works great! Even the names of the methods, "push" and "pop" are conceptually correct. We'll just overlook the fact that you could do this.

alert( stack[0] );//This should not be possible on a true stack

To create a Javascript Queue we can do this:

var queue = [];
queue.push('vanilla');
queue.push('chocolate');
queue.push('strawberry');
var v = queue.shift();
alert(v);   //this will output 'vanilla'

Queues are FIFO (First-in First-out) data structures, so shift() gives us back vanilla, which was added first. So it works, but this is not quite as nice as when we used an array as a Stack. The correct name for the operation for adding an element to a Queue should be enqueue(), not push(). (This is not a Stack!) Similarly, Javascript arrays' way of getting something out of a queue is called shift(), but it should be called dequeue().

And again, we can violate the structure's conceptual accessors and grab something off of the back end using code like this:

var evilAccessElement = queue[queue.length - 1];

Once we get to the Set data type, however, things really break down. The characteristics of a Set mean that it:

Must not allow duplicate elements,
Must only support insert() and delete() with no provision for adding or removing at an index,
Must offer union(), difference() and intersection() operations.

Our humble Javascript array was doing fairly well up to this point, but now it is hopelessly inadequate to mimic the desired data type. But do we really need Sets for ServiceNow coding? I would argue yes.

How many times have you had to remove duplicates from an array? Have you ever loaded a user's roles from sys_user_has_roles? Sure we can write a GlideAggregate query that groups by the role's sys_id to eliminate the duplicates, but what if the data structure could just quietly disregard the addition of redundant elements while we iterated over the elements after running the simple query? And what about the power of intersections, unions and differences? If we take the example of working with groups of approvers (this is a frequent use-case in our development of catalog items), the power becomes clear. Storing the approvers' ids in arrays forces you to repeatedly, painstakingly re-implement comparison code which could have been written (and tested!) once as a part of the data structure itself.

As Michael Ritchie has pointed out, ServiceNow provides the ArrayUtil to support the use of Javascript's array type in situations where Set-like behaviors are required. I have used the ArrayUtil and I am sincerely grateful to our friends at ServiceNow for providing us with tools, but I am not a huge fan of the ArrayUtil/array-as-a-Set paradigm for a few reasons:

1) I want the data structure to throw an exception if I accidentally add an element of the wrong type or attempt to use it incorrectly. But even if I do something catastrophically wrong, such as providing a string in place of the required array-type first parameter of indexOf(), the ArrayUtil does not throw an exception. Instead, it returns the -1 (not found) flag. That behavior leads me to believe that my call was well formed and that the desired element just isn't there. But, how are we going log and handle errors, if we can't detect them? The human who raises an INC becomes our only "catch" mechanism!

var x = [1, 2, 3];
var util = new ArrayUtil();
try{     
     gs.print(util.indexOf("This should be an array not a string", "1"));//This outputs -1!
} catch(e){
     gs.print('Error:'+e);
}

Similarly, the concat method is oddly tolerant when I do this:

//Outputs *** Script: This should be an array not a string
//Does not throw an error
var x = [1, 2, 3];
var util = new ArrayUtil();
try{
     gs.print(util.concat("This should be an array not a string", x));
} catch(e){
     gs.print('Error:'+e);
}

2) It allows you to perform set operations on arrays of wildly different type elements:

var arrayUtil = new ArrayUtil();
var a1 = ["1","2","3","4","5"];
var a2 = [{foo:'bar'}];
var a3 = [undefined,null,3,'string'];
gs.print(arrayUtil.diff(a1, a2, a3)); //*** Script: 1,2,3,4,5

While this is not an error per se, it silently (complicitly?) tolerates meaningless comparisons.

3) The implementation of the indexOf() method returns inconsistent results when the array contains string and number versions of the same value.

var x = [1, "1"];
var util = new ArrayUtil();
gs.print(util.indexOf(x, "1"));//This returns 0, even though the string   "1" is at index 1!

4) The wiki article documenting its use contains errors and omissions.

indexOf

indexOf (Array array, [int startIndex]);

arrayUtil.indexOf(a1, "b"));//The parameter "b" doesn't look much like a start index!

ensureArray and convertArray

There is no documentation for the ensureArray or convertArray methods. Given that objects can have complex, nested properties, how would theses conversions work?

5) It blurs the lines between the list and set data types.

It supports retrieval of indices suggesting a List data type.
It supports intersection|difference|union operations suggesting a Set data type.
You can change conceptual data structures suddenly. The structure (an array) tolerates duplicates, but then removes them when you call unique. What was the data-type before the call to unique? What is it after the call?

6) It violates Solid OO Design principles.

Putting the state into one object and behaviors into another just doesn't make sense.

7) Lastly, and perhaps most importantly: The ArrayUtil is not available on the client.

No client scripts can make immediate use of unique(), intersection(), diff(), union(), indexOf(), etc. If you include this code in a client script, it will error out:

var arrayUtil = new ArrayUtil();

It is possible to use the ArrayUtil methods by creating a client-callable Script Include to wrap the operations and make them available on the client, however, the inherent network latency involved in making an ajax call means that there will always be a noticeable lag while the result is retrieved.

For these reasons I found that it made sense to create a separate, new u_GenericSet data type. The structure is "generic" in the sense of Java generics, in which collections are permanently typed at construction, and which throw exceptions when passed parameters of an incorrect type.

// 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 (elementType == undefined || elementType == null || 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 && array.length ) {
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;
},
//Returns an object with functions: next(), hasNext(), and getValue();
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'
}

Exaples of usage:

Intersection:

//If we ever need to find the set of items that belong to both set a AND set b, we can use the intersection() method.
var a = new u_GenericSet('number',[2002,2004,2006]); 
for(var i = 0; i < 1000; i++){ 
     a.add(i); 
} 
var b = new u_GenericSet('number', [3,6,9]); 
for(var j = 2000; j < 5000; j++){ 
     b.add(j); 
} 
var res = a.intersection(b); 
gs.print(res.toString());

There are thousand of elements in these sets, but they only share these few elements:

Union:

//If we ever need to find the set of elements that are in set a OR in set b we can take the set union of the two sets
var a = new u_GenericSet('number'); 
for(var i = 0; i < 10; i++){ 
     a.add(i); 
} 
var b = new u_GenericSet('number'); 
for(var j = 5; j < 15; j++){ 
     b.add(j); 
} 
var res = a.union(b); 
gs.print(res.toString());

Notice that even though 5-10 were in both, they only appear in the resulting Set once.

Difference:

//If we ever need to find elements that are in set a, but not in set b we can take the set difference
var a = new u_GenericSet('number'); 
for(var i = 0; i < 10; i++){ 
     a.add(i); 
} 
var b = new u_GenericSet('number'); 
for(var j = 7; j < 20; j++){ 
     b.add(j); 
} 
var res = a.difference(b); 
gs.print(res.toString());

Only 0-6 were in Set a and not in Set b. 7-10 were in Set b, so they were removed from the result set. 11-19 were never even checked; since they were not in Set a, we automatically discarded them.

So there you have it: a Generic Set data structure that you can use for your Service-Now development. Enjoy! Make sure that you wrap your code in try/catch blocks and handle the exceptions that it throws when you pass the wrong type elements into it. The really nice thing about this class is that it will work both from client code and from server code. I have it loaded as a global UI Script so that I can use it from any client script. I am also using it as a server-side script include. I really like the result, since I can now use a u_GenericSet from any script without having to change gears between client and server scripts.

If you like this article, make sure that you check out my post on a Map/Dictionary for Client and Server side use in ServiceNow code: A Map Data Type for ServiceNow

Happy coding. We work on an amazing platform. Enjoy it!