Blake O'Hare .com

.NET/Java-Style Collections for JavaScript

Let's face it, arrays in JavaScript are just willy nilly and I feel a cold chill each time I'm forced to use them. The associative arrays only allow you to use strings as keys. Contrast that to the multitude of robust collections available in the .NET library. Dictionaries can have keys that are any type, such as arbitrary objects or integers that aren't an ordered index. And if you start removing items from the middle of a list, they should affect the computed length of the array the way God intended, which .length doesn't do so well. So here I offer a re-implementation of the .NET collections (which are similar enough to the Java collections) in JavaScript.

...because sometimes, you just really need an actual dictionary object.

This implementation includes the following:
  • List
  • Stack
  • Queue
  • HashSet
  • Dictionary

Additionally, all these collections implement GetEnumerator.

I've sanity tested all the methods on each collection type, but I do not guarantee it is completely bullet-proof. If you run in to issues, let me know and I will fix them as soon as possible.

/*
  JavaScript collections that roughly mimic the functionality
  of the .NET or Java collection classes
  
  Written by Blake O'Hare, King of the Internet
  www.nerdparadise.com | www.blakeohare.com
  
  Released under the Go-ahead-and-steal-this-I-don't-really-care License v2
  
  Instructions:
    Create a new collection by calling the proper factory method.
    var myStack = newStack();
    
    You can also supply initial values if you wish:
    var myHashSet = newHashSet([1, 2, 3, 4, 5]);
    
    Initial values for dictionaries are associative arrays. 
    All others accept a 1-dimensional array.
    
    YES - you may use ANY type of object as a dictionary or hashset key. However,
    in order to get the O(1) lookup time, you must enable _collections_enable_object_tagging
    by setting it to true which is the first line of code (this is done by default). 
    Because JavaScript offers no way of creating unique hashes of unique objects, a 
    field is added to Objects (and only objects, strings and numbers are unaffected)
    used as keys in dictionaries and hash sets called __objectKeyId. If this is not 
    acceptable, you can set this to value to false to keep your objects unaffected. 
    Under normal circumstances this should not affect the behavior of your code unless 
    you write a loop that iterates through object keys. 
    
    The following methods are implemented:
    
    .Add(item) - adds an item to the collection (at the end for lists)
    [List, HashSet]
    
    .AddRange(array of items) - adds the list of items to the collection
    [List, HashSet]
    
    .Add(key, item) - adds the item to a dictionary
    [Dictionary]
    
    .Count - a property (not a method) that is the number of items in the collection
    [All]
    
    .ItemAt(index) - random access for an item in an ordered list. This is the alternative
            for "bracket" access such as var item = list[4];
    [List, Stack, Queue]
    
    .GetValue(key) - returns the value stored in the dictionary with the key.
            If the key is not present an exception is thrown
    [Dictionary]
    
    .TryGetValue(key, reference to an array) - if the item with the given key is present
            this method will return true and apply the item to index 0 of the array.
            Otherwise, false is returned and the array is unmodified.
    [Dictionary]
    
    .IndexOf(item) - returns the index of the item if it is present in the ordered list.
            returns -1 if it is not found.
    [List, Stack, Queue]
    
    .Keys() - returns an array of all the keys in a dictionary or hash set.
    [Dictionary]
    
    .ToArray() - returns a regular JavaScript array of the items in the ordered list
    [List, Stack, Queue]
    
    .Contains(item) - returns a boolean if the item is in the collection
    [List, Stack, Queue, HashSet]
    
    .ContainsKey(key) - returns a boolean if the key is used in the dictinoary
    [Dictionary]
    
    .ContainsValue(item) - returns a boolean if the value appears in the dictionary
    [Dictionary]
    
    .GetEnumerator() - returns an enumerator object that will traverse all items in the
              collection. Once the collection is modified after the enumerator
              is created, the enumerator is no longer valid and will throw
              an exception.
              The enumerator index starts at -1 so .MoveNext must be called
              upon it.
              Enumerators will work for unordered collections (HashTables and
              Dictionaries) internally using the key list as the traversal list
              and returns the values stored at those keys.
              See enumerator methods below
    [All]
    
    enumerator.MoveNext() - moves the enumerator to the next index. Returns true if the
              enumerator is still in the range of the list. Returns false if
              the enumerator has finished traversing all items.
    enumerator.Reset() - moves the index of the enumerator back to -1
    enumerator.Current() - returns the current item when the enumerator is in a valid state.
    
    
    .Remove(item) - will remove the item if it is in the collection. Returns true if it
            was present.
    [All]
    
    .RemoveAt(index) - will remove the item located at the given index in an ordered list
    [List, Stack, Queue]
    
    .Insert(index, item) - will insert the item at the given index
    [List, Stack, Queue]
    
    .InsertRange(index, items) - will insert the given items at the given index
    [List, Stack, Queue]
    
    .Clear() - will remove all items from the collection
    [All]
    
    .Push(item) - will add an item to the top of the stack
    [Stack]
    
    .Pop() - will return and remove the at the top of the stack
    [Stack]
    
    .Enqueue(item) - will add an item to the end of a queue
    [Queue]
    
    .Dequeue() - will remove and return the item at the front of a queue
    [Queue]
    
*/

