#############################################################################
# Path and cell management for Graph::Easy.
#
#############################################################################

package Graph::Easy::Layout::Path;

$VERSION = '0.76';

#############################################################################
#############################################################################

package Graph::Easy::Node;

use strict;
use warnings;

use Graph::Easy::Edge::Cell qw/
 EDGE_END_E EDGE_END_N EDGE_END_S EDGE_END_W
/;

sub _shuffle_dir
  {
  # take a list with four entries and shuffle them around according to $dir
  my ($self, $e, $dir) = @_;

  # $dir: 0 => north, 90 => east, 180 => south, 270 => west

  $dir = 90 unless defined $dir;		# default is east

  return [ @$e ] if $dir == 90;			# default is no shuffling

  my @shuffle = (0,1,2,3);			# the default
  @shuffle = (1,2,0,3) if $dir == 180;		# south
  @shuffle = (2,3,1,0) if $dir == 270;		# west
  @shuffle = (3,0,2,1) if $dir == 0;		# north

  [
    $e->[ $shuffle[0] ],
    $e->[ $shuffle[1] ],
    $e->[ $shuffle[2] ],
    $e->[ $shuffle[3] ],
  ];
  }

sub _shift
  {
  # get a flow shifted by X° to $dir
  my ($self, $turn) = @_;

  my $dir = $self->flow();

  $dir += $turn;
  $dir += 360 if $dir < 0;
  $dir -= 360 if $dir > 360;
  $dir;
  }

sub _near_places
  {
  # Take a node and return a list of possible placements around it and
  # prune out already occupied cells. $d is the distance from the node
  # border and defaults to two (for placements). Set it to one for
  # adjacent cells.

  # If defined, $type contains four flags for each direction. If undef,
  # two entries (x,y) will be returned for each pos, instead of (x,y,type).

  # If $loose is true, no checking whether the returned fields are free
  # is done.

  my ($n, $cells, $d, $type, $loose, $dir) = @_;

  my $cx = $n->{cx} || 1;
  my $cy = $n->{cy} || 1;

  $d = 2 unless defined $d;		# default is distance = 2

  my $flags = $type;

  if (ref($flags) ne 'ARRAY')
    {
    $flags = [
      EDGE_END_W,
      EDGE_END_N,
      EDGE_END_E,
      EDGE_END_S,
     ];
    }
  $dir = $n->flow() unless defined $dir;

  my $index = $n->_shuffle_dir( [ 0,3,6,9], $dir);

  my @places = ();

  # single-celled node
  if ($cx + $cy == 2)
    {
    my @tries  = (
  	$n->{x} + $d, $n->{y}, $flags->[0],	# right
	$n->{x}, $n->{y} + $d, $flags->[1],	# down
	$n->{x} - $d, $n->{y}, $flags->[2],	# left
	$n->{x}, $n->{y} - $d, $flags->[3],	# up
      );

    for my $i (0..3)
      {
      my $idx = $index->[$i];
      my ($x,$y,$t) = ($tries[$idx], $tries[$idx+1], $tries[$idx+2]);

#      print STDERR "# Considering place $x, $y \n";

      # This quick check does not take node clusters or multi-celled nodes
      # into account. These are handled in $node->_do_place() later.
      next if !$loose && exists $cells->{"$x,$y"};
      push @places, $x, $y;
      push @places, $t if defined $type;
      }
    return @places;
    }

  # Handle a multi-celled node. For a 3x2 node:
  #      A   B   C
  #   J [00][10][20] D
  #   I [10][11][21] E
  #      H   G   F
  # we have 10 (3 * 2 + 2 * 2) places to consider

  my $nx = $n->{x};
  my $ny = $n->{y};
  my ($px,$py);

  my $idx = 0;
  my @results = ( [], [], [], [] );

  $cy--; $cx--;
  my $t = $flags->[$idx++];
  # right
  $px = $nx + $cx + $d;
  for my $y (0 .. $cy)
    {
    $py = $y + $ny;
    next if exists $cells->{"$px,$py"} && !$loose;
    push @{$results[0]}, $px, $py;
    push @{$results[0]}, $t if defined $type;
    }

  # below
  $py = $ny + $cy + $d;
  $t = $flags->[$idx++];
  for my $x (0 .. $cx)
    {
    $px = $x + $nx;
    next if exists $cells->{"$px,$py"} && !$loose;
    push @{$results[1]}, $px, $py;
    push @{$results[1]}, $t if defined $type;
    }

  # left
  $px = $nx - $d;
  $t = $flags->[$idx++];
  for my $y (0 .. $cy)
    {
    $py = $y + $ny;
    next if exists $cells->{"$px,$py"} && !$loose;
    push @{$results[2]}, $px, $py;
    push @{$results[2]}, $t if defined $type;
    }

  # top
  $py = $ny - $d;
  $t = $flags->[$idx];
  for my $x (0 .. $cx)
    {
    $px = $x + $nx;
    next if exists $cells->{"$px,$py"} && !$loose;
    push @{$results[3]}, $px, $py;
    push @{$results[3]}, $t if defined $type;
    }

  # accumulate the results in the requested, shuffled order
  for my $i (0..3)
    {
    my $idx = $index->[$i] / 3;
    push @places, @{$results[$idx]};
    }

  @places;
  }

