/**
 * This document is work in progress. It implements w3c Range for browsers
 * that do not support it natively like Internet Explorer. The implementation
 * is cross-browser compatible but only gets binded if no w3c Range
 * implementation exists.
 *
 * Range methods:
 *
 *   setStart                 IMPLEMENTED
 *   setEnd                   IMPLEMENTED
 *   setStartBefore           IMPLEMENTED
 *   setStartAfter            IMPLEMENTED
 *   setEndBefore             IMPLEMENTED
 *   setEndAfter              IMPLEMENTED
 *   collapse                 IMPLEMENTED
 *   selectNode               IMPLEMENTED
 *   selectNodeContents       IMPLEMENTED
 *   compareBoundaryPoints    IMPLEMENTED
 *   deleteContents           IMPLEMENTED
 *   extractContents          IMPLEMENTED
 *   cloneContents            IMPLEMENTED
 *   insertNode               IMPLEMENTED
 *   surroundContents         IMPLEMENTED (Need to be Unit Tested)
 *   cloneRange               IMPLEMENTED
 *   toString                 NOT IMPLEMENTED YET
 *   detach                   IMPLEMENTED
 *
 * This whole package needs to be unit tested though... I am not quite sure
 * about the quality.
 *
 * @author Jorgen Horstink <mail@jorgenhorstink.nl>
 */

ExceptionStack = new function () {
  // singleton class, cannot be prototyped

  this.objects = [];
  this.codes   = [];

  this.callers = [];

  var self = this;

  this.push = function (object, code) {
    self.objects[self.objects.length] = object;
    self.codes[self.codes.length]     = code;
  }

  this.last = function () {
    var caller = this.callers[this.callers.length - 1];
    if (typeof caller == 'undefined') {
      caller = "Unknown method reports\n\n";
    } else {
      caller = caller + " reports\n\n";
    }

    var message = this.objects[this.objects.length - 1].toString[this.codes[this.codes.length - 1]];
    if (typeof message == 'undefined') {
      return caller + 'Unknown exception message';
    } else {
      return caller + message;
    }
  }

  this.pushCaller = function (caller) {
    if (!caller) {
      caller = 'Unknown';
    }
    this.callers[this.callers.length] = caller;
  }

  this.popCaller = function () {
    this.callers.length--;
  }

  this.empty = function () {
    return this.objects.length == 0;
  }
}

function Exception (object, code) {
  ExceptionStack.push(object, code);
  alert(ExceptionStack.last());
}

DOMException = new function () {
  this.INDEX_SIZE_ERR              = 1;
  this.DOMSTRING_SIZE_ERR          = 2;
  this.HIERARCHY_REQUEST_ERR       = 3;
  this.WRONG_DOCUMENT_ERR          = 4;
  this.INVALID_CHARACTER_ERR       = 5;
  this.NO_DATA_ALLOWED_ERR         = 6;
  this.NO_MODIFICATION_ALLOWED_ERR = 7;
  this.NOT_FOUND_ERR               = 8;
  this.NOT_SUPPORTED_ERR           = 9;
  this.INUSE_ATTRIBUTE_ERR         = 10;
  this.INVALID_STATE_ERR           = 11;
  this.SYNTAX_ERR                  = 12;
  this.INVALID_MODIFICATION_ERR    = 13;
  this.NAMESPACE_ERR               = 14;
  this.INVALID_ACCESS_ERR          = 15;
  this.VALIDATION_ERR              = 16;
  this.TYPE_MISMATCH_ERR           = 17;

  this.toString = {
    1:"Index or size is negative or greater than the allowed amount",
    2:"DOMSTRING_SIZE_ERR",
    3:"HIERARCHY_REQUEST_ERR",
    4:"WRONG_DOCUMENT_ERR",
    5:"INVALID_CHARACTER_ERR",
    6:"NO_DATA_ALLOWED_ERR",
    7:"NO_MODIFICATION_ALLOWED_ERR",
    8:"NOT_FOUND_ERR",
    9:"NOT_SUPPORTED_ERR",
    10:"INUSE_ATTRIBUTE_ERR",
    11:"An attempt was made to use an object this is not, or is no longer, usable",
    12:"SYNTAX_ERR",
    13:"INVALID_MODIFICATION_ERR",
    14:"NAMESPACE_ERR",
    15:"INVALID_ACCESS_ERR",
    16:"VALIDATION_ERR",
    17:"TYPE_MISMATCH_ERR"
  };
}

RangeException = new function() {
  this.BAD_BOUNDARYPOINTS_ERR = 1;
  this.INVALID_NODE_TYPE_ERR  = 2;

  this.COMPARE_BOUNDARY_POINT_IMPLEMENTATION_ERR = 91;

  this.toString = {
    1:"BAD_BOUNDARYPOINTS_ERR",
    2:"INVALID_NODE_TYPE_ERR",
    91:"An error has occured in the private Range._compareBoundaryPoints implementation."
  }
}

