DailyJS

DailyJS

The JavaScript blog.


AuthorJustin Naifeh
Featured

reflection dynamic invocation method

Dynamic Invocation Part 1: Methods

Posted on .

Today we will explore dynamic invocation, which is a clever way of saying "invoke a method using the string method name." Many people, including myself, refer to this as reflection, which is terminology borrowed from Java's Reflection library. Because we don't want to be sued, especially on a Friday, this will be known as dynamic invocation in the article, although it probably goes by other names.

JavaScript benefits from dynamic invocation because the capability is intrinsic to the language; no library is required. This means we can leverage dynamic invocation in all JavaScript environments! The question is...how?

The Interview Question

This is one of many interview questions I created at my company to test a developer's knowledge of the JavaScript language.

We start with a basic domain class called Employee.

Employee_UML

In case you want to float code in your head or test it yourself, here's the (optional) reference implementation.

/**
 * Constructor for the Employee class.
 * @param String name The full name of the employee.
 * @param String position The employee's position.
 */
var Employee = function(name, position) {  
  this._name = name;
  this._position = position;
};

Employee.prototype = {  
  /**
   * @return String The Employee's name.
   */
  getName: function() {
    return this._name;
  },

  /**
   * @return String The Employee's position.
   */
  getPosition: function() {
    return this._position;
  },

  /**
   * Promotes an Employee to a new position.
   * @param String The Employee's new position.
   */
  promote: function(newPosition) {
    this._position = newPosition;
  }
};

We assume the following instance of Employee for the question:

var emp = new Employee("Tom Anders", "junior developer");  

After years of hard work, Tom Anders has been promoted to "senior developer," which must be evaluated by the code. The application in which this is hosted, due to its architecture, does not have direct knowledge of the promote() method. Instead, only the method name is known as a string. Given the following code setup, how does one promote Tom to senior developer?

var emp = new Employee("Tom Anders", "junior developer");

// ...

var method = "promote";  
var newPosition = "senior developer";

// promote emp [Tom] to the position of newPosition
// ...???

How would you execute promote() in the context of emp?

There are two answers, both of which are correct, although one is more dynamic and powerful than the other.

The first answer casts the mantra eval is evil aside in the name of convenience. By concatenating the variable name with the method name and input a developer can promote the employee.

eval("emp."+method+"(\""+newPosition+"\")");  
console.log(emp.getPosition()); // "senior developer"  

This works...for now. But keep in mind that not only is the arbitrary execution of code insecure, new variables cannot be created by eval() in ES5's strict mode. The solution will not scale over time.

Without eval() how could we possibly invoke the method? Remember that methods are like any other properties, and once attached to the object or its prototype it becomes accessible via bracket notation.

console.log(emp["promote"] === emp[method]); // true  
console.log(emp[method] === emp.promote); // true  
console.log(emp[method] instanceof Function); // true  

Knowing this we can dynamically invoke the method with the arguments we want.

emp[method](newPosition);  
console.log(emp.getPosition()); // "senior developer"  

This style of invocation is effective but vanilla. It assumes the number of arguments are known and the this context is the object referencing the method. This is only the tip of the iceberg, for invocation can be much more dynamic when the arguments and this context are unknown beforehand.

Before advancing, note that each object has an implicit property that references its defining class's prototype, thus solidifying the relationship between a class and its instances.

console.log(emp.promote === Employee.prototype.promote); // true  
console.log(emp.__proto__ === Employee.prototype); // true  
console.log(emp.__proto__.promote === Employee.prototype.promote); // true  

With this in mind, we can combine class, prototype, and object references with the string method to achieve truly dynamic invocations. This will help us demystify calls ubiquitous in framework and library code (e.g., Array.prototype.slice.call(arguments, 0, arguments.length)).

call() and apply()

Just as the class Employee defines promote(), the class Function defines methods call() and apply(), which are methods on methods. In other words, methods--instance/member functions--are first-class objects in JavaScript, hence its functional nature!

The methods call() and apply() take the same first argument, the this context of execution. The second argument of call() is n-arguments in explicit order, while apply() takes a single array where each element is an argument that is flattened in order as if call() were applied. Using the class's prototype we can statically access methods yet execute them with a specific context.

// call
Employee.prototype[method].call(emp, newPosition);

// apply
Employee.prototype[method].apply(emp, [newPosition]);

console.log(emp.getPosition()); // "senior developer"  

This syntax can also be used with the object itself because emp[method] === Employee.prototype[method].

// call
emp[method].call(emp, newPosition);

// apply
emp[method].apply(emp, [newPosition]);

console.log(emp.getPosition()); // "senior developer"  

It might seem redundant to specify the context as emp when invoking promote() on that object, but this is the required syntax, and it allows for variable arguments.