sub _allowed_places
  {
  # given a list of potential positions, and a list of allowed positions,
  # return the valid ones (e.g. that are in both lists)
  my ($self, $places, $allowed, $step) = @_;

  print STDERR
   "# calculating allowed places for $self->{name} from " . @$places .
   " positions and " . scalar @$allowed . " allowed ones:\n"
    if $self->{graph}->{debug};

  $step ||= 2;				# default: "x,y"

  my @good;
  my $i = 0;
  while ($i < @$places)
    {
    my ($x,$y) = ($places->[$i], $places->[$i+1]);
    my $allow = 0;
    my $j = 0;
    while ($j < @$allowed)
      {
      my ($m,$n) = ($allowed->[$j], $allowed->[$j+1]);
      $allow++ and last if ($m == $x && $n == $y);
      } continue { $j += 2; }
    next unless $allow;
    push @good, $places->[$i + $_ -1] for (1..$step);
    } continue { $i += $step; }

  print STDERR "#  left with " . ((scalar @good) / $step) . " position(s)\n" if $self->{graph}->{debug};
  @good;
  }

sub _allow
  {
  # return a list of places, depending on the start/end attribute:
  # "south" - any place south
  # "south,0" - first place south
  # "south,-1" - last place south
  # XXX TODO:
  # "south,0..2" - first three places south
  # "south,0,1,-1" - first, second and last place south

  my ($self, $dir, @pos) = @_;

  # for relative direction, get the absolute flow from the node
  if ($dir =~ /^(front|forward|back|left|right)\z/)
    {
    # get the flow at the node
    $dir = $self->flow();
    }

  my $place = {
    'south' => [  0,0, 0,1, 'cx', 1,0 ],
    'north' => [ 0,-1, 0,0, 'cx', 1,0 ],
    'east' =>  [  0,0, 1,0, 'cy', 0,1 ],
    'west' =>  [ -1,0, 0,0, 'cy', 0,1 ] ,
    180 => [  0,0, 0,1, 'cx', 1,0 ],
    0 => [ 0,-1, 0,0, 'cx', 1,0 ],
    90 =>  [  0,0, 1,0, 'cy', 0,1 ],
    270 =>  [ -1,0, 0,0, 'cy', 0,1 ] ,
    };

  my $p = $place->{$dir};

  return [] unless defined $p;

  # start pos
  my $x = $p->[0] + $self->{x} + $p->[2] * $self->{cx};
  my $y = $p->[1] + $self->{y} + $p->[3] * $self->{cy};

  my @allowed;
  push @pos, '' if @pos == 0;

  my $c = $p->[4];
  if (@pos == 1 && $pos[0] eq '')
    {
    # allow all of them
    for (1 .. $self->{$c})
      {
      push @allowed, $x, $y;
      $x += $p->[5];
      $y += $p->[6];
      }
    }
  else
    {
    # allow only the given position
    my $ps = $pos[0];
    # limit to 0..$self->{cx}-1
    $ps = $self->{$c} + $ps if $ps < 0;
    $ps = 0 if $ps < 0;
    $ps = $self->{$c} - 1 if $ps >= $self->{$c};
    $x += $p->[5] * $ps;
    $y += $p->[6] * $ps;
    push @allowed, $x, $y;
    }

  \@allowed;
  }

