using System.Collections;
using System.Collections.Generic;
using System;

namespace Rokojori
{
  public abstract class GraphWalker<N> where N:class
  {
    public virtual int NumConnectedFrom( N node ){ return 0;}
    public virtual N GetConnectedFrom( N node, int index ){ return default(N);}

    public abstract int NumConnectedTo( N node );
    public abstract N GetConnectedTo( N node, int index );

    public int NumConnectedAll( N node )
    {
      return NumConnectedTo( node ) + NumConnectedFrom( node );
    }

    public N GetConnected( N node, int index )
    {
      var fromConnections = NumConnectedFrom( node );

      return index < fromConnections ? GetConnectedFrom( node, index ) : GetConnectedTo( node, index - fromConnections );
    }


    public bool IsConnectedTo( N source, N destination )
    {
      var processed = new HashSet<N>();
      var toDo = new List<N>();

      toDo.Add( source );

      while ( toDo.Count > 0 )
      {
        var current = Lists.RemoveFirst( toDo );
        
        if ( processed.Contains( current ) )
        {
          continue;
        }

        processed.Add( current );

        var numConnected = NumConnectedTo( current );
        
        for ( int i = 0; i < numConnected; i++ )
        {
          var connected = GetConnected( current, i );
          
          if ( connected == destination )
          {
            return true;
          }

          if ( ! processed.Contains( connected ) )
          {
            toDo.Add( connected );
          }
        }
      }

      return false;
    }

    

    public bool IsDirectlyConnectedTo( N node, N other )
    {
      if ( node == null || other == null )
      {
        return false;
      }

      var connected = NumConnectedTo( node );

      for ( int i = 0; i < connected; i++ )
      {
        if ( GetConnected( node, i ) == other ) 
        {
          return true;
        }
      }

      return false;
    }
  }
}