Node = new function () {
  this.ELEMENT_NODE                = 1;
  this.ATTRIBUTE_NODE              = 2;
  this.TEXT_NODE                   = 3;
  this.CDATA_SECTION_NODE          = 4;
  this.ENTITY_REFERENCE_NODE       = 5;
  this.ENTITY_NODE                 = 6;
  this.PROCESSING_INSTRUCTION_NODE = 7;
  this.COMMENT_NODE                = 8;
  this.DOCUMENT_NODE               = 9;
  this.DOCUMENT_TYPE_NODE          = 10;
  this.DOCUMENT_FRAGMENT_NODE      = 11;
  this.NOTATION_NODE               = 12;
}

Range = function (ownerDocument) {

  this.ownerDocument = ownerDocument;

/**
 * The initial state of the Range returned from this method is such
 * that both of its <em>boundary-point</em></a>s
 * are positioned at the beginning of the corresponding Document,
 * before any content. In other words, the <em>container</em> of 
 * each <em>boundary-point</em> is the Document node and the offset 
 * within that node is 0.
 */
  this.startContainer          = this.ownerDocument.documentElement;
  this.startOffset             = 0;
  this.endContainer            = this.ownerDocument.documentElement;
  this.endOffset               = 0;
  this.collapsed               = true;

  this.commonAncestorContainer = this._commonAncestorContainer(this.startContainer, this.endContainer);

  this.detached                = false;

  // compare how
  this.START_TO_START = 0;
  this.START_TO_END   = 1;
  this.END_TO_END     = 2;
  this.END_TO_START   = 3;

  this.CLONE_CONTENTS   = 0;
  this.DELETE_CONTENTS  = 1;
  this.EXTRACT_CONTENTS = 2;
}


// bind the Range object to createRange if no implementation exists
if (!document.createRange) {
  document.createRange = function () {
    // provide a context; ownerDocument
    return new Range(this);
  }
}

Range.prototype.cloneContents = function () {
  try {
    ExceptionStack.pushCaller('Range.cloneContents');

    if (this.detached == true) {
      throw new Exception(DOMException, DOMException.INVALID_STATE_ERR);
    }

    this._processContents(this.CLONE_CONTENTS);

    ExceptionStack.popCaller();
  } catch (e) {}
}

Range.prototype.cloneRange = function () {
  try {
    ExceptionStack.pushCaller('Range.cloneRange');

    if (this.detached) {
      throw new Exception(DOMException, DOMException.INVALID_STATE_ERR);
    }

    var clone = new Range(this.ownerDocument);
    // a range solely exists of these properties.
    clone.startContainer          = this.startContainer;
    clone.startOffset             = this.startOffset;
    clone.endContainer            = this.endContainer;
    clone.endOffset               = this.endOffset;
    clone.collapsed               = this.collapsed;
    clone.commonAncestorContainer = this.commonAncestorContainer;
    clone.detached                = this.detached;

    ExceptionStack.popCaller();

    return clone;

  } catch (e) {}

}

/**
 * Collapse a Range onto one of its boundary-points
 *
 * @param toStart If TRUE, collapses the Range onto its start; 
 * if FALSE, collapses it onto its end.
 *
 * @return
 *
 * @exception DOMException
 *   INVALID_STATE_ERR: Raised if <code>detach()</code> has already
 *   been invoked on this object.
 */
Range.prototype.collapse = function (toStart) {
  try {
    ExceptionStack.pushCaller('Range.collapse');

    if (this.detached) {
      throw new Exception(DOMException, DOMException.INVALID_STATE_ERR);
    }

    if (toStart) {
      this.endContainer   = this.startContainer;
      this.endOffset      = this.startOffset;
    } else {
      this.startContainer = this.endContainer;
      this.startOffset    = this.endOffset;
    }

    ExceptionStack.popCaller();
  } catch (e) {}

}

Range.prototype.compareBoundaryPoints = function (compareHow, sourceRange) {
  try {
    var cmnSelf, cmnSource, rootSelf, rootSource;

    ExceptionStack.pushCaller('Range.collapse');

    if (this.detached) {
      throw new Exception(DOMException, DOMException.INVALID_STATE_ERR);
    }

    if (!sourceRange) {
      throw new Exception(DOMException, DOMException.NOT_FOUND_ERR);
    }

    // An exception is thrown if the two Ranges have different root containers.
    cmnSelf   = this.commonAncestorContainer;
    cmnSource = sourceRange.commonAncestorContainer;

    if (this.ownerDocument != sourceRange.ownerDocument) {
      throw new Exception(DOMException, DOMException.WRONG_DOCUMENT_ERR);
    }
    rootSelf = cmnSelf;
    while (rootSelf.parentNode) {
      rootSelf = rootSelf.parentNode;
    }

    rootSource = cmnSource;
    while (rootSource.parentNode) {
      rootSource = rootSource.parentNode;
    }


    if (rootSelf != rootSource) {
      throw new Exception(DOMException, DOMException.WRONG_DOCUMENT_ERR);
    }

    switch (compareHow) {
      case this.START_TO_START:
        ExceptionStack.popCaller();
        return this._compareBoundaryPoints(this.startContainer, this.startOffset, sourceRange.startContainer, sourceRange.startOffset);
        break;
      case this.START_TO_END:
        ExceptionStack.popCaller();
        return this._compareBoundaryPoints(this.startContainer, this.startOffset, sourceRange.endContainer, sourceRange.endOffset);
        break;
      case this.END_TO_END:
        ExceptionStack.popCaller();
        return this._compareBoundaryPoints(this.endContainer, this.endOffset, sourceRange.endContainer, sourceRange.endOffset);
        break;
      case this.END_TO_START:
        ExceptionStack.popCaller();
        return this._compareBoundaryPoints(this.endContainer, this.endOffset, sourceRange.startContainer, sourceRange.startOffset);
        break;
      default:
        throw new Exception (DOMException, DOMException.SYNTAX_ERR);
    }

    ExceptionStack.popCaller();

  } catch (e) {}

}