package Graph::Easy;
use strict;
use Graph::Easy::Node::Cell;

use Graph::Easy::Edge::Cell qw/
  EDGE_HOR EDGE_VER EDGE_CROSS
  EDGE_TYPE_MASK
  EDGE_HOLE
 /;

sub _clear_tries
  {
  # Take a list of potential positions for a node, and then remove the
  # ones that are immediately near any other node.
  # Returns a list of "good" positions. Afterwards $node->{x} is undef.
  my ($self, $node, $cells, $tries) = @_;

  my $src = 0; my @new;

  print STDERR "# clearing ", scalar @$tries / 2, " tries for $node->{name}\n" if $self->{debug};

  my $node_grandpa = $node->find_grandparent();

  while ($src < scalar @$tries)
    {
    # check the current position

    # temporary place node here
    my $x = $tries->[$src];
    my $y = $tries->[$src+1];

#    print STDERR "# checking $x,$y\n" if $self->{debug};

    $node->{x} = $x;
    $node->{y} = $y;

    my @near = $node->_near_places($cells, 1, undef, 1);

    # push also the four corner cells to avoid placing nodes corner-to-corner
    push @near, $x-1, $y-1,					# upperleft corner
                $x-1, $y+($node->{cy}||1),			# lowerleft corner
                $x+($node->{cx}||1), $y+($node->{cy}||1),	# lowerright corner
                $x+($node->{cx}||1), $y-1;			# upperright corner

    # check all near places to be free from nodes (except our children)
    my $j = 0; my $g = 0;
    while ($j < @near)
      {
      my $xy = $near[$j]. ',' . $near[$j+1];

#      print STDERR "# checking near-place: $xy: " . ref($cells->{$xy}) . "\n" if $self->{debug};

      my $cell = $cells->{$xy};

      # skip, unless we are a children of node, or the cell is our children
      next unless ref($cell) && $cell->isa('Graph::Easy::Node');

      my $grandpa = $cell->find_grandparent();

      #       this cell is our children
      #                            this cell is our grandpa
      #                                                      has the same grandpa as node
      next if $grandpa == $node || $cell == $node_grandpa || $grandpa == $node_grandpa;

      $g++; last;

      } continue { $j += 2; }

    if ($g == 0)
      {
      push @new, $tries->[$src], $tries->[$src+1];
      }
    $src += 2;
    }

  $node->{x} = undef;

  @new;
  }

my $flow_shift = {
  270 => [ 0, -1 ],
   90 => [ 0,  1 ],
    0 => [ 1,  0 ],
  180 => [ -1, 0 ],
  };

sub _placed_shared
  {
  # check whether one of the nodes from the list of shared was already placed
  my ($self) = shift;

  my $placed;
  for my $n (@_)
    {
    $placed = [$n->{x}, $n->{y}] and last if defined $n->{x};
    }
  $placed;
  }

use Graph::Easy::Util qw(first_kv);

