gistfile1.js

// tree to find the short tag name for each
// of a list of tag names
// ['a','a','b','button','button'] => ['a1','a2','b','bu1','bu2']
function StringNode(str, parent) {
  this.string = str || '';
  this.parent = parent;
  this.children = {};
  this.childCount = 0;
  this.pointerCount = 0;
}

StringNode.prototype.add = function(suffix) {
  var c = suffix.charAt(0),
      rem = suffix.substr(1),
      child = this.children[c];

  if (!child) {
    child = this.children[c] = new StringNode(this.string + c, this);
    this.childCount++;
  }

  if (rem) {
    return child.add(rem);
  } else {
    return child.pointer();
  }
};

StringNode.prototype.uniquePrefix = function() {
  var node = this;
  while(node.parent && node.parent.childCount == 1) {
    node = node.parent;
  }
  return node.string;
};

StringNode.prototype.pointer = function() {
  return new StringNodePointer(this, this.pointerCount++);
};

StringNodePointer = function(node, offset) {
  this.node = node;
  this.offset = offset;
};

StringNodePointer.prototype.toString = function() {
  return this.node.uniquePrefix() + (this.node.pointerCount > 1 ? this.offset+1 : '');
};