// does not check for read-only
Range.prototype.deleteContents = function () {
  try {
    ExceptionStack.pushCaller('Range.deleteContents');

    if (this.detached == true) {
      throw new Exception(DOMException, DOMException.INVALID_STATE_ERR);
    }

    this._processContents(this.DELETE_CONTENTS);

    ExceptionStack.popCaller();
  } catch (e) {}
}

/**
 * Called to indicate that the Range is no longer
 * in use and that the implementation may relinquish any resources
 * associated with this Range. Subsequent calls to any methods or
 * attribute getters on this Range will result in a
 * <code>DOMException</code> being thrown with an error code of
 * <code>INVALID_STATE_ERR</code>. 
 *
 * @return
 *
 * @exception 
 *   INVALID_STATE_ERR: Raised if <code>detach()</code> has already
 *   been invoked on this object.
 */
Range.prototype.detach = function () {
  try {

    ExceptionStack.pushCaller('Range.detach');

    if (this.detached == true) {
      throw new Exception(DOMException, DOMException.INVALID_STATE_ERR);
    } else {
      this.detached = true;
    }

    ExceptionStack.popCaller();

  } catch (e) {}
}

// does not check for read-only
Range.prototype.extractContents = function () {
  try {
    ExceptionStack.pushCaller('Range.extractContents');

    if (this.detached == true) {
      throw new Exception(DOMException, DOMException.INVALID_STATE_ERR);
    }

    return this._processContents(this.EXTRACT_CONTENTS);

    ExceptionStack.popCaller();
  } catch (e) {}
}

// does not check for child-type allowed or read-only
Range.prototype.insertNode = function (newNode) {
  try {
    ExceptionStack.pushCaller('Range.insertNode');

    var n, newText, offset;

    if (this.detached == true) {
      throw new Exception(DOMException, DOMException.INVALID_STATE_ERR);
    }

    if (this.ownerDocument != newNode.ownerDocument) {
      throw new Exception(DOMException, DOMException.WRONG_DOCUMENT_ERR);
    }

    if (this.startContainer.nodeType == Node.TEXT_NODE && !this.startContainer.parentNode) {
      throw new Exception(DOMException, DOMException.HIERARCHY_REQUEST_ERR);
    }

    for (n = this.startContainer; n; n = n.parentNode) {
      if (n == newNode) {
        throw new Exception(DOMException, DOMException.HIERARCHY_REQUEST_ERR);
      }
    }

    switch (newNode.nodeType) {
      case Node.ATTRIBUTE_NODE:
      case Node.DOCUMENT_NODE:
      case Node.ENTITY_NODE:
      case Node.NOTATION_NODE:
        throw new Exception(RangeException, RangeException.INVALID_NODE_TYPE_ERR);
    }
    switch (this.startContainer.nodeType) {
      case Node.CDATA_SECTION_NODE:
      case Node.TEXT_NODE:
        
        newText = this.startContainer.splitText(this.startOffset);

        this.startContainer.parentNode.insertBefore(newNode, newText);
        break;
      default:
        if (this.startContainer.childNodes.length == 0) {
          offset = null;
        } else {
          offset = this.startContainer.childNodes(this.startOffset);
        }
        this.startContainer.insertBefore(newNode, offset);
    }

    ExceptionStack.popCaller();
  } catch (e) {}
}

Range.prototype.selectNode = function (refNode) {

  try {

    ExceptionStack.pushCaller('Range.selectNode');

    this._validateParametersSelectNode(refNode);

    switch (refNode.nodeType) {
      case Node.ATTRIBUTE_NODE:
      case Node.DOCUMENT_FRAGMENT_NODE:
      case Node.DOCUMENT_NODE:
      case Node.ENTITY_NODE:
      case Node.NOTATION_NODE:
        throw new Exception(RangeException, RangeException.INVALID_NODE_TYPE_ERR);
    }

    this.setStartBefore(refNode);
    this.setEndAfter(refNode);

    ExceptionStack.popCaller();

  } catch (e) {}

}

Range.prototype.selectNodeContents = function (refNode) {

  try {

    ExceptionStack.pushCaller('Range.selectNodeContents');

    this._validateParametersSelectNode(refNode);

    this.setStart(refNode, 0);
    this.setEnd(refNode, refNode.childNodes.length);

    ExceptionStack.popCaller();

  } catch (e) {}
}