sub _find_node_place
  {
  # Try to place a node (or node cluster). Return score (usually 0).
  my ($self, $node, $try, $parent, $edge) = @_;

  $try ||= 0;

  print STDERR "# Finding place for $node->{name}, try #$try\n" if $self->{debug};
  print STDERR "# Parent node is '$parent->{name}'\n" if $self->{debug} && ref $parent;

  print STDERR "# called from ". join (" ", caller) . "\n" if $self->{debug};

  # If the node has a user-set rank, see if we already placed another node in that
  # row/column
  if ($node->{rank} >= 0)
    {
    my $r = abs($node->{rank});
#    print STDERR "# User-set rank for $node->{name} (rank $r)\n";
    my $c = $self->{_rank_coord};
#    use Data::Dumper; print STDERR "# rank_pos: \n", Dumper($self->{_rank_pos});
    if (exists $self->{_rank_pos}->{ $r })
      {
      my $co = { x => 0, y => 0 };
      $co->{$c} = $self->{_rank_pos}->{ $r };
      while (1 < 3)
        {
#	print STDERR "# trying to force placement of '$node->{name}' at $co->{x} $co->{y}\n";
        return 0 if $node->_do_place($co->{x},$co->{y},$self);
        $co->{$c} += 2;
        }
      }
    }

  my $cells = $self->{cells};

#  local $self->{debug} = 1;

  my $min_dist = 2;
  # minlen = 0 => min_dist = 2,
  # minlen = 1 => min_dist = 2,
  # minlen = 2 => min_dist = 3, etc
  $min_dist = $edge->attribute('minlen') + 1 if ref($edge);

  # if the node has outgoing edges (which might be shared)
  if (!ref($edge))
    {
    (undef,$edge) = first_kv($node->{edges}) if keys %{$node->{edges}} > 0;
    }

  my $dir = undef; $dir = $edge->flow() if ref($edge);

  my @tries;
#  if (ref($parent) && defined $parent->{x})
  if (keys %{$node->{edges}} > 0)
    {
    my $src_node = $parent; $src_node = $edge->{from} if ref($edge) && !ref($parent);
    print STDERR "#  from $src_node->{name} to $node->{name}: edge $edge dir $dir\n" if $self->{debug};

    # if there are more than one edge to this node, and they share a start point,
    # move the node at least 3 cells away to create space for the joints

    my ($s_p, @ss_p);
    ($s_p, @ss_p) = $edge->port('start') if ref($edge);

    my ($from,$to);
    if (ref($edge))
      {
      $from = $edge->{from}; $to = $edge->{to};
      }

    my @shared_nodes;
    @shared_nodes = $from->nodes_sharing_start($s_p,@ss_p) if defined $s_p && @ss_p > 0;

    print STDERR "# Edge from '$src_node->{name}' shares an edge start with ", scalar @shared_nodes, " other nodes\n"
	if $self->{debug};

    if (@shared_nodes > 1)
      {
      $min_dist = 3 if $min_dist < 3;				# make space
      $min_dist++ if $edge->label() ne '';			# make more space for the label

      # if we are the first shared node to be placed
      my $placed = $self->_placed_shared(@shared_nodes);

      if (defined $placed)
        {
        # we are not the first, so skip the placement below
	# instead place on the same column/row as already placed node(s)
        my ($bx, $by) = @$placed;

	my $flow = $node->flow();

	print STDERR "# One of the shared nodes was already placed at ($bx,$by) with flow $flow\n"
	  if $self->{debug};

	my $ofs = 2;			# start with a distance of 2
	my ($mx, $my) = @{ ($flow_shift->{$flow} || [ 0, 1 ]) };

	while (1)
	  {
	  my $x = $bx + $mx * $ofs; my $y = $by + $my * $ofs;

	  print STDERR "# Trying to place $node->{name} at ($x,$y)\n"
	    if $self->{debug};

	  next if $self->_clear_tries($node, $cells, [ $x,$y ]) == 0;
	  last if $node->_do_place($x,$y,$self);
	  }
	continue {
	    $ofs += 2;
	  }
        return 0;			# found place already
	} # end we-are-the-first-to-be-placed
      }

    # shared end point?
    ($s_p, @ss_p) = $edge->port('end') if ref($edge);

    @shared_nodes = $to->nodes_sharing_end($s_p,@ss_p) if defined $s_p && @ss_p > 0;

    print STDERR "# Edge from '$src_node->{name}' shares an edge end with ", scalar @shared_nodes, " other nodes\n"
	if $self->{debug};

    if (@shared_nodes > 1)
      {
      $min_dist = 3 if $min_dist < 3;
      $min_dist++ if $edge->label() ne '';			# make more space for the label

      # if the node to be placed is not in the list to be placed, it is the end-point

      # see if we are the first shared node to be placed
      my $placed = $self->_placed_shared(@shared_nodes);

#      print STDERR "# "; for (@shared_nodes) { print $_->{name}, " "; } print "\n";

      if ((grep( $_ == $node, @shared_nodes)) && defined $placed)
	{
        # we are not the first, so skip the placement below
	# instead place on the same column/row as already placed node(s)
        my ($bx, $by) = @$placed;

	my $flow = $node->flow();

	print STDERR "# One of the shared nodes was already placed at ($bx,$by) with flow $flow\n"
	  if $self->{debug};

	my $ofs = 2;			# start with a distance of 2
	my ($mx, $my) = @{ ($flow_shift->{$flow} || [ 0, 1 ]) };

	while (1)
	  {
	  my $x = $bx + $mx * $ofs; my $y = $by + $my * $ofs;

	  print STDERR "# Trying to place $node->{name} at ($x,$y)\n"
	    if $self->{debug};

	  next if $self->_clear_tries($node, $cells, [ $x,$y ]) == 0;
	  last if $node->_do_place($x,$y,$self);
	  }
	continue {
	    $ofs += 2;
	  }
        return 0;			# found place already
	} # end we-are-the-first-to-be-placed
      }
    }

  if (ref($parent) && defined $parent->{x})
    {
    @tries = $parent->_near_places($cells, $min_dist, undef, 0, $dir);

    print STDERR
	"# Trying chained placement of $node->{name} with min distance $min_dist from parent $parent->{name}\n"
	if $self->{debug};

    # weed out positions that are unsuitable
    @tries = $self->_clear_tries($node, $cells, \@tries);

    splice (@tries,0,$try) if $try > 0;	# remove the first N tries
    print STDERR "# Left with " . scalar @tries . " tries for node $node->{name}\n" if $self->{debug};

    while (@tries > 0)
      {
      my $x = shift @tries;
      my $y = shift @tries;

      print STDERR "# Trying to place $node->{name} at $x,$y\n" if $self->{debug};
      return 0 if $node->_do_place($x,$y,$self);
      } # for all trial positions
    }

  print STDERR "# Trying to place $node->{name} at 0,0\n" if $try == 0 && $self->{debug};
  # Try to place node at upper left corner (the very first node to be
  # placed will usually end up there).
  return 0 if $try == 0 && $node->_do_place(0,0,$self);

  # try to place node near the predecessor(s)
  my @pre_all = $node->predecessors();

  print STDERR "# Predecessors of $node->{name} " . scalar @pre_all . "\n" if $self->{debug};

  # find all already placed predecessors
  my @pre;
  for my $p (@pre_all)
    {
    push @pre, $p if defined $p->{x};
    print STDERR "# Placed predecessors of $node->{name}: $p->{name} at $p->{x},$p->{y}\n" if $self->{debug} && defined $p->{x};
    }

  # sort predecessors on their rank (to try first the higher ranking ones on placement)
  @pre = sort { $b->{rank} <=> $a->{rank} } @pre;

  print STDERR "# Number of placed predecessors of $node->{name}: " . scalar @pre . "\n" if $self->{debug};

  if (@pre <= 2 && @pre > 0)
    {

    if (@pre == 1)
      {
      # only one placed predecessor, so place $node near it
      print STDERR "# placing $node->{name} near predecessor\n" if $self->{debug};
      @tries = ( $pre[0]->_near_places($cells, $min_dist), $pre[0]->_near_places($cells,$min_dist+2) );
      }
    else
      {
      # two placed predecessors, so place at crossing point of both of them
      # compute difference between the two nodes

      my $dx = ($pre[0]->{x} - $pre[1]->{x});
      my $dy = ($pre[0]->{y} - $pre[1]->{y});

      # are both nodes NOT on a straight line?
      if ($dx != 0 && $dy != 0)
        {
        # ok, so try to place at the crossing point
	@tries = (
	  $pre[0]->{x}, $pre[1]->{y},
	  $pre[0]->{y}, $pre[1]->{x},
	);
        }
      else
        {
        # two nodes on a line, try to place node in the middle
        if ($dx == 0)
          {
	  @tries = ( $pre[1]->{x}, $pre[1]->{y} + int($dy / 2) );
          }
        else
          {
	  @tries = ( $pre[1]->{x} + int($dx / 2), $pre[1]->{y} );
          }
        }
      # XXX TODO BUG: shouldn't we also try this if we have more than 2
      # placed predecessors?

      # In addition, we can also try to place the node around the
      # different nodes:
      foreach my $n (@pre)
        {
        push @tries, $n->_near_places($cells, $min_dist);
        }
      }
    }

  my @suc_all = $node->successors();

  # find all already placed successors
  my @suc;
  for my $s (@suc_all)
    {
    push @suc, $s if defined $s->{x};
    }
  print STDERR "# Number of placed successors of $node->{name}: " . scalar @suc . "\n" if $self->{debug};
  foreach my $s (@suc)
    {
    # for each successors (especially if there is only one), try to place near
    push @tries, $s->_near_places($cells, $min_dist);
    push @tries, $s->_near_places($cells, $min_dist + 2);
    }

  # weed out positions that are unsuitable
  @tries = $self->_clear_tries($node, $cells, \@tries);

  print STDERR "# Left with " . scalar @tries . " for node $node->{name}\n" if $self->{debug};

  splice (@tries,0,$try) if $try > 0;	# remove the first N tries

  while (@tries > 0)
    {
    my $x = shift @tries;
    my $y = shift @tries;

    print STDERR "# Trying to place $node->{name} at $x,$y\n" if $self->{debug};
    return 0 if $node->_do_place($x,$y,$self);

    } # for all trial positions

  ##############################################################################
  # all simple possibilities exhausted, try a generic approach

  print STDERR "# No more simple possibilities for node $node->{name}\n" if $self->{debug};

  # XXX TODO:
  # find out which sides of the node predecessor node(s) still have free
  # ports/slots. With increasing distances, try to place the node around these.

  # If no predecessors/incoming edges, try to place in column 0, otherwise
  # considered the node's rank, too

  my $col = 0; $col = $node->{rank} * 2 if @pre > 0;

  $col = $pre[0]->{x} if @pre > 0;

  # find the first free row
  my $y = 0;
  $y +=2 while (exists $cells->{"$col,$y"});
  $y += 1 if exists $cells->{"$col," . ($y-1)};		# leave one cell spacing

  # now try to place node (or node cluster)
  while (1)
    {
    next if $self->_clear_tries($node, $cells, [ $col,$y ]) == 0;
    last if $node->_do_place($col,$y,$self);
    }
    continue {
    $y += 2;
    }

  $node->{x} = $col;

  0;							# success, score 0
  }