// Factory methods. The initialValues is an optional parameter
function newStack(initialValues) { return ___newCollection('stack', initialValues); }
function newQueue(initialValues) { return ___newCollection('queue', initialValues); }
function newList(initialValues) { return ___newCollection('list', initialValues); }
function newEnumerable(initialValues) { return ___newCollection('enumerable', initialValues); }
function newHashSet(initialValues) { return ___newCollection('hashset', initialValues); }

// for dictionaries, initial values is an associative array
function newDictionary(initialValues) { return ___newCollection('dictionary', initialValues); }

// when using objects as keys, they need to be tagged with an ID number
// this tag is applied to the object as a key called "__objectKeyID" which
// should not affect outside code unless you iterate through keys on these objects
var _collections_enable_object_tagging = true;

var _collections_next_object_key_ID = 0;

function ___newCollection(type, initialValues)
{
  var collection = {}
  collection['Count'] = 0;
  var orderedList = !(type == 'hashset' || type == 'dictionary');
  
  var keyList = [];
  var keyListValid = true;
  var transactionId = 0;
  
  var getBucket = orderedList ? 0 : function(key)
  {
    if (key === null) return null;
    if (key === undefined) return null;
    
    var type = typeof(key);
    if (type == "number") return "#" + key;
    if (type == "string") return "$" + key;
    if (type == "boolean") return "!" + key;
    if (type == "function") return "@" + key;
    
    var newKey = '&';
    if (_collections_enable_object_tagging)
    {
      if (key['__objectKeyId'] === undefined)
      {
        key['__objectKeyId'] = _collections_next_object_key_ID;
        _collections_next_object_key_ID++;
      }
      newKey += key['__objectKeyId'];
    }
    return newKey;
  }
  
  var items = orderedList ? [] : {};
  
  // Add
  if (orderedList)
  {
    if (type != 'queue' && type != 'stack')
    {
      collection['Add'] = function(item)
      {
        transactionId++;
        items.push(item);
        collection['Count']++;
      }
    }
  }
  else
  {
    var add = function(key, value)
    {
      var stringKey = getBucket(key);
      if (items[stringKey])
      {
        var bucketLength = items[stringKey].length;
        var exists = false;
        
        for (var i = 0; i < bucketLength; ++i)
        {
          if (items[stringKey][i][0] === key)
          {
            exists = true;
            break;
          }
        }
        
        if (exists)
        {
          throw("Duplicate key: " + key);
        }
        
        items[stringKey].push([key, value]);
        keyList.push(key);
      }
      else
      {
        items[stringKey] = [[key, value]];
        keyList.push(key);
      }
      transactionId++;
      collection['Count']++;
    }
    
    if (type == 'hashset')
    {
      collection['Add'] = function(item)
      {
        add(item, 1);
      }
    }
    else if (type == 'dictionary')
    {
      collection['Add'] = function(key, item)
      {
        add(key, item);
      }
    }
  }
  
  // AddRange
  if (orderedList)
  {
    if (type != 'queue' && type != 'stack')
    {
      collection['AddRange'] = function(newItems)
      {
        for (var i = 0; i < newItems.length; ++i)
        {
          collection.Add(newItems[i]);
        }
      }
    }
  }
  else if (type == 'hashset')
  {
    collection['AddRange'] = function(newItems)
    {
      for (var i = 0; i < newItems.length; ++i)
      {
        collection.Add(newItems[i]);
      }
    }
  }
  
  // ItemAt
  if (orderedList)
  {
    collection['ItemAt'] = function(index)
    {
      return items[index];
    }
  }
  
  // GetValue
  if (type == 'dictionary')
  {
    var getValueImpl = function(key)
    {
      var bucket = getBucket(key);
      if (items[bucket])
      {
        for (var i = 0; i < items[bucket].length; ++i)
        {
          if (items[bucket][i][0] === key)
          {
            return [true, items[bucket][i][1]];
          }
        }
      }
      
      return [false];
    }
    
    collection['GetValue'] = function(key)
    {
      var value = getValueImpl(key);
      if (value[0])
      {
        return value[1];
      }
      
      throw("Key not found: " + key);
    }
    
    collection['TryGetValue'] = function(key, arrayReference)
    {
      var value = getValueImpl(key);
      if (value[0])
      {
        // cheesy, yes. 
        arrayReference[0] = value[1];
        return true;
      }
      
      return false;
    }
  }
  
  
  // IndexOf
  if (orderedList)
  {
    collection['IndexOf'] = function(item)
    {
      var length = items.length;
      for (var i = 0; i < length; ++i)
      {
        if (item === items[i])
        {
          return i;
        }
      }
      return -1;
    }
  }
  
  // Keys
  if (!orderedList)
  {
    var getKeys = function()
    {
      if (!keyListValid)
      {
        var newKeyList = [];
        for (bucket in items)
        {
          for (var i = 0; i < items[bucket].length; ++i)
          {
            keyList.push(item[bucket][i][0]);
          }
        }
        keyList = newKeyList;
        keyListValid = true;
      }
      return keyList.slice(0);
    };
    if (type == 'dictionary')
    {
      collection['Keys'] = getKeys;
    }
  }
  
  // ToArray
  if (orderedList)
  {
    collection['ToArray'] = function()
    {
      return items.slice(0);
    }
  }
  
  // Contains
  if (orderedList)
  {
    collection['Contains'] = function(item)
    {
      return collection.IndexOf(item) > -1;
    }
  }
  else
  {
    
    // Contains Key
    var containsThing = function(value, pairItem)
    {
      for (bucket in items)
      {
        for (var i = 0; i < items[bucket].length; ++i)
        {
          if (items[bucket][i][pairItem] === value)
          {
            return true;
          }
        }
      }
      return false;
    }
    
    if (type == 'hashset')
    {
      collection['Contains'] = function(key) { return containsThing(key, 0); };
    }
    else if (type == 'dictionary')
    {
      collection['ContainsKey'] = function(key) { return containsThing(key, 0); };
    }
    
    // Contains Value
    if (type == 'dictionary')
    {
      collection['ContainsValue'] = function(value) { return containsThing(value, 1); };
    }
  }
  
  
  // GetEnumerator
  if (orderedList)
  {
    collection['GetEnumerator'] = function()
    {
      var enumeratorCreator = function(validTag)
      {
        var index = -1;
        var validAsOf = validTag;
        var enumerator = {
          'MoveNext' : function() {
            index++;
            return items.length > index;
          },
          'Current' : function()
          {
            if (index < 0)
            {
              throw("The enumerator is positioned before the first element.");
            }
            else if (validAsOf != transactionId)
            {
              throw("The collection was modified after the enumerator was created.");
            }
            else if (items.length > index)
            {
              return items[index];
            }
            else
            {
              throw("Enumerator has moved passed the end of the collection.");
            }
          },
          'Reset' : function()
          {
            index = 0;
          }
        };
        return enumerator;
      }
      
      return enumeratorCreator(transactionId);
    }
  }
  else
  {
    var isHash = type == 'hashset';
    
    collection['GetEnumerator'] = function()
    {
      var enumeratorCreator = function(validTag)
      {
        var index = -1;
        var validAsOf = validTag;
        var keys = getKeys();
        var enumerator = {
          'MoveNext' : function() {
            index++;
            return keys.length > index;
          },
          'Current' : function()
          {
            if (index < 0)
            {
              throw("The enumerator is positioned before the first element.");
            }
            else if (validAsOf != transactionId)
            {
              throw("The collection was modified after the enumerator was created.");
            }
            else if (keys.length > index)
            {
              return isHash ? keys[index] : collection.GetValue(keys[index]);
            }
            else
            {
              throw("Enumerator has moved passed the end of the collection.");
            }
          },
          'Reset' : function()
          {
            index = 0;
          }
        };
        return enumerator;
      }
      
      return enumeratorCreator(transactionId);
    }
  }
  
  // Remove
  if (orderedList)
  {
    collection['Remove'] = function(item)
    {
      var index = collection.IndexOf(item);
      
      if (index == -1) return false;
      
      collection.RemoveAt(index);
      return true;
    }
  }
  else
  {
    collection['Remove'] = function(key)
    {
      var bucketName = getBucket(key);
      
      if (items[bucketName])
      {
        for (var i = 0; i < items[bucketName].length; ++i)
        {
          if (items[bucketName][i][0] === key)
          {
            keysListValid = false;
            collection['Count']--;
            
            if (items[bucketName].length == 1)
            {
              delete collection[bucketName];
            }
            else if (i == 0)
            {
              items[bucketName] = items[bucketName].slice(1);
            }
            else if (i == items[bucketName].length - 1)
            {
              items[bucketName] = items[bucketName].slice(0, items[bucketName].length - 1);
            }
            else
            {
              var left = items[bucketName].slice(0, i);
              var right = items[bucketName].slice(i + 1);
              for (var j = 0; j < right.length; ++j)
              {
                left.push(right[j]);
              }
              items[bucketName] = left;
            }
            
            transactionId++;
            return true;
          }
        }
      }
      return false;
    }
  }
  
  // RemoveAt
  if (orderedList)
  {
    collection['RemoveAt'] = function(index)
    {
      if (index < 0 || index >= items.length)
      {
        throw("Index out of range");
      }
      
      if (items.length == 1)
      {
        items = [];
      }
      else if (index == 0)
      {
        items = items.slice(1);
      }
      else if (index == items.length - 1)
      {
        items = items.slice(0, items.length - 1);
      }
      else
      {
        var a = items.slice(0, index);
        var b = items.slice(index + 1);
        items = a;
        for (var i = 0; i < b.length; ++i)
        {
          items.push(b[i]);
        }
      }
      
      transactionId++;
      collection['Count'] = items.length;
    }
  }
  
  // Insert
  if (orderedList)
  {
    if (type != 'queue' && type != 'stack')
    {
      collection['Insert'] = function(index, item)
      {
        collection.InsertRange(index, [item]);
      }
    }
  }
  
  // InsertRange
  if (orderedList)
  {
    if (type != 'queue' && type != 'stack')
    {
      collection['InsertRange'] = function(index, newItems)
      {
        if (items.length == 0)
        {
          transactionId++;
          items = newItems.slice(0);
          collection['Count'] = items.length;
          return;
        }
        
        if (items.length < index || index < 0)
        {
          throw("Index out of range");
        }
        
        var left = index == 0 ? [] : items.slice(0, index);
        var right = index == items.length ? [] : items.slice(index);
        for (var i = 0; i < newItems.length; ++i)
        {
          left.push(newItems[i]);
        }
        for (var i = 0; i < right.length; ++i)
        {
          left.push(right[i]);
        }
        items = left;
        transactionId++;
        collection['Count'] = items.length;
      }
    }
  }
  
  // Clear
  if (orderedList)
  {
    collection['Clear'] = function()
    {
      transactionId++;
      items = [];
      collection['Count'] = 0;
    }
  }
  else
  {
    collection['Clear'] = function()
    {
      transactionId++;
      items = {};
      keyList = [];
      keyListValid = true;
      collection['Count'] = 0;
    }
  }
  
  if (orderedList)
  {
    collection['Reverse'] = function()
    {
      transactionId++;
      items = items.reverse();
    }
  }
  
  if (type == 'stack')
  {
    // Push
    collection['Push'] = function(item)
    {
      transactionId++;
      items.push(item);
      collection['Count'] = items.length;
    }
    
    // Pop
    collection['Pop'] = function()
    {
      if (items.length == 0)
      {
        throw("Cannot pop an empty stack");
      }
      var value = items.pop();
      collection['Count'] = items.length;
      return value;
    }
  }
  
  if (type == 'queue')
  {
    // Enqueue
    collection['Enqueue'] = function(item)
    {
      transactionId++;
      items.push(item);
      collection['Count'] = items.length;
    }
    
    // Dequeue
    collection['Dequeue'] = function()
    {
      if (items.length == 0)
      {
        throw("Cannot dequeue from an empty queue");
      }
      
      var value = items[0];
      items = items.slice(1);
      collection['Count'] = items.length;
      return value;
    }
  }
  
  if (initialValues !== undefined)
  {
    if (orderedList || type == 'hashset')
    {
      for (var i = 0; i < initialValues.length; ++i)
      {
        collection.Add(initialValues[i]);
      }
    }
    else if (type == 'dictionary')
    {
      for (var key in initialValues)
      {
        collection.Add(key, initialValues[key]);
      }
    }
  }
  
  return collection;
}