/**
 * Sets the attributes describing the start of the range.
 *
 * @param refNode The <code> refNode </code> value. This parameter
 * must be different from <code> null </code>.
 *
 * @param offset The <code> startOffset </code> value.
 *
 * @return
 *
 * @exception DOMException
 *   NOT_FOUND_ERR: Raised if <code>refNode</code> is <code>null</code>.
 *
 *   INDEX_SIZE_ERR: Raised if <code>offset</code> is negative or
 *   greater than the number of child units in <code>refNode</code>.
 *   Child units are <em>16-bit
 *   units</em> if <code>refNode</code> is a type of CharacterData
 *   node (e.g., a Text or Comment node) or a ProcessingInstruction
 *   node. Child units are Nodes in all other cases.
 *
 * @exception RangeException
 *   INVALID_NODE_TYPE_ERR: Raised if <code>refNode</code> or an
 *   ancestor of <code>refNode</code> is an Attr, Entity,
 *   Notation, or DocumentType node.
 */
Range.prototype.setStart = function(refNode, offset)
{
  try {

    ExceptionStack.pushCaller('Range.setStart');

    var endRootContainer, startRootContainer;

    if (this.detached) {
      throw new Exception(DOMException, DOMException.INVALID_STATE_ERR);
    }

    if (!refNode) {
      throw new Exception(DOMException, DOMException.NOT_FOUND_ERR);
    }

    // checks for INDEX_SIZE_ERR and INVALID_NODE_TYPE_ERR Exceptions
    this._validateParameters(refNode, offset);

    // The specification does not require to throw an exception here, but
    // it is clear an exception must be thrown. The specification states:
    //
    //   "Ranges created via a particular document instance can select only 
    //   content associated with that Document, or with DocumentFragments 
    //   and Attrs for which that Document is the ownerDocument. Such 
    //   Ranges, then, can not be used with other Document instances."
    //
    // It is not required to throw an exception though if you sin against
    // the rule. This also applies to Range.setStartBefore,
    // Range.setStartAfter, Range.setEnd, Range.setEndBefore,
    // Range.setEndAfter.
    if (this.ownerDocument != refNode.ownerDocument) {
      throw new Exception(DOMException, DOMException.WRONG_DOCUMENT_ERR);
    }

    this.startContainer = refNode;
    this.startOffset    = offset;

    // If one boundary-point of a Range is set to have a root container 
    // other than the current one for the Range, the Range is collapsed to 
    // the new position. This enforces the restriction that both boundary-
    // points of a Range must have the same root container.
    endRootContainer = this.endContainer;
    while (endRootContainer.parentNode) {
      endRootContainer = endRootContainer.parentNode;
    }
    startRootContainer = this.startContainer;
    while (startRootContainer.parentNode) {
      startRootContainer = startRootContainer.parentNode;
    }
    if (startRootContainer != endRootContainer) {
      this.collapse(true);
    } else {
      // The start position of a Range is guaranteed to never be after the 
      // end position. To enforce this restriction, if the start is set to 
      // be at a position after the end, the Range is collapsed to that 
      // position.
      if (this._compareBoundaryPoints(this.startContainer, this.startOffset, this.endContainer, this.endOffset) > 0) {
        this.collapse(true);
      }
    }

    this.collapsed = this._isCollapsed();
  
    this.commonAncestorContainer = this._commonAncestorContainer(this.startContainer, this.endContainer);

    ExceptionStack.popCaller();

  } catch (e) {}

}

Range.prototype.setStartAfter = function (refNode) {
  try {
    ExceptionStack.pushCaller('Range.setStartAfter');

    this._validateParametersBeforeAfter(refNode);

    this.setStart(refNode.parentNode, this._nodeIndex(refNode) + 1);

    ExceptionStack.popCaller();
  } catch (e) {}

}

Range.prototype.setStartBefore = function (refNode) {
  try {
    ExceptionStack.pushCaller('Range.setStartBefore');

    this._validateParametersBeforeAfter(refNode);

    this.setStart(refNode.parentNode, this._nodeIndex(refNode));

    ExceptionStack.popCaller();
  } catch (e) {}
}

/**
 * Sets the attributes describing the end of a range.
 *
 * @param refNode The <code> refNode </code> value. This parameter
 * must be different from <code> null </code> .
 *
 * @param offset The <code> endOffset </code> value.
 *
 * @return
 *
 * @exception DOMException
 *   NOT_FOUND_ERR: Raised if <code>refNode</code> is <code>null</code>.
 *
 *   INDEX_SIZE_ERR: Raised if <code>offset</code> is negative or
 *   greater than the number of child units in <code>refNode</code>.
 *   Child units are <em>16-bit
 *   units</em> if <code>refNode</code> is a type of CharacterData
 *   node (e.g., a Text or Comment node) or a ProcessingInstruction
 *   node. Child units are Nodes in all other cases.
 *
 * @exception RangeException
 *   INVALID_NODE_TYPE_ERR: Raised if <code>refNode</code> or an
 *   ancestor of <code>refNode</code> is an Attr, Entity,
 *   Notation, or DocumentType node.
 */