sub _trace_path
  {
  # find a free way from $src to $dst (both need to be placed beforehand)
  my ($self, $src, $dst, $edge) = @_;

  print STDERR "# Finding path from '$src->{name}' to '$dst->{name}'\n" if $self->{debug};
  print STDERR "# src: $src->{x}, $src->{y} dst: $dst->{x}, $dst->{y}\n" if $self->{debug};

  my $coords = $self->_find_path ($src, $dst, $edge);

  # found no path?
  if (!defined $coords)
    {
    print STDERR "# Unable to find path from $src->{name} ($src->{x},$src->{y}) to $dst->{name} ($dst->{x},$dst->{y})\n" if $self->{debug};
    return undef;
    }

  # path is empty, happens for sharing edges with only a joint
  return 1 if scalar @$coords == 0;

  # Create all cells from the returned list and score path (lower score: better)
  my $i = 0;
  my $score = 0;
  while ($i < scalar @$coords)
    {
    my $type = $coords->[$i+2];
    $self->_create_cell($edge,$coords->[$i],$coords->[$i+1],$type);
    $score ++;					# each element: one point
    $type &= EDGE_TYPE_MASK;			# mask flags
    # edge bend or cross: one point extra
    $score ++ if $type != EDGE_HOR && $type != EDGE_VER;
    $score += 3 if $type == EDGE_CROSS;		# crossings are doubleplusungood
    $i += 3;
    }

  $score;
  }

