// DOM2 Traversal  v1.0
// documentation: http://www.dithered.com/javascript/dom2_traversal/index.html
// license: http://creativecommons.org/licenses/by/1.0/
// code by Chris Nott (chris[at]dithered[dot]com)


if (!(document.implementation && document.implementation.hasFeature && document.implementation.hasFeature('Traversal', '2.0'))) {
   
   /*****************************************************************************
      NodeFilter Interface
    *****************************************************************************/ 

   if (!document.createNodeIterator && !document.createTreeWalker) {
      var NodeFilter = {
         FILTER_ACCEPT : 1,
         FILTER_REJECT : 2,
         FILTER_SKIP : 3,
         SHOW_ALL     : 0xFFFFFFFF,
         SHOW_ELEMENT : 0x00000001,
         SHOW_ATTRIBUTE : 0x00000002,
         SHOW_TEXT : 0x00000004,
         SHOW_CDATA_SECTION : 0x00000008,
         SHOW_ENTITY_REFERENCE : 0x00000010,
         SHOW_ENTITY : 0x00000020,
         SHOW_PROCESSING_INSTRUCTIONS : 0x00000040,
         SHOW_COMMENT : 0x00000080,
         SHOW_DOCUMENT : 0x00000100,
         SHOW_DOCUMENT_TYPE : 0x00000200,
         SHOW_DOCUMENT_FRAGMENT : 0x00000400,
         SHOW_NOTATION : 0x00000800
         };
   }
   
   
   /*****************************************************************************
      NodeIterator Interface
    *****************************************************************************/ 
      
   if (!document.createNodeIterator) {
      //function NodeIterator(root, whatToShow, filter, expandEntityReferences) {}
      //NodeIterator.prototype.nextNode = function() {};
      //NodeIterator.prototype.previousNode = function() {};
      //NodeIterator.prototype.detach = function() {};
      //document.createNodeIterator = function(root, whatToShow, filter, expandEntityReferences) {};
   }
   

   /*****************************************************************************
      TreeWalker Interface
    *****************************************************************************/ 
   
   if (!document.createTreeWalker) {
   
      function TreeWalker(root, whatToShow, filter, expandEntityReferences) {
         this.root = root;
         this.whatToShow = whatToShow;
         this.filter = filter;
         this.expandEntityReferences = expandEntityReferences;
         this.currentNode = root;
      }
      
      //*************************************
      // Public Members
      
      TreeWalker.prototype.parentNode = function() {
         var testNode = currentNode;
         do {
            if (testNode.parentNode != this.root && testNode.parentNode != null) {
               testNode = testNode.parentNode;
            }
            else {
               return null;
            }
         } while (this._getFilteredStatus(testNode) != NodeFilter.FILTER_ACCEPT);
         return testNode;
      };
      
      TreeWalker.prototype.firstChild = function() {
         var childNodes = currentNode.childNodes;
         for (var childIndex = 0; childIndex < childNodes.length; childIndex++) {
            var testNode = childNodes[childIndex];
            if (this._getFilteredStatus(testNode) != NodeFilter.FILTER_ACCEPT) {
               this.currentNode = testNode;
               return testNode;
            }
         }
         return null;
      };
      
      TreeWalker.prototype.lastChild = function() {
         var childNodes = currentNode.childNodes;
         for (var childIndex = childNodes.length - 1; childIndex >= 0; childIndex--) {
            var testNode = childNodes[childIndex];
            if (this._getFilteredStatus(testNode) != NodeFilter.FILTER_ACCEPT) {
               this.currentNode = testNode;
               return testNode;
            }
         }
         return null;      
      };
      
      TreeWalker.prototype.nextNode = function() {
         
         // look for a filter-acceptable node after current node
         var testNode = this.currentNode;
         while (testNode != null) {
            
            // next node is the first child, if any
            if (testNode.childNodes.length != 0 && this._getFilteredStatus(testNode) != NodeFilter.FILTER_REJECT) {
               testNode = testNode.firstChild;
            }
            
            // or the next sibling, if any
            else if (testNode.nextSibling != null) {
               testNode = testNode.nextSibling;
            }
            
            // or the closest ancestor with a next sibling's next sibling, if any
            else {
               do {
                  if (testNode.parentNode != this.root && testNode.parentNode != null) {
                     if (testNode.parentNode.nextSibling != null) {
                        testNode = testNode.parentNode.nextSibling;
                        break;
                     }
                     else {
                        testNode = testNode.parentNode;
                     }
                  }
                  else {
                     testNode = null;
                  }
               } while (testNode != null);
            }
            
            if (testNode != null && this._getFilteredStatus(testNode) == NodeFilter.FILTER_ACCEPT) {
               break;
            }
         }
         
         // if an acceptable node was found, update the current node
         if (testNode != null) {
            this.currentNode = testNode;
         }
         
         // return found node (or null if no next node)
         return testNode;
      };
      
      TreeWalker.prototype.previousNode = function() {
         
         // look for a filter-acceptable node before current node
         var testNode = this.currentNode;
         while (testNode != null) {
            
            // next node is the last child, if any (as long as test node isn't the current node)
            if (testNode != currentNode && testNode.childNodes.length != 0 && this._getFilteredStatus(testNode) != NodeFilter.FILTER_REJECT) {
               testNode = testNode.lastChild;
            }
            
            // or the previous sibling, if any
            else if (testNode.previousSibling != null) {
               testNode = testNode.previousSibling;
            }
            
            // or the closest ancestor with a previous sibling's previous sibling, if any
            else {
               do {
                  if (testNode.parentNode != this.root && testNode.parentNode != null) {
                     if (testNode.parentNode.previousSibling != null) {
                        testNode = testNode.parentNode.previousSibling;
                        break;
                     }
                     else {
                        testNode = testNode.parentNode;
                     }
                  }
                  else {
                     testNode = null;
                  }
               } while (testNode != null);
            }
            
            if (testNode != null && this._getFilteredStatus(testNode) == NodeFilter.FILTER_ACCEPT) {
               break;
            }
         }
         
         // if an acceptable node was found, update the reference node
         if (testNode != null) {
            this.currentNode = testNode;
         }
         
         // return found node (or null if no previous node)
         return testNode;
      };
      
      TreeWalker.prototype.nextSibling = function() {
         var testNode = currentNode;
         do {
            if (currentNode.nextSibling != null) {
               testNode = currentNode.nextSibling;
            }
            else {
               return null;
            }
         } while (this._getFilteredStatus(testNode) != NodeFilter.FILTER_ACCEPT);
         return testNode;
      };

      TreeWalker.prototype.previousSibling = function() {
         var testNode = currentNode;
         do {
            if (currentNode.previousSibling != null) {
               testNode = currentNode.previousSibling;
            }
            else {
               return null;
            }
         } while (this._getFilteredStatus(testNode) != NodeFilter.FILTER_ACCEPT);
         return testNode;
      };
      
      document.createTreeWalker = function(root, whatToShow, filter, expandEntityReferences) {
         return new TreeWalker(root, whatToShow, filter, expandEntityReferences);
      };


      //*************************************
      // Private Members
   
      TreeWalker.prototype._getFilteredStatus = function(node) {
   
         // check node against whatToShow flags
         if ( (node.nodeType == Node.ELEMENT_NODE && (this.whatToShow & NodeFilter.SHOW_ELEMENT == 0x0) ) ||
           (node.nodeType == Node.ATTRIBUTE_NODE && (this.whatToShow & NodeFilter.SHOW_ATTRIBUTE == 0x0) ) ||
           (node.nodeType == Node.TEXT_NODE && (this.whatToShow & NodeFilter.SHOW_TEXT == 0x0) ) ||
           (node.nodeType == Node.CDATA_SECTION_NODE && (this.whatToShow & NodeFilter.SHOW_CDATA_SECTION == 0x0) ) ||
           (node.nodeType == Node.ENTITY_REFERENCE_NODE && (this.whatToShow & NodeFilter.SHOW_ENTITY_REFERENCE == 0x0) ) ||
           (node.nodeType == Node.ENTITY_NODE && (this.whatToShow & NodeFilter.SHOW_ENTITY == 0x0) ) ||
           (node.nodeType == Node.PROCESSING_INSTRUCTION_NODE && (this.whatToShow & NodeFilter.SHOW_PROCESSING_INSTRUCTION == 0x0) ) ||
           (node.nodeType == Node.COMMENT_NODE && (this.whatToShow & NodeFilter.SHOW_COMMENT == 0x0) ) ||
           (node.nodeType == Node.DOCUMENT_NODE && (this.whatToShow & NodeFilter.SHOW_DOCUMENT == 0x0) ) ||
           (node.nodeType == Node.DOCUMENT_TYPE_NODE && (this.whatToShow & NodeFilter.SHOW_DOCUMENT_TYPE == 0x0) ) ||
           (node.nodeType == Node.DOCUMENT_FRAGMENT_NODE && (this.whatToShow & NodeFilter.SHOW_DOCUMENT_FRAGMENT == 0x0) ) ||
           (node.nodeType == Node.NOTATION_NODE && (this.whatToShow & NodeFilter.SHOW_NOTATION == 0x0) ) ) {
            return NodeFilter.FILTER_SKIP;
         }
         
         // check node against filter if one exists
         if (this.filter != null && this.filter.acceptNode != null) {
            return this.filter.acceptNode(node);
         }
         else {
            return NodeFilter.FILTER_ACCEPT;
         }
      };
   }
}