Range.prototype.setEnd = function(refNode, offset)
{
  try {
    ExceptionStack.pushCaller('Range.setEnd');

    if (this.detached) {
      throw new Exception(DOMException, DOMException.INVALID_STATE_ERR);
    }

    if (!refNode) {
      throw new Exception(DOMException, DOMException.NOT_FOUND_ERR);
    }

    // checks for INDEX_SIZE_ERR and INVALID_NODE_TYPE_ERR Exceptions
    this._validateParameters(refNode, offset);

    if (this.ownerDocument != refNode.ownerDocument) {
      throw new Exception(DOMException, DOMException.WRONG_DOCUMENT_ERR);
    }

    this.endContainer = refNode;
    this.endOffset    = offset;

    // If one boundary-point of a Range is set to have a root container 
    // other than the current one for the Range, the Range is collapsed to 
    // the new position. This enforces the restriction that both boundary-
    // points of a Range must have the same root container.
    endRootContainer = this.endContainer;
    while (endRootContainer.parentNode) {
      endRootContainer = endRootContainer.parentNode;
    }
    startRootContainer = this.startContainer;
    while (startRootContainer.parentNode) {
      startRootContainer = startRootContainer.parentNode;
    }
    if (startRootContainer != endRootContainer) {
      this.collapse(false);
    } else {
      // ... Similarly, if the end is set to be at a position before the 
      // start, the Range is collapsed to that position.
      if (this._compareBoundaryPoints(this.startContainer, this.startOffset, this.endContainer, this.endOffset) > 0) {
        this.collapse(false);
      }
    }

    this.collapsed = this._isCollapsed();

    this.commonAncestorContainer = this._commonAncestorContainer(this.startContainer, this.endContainer);

    ExceptionStack.popCaller();

  } catch (e) {}

}

Range.prototype.setEndAfter = function (refNode) {
  try {
    ExceptionStack.pushCaller('Range.setEndAfter');

    this._validateParametersBeforeAfter(refNode);

    this.setEnd(refNode.parentNode, this._nodeIndex(refNode) + 1);

    ExceptionStack.popCaller();
  } catch (e) {}

}

Range.prototype.setEndBefore = function (refNode) {
  try {
    ExceptionStack.pushCaller('Range.setEndBefore');

    this._validateParametersBeforeAfter(refNode);

    this.setEnd(refNode.parentNode, this._nodeIndex(refNode));

    ExceptionStack.popCaller();
  } catch (e) {}
}

Range.prototype.surroundContents = function (newParent) {

  try {
    ExceptionStack.pushCaller('Range.surroundContents');

    var n, fragment;

    if (this.detached) {
      throw new Exception(DOMException, DOMException.INVALID_STATE_ERR);
    }

    if (!newParent) {
      throw new Exception(DOMException, DOMException.NOT_FOUND_ERR);
    }

    switch (newParent.nodeType) {
      case Node.ATTRIBUTE_NODE:
      case Node.DOCUMENT_FRAGMENT_NODE:
      case Node.DOCUMENT_NODE:
      case Node.DOCUMENT_TYPE_NODE:
      case Node.ENTITY_NODE:
      case Node.NOTATION_NODE:
        throw new Exception(RangeException, RangeException.INVALID_NODE_TYPE_ERR);
    }

    // should check for read-only

    if (this.ownerDocument != this.startContainer.ownerDocument) {
      throw new Exception(DOMException, DOMException.WRONG_DOCUMENT_ERR);
    }
    
    // should check for child type allowed


    for (n = this.startContainer; n; n = n.parentNode) {
      if (n == newParent) {
        throw new Exception(DOMException, DOMException.HIERARCHY_REQUEST_ERR);
      }
    }

    if (!this._offsetInCharacters(this.startContainer)) {
      if (this.startOffset > 0 && this.startOffset < this.startContainer.childNodes.length) {
        throw new Exception(RangeException, RangeException.BAD_BOUNDARYPOINTS_ERR);
      }
    }
    if (!this._offsetInCharacters(this.endContainer)) {
      if (this.endOffset > 0 && this.endOffset < this.endContainer.childNodes.length) {
        throw new Exception(RangeException, RangeException.BAD_BOUNDARYPOINTS_ERR);
      }
    }

    // empty the newParent
    while (newParent.firstChild) {
      newParent.removeChild(newParent.firstChild);
    }

    fragment = this.extractContents();
    this.insertNode(newParent);
    newParent.appendChild(fragment);
    this.selectNode(newParent);

    ExceptionStack.popCaller();
  } catch (e) {}
}