sub _create_cell
  {
  my ($self,$edge,$x,$y,$type) = @_;

  my $cells = $self->{cells}; my $xy = "$x,$y";

  if (ref($cells->{$xy}) && $cells->{$xy}->isa('Graph::Easy::Edge'))
    {
    $cells->{$xy}->_make_cross($edge,$type & EDGE_FLAG_MASK);
    # insert a EDGE_HOLE into the cells of the edge (but not into the list of
    # to-be-rendered cells). This cell will be removed by the optimizer later on.
    Graph::Easy::Edge::Cell->new( type => EDGE_HOLE, edge => $edge, x => $x, y => $y );
    return;
    }

  my $path = Graph::Easy::Edge::Cell->new( type => $type, edge => $edge, x => $x, y => $y );
  $cells->{$xy} = $path;	# store in cells
  }

sub _path_is_clear
  {
  # For all points (x,y pairs) in the path, check that the cell is still free
  # $path points to a list of [ x,y,type, x,y,type, ...]
  my ($self,$path) = @_;

  my $cells = $self->{cells};
  my $i = 0;
  while ($i < scalar @$path)
    {
    my $x = $path->[$i];
    my $y = $path->[$i+1];
    # my $t = $path->[$i+2];
    $i += 3;

    return 0 if exists $cells->{"$x,$y"};	# obstacle hit
    }
  1;						# path is clear
  }

