/*
if ( typeof document.implementation == "undefined" ||
	(typeof document.createTreeWalker == "undefined" &&
	!document.implementation.hasFeature("Traversal", "2.0" ) ) ) {
*/

document.createTreeWalker = function ( root, whatToShow, filter, expandEntityReferences ) {
	return new TreeWalker( root, whatToShow, filter, expandEntityReferences );
};

//////////////////////////////////////////////////////////////////////////////
// TreeWalker
//

function TreeWalker( root, whatToShow, filter, expandEntityReferences ) {
	this.root = root;
	this.whatToShow = whatToShow;
	this.filter = filter;
	this.expandEntityReferences = expandEntityReferences;	// not taken into account
	this.currentNode = root
}

TreeWalker.prototype.parentNode = function() {
	var n = this.currentNode.parentNode;
	// loop until a node is found
	while ( n != this.root && n != null && !this._isAccepted( n ) )
		n = n.parentNode;
	if ( n != null )
		this.currentNode = n;
	return n;	
};

TreeWalker.prototype.firstChild = function() {
	var n = this.currentNode.firstChild;
	// loop until a node is found
	while ( n != null && !this._isAccepted( n ) )
		n = n.nextSibling;
	if ( n != null )
		this.currentNode = n;
	return n;
};

TreeWalker.prototype.lastChild = function() {
	var n = this.currentNode.lastChild;
	// loop until a node is found
	while ( n != null && !this._isAccepted( n ) )
		n = n.previousSibling;
	if ( n != null )
		this.currentNode = n;
	return n;
};

TreeWalker.prototype.nextSibling = function() {
	var n = this.currentNode.nextSibling;
	// loop until a node is found
	while ( n != null && !this._isAccepted( n ) )
		n = n.nextSibling;
	if ( n != null )
		this.currentNode = n;
	return n;
};

TreeWalker.prototype.previosuSibling = function() {
	var n = this.currentNode.previousSibling;
	// loop until a node is found
	while ( n != null && !this._isAccepted( n ) )
		n = n.previousSibling;
	if ( n != null )
		this.currentNode = n;
	return n;
};

TreeWalker.prototype.nextNode = function() {
	var n = this.currentNode;
	var isPartOfSubTree = this._getNodeContains( this.root, this.currentNode );
	var insideRoot, nodeFilterConstant = NodeFilter.FILTER_ACCEPT;
	do {
		n = this._getNodeAfter( n, nodeFilterConstant );
		nodeFilterConstant = this._acceptNode( n );
		insideRoot = !isPartOfSubTree || this._getNodeContains( this.root, n );
	} while ( n != null && insideRoot && nodeFilterConstant != NodeFilter.FILTER_ACCEPT );
	
	if ( n != null && insideRoot )
		this.currentNode = n;
	else if ( !insideRoot )
		return null;
	return n;
};

TreeWalker.prototype.previousNode = function() {
	var n = this.currentNode;
	var isPartOfSubTree = this._getNodeContains( this.root, this.currentNode );
	var insideRoot, nodeFilterConstant = NodeFilter.FILTER_ACCEPT;
	do {
		n = this._getNodeBefore( n, nodeFilterConstant );
		nodeFilterConstant = this._acceptNode( n );
		insideRoot = !isPartOfSubTree || this._getNodeContains( this.root, n );
	} while ( n != null && insideRoot && nodeFilterConstant != NodeFilter.FILTER_ACCEPT );
	
	if ( n != null && insideRoot )
		this.currentNode = n;
	else if ( !insideRoot )
		return null;
	return n;
};

// private methods

// checks whatToShow and filter to decide whether to accept node or not
TreeWalker.prototype._isAccepted = function ( n ) {
	return this._acceptNode( n ) == NodeFilter.FILTER_ACCEPT;
};

/*
// checks whatToShow and filter to decide whether to reject node or not
TreeWalker.prototype._isRejected = function ( n ) {
	if ( this.filter != null )
		return this.filter.acceptNode( n ) == NodeFilter.FILTER_REJECT;
	return false;
};
*/

// first checks the whatToShow and then the filter
TreeWalker.prototype._acceptNode = function ( n ) {
	if ( n == null )
		return NodeFilter.FILTER_REJECT;
	var whatToShowAccepted = NodeFilter._acceptNode( n, this.whatToShow );
	if ( whatToShowAccepted != NodeFilter.FILTER_ACCEPT )
		return whatToShowAccepted;
	if ( this.filter != null )
		return this.filter.acceptNode( n );
	return NodeFilter.FILTER_ACCEPT;	
};