Range.prototype._compareBoundaryPoints = function (containerA, offsetA, containerB, offsetB) {

  var c, offsetC, n, cmnRoot, childA;
  // In the first case the boundary-points have the same container. A is before B 
  // if its offset is less than the offset of B, A is equal to B if its offset is 
  // equal to the offset of B, and A is after B if its offset is greater than the 
  // offset of B.
  if (containerA == containerB) {
    if (offsetA == offsetB) {
      return 0; // equal
    } else if (offsetA < offsetB) {
      return -1; // before
    } else {
      return 1; // after
    }
  }


  // In the second case a child node C of the container of A is an ancestor 
  // container of B. In this case, A is before B if the offset of A is less than or 
  // equal to the index of the child node C and A is after B otherwise.
  c = containerB;
  while (c && c.parentNode != containerA) {
    c = c.parentNode;
  }
  if (c) {
    offsetC = 0;
    n = containerA.firstChild;
    while (n != c && offsetC < offsetA) {
      offsetC++;
      n = n.nextSibling;
    }
    if (offsetA <= offsetC) {
      return -1; // before
    } else {
      return 1; // after
    }
  }

  // In the third case a child node C of the container of B is an ancestor container 
  // of A. In this case, A is before B if the index of the child node C is less than 
  // the offset of B and A is after B otherwise.
  c = containerA;
  while (c && c.parentNode != containerB) {
    c = c.parentNode;
  }
  if (c) {
    offsetC = 0;
    n = containerB.firstChild;
    while (n != c && offsetC < offsetB) {
      offsetC++;
      n = n.nextSibling;
    }
    if (offsetC < offsetB) {
      return -1; // before
    } else {
      return 1; // after
    }
  }

  // In the fourth case, none of three other cases hold: the containers of A and B 
  // are siblings or descendants of sibling nodes. In this case, A is before B if 
  // the container of A is before the container of B in a pre-order traversal of the
  // Ranges' context tree and A is after B otherwise.
  cmnRoot = this._commonAncestorContainer(containerA, containerB);
  childA = containerA;
  while (childA && childA.parentNode != cmnRoot) {
    childA = childA.parentNode;  
  }
  if (!childA) {
    childA = cmnRoot;
  }
  childB = containerB;
  while (childB && childB.parentNode != cmnRoot) {
    childB = childB.parentNode;
  }
  if (!childB) {
    childB = cmnRoot;
  }

  if (childA == childB) {
    return 0; // equal
  }

  n = cmnRoot.firstChild;
  while (n) {
    if (n == childA) {
      return -1; // before
    }
    if (n == childB) {
      return 1; // after
    }
    n = n.nextSibling;
  }

  try {
    throw new Exception(RangeException, RangeException.COMPARE_BOUNDARY_POINT_IMPLEMENTATION_ERR);
  } catch (e) {}
  // can never happen...
  
}

Range.prototype._commonAncestorContainer = function (containerA, containerB) {
  var parentStart = containerA, parentEnd;
  while (parentStart) {
    parentEnd = containerB;
    while (parentEnd && parentStart != parentEnd) {
      parentEnd = parentEnd.parentNode;
    }
    if (parentStart == parentEnd) {
      break;
    }
    parentStart = parentStart.parentNode;
  }

  if (!parentStart && containerA.ownerDocument) {
    return containerA.ownerDocument.documentElement;
  }

  return parentStart;
}

Range.prototype._isCollapsed = function() {
  return (this.startContainer == this.endContainer && this.startOffset == this.endOffset);
}

Range.prototype._offsetInCharacters = function (node) {
  switch (node.nodeType) {
    case Node.CDATA_SECTION_NODE:
    case Node.COMMENT_NODE:
    case Node.ELEMENT_NODE:
    case Node.PROCESSION_INSTRUCTION_NODE:
      return true;
    default:
      return false;
  }
}

