library-ts/browser/graphs/TreeWalker.ts

// (boolean|N|number)\s+(\w+)\(\s*(?:(\w+)\s*(\w+))\s*\)
// $2( $4:$3 ):$1
// (boolean|N|number)\s+(\w+)\(\s*(?:(\w+)\s*(\w+))\s*(?:\,\s*(\w+)\s*(\w+))\s*\)
// $2( $4:$3, $6:$5 ):$1
// (\w+)\(\s+(\w+)\s+\)
// this.$1( $2 )
// (\w+)\(\s+(\w+)\s+\)
// this.$1( $2 )
export abstract class TreeWalker<N> 
{
  abstract parent( node:N ):N;  
  
  abstract childAt( node:N, index:number ):N;  
  
  abstract numChildren( node:N ):number;  
  
  hasChildren( node:N ):boolean
  {
		return this.numChildren( node )>0;
	}
	
  hasParent( node:N ):boolean
  {
		return this.parent( node ) != null;
	}
  
  childIndexOf( node:N ):number
  {
    let p = this.parent( node );

    if ( p == null )
    {
      return -1;
    }
    
    let numKids = this.numChildren( p );
    
    for ( let i = 0; i<numKids; i++ )
    {
      if ( this.childAt( p, i ) == node )
      {
        return i;
      }
    }
    
    return -1;
    
  }
	
  siblingAt( node:N, index:number ):N
	{
		let p = this.parent( node );
    
		if ( p == null || index<0 || index >= this.numChildren( p ) )
		{ return null; }

		return this.childAt( p, index );
	}
  
  
  nextSibling( node:N ):N
  {
    let index = this.childIndexOf( node );      
    return this.siblingAt( node, index+1 );
  }
  
  
  previousSibling( node:N ):N
  {
    let index = this.childIndexOf( node );      
    return this.siblingAt( node, index-1 );
  }
  
  
  hasSiblingAt( node:N, index:number ):boolean
	{
		let p = this.parent( node );
		if ( p == null || index<0 || index >= this.numChildren( p ) )
		{ return false; }
		return true;
	}
  
  
  firstChild( node:N ):N
  {
		return this.numChildren( node )<=0?null:this.childAt( node, 0 );
	}
	
	
  lastChild( node:N ):N
  {
		let num = this.numChildren( node );
		return num <= 0?null:this.childAt( node, num-1 );
	}

  getAll( node:N, selector:( n:N )=> boolean )
  {
    let output:N[] = [];
    
    for ( let i = 0; i < this.numChildren( node ); i++ )
    {
      let n = this.childAt( node, i );

      if ( ! selector( n ) )
      {
        continue;
      }

      output.push( n );
    }

    return output;
  }
  
  forAll( node:N, callback:( node:N ) => void )
  {
    let end = this.iterationEndOf( node );

    let it = node;
    
    while ( it && it !== end )
    {
      callback( it );
      it = this.nextNode( it );
    }
    
  }
	
  nextNode( node:N ):N
  {
		if ( this.hasChildren( node ) )
		{
			return this.firstChild( node );
		}
		
		let next = this.nextSibling( node );
		
		if ( next != null )
		{
			return next;
		}

		let parent = this.parent( node );
		
		while ( parent != null )
		{
			let n = this.nextSibling( parent );

			if ( n != null )
			{
				return n;
			}

			parent = this.parent( parent );
		}
    
		return null;
	}
	
	
  previousNode( node:N ):N
  {
		let prev = this.previousSibling( node );
		
		if ( prev != null )
		{
			while ( this.hasChildren( prev ) )
			{
				prev = this.lastChild( prev );
			}
			return prev;
		}

		return this.parent( node );
	}
  
  
  rootParent( node:N ):N
  {
		node = this.parent( node );

		if ( node == null )
		{
			return null;
		}

		while ( this.hasParent( node ) )
		{
			node = this.parent( node );
		}

		return node;
	}
  
  
  lastGrandChild( node:N ):N
  {
		if ( this.hasChildren( node ) )
		{
			node = this.lastChild( node );

			while ( this.hasChildren( node ) )
			{
				node = this.lastChild( node );
			}
      
			return node;
		}
    
		return null;
	}
  
  isChildOfAny( child:N, set:Set<N> ):boolean 
  {
    let p = this.parent( child );

    while ( p )
    {
      if ( set.has( p ) )
      {
        return true;
      }

      p = this.parent( p ); 
    }

    return false;
  }

  childOf( child:N, parent:N ):boolean
	{
		let p = this.parent( child );

		while ( p != null )
		{
			if ( p == parent )
			{
				return true;
			}
			p = this.parent( p );
		}

		return false;
	}
  
  
  numParents( node:N ):number
  {
		let num = 0;
		let p = this.parent( node );

		while ( p != null )
		{
			num++;
			p = this.parent( p );
		}

		return num;
	}
  
  
  lastOuterNode( node:N ):N
  {  	
		while ( this.hasChildren( node ) )
		{
			node = this.lastChild( node );
		}

		return node;
	}
	
	
  nextNonChild( node:N ):N
  {
		return this.nextNode( this.lastOuterNode( node ) );
	}    
  
  iterationEndOf( node:N ):N
  {
    return this.nextNonChild( node );
  }
  
}