// returns node after. Takes the filter into account in case of a reject
TreeWalker.prototype._getNodeAfter = function ( n, nodeFilterConstant ) {
	if ( n == null )
		return null;
	else if ( n.hasChildNodes() && nodeFilterConstant != NodeFilter.FILTER_REJECT )
		return n.firstChild;
	else if ( n.nextSibling != null )
		return n.nextSibling;
	else {
		var tmp = n;
		while ( true ) {
			if ( tmp == null)
				return null;
			else if ( tmp.nextSibling != null )
				return tmp.nextSibling;
			else
				tmp = tmp.parentNode;
		}
	}
};

TreeWalker.prototype._getNodeBefore = function( n, nodeFilterConstant ) {
	if ( n == null )
		return null;
	if ( n.previousSibling != null )
		return this._getLastDescendant( n.previousSibling, nodeFilterConstant );
	else
		return n.parentNode;
};

// returns node after. Takes the filter into account in case of a reject
TreeWalker.prototype._getLastDescendant = function ( n, nodeFilterConstant ) {
	if ( n.hasChildNodes() && !nodeFilterConstant != NodeFilter.FITLER_REJECT )
		return this._getLastDescendant( n.lastChild );
	else
		return n;
};

TreeWalker.prototype._getNodeContains = function ( p, c ) {
	if ( c == null )
		return false;
	else if ( p == c )
		return true;
	else
		return this._getNodeContains( p, c.parentNode );
}




//////////////////////////////////////////////////////////////////////////////
// NodeFilter
//

function NodeFilter() {}

// Constants returned by acceptNode
NodeFilter.FILTER_ACCEPT                  = 1;
NodeFilter.FILTER_REJECT                  = 2;
NodeFilter.FILTER_SKIP                    = 3;

 // Constants for whatToShow
NodeFilter.SHOW_ALL                       = 0xFFFFFFFF;
NodeFilter.SHOW_ELEMENT                   = 0x00000001;
NodeFilter.SHOW_ATTRIBUTE                 = 0x00000002;
NodeFilter.SHOW_TEXT                      = 0x00000004;
NodeFilter.SHOW_CDATA_SECTION             = 0x00000008;
NodeFilter.SHOW_ENTITY_REFERENCE          = 0x00000010;
NodeFilter.SHOW_ENTITY                    = 0x00000020;
NodeFilter.SHOW_PROCESSING_INSTRUCTION    = 0x00000040;
NodeFilter.SHOW_COMMENT                   = 0x00000080;
NodeFilter.SHOW_DOCUMENT                  = 0x00000100;
NodeFilter.SHOW_DOCUMENT_TYPE             = 0x00000200;
NodeFilter.SHOW_DOCUMENT_FRAGMENT         = 0x00000400;
NodeFilter.SHOW_NOTATION                  = 0x00000800;

NodeFilter.prototype.acceptNode = function ( n ) {
	return NodeFilter.FILTER_ACCEPT;
};

// this funtion uses the whatToShow bit mask and checks the current
// node type to see if will be accepted
NodeFilter._acceptNode = function ( n, whatToShow ) {
	if ( whatToShow == NodeFilter.SHOW_ALL )
		return NodeFilter.FILTER_ACCEPT;
		
	var bitMask;
	switch ( n.nodeType ) {
		
		case 1:
			bitMask = NodeFilter.SHOW_ELEMENT;
			break;
		case 2:
			bitMask = NodeFilter.SHOW_ATTRIBUTE
			break;
		case 3:
			bitMask = NodeFilter.SHOW_TEXT;
			break;
		case 4:
			bitMask = NodeFilter.SHOW_CDATA_SECTION;
			break;
		case 5:
			bitMask = NodeFilter.SHOW_ENTITY_REFERENCE;
			break;
		case 6:
			bitMask = NodeFilter.SHOW_ENTITY;
			break;
		case 7:
			bitMask = NodeFilter.SHOW_PROCESSING_INSTRUCTION;
			break;
		case 8:
			bitMask = NodeFilter.SHOW_COMMENT;
			break;
		case 9:
			bitMask = NodeFilter.SHOW_DOCUMENT;
			break;
		case 10:
			bitMask = NodeFilter.SHOW_DOCUMENT_TYPE;
			break;
		case 11:
			bitMask = NodeFilter.SHOW_DOCUMENT_FRAGMENT;
			break;
		case 12:
			bitMask = NodeFilter.SHOW_NOTATION;
			break;
	}

	return (bitMask & whatToShow) != 0 ?
			NodeFilter.FILTER_ACCEPT :
			NodeFilter.FILTER_SKIP;
};
/*
}// close if statement
*/