Range.prototype._processContents = function(action) {

  try {

    var cmnRoot, partialStart = null, partialEnd = null, fragment, n, c, i;
    var leftContents, leftParent, leftContentsParent;
    var rightContents, rightParent, rightContentsParent;
    var next, prev;
    var processStart, processEnd;
    if (this.collapsed) {
      return;
    }

    cmnRoot = this.commonAncestorContainer;

    if (this.startContainer != cmnRoot) {
      partialStart = this.startContainer;
      while (partialStart.parentNode != cmnRoot) {
        partialStart = partialStart.parentNode;
      }
    }

    if (this.endContainer != cmnRoot) {
      partialEnd = this.endContainer;
      while (partialEnd.parentNode != cmnRoot) {
        partialEnd = partialEnd.parentNode;
      }
    }

    if (action == this.EXTRACT_CONTENTS || action == this.CLONE_CONTENTS) {
      fragment = this.ownerDocument.createDocumentFragment();
    }

    if (this.startContainer == this.endContainer) {
      switch (this.startContainer.nodeType) {
        case Node.CDATA_SECTION_NODE:
        case Node.COMMENT_NODE:
        case Node.TEXT_NODE:
          if (action == this.EXTRACT_CONTENTS || action == this.CLONE_CONTENTS) {
            c = this.startContainer.cloneNode();
            c.deleteData(this.endOffset, this.startContainer.data.length - this.endOffset);
            c.deleteData(0, this.startOffset);
            fragment.appendChild(c);
          }
          if (action == this.EXTRACT_CONTENTS || action == this.DELETE_CONTENTS) {
            this.startContainer.deleteData(this.startOffset, this.endOffset - this.startOffset);
          }
          break;
        case Node.PROCESSING_INSTRUCTION_NODE:
          //
          break;
        default:
          n = this.startContainer.firstChild;
          for (i = 0; i < this.startOffset; i++) {
            n = n.nextSibling;
          }
          while (n && i < this.endOffset) {
            next = n.nextSibling;
            if (action == this.EXTRACT_CONTENTS) {
              fragment.appendChild(n);
            } else if (action == this.CLONE_CONTENTS) {
              fragment.appendChild(n.cloneNode());
            } else {
              this.startContainer.removeChild(n);
            }
            n = next;
            i++;
          }
      }
      this.collapse(true);
      return fragment;
    }


    if (this.startContainer != cmnRoot) {
      switch (this.startContainer.nodeType) {
        case Node.CDATA_SECTION_NODE:
        case Node.COMMENT_NODE:
        case Node.TEXT_NODE:
          if (action == this.EXTRACT_CONTENTS || action == this.CLONE_CONTENTS) {
            c = this.startContainer.cloneNode(true);
            c.deleteData(0, this.startOffset);
            leftContents = c;
          }
          if (action == this.EXTRACT_CONTENTS || action == this.DELETE_CONTENTS) {
            this.startContainer.deleteData(this.startOffset, this.startContainer.data.length - this.startOffset);
          }
          break;
        case Node.PROCESSING_INSTRUCTION_NODE:
          //
          break;
        default:
          if (action == this.EXTRACT_CONTENTS || action == this.CLONE_CONTENTS) {
            leftContents = this.startContainer.cloneNode(false);
          }
          n = this.startContainer.firstChild;
          for (i = 0; i < this.startOffset; i++) {
            n = n.nextSibling;
          }
          while (n && i < this.endOffset) {
            next = n.nextSibling;
            if (action == this.EXTRACT_CONTENTS) {
              fragment.appendChild(n);
            } else if (action == this.CLONE_CONTENTS) {
              fragment.appendChild(n.cloneNode());
            } else {
              this.startContainer.removeChild(n);
            }
            n = next;
            i++;
          }
      }

      leftParent = this.startContainer.parentNode;
      n = this.startContainer.nextSibling;
      for(; leftParent != cmnRoot; leftParent = leftParent.parentNode) {
        if (action == this.EXTRACT_CONTENTS || action == this.CLONE_CONTENTS) {
          leftContentsParent = leftParent.cloneNode(false);
          leftContentsParent.appendChild(leftContents);
          leftContents = leftContentsParent;
        }

        for (; n; n = next) {
          next = n.nextSibling;
          if (action == this.EXTRACT_CONTENTS) {
            leftContents.appendChild(n);
          } else if (action == this.CLONE_CONTENTS) {
            leftContents.appendChild(n.cloneNode(true));
          } else {
            leftParent.removeChild(n);
          }
        }
        n = leftParent.nextSibling;
      }
    }

    if (this.endContainer != cmnRoot) {
      switch (this.endContainer.nodeType) {
        case Node.CDATA_SECTION_NODE:
        case Node.COMMENT_NODE:
        case Node.TEXT_NODE:
          if (action == this.EXTRACT_CONTENTS || action == this.CLONE_CONTENTS) {
            c = this.endContainer.cloneNode(true);
            c.deleteData(this.endOffset, this.endContainer.data.length - this.endOffset);
            rightContents = c;
          }
          if (action == this.EXTRACT_CONTENTS || action == this.DELETE_CONTENTS) {
            this.endContainer.deleteData(0, this.endOffset);
          }
          break;
        case Node.PROCESSING_INSTRUCTION_NODE:
          //
          break;
        default:
          if (action == this.EXTRACT_CONTENTS || action == this.CLONE_CONTENTS) {
            rightContents = this.endContainer.cloneNode(false);
          }
          n = this.endContainer.firstChild;
          if (n && this.endOffset) {
            for (i = 0; i+1 < this.endOffset; i++) {
              next = n.nextSibling;
              if (!next) {
                break;
              }
              n = next;
            }
            for (; n; n = prev) {
              prev = n.previousSibling;
              if (action == this.EXTRACT_CONTENTS) {
                rightContents.insertBefore(n, rightContents.firstChild);
              } else if (action == CLONE_CONTENTS) {
                rightContents.insertBefore(n.cloneNode(True), rightContents.firstChild);
              } else {
                this.endContainer.removeChild(n);
              }
            }
          }
      }

      rightParent = this.endContainer.parentNode;
      n = this.endContainer.previousSibling;
      for(; rightParent != cmnRoot; rightParent = rightParent.parentNode) {
        if (action == this.EXTRACT_CONTENTS || action == this.CLONE_CONTENTS) {
          rightContentsParent = rightContents.cloneNode(false);
          rightContentsParent.appendChild(rightContents);
          rightContents = rightContentsParent;
        }

        for (; n; n = prev) {
          prev = n.previousSibling;
          if (action == this.EXTRACT_CONTENTS) {
            rightContents.insertBefore(n, rightContents.firstChild);
          } else if (action == this.CLONE_CONTENTS) {
            rightContents.appendChild(n.cloneNode(true), rightContents.firstChild);
          } else {
            rightParent.removeChild(n);
          }
        }
        n = rightParent.previousSibling;
      }
    }

    if (this.startContainer == cmnRoot) {
      processStart = this.startContainer.firstChild;
      for (i = 0; i < this.startOffset; i++) {
        processStart = processStart.nextSibling;
      }
    } else {
      processStart = this.startContainer;
      while (processStart.parentNode != cmnRoot) {
        processStart = processStart.parentNode;
      }
      processStart = processStart.nextSibling;
    }
    if (this.endContainer == cmnRoot) {
      processEnd = this.endContainer.firstChild;
      for (i = 0; i < this.endOffset; i++) {
        processEnd = processEnd.nextSibling;
      }
    } else {
      processEnd = this.endContainer;
      while (processEnd.parentNode != cmnRoot) {
        processEnd = processEnd.parentNode;
      }
    }

    if ((action == this.EXTRACT_CONTENTS || action == this.CLONE_CONTENTS) && leftContents) {
      fragment.appendChild(leftContents);
    }

    if (processStart) {
      for (n = processStart; n && n != processEnd; n = next) {
        next = n.nextSibling;
        if (action == this.EXTRACT_CONTENTS) {
          fragment.appendChild(n);
        } else if (action == this.CLONE_CONTENTS) {
          fragment.appendChild(n.cloneNode(true));
        } else {
          cmnRoot.removeChild(n);
        }
      }
    }

    if ((action == this.EXTRACT_CONTENTS || action == this.CLONE_CONTENTS) && rightContents) {
      fragment.appendChild(rightContents);
    }

    if (action == this.EXTRACT_CONTENTS || action == this.DELETE_CONTENTS) {
      if (!partialStart && !partialEnd) {
        this.collapse(true);
      } else if (partialStart) {
        this.startContainer = partialStart.parentNode;
        this.endContainer = partialStart.parentNode;
        this.startOffset = this.endOffset = this._nodeIndex(partialStart) + 1;
      } else if (partialEnd) {
        this.startContainer = partialEnd.parentNode;
        this.endContainer = partialEnd.parentNode;
        this.startOffset = this.endOffset = this._nodeIndex(partialEnd);
      }
    }

    return fragment;

  } catch (e) {}  
}