1;
__END__

=head1 NAME

Graph::Easy::Layout::Path - Path management for Manhattan-style grids

=head1 SYNOPSIS

	use Graph::Easy;

	my $graph = Graph::Easy->new();

	my $bonn = Graph::Easy::Node->new(
		name => 'Bonn',
	);
	my $berlin = Graph::Easy::Node->new(
		name => 'Berlin',
	);

	$graph->add_edge ($bonn, $berlin);

	$graph->layout();

	print $graph->as_ascii( );

	# prints:

	# +------+     +--------+
	# | Bonn | --> | Berlin |
	# +------+     +--------+

=head1 DESCRIPTION

C<Graph::Easy::Layout::Scout> contains just the actual path-managing code for
L<Graph::Easy|Graph::Easy>, e.g. to create/destroy/maintain paths, node
placement etc.

=head1 EXPORT

Exports nothing.

=head1 SEE ALSO

L<Graph::Easy>.

=head1 METHODS into Graph::Easy

This module injects the following methods into C<Graph::Easy>:

=head2 _path_is_clear()

	$graph->_path_is_clear($path);

For all points (x,y pairs) in the path, check that the cell is still free.
C<$path> points to a list x,y,type pairs as in C<< [ [x,y,type], [x,y,type], ...] >>.

=head2 _create_cell()

	my $cell = $graph->($edge,$x,$y,$type);

Create a cell at C<$x,$y> coordinates with type C<$type> for the specified
edge.

=head2 _path_is_clear()

	$graph->_path_is_clear();

For all points (x,y pairs) in the path, check that the cell is still free.
C<$path> points to a list of C<[ x,y,type, x,y,type, ...]>.

Returns true when the path is clear, false otherwise.

=head2 _trace_path()

	my $path = my $graph->_trace_path($src,$dst,$edge);

Find a free way from source node/group to destination node/group for the
specified edge. Both source and destination need to be placed beforehand.

=head1 METHODS in Graph::Easy::Node

This module injects the following methods into C<Graph::Easy::Node>:

=head2 _near_places()

	my $node->_near_places();

Take a node and return a list of possible placements around it and
prune out already occupied cells. $d is the distance from the node
border and defaults to two (for placements). Set it to one for
adjacent cells.

=head2 _shuffle_dir()

	my $dirs = $node->_shuffle_dir( [ 0,1,2,3 ], $dir);

Take a ref to an array with four entries and shuffle them around according to
C<$dir>.

=head2 _shift()

	my $dir = $node->_shift($degrees);

Return a the C<flow()> direction shifted by X degrees to C<$dir>.

=head1 AUTHOR

Copyright (C) 2004 - 2007 by Tels L<http://bloodgate.com>.

See the LICENSE file for information.

=cut