Regardless of the syntax used, dynamic invocation is extremely flexible and introspective. Once the class, prototype, object, and property relationships are understood, a developer can manipulate the language and its constructs in clever ways. Unsolvable problems become solvable.

Conclusion

Dynamic invocation is useful when generating JavaScript code from the server or when matching aspect-oriented rules. And sometimes it's just helpful to avoid the rightfully deprecated eval().

In part 2 I will go into detail about dynamic invocation and constructors.

Featured

software design command query separation

Command-Query Separation in Practice

Posted on .

Let's end the week by learning about a software design principle that is easy to follow, yet a violation of it can cause bugs and coincidental correctness.

Command-query Separation (CQS) is the principle by which a method is defined to perform a query, execute a command, but never both. A query returns information about the state of the system, which can include anything from primitive data to objects, or even complex aggregation results. A command, on the other hand, changes the state of the system, usually by writing (persisting) modified objects or data. If we are working with a domain to manage Person objects a query method to find a person by name could be PersonQuery.find(name), and a command to persist an instance could be Person.apply().

Normal Violations

While CQS is a sensible principle, it is violated in everyday practice. This is not as troublesome as it sounds, depending on the type of violation. Strict adherence to CQS makes some methods impossible such as query methods that count the number of invocations, thus allowing a developer to query the number of queries.

/**
 * Finds a user by name and increments the
 * query counter.
 * @return the found Person or null if one was not found
 */
PersonQuery.prototype.find = function(name) {  
  this._queriesPerformed++;

  // get the Person from the datasource or null if not found
  var person = this.dataSource.find("Person", name);
  return person;
};

/**
 * @return the number of queries performed.
 */
PersonQuery.prototype.getQueriesPerformed = function() {  
  return this._queriesPerformed;
};

We could create an incrementQueriesPerformed() method instead of incrementing the counter within find(), but that would be excessive and burden the calling code.

// now the developer must synchronize the state of PersonQuery. Yikes!
var person = personQuery.find("someuser");  
personQuery.incrementQueryiesPerformed();  

In practice, CQS is rarely taken in its pedantic form because doing so would make certain types of batched/transactional calls cumbersome. Also, multi-threaded and asynchronous tasks would be difficult to coordinate.