Range.prototype._validateParameters = function (node, offset) {
  try {
    if (offset < 0) {
      throw new Exception(DOMException, DOMException.INDEX_SIZE_ERR);
    }

    switch (node.nodeType) {
      case Node.DOCUMENT_TYPE_NODE:
      case Node.ENTITY_NODE:
      case Node.NOTATION_NODE:
        throw new Exception(RangeException, RangeException.INVALID_NODE_TYPE_ERR);
        break;
      case Node.CDATA_SECTION_NODE:
      case Node.COMMENT_NODE:
      case Node.PROCESSING_INSTRUCTION_NODE:
      case Node.TEXT_NODE:
        if (offset > node.data.length) {
          throw new Exception(DOMException, DOMException.INDEX_SIZE_ERR);
        }
        break;
      case Node.ELEMENT_NODE:
        if (offset > node.childNodes.length) {
          throw new Exception(DOMException, DOMException.INDEX_SIZE_ERR);
        }
    }
  } catch (e) {}
}

/**
 * Used within the following methods for validating the refNode constraints
 *   Range.setStartBefore
 *   Range.setStartAfter
 *   Range.setEndBefore
 *   Range.setEndAfter
 *
 * @return
 *
 */
Range.prototype._validateParametersBeforeAfter = function (refNode) {
  try {

    if (this.detached == true) {
      throw new Exception(DOMException, DOMException.INVALID_STATE_ERR);
    }

    if (!refNode) {
      throw new Exception(DOMException, DOMException.NOT_FOUND_ERR);
    }

    if (this.ownerDocument != refNode.ownerDocument) {
      throw new Exception(DOMException, DOMException.WRONG_DOCUMENT_ERR);
    }

    var root = refNode;
    while (root.parentNode) {
      root = root.parentNode;
    }
    switch (root.nodeType) {
      case Node.ATTRIBUTE_NODE:
      case Node.DOCUMENT_FRAGMENT_NODE:
      case Node.DOCUMENT_NODE:
        break;
      default:
        throw new Exception(RangeException, RangeException.INVALID_NODE_TYPE_ERR);
    }
    switch (refNode.nodeType) {
      case Node.ATTRIBUTE_NODE:
      case Node.DOCUMENT_FRAGMENT_NODE:
      case Node.DOCUMENT_NODE:
      case Node.ENTITY_NODE:
      case Node.NOTATION_NODE:
        throw new Exception(RangeException, RangeException.INVALID_NODE_TYPE_ERR);
    }
  } catch (e) {}
}

Range.prototype._validateParametersSelectNode = function (refNode) {
  try {
    if (this.detached == true) {
      throw new Exception(DOMException, DOMException.INVALID_STATE_ERR);
    }

    if (!refNode) {
      throw new Exception(DOMException, DOMException.NOT_FOUND_ERR);
    }

    var ancestor;
    while (ancestor) {
      switch (ancestor.nodeType) {
        case Node.DOCUMENT_TYPE_NODE:
        case Node.ENTITY_NODE:
        case Node.NOTATION_NODE:
          throw new Exception(RangeException, RangeException.INVALID_NODE_TYPE_ERR);
      }

      ancestor = ancestor.parentNode;
    }
  } catch (e) {}
}

Range.prototype._nodeIndex = function (refNode) {
  var nodeIndex = 0;
  while (refNode.previousSibling) {
    nodeIndex++;
    refNode = refNode.previousSibling;
  }
  return nodeIndex;
}