Two classic violations are the Stack.pop() and HashMap.remove() methods as was the case in the LinkedHashMap article (inspired by Java's Map interface).

var map = new LinkedHashMap();  
map.put('myNum', 5);

// ...

var val = map.remove('myNum');  
alert(val); // prints "5"  

The remove() method is both a command and query because it removes the value associated with the key (command) and returns the value, if any, that was associated with the key (query). While the violation is subtle, the same behavior could have been implemented with a remove():void method.

var map = new LinkedHashMap();  
map.put('myNum', 5);

// ...

var val = map.get('myNum');  
map.remove('myNum');  
alert(val); // prints "5"  

As with many instances, the code to avoid CQS violation is clunky and overkill.

Although there are often violations of CQS at the method scale, many libraries violate CQS as an integral approach to their API design by combining both getter and setter behavior within the same method.

var person = new Person("someuser");

// one possibility
person.enabled(true); // set enabled to true  
var enabled = person.enabled(); // return true

// another possibility
person.value('enabled', true); // set enabled to true  
var enabled = person.value('enabled'); // return true  

I personally do not prefer this flavor of behavior overloading--instead recommending getEnabled() and setEnabled(Boolean)--but as long as the API is intuitive and documented then it's generally not a problem.

Dangerous Violations

There are, however, instances where CQS violations cause side effects that can be difficult to debug. This usually happens when code tries to be too clever or helpful by merging command and query behavior.

Consider the following code to query and create a Person:

var person = personQuery.find("someuser");  
if (person === null) {  
  person = new Person("someuser");
  person.apply(); // persisted
  console.log("Created the Person ["+person+"]");
} else {
  console.log("Person ["+person+"] already exists.");
}

The code attempts to find a Person and create one if it does not exist; further calls to find() will correctly return the Person. The logic is trivial and easy to understand, but imagine that a developer decides to reduce the effort by changing find() to create a Person if a result is not found.

PersonQuery.prototype.find = function(name) {  
  var person = this.dataSource.find("Person", name);

  if (person === null) {
    person = new Person(name);
    person.apply();
  }

  return person;
};

It can be argued that by combining both query and command behavior into find(), calling code can remove the if/else checks for null, thus making it simplier.

var person = personQuery.find("someuser");  
console.log("Person ["+person+"] exists.");  

The amount of code has been reduced, but we must consider other circumstances in which find() will be called.

As an example, when a user is creating a new Person via a standard HTML form, the system calls find() to ensure the name is not already taken. When find() was just a query method it could be called any number of times without affecting the system. But now it creates the Person it is attempting to find so a uniqueness constraint violation will occur.

// request one
var person = personQuery.find("newuser"); // returns newuser  
if (person !== null) {  
  alert("The name is already taken.");
}

// ... however, in a second request

// request two
var person = personQuery.find("newuser"); // Error (duplicate name)  
if (person !== null) {  
  // we can never reach this
  alert("The name is already taken.");
}

By adding command behavior to find(), the developer has accidentally broken the code. The original post-condition, the condition known to the code at the time, changed from returns null if no match was found to creates a Person and returns it if no match was found. Now the developer must spend time to refactor the original code, but maybe it's legacy or outside of his or her control. Care must be taken when changing method conditions.

One solution is to name the method more aptly to describe its behavior: PersonQuery.findOrCreate(). Then the method find() could be added as a pure query alternative, and calling code can choose which one to invoke under the circumstances.

Another solution is to not change find() at all. It worked before, and it will work in the future.

Conclusion

Strict adherence to CQS is nearly impossible to achieve in normal application programming, although some special applications might require such an architecture.

What should be kept in mind is that a looser definition of CQS is valid and useful in practice. A method should stick to being a command or query, but if both behaviors are needed the method name should reflect its dual nature and a non-query/command alternative should be offered.

Featured

pattern object-oriented decorator

Decorating Your JavaScript

Posted on .

The decorator pattern, also known as a wrapper, is a mechanism by which to extend the run-time behavior of an object, a process known as decorating. The pattern is often overlooked because its simplicity belies its object-oriented benefits when writing scalable code. Decorating objects is also neglected in JavaScript because the dynamic nature of the language allows developers to abuse the malleability of objects, but just because you can doesn't mean you should.

Before delving into the decorator pattern, let's examine a realistic coding problem that can be solved with other solutions. The decorator is best understood after the shortcomings of other common solutions have been explored.

The Problem

You are writing a simple archiving tool that manages the display and lifecycle of publications and their authors. An important feature is the ability to list the contributing authors, which may be a subset of all authors. The default is to show the first three authors of any publication. The initial domain model is basic:

domain

Using plain JavaScript we implement the read-only classes as follows:

/**
 * Author constructor.
 *
 * @param String firstName
 * @param String lastName
 */
var Author = function(firstName, lastName) {  
  this._firstName = firstName;
  this._lastName = lastName;
};

Author.prototype = {

  /**
   * @return String The author's first name.
   */
  getFirstName: function() {
    return this._firstName;
  },

  /**
   * @return String The author's last name.
   */
  getLastName: function() {
    return this._lastName;
  },

  /**
   * @return String The representation of the Author.
   */
  toString: function() {
    return this.getFirstName()+' '+this.getLastName();
  }
};

/**
 * Publication constructor.
 *
 * @param String title
 * @param Author[] authors
 * @param int type
 */
var Publication = function(title, authors, type) {  
  this._title = title;
  this._authors = authors;
  this._type = type;
};

Publication.prototype = {

  /**
   * @return String The publication title.
   */
  getTitle: function() {
    return this._title;
  },

  /**
   * @return Author[] All authors.
   */
  getAuthors: function() {
    return this._authors;
  },

  /**
   * @return int The publication type.
   */
  getType: function() {
    return this._type;
  },

  /**
   * A publication might have several authors, but we
   * are only interested in the first three for a standard publication.
   *
   * @return Author[] The significant contributors.
   */
  contributingAuthors: function() {
    return this._authors.slice(0, 3);
  },

  /**
   * @return String the representation of the Publication.
   */
  toString: function() {
    return '['+this.getType()+'] "'+this.getTitle()+'" by '+this.contributingAuthors().join(', ');
  }
};

The API is straightforward. Consider the following invocations:

var pub = new Publication('The Shining',  
  [new Author('Stephen', 'King')],
  'horror');

// rely on the default toString() to print: [horror] "The Shining" by Stephen King
alert(pub);

// ...

var pub2 = new Publication('Design Patterns: Elements of Reusable Object-Oriented Software', [  
  new Author('Erich', 'Gamma'),
  new Author('Richard', 'Helm'),
  new Author('Ralph', 'Johnson'),
  new Author('John', 'Vlissides')
], 'programming');

// prints: [programming] "Design Patterns: Elements of Reusable Object-Oriented Software" by Erich Gamma, Richard Helm, Ralph Johnson
alert(pub2);  

The design is simple and reliable...at least until the client specifies a new requirement:

In accordance with the convention for medical publications, only list the first (primary) and last (supervisor) authors if multiple authors exist.

This means that if Publication.getType() returns "medical" we must perform special logic to list the contributing authors. All other types (e.g., horror, romance, computer, etc) will use the default behavior.

Solutions

There are many solutions to satisfy the new requirement, but some have disadvantages that are not readily apparent. Let's explore a few of these and see why they are not ideal even though they are commonplace.

Overwrite Behavior

// overwrite the contributingAuthors definition
if (pub.getType() === 'medical') {  
  pub.contributingAuthors = function() {
    var authors = this.getAuthors();

    // return the first and last authors if possible
    if (authors.length > 1) {
      return authors.slice(0, 1).concat(authors.slice(-1));
    } else {
      return authors.slice(0, 1);
    }
  }
}

This, one could argue, can be the most abused feature of the language: the ability to arbitrarily overwrite properties and behavior at run-time. Now the if/else condition must be maintained and expanded if more requirements are added to specify contributing authors. Furthermore, it is debatable whether or not pub is still an instance of Publication. A quick instanceof check will confirm that it is, but a class defines a set of state and behavior. In this case we have modified select instances and the calling code can no longer trust the consistency of Publication objects.

Change the Calling Code

var listing;  
if (pub.getType() === 'medical') {  
  var contribs = pub.getAuthors();

  // return the first and last authors if possible
  if (contribs.length > 1) {
    contribs = contribs.slice(0, 1).concat(contribs.slice(-1));
  } else {
    contribs = contribs.slice(0, 1);
  }

  listing = '['+pub.getType()+'] "'+pub.getTitle()+'" by '+contribs.join(', ');
} else {
  listing = pub.toString();
}

alert(listing);  

This solution violates encapsulation by forcing calling code to understand the internal implementation of Publication.toString() and recreate it outside of the class. A good design should not burden calling code.

Subclass the Component

subclass

One of the most common solutions is to create a MedicalPublication class that extends Publication, with a contributingAuthors() override to provide custom behavior. While this approach is arguably less flawed than the first two, it pushes the limit of clean inheritance. We should always favor composition over inheritance to avoid overreliance on the base class internals (for the developer masochists).

Subclassing also fails as a viable strategy when more than one customization might occur or when there is an unknown combination of customizations. An often cited example is a program to model a coffee shop where customers can customize their cup of coffee, thus affecting the price. A developer could create subclasses that reflect the myriad combinations such as CoffeeWithCream and CoffeeWithoutCreamExtraSugar that override Coffee.getPrice(), but it is easy to see that the design will not scale.

Modify the Source Code

contributingAuthors: function() {  
  if (this.getType() === 'medical') {
    var authors = this.getAuthors();

    if (authors.length > 1) {
      return authors.slice(0, 1).concat(authors.slice(-1));
    } else {
      return authors.slice(0, 1);
    }
  } else {
    return this._authors.slice(0, 3);
  }
}

This is somewhat of a hack, but in a small project where you control the source code it might suffice. A clear disadvantage is that the if/else condition must grow with every custom behavior, making it a potential maintenance nightmare.

Another thing to note is that you should never, ever modify source code outside of your control. Even the mention of such an idea should leave a taste in your mouth worse than drinking orange juice after brushing your teeth. Doing so will inextricably couple your code to that revision of the API. The cases where this is a valid option are so few and far between that it is usually an architectural issue in the application, not in the outside code.

The Decorator

These solutions fulfill the requirement at the cost of jeopardizing maintainability and scalability. As a developer you must pick what is right for your application, but there is one more option to examine before making a decision.

I recommend using a decorator, a flexible pattern by which to extend the behavior of your existing objects. The following UML represents an abstract implementation of the pattern:

decorator uml

The ConcreteComponent and Decorator classes implement the same Component interface (or extend Component if it's a superclass). The Decorator keeps a reference to a Component for delegation except in the case where we "decorate" by customizing the behavior.

By adhering to the Component contract, we are guaranteeing a consistent API and guarding against implementation internals because calling code will not and should not know if the object is a ConcreteComponent or Decorator. Programming to the interface is the cornerstone of good object-oriented design.

Some argue that JavaScript is not object-oriented, and while it supports prototypical inheritance instead of classical, objects are still innate to the language. The language supports polymorphism and that fact that all objects extend Object is sufficient to argue the language is object-oriented as well as functional.

The Implementation

Our solution will use a slight variant of the decorator pattern because JavaScript does not have some classical inheritance concepts such as interfaces or abstract classes. There are many libraries that simulate such constructs, which is beneficial for certain applications, but here we will use the languages basics.

publication

The class MedicalPublication and Publication implicitly implement PublicationIF. In this case MedicalPublication acts as the decorator to list the first and last authors as contributors while unchanging other behavior.

Note that MedicalPublication references PublicationIF, and not Publication. By referencing the interface instead of a specific implementation we can arbitrarily nest decorators within one another! (In the coffee shop problem we can create decorators such as WithCream, WithoutCream, and ExtraSugar--these can be nested to handle any complex order.)

The MedicalPublication class delegates for all standard operations and overrides contributingAuthors() to provide the "decorated" behavior.

/**
 * MedicalPublication constructor.
 *
 * @param PublicationIF The publication to decorate.
 */
var MedicalPublication = function(publication) {  
  this._publication = publication;
};

MedicalPublication.prototype = {

  /**
   * @return String The publication title.
   */
  getTitle:  function() {
    return this._publication.getTitle();
  },

  /**
   * @return Author[] All authors.
   */
  getAuthors: function() {
    return this._publication.getAuthors();
  },

  /**
   * @return int The publication type.
   */
  getType: function() {
    return this._publication.getType();
  },

  /**
   * Returns the first and last authors if multiple authors exists.
   * Otherwise, the first author is returned. This is a convention in the
   * medical publication domain.
   *
   * @return Author[] The significant contributors.
   */
  contributingAuthors: function() {

    var authors = this.getAuthors();

    if (authors.length > 1) {
      // fetch the first and last contributors
      return authors.slice(0, 1).concat(authors.slice(-1));
    } else {
      // zero or one contributors
      return authors.slice(0, 1);
    }
  },

  /**
   * @return String the representation of the Publication.
   */
  toString: function() {
    return 'Decorated - ['+this.getType()+'] "'+this.getTitle()+'" by '+this.contributingAuthors().join(', ');
  }
};

/**
 * Factory method to instantiate the appropriate PublicationIF implementation.
 *
 * @param String The discriminating type on which to select an implementation.
 * @param String The publication title.
 * @param Author[] The publication's authors.
 * @return PublicationIF The created object.
 */
var publicationFactory = function(title, authors, type) {

  if (type === 'medical') {
    return new MedicalPublication(new Publication(title, authors, type));
  } else {
    return new Publication(type, title, authors);
  }
};

By using the factory method we can safely create an instance of PublicationIF.

var title = 'Pancreatic Extracts as a Treatment for Diabetes';  
var authors = [new Author('Adam', 'Thompson'),  
  new Author('Robert', 'Grace'), 
  new Author('Sarah', 'Townsend')];
var type = 'medical';

var pub = publicationFactory(title, authors, type);

// prints: Decorated - [medical] 'Pancreatic Extracts as a Treatment of Diabetes' by Adam Thompson, Sarah Townsend
alert(pub);  

In these examples we are using toString() for brevity and debugging, but now we can create utility classes and methods to print PublicationIF objects for application display.

printer

Once the application is modified to expect PublicationIF objects we can accommodate further requirements to handle what constitutes a contributing author by adding new decorators. Also, the design is now open for any PublicationIF implementations beyond decorators to fulfill other requirements, which greatly increases the flexibility of the code.

Criticisms

One criticism is that the decorator must be maintained to adhere to its interface. All code, regardless of design, must be maintained to a degree, but it can be argued that maintaining a design with a clearly stated contract and pre- and post-conditions is much simpler than searching if/else conditions for run-time state and behavior modifications. More importantly, the decorator pattern safeguards calling code written by other developers (or even yourself) by leveraging object-oriented principles.

Another criticism is that decorators must implement all operations defined by a contract to enforce a consistent API. While this can be tedious at times, there are libraries and methodologies that can be used with JavaScript's dynamic nature to expedite coding. Reflection-like invocation can be used to allay concerns when dealing with a changing API.

/**
 * Invoke the target method and rely on its pre- and post-conditions.
 */
Decorator.prototype.someOperation = function() {  
  return this._decorated.someOperation.apply(this._decorated, arguments);
};

// ... or a helper library can automatically wrap the function

/**
 * Dynamic invocation.
 *
 * @param Class The class defining the function.
 * @param String The func to execute.
 * @param Object The *this* execution context.
 */
function wrapper(klass, func, context) {  
  return function() {
    return klass.prototype[func].apply(context, arguments);
  };
};

The details are up to the developer, but even the most primitive decorator pattern is extremely powerful. The overhead and maintenance for the pattern itself is minimal, especially when compared to that of the opposing solutions.

Conclusion

The decorator pattern is not flashy, despite its name, nor does it give the developer bragging rights in the "Look at what I did!" department. What the decorator does do, however, is correctly encapsulate and modularize your code to make it scalable for future changes. When a new requirement states that a certain publication type must list all authors as contributors, regardless of ordinal rank, you won't fret about having to refactor hundreds of lines of code. Instead, you'll write a new decorator, drop it into the factory method, and take an extra long lunch because you've earned it.

Featured

tutorials data structures linked hash map

Linking the Hash Map

Posted on .

The Hashmap

The hash map is a classic and indispensable data structure in application programming. It is so ubiquitous that almost every modern language supports it either with a library, or by baking the functionality into the syntax itself. Hash maps are often implemented as an associative array.

A hash map provides constant-time access to a value via a unique key. The most common methodology in JavaScript is to use an object literal as a hash map.

var map = {};

// dot notation
map.foo = "bar";  
console.log(map.foo); // "bar"

// bracket notation
map["foo"] = "bar";  
console.log(map["foo"]); // "bar"

// mix and match
map.foo = "bar";  
console.log(map["foo"]); // "bar"  

In this example, the string "bar" is the value assigned to the object property foo. Notice that treating an object literal like a hash map is the same syntax as normal property access and manipulation; we can leverage the language itself as a data structure. Because there isn't native hash code support in JavaScript, the Object.prototype.toString() method is invoked on the key to create the property name.

var map = {};

map[1] = "one";  
console.log(map[1] === "one"); // true  
console.log(map["1"] === "one"); // true  
console.log(map[(1).toString()] === "one"); // true  

While object literals suffice for basic hash map uses like caching, there are many operations that require boilerplate code such as listing all values in a hash map:

var map = {};

map["key1"] = "one";  
map["key2"] = "two";  
map["key3"] = "three";

// get all values
var values = [];  
for (var key in map) {  
  if (map.hasOwnProperty(key)) {
    values.push(map[key]);
  }
}

// the key order is not guaranteed with a basic hash map
// and each browser might have different implementations
console.log(values.join(',')); // "two,three,one"  

To rescue ourselves from reinventing the wheel, it is advisable to use a hash map class that encapsulates the behavior. The details of implementation is beyond the scope of this article, but there are many open-source libraries and articles that are worth perusing for details. For this article, we will use the following rudimentary hash map class:

Hash Map

/**
 * Simple hash map class.
 */
var HashMap = function() {  
  this._size = 0;
  this._map = {};
};

HashMap.prototype = {

  /**
   * Puts the key/value pair into the map, overwriting
   * any existing entry.
   */
  put: function(key, value) {
    if (!this.containsKey(key)) {
      this._size++;
    }
    this._map[key] = value;
  },

  /**
   * Removes the entry associated with the key
   * and returns the removed value.
   */
  remove: function(key) {
    if (this.containsKey(key)) {
      this._size--;
      var value = this._map[key];
      delete this._map[key];
      return value;
    } else {
      return null;
    }
  },

  /**
   * Checks if this map contains the given key.
   */
  containsKey: function(key) {
    return this._map.hasOwnProperty(key);
  },

  /**
   * Checks if this map contains the given value.
   * Note that values are not required to be unique.
   */
  containsValue: function(value) {
    for (var key in this._map) {
      if (this._map.hasOwnProperty(key)) {
        if (this._map[key] === value) {
          return true;
        }
      }
    }

    return false;
  },

  /**
   * Returns the value associated with the given key.
   */
  get: function(key) {
    return this.containsKey(key) ? this._map[key] : null;
  },

  /**
   * Clears all entries from the map.
   */
  clear: function() {
    this._size = 0;
    this._map = {};
  },

  /**
   * Returns an array of all keys in the map.
   */
  keys: function() {
    var keys = [];
    for (var key in this._map) {
      if (this._map.hasOwnProperty(key)) {
        keys.push(key);
      }
    }
    return keys;
  },

  /**
   * Returns an array of all values in the map.
   */
  values: function() {
    var values = [];
    for (var key in this._map) {
      if (this._map.hasOwnProperty(key)) {
        values.push(this._map[key]);
      }
    }
    return values;
  },

  /**
   * Returns the size of the map, which is
   * the number of keys.
   */
  size: function() {
    return this._size;
  }
};

This HashMap class lacks advanced features, but it is simple, effective, and library-agnostic.

Insertion Order

Even a robust and well tested hash map has one shortcoming if it relies on an object literal backbone: the return order of HashMap.keys() or HashMap.values() is unpredictable, meaning insertion order is not preserved. The overhead of tracking insertion order is why most hash map implementations ignore such a requirement and do not guarantee return order.

Although insertion order seems trivial, there are many cases in which it is critical to use hash maps for constant time access while also tracking when key/value pairs were inserted into the map. For example, a user interface library might allow a developer to add widgets to a dashboard.

Composition

Widget objects are added to a Dashboard, and when a Dashboard is rendered, so too are all of its Widget children in a predictable order. This is to avoid having a dashboard's widgets randomly allocated to different layout slots per render.

var dashboard = new Dashboard();  
dashboard.add(new Calendar("myCalendar"));  
dashboard.add(new StockTicker("myStockTicker"));  
dashboard.add(new Twitter("myTwitter"));

// modify the Calendar before rendering
var calendar = dashboard.getWidget("myCalendar");  
calendar.setTimeZone("MST");

// render the dashboard and its widgets in order: Calendar, StockTicker, Twitter
dashboard.render();  

We access the Calendar object--and other Widget objects--by its unique id, with Dashboard.getWidget() internally delegating to a private hash map. This introduces an implementation problem: we want to preserve the widget insertion order but give the developer constant time access to its Widget children. A common solution is to maintain two data structures within the Dashboard by synchronizing a hash map for access and an Array for order.

Dashboard

The code to ensure consistency and integrity between the two structures is non-trivial and not reusable, hence it is not ideal. Another solution is to abandon the hash map and rely solely on an Array, but this will slow Widget access time to a crawling O(n), which is also unacceptable.

Enter the linked hash map.

A linked hash map is a specialized hash map that is synchronized with a doubly linked list. We can merge these two data structures into a new class called LinkedHashMap, which allows constant time access backed by a doubly linked list to preserve insertion order. There is minimal overhead to synchronize the two structures when performing write operations on the core hash map. By extending the HashMap class we can add an optimized doubly linked list to track the keys. (If the hash map cannot be subclassed then consider decorating it or rolling your own if there are application-specific or critical optimization requirements.)

LinkedHashMap

/**
 * Constructor that initializes the parent HashMap
 * and the doubly linked list head and tail.
 */
var LinkedHashMap = function() {  
  // invoke super constructor
  HashMap.apply(this, arguments);

  // "inner" Entry class
  this._Entry = function(value) {
    this.prev = null;
    this.next = null;
    this.value = value;
  };

  // doubly linkedlist instance variables
  this._head = this._tail = null;
};

// extend HashMap and overwrite the necessary functions
var temp = function() {};  
temp.prototype = HashMap.prototype;  
LinkedHashMap.prototype = new temp();

/**
 * Puts the key/value pair in the HashMap and records
 * the insertion record if it does not exist.
 * 
 * @override HashMap.put()
 */
LinkedHashMap.prototype.put = function(key, value) {  
  var entry = new this._Entry(key);

  if (!this.containsKey(key)) {
    if (this.size() === 0) {
      this._head = entry;
      this._tail = entry;
    } else {
      this._tail.next = entry;
      entry.prev = this._tail;
      this._tail = entry;
    }
  }

  /*
   * EDIT: Added optimization suggested
   * by Chad Walker (see article comments).
   */
  // overwrite the value with an optimized Object wrapper
  value = {value:value, entry:entry};

  HashMap.prototype.put.call(this, key, value);
};

/**
 * Returns the value associated with the key.
 * 
 * @override HashMap.get()
 */
LinkedHashMap.prototype.get = function(key){  
  var value = HashMap.prototype.get.call(this, key);

  /*
   * EDIT: Added optimization suggested 
   * by Chad Walker (see article comments).
   */  
  // we must unwrap the value
  return value != null ? value.value : null;
};

/**
 * Removes the key/value pair from the map and 
 * the key from the insertion order.
 * 
 * @override Hashmap.remove()
 */
LinkedHashMap.prototype.remove = function(key) {

  /*
   * EDIT: Added optimization suggested 
   * by Chad Walker (see article comments).
   */
  var value = HashMap.prototype.remove.apply(this, arguments);

  if (value != null) {

    var entry = value.entry;

    if (entry === this._head) {
      this._head = entry.next;
      this._head.prev = null;
    } else if (entry === this._tail) {
      this._tail = entry.prev;
      this._tail.next = null;
    } else {
      entry.prev.next = entry.next;
      entry.next.prev = entry.prev;
    }
  }

  return value;
};

/**
 * Clears the HashMap and insertion order.
 *
 * @override HashMap.clear()
 */
LinkedHashMap.prototype.clear = function() {  
  HashMap.prototype.clear.apply(this, arguments);
  this._head = this._tail = null;
};

/**
 * Returns the HashMap keys in insertion order.
 *
 * @override HashMap.keys()
 */
LinkedHashMap.prototype.keys = function() {  
  var keys = [];
  for (var cur = this._head; cur != null; cur = cur.next) {
    keys.push(cur.value);
  }
  return keys;
};

/**
 * Returns the HashMap values in insertion order.
 * 
 * @override HashMap.values()
 */
LinkedHashMap.prototype.values = function() {  
  var values = [];
  for (var cur = this._head; cur != null; cur = cur.next) {
    values.push(this.get(cur.value));
  }
  return values;
};

This new data structure, a marriage between a hash map and doubly linked list, is perfect as the sole backbone of Dashboard to manage widgets.

Dashboard

Moving On

With just a little overhead for write operations to the LinkedHashMap, even basic problems that require hash map behavior can query the insertion order with ease.

var map = new LinkedHashMap();

map.put("key1", "one");  
map.put("key2", "two");  
map.put("key3", "three");

// return order is now predictable
console.log(map.keys().join(',')); // "key1,key2,key3"  
console.log(map.values().join(',')); // "one,two,three"  

Because LinkedHashMap implements the same API as HashMap via inheritance, calling code can switch to a LinkedHashMap at runtime without breaking. The beauty of object-oriented design is that the declared type (HashMap) of a variable is irrelevant to the runtime type (LinkedHashMap). The only difficulty is enforcing the API in a type-unsafe language like JavaScript...but that's another article.

Featured

tutorial encapsulation

Encapsulation Breaking

Posted on .

Encapsulation is the process by which an object's internal components and behavioral details are hidden from calling code. Only that which should be exposed is exposed, making objects self-contained black boxes to the outside world. Many languages support encapsulation by supplying visibility modifiers (e.g., private) and constructs such as inner classes.

Unfortunately, JavaScript offers very little in the encapsulation department. While there are certain tricks that can wrap protected code in closures (see Module Pattern), many have disadvantages that compromise code flexibility and extensibility.

Standard Convention

Instead of using closure-based encapsulation, which often makes object-oriented inheritance difficult, many libraries and code-bases opt to mark private properties and functions with an underscore prepend. This convention makes inspecting the properties and functions easy within browser debuggers.

var Person = function(first, last){  
  // private properties _first, _last, and _id
  this._first = first;
  this._last = last;
  this._id = this._generateId();
};

Person.prototype = {  
  getId : function(){
    return this._id;
  },
  getFirstName: function(){
    return this._first;
  },
  getLastName : function(){
    return this._last;
  },
  // private function to generate an id for this object
  _generateId : function(){
    return new Date().getTime().toString();
  }
};

This convention is commonplace, similar to naming constants in uppercase. The downside is that private properties and functions can still be accessed, thus breaking encapsulation because of careless coding.

Encapsulation Breaking

The dynamic nature of JavaScript allows for a free-for-all environment where a developer can do whatever he or she wants. Consider the following:

var person = new Person("Bob", "Someguy");  
console.log(person._first); // logs "Bob"  

This appears all fine and well, but now we've coupled our code to the Person implementation. Any change to the internals -- the category of change encapsulation should protect us against -- could break calling code.

var Person = function(first, last){  
  this._firstName = first; // property change
  this._lastName = last; // property change
  this._id = this._generateId();
};

// ... 
var person = new Person("Bob", "Someguy");  
console.log(person._first); // logs "undefined"  

These bugs can be difficult to track, especially since the application code may not have changed...an updated external library or resource, in which Person may be defined, is all that it takes. The best defense against such couplings is to avoid breaking encapsulation. If a property or method is marked as private, do not access, modify, or invoke it. The overhead in rethinking the architecture and design is almost always less than the cost of dealing with the consequences of breaking encapsulation.

In other words: "Developers don't let developers break encapsulation."

Method Stealing

As troublesome as accessing private properties can be in JavaScript, there is another much more insidious practice that seems commonly accepted: method stealing.

The methods Function.prototype.call and Function.protoype.apply are integral to modern libraries and code-bases by allowing a method to inject a custom context (this reference) into the execution scope. Without these capabilities the reliance on closures to achieve the same effect would be too cumbersome.

Just as some properties should be hidden, so too should some methods. Given our prior example, Person.prototype._generateId() might function as an inadequate UUID generator. A clever developer notices that another available method Book.prototype._setUUID() sets a this._id property on all Book objects whose value is much more unique across space and time than Person.prototype._generateId();

var Book = function(title, author){  
  this._title = title;
  this._author = author;
  this._id = null;
  this._setUUID();
}
Book.prototype = {  
  getId : function(){
    return this._id;
  },
  getTitle : function(){
    return this._title;
  },
  getAuthor : function(){
    return this._author;
  },
  _setUUID : function(){
    var result = '';
    for(var i=0; i<32; i++)
    {
      result += Math.floor(Math.random()*16).toString(16);
    } 
    this._id = result;
  }
};

In return, the developer has chosen to "steal" this behavior from Book for Person and modify Person.prototype._generateId() to invoke Book.prototype._setUUID().

var Person = function(first, last){  
  // private properties _first, _last, and _id
  this._first = first;
  this._last = last;
  this._id = null;
  this._generateId();
};

Person.prototype = {  
  getId : function(){
    return this._id;
  },
  getFirstName: function(){
    return this._first;
  },
  getLastName : function(){
    return this._last;
  },
  // private function to generate an id for this object
  _generateId : function(){
    // sets this._id withing _setUUID()
    Book.prototype._setUUID.call(this);
  }
};

Again this works...ostensibly so, by having this._id set by Book.prototype._setUUID(). The design is brittle, however, because Book's internals can be refactored unbeknownst to Person, thus breaking Person objects. If Book.prototype._setUUID() is refactored to set this._uuid rather than this._id then all Person.prototype.getId() invocations will return undefined. With one myopic decision we broke our application because it was easier to break encapsulation rather than rethink the design.

Conclusion

There is not much of a conclusion except do not break encapsulation. In fact, apply the Golden Rule while coding: treat other code as you wish yours would be treated. Any API deficiencies should be brought to the original author, not hacked apart to make it usable for one use case or instance. The maintenance headache down the road is just not worth it.