#!/usr/local/bin/perl
# -*- perl -*-
#####################################################################
# Program: makefeedmap -- Make netnews flow map                     #
# Author: Hideki ONO <ono@4u.net>                                   #
# Latest version:                                                   #
#     http://www.tamaru.kuee.kyoto-u.ac.jp/~ono/tools/makefeedmap/  #
#####################################################################

$version ='$Id: makefeedmap,v 1.1.1.1 2003/05/16 11:20:02 ono Exp $ ';

use Getopt::Std;
use GD;

$start = 'tamaru-news';
$title_pre = 'Newsfeed at ';
$feedDepth = 10;
$feedWidth = 8;
$radius = 20;
$RAND = 50;
$image_size = [1200,1000];
$title_height = gdLargeFont->height+10;
$mode = 0;

sub min {
    local($a,$b) = (@_);
    ($a<$b) ? $a : $b;
}
sub max {
    local($a,$b) = (@_);
    ($a>$b) ? $a : $b;
}

sub myline {
    local($x1,$y1,$x2,$y2,$width) = (@_);
    $poly = new GD::Polygon;
    $w = $radius * $width / $total;
    $theta = atan2($y1-$y2,$x1-$x2);
    $poly->addPt($x2+$w*sin($theta),$y2-$w*cos($theta));
    $poly->addPt($x2-$w*sin($theta),$y2+$w*cos($theta));
    if (! $opt_a) {
	$poly->addPt($x1-$w*sin($theta),$y1+$w*cos($theta));
	$poly->addPt($x1+$w*sin($theta),$y1-$w*cos($theta));
    } else {
	$wa = max($w*3,$radius/3);
	$x1 = $x1-$radius * cos($theta);
	$y1 = $y1-$radius * sin($theta);
	$poly->addPt($x1-$w*sin($theta)-$wa*cos($theta),$y1-$wa*sin($theta)+$w*cos($theta));
	$poly->addPt($x1-$wa*sin($theta)-$wa*cos($theta),$y1-$wa*sin($theta)+$wa*cos($theta));
	$poly->addPt($x1,$y1);
	$poly->addPt($x1+$wa*(sin($theta)-cos($theta)),$y1+$wa*(-sin($theta)-cos($theta)));
	$poly->addPt($x1+$w*sin($theta)-$wa*cos($theta),$y1-$wa*sin($theta)-$w*cos($theta));
    }
    $im->filledPolygon($poly,$blue);
}

getopts('acd:e:hg:m:r:R:w:vx');

if ($opt_h) {
    print STDERR <<"EOF";
$version
Usage: $0 [switches] file >output.gif
  -a      enable arrow lines
  -e arg  name of the end node            [default: $start]
  -d num  max vertical nodes              [default: $feedDepth]
  -w num  max horizontal nodes            [default: $feedWidth]
  -r num  node radius                     [default: $radius]
  -R num  random factor for node location [default: $RAND]
  -g x,y  canvas size                     [default: $image_size->[0],$image_size->[1]]
  -c      circle mode
  -m      mode(0..1)                      [default: $mode]

  -h      show this document
EOF
    exit;
}

if ($opt_d) {
    $feedDepth = $opt_d;
}
if ($opt_w) {
    $feedWidth = $opt_w;
}
if ($opt_g) {
    if ($opt_g =~ /(\d+),(\d+)/) {
	$image_size = [$1,$2];
    }
}
if ($opt_e) {
    $start = $opt_e;
}
if ($opt_r) {
    $radius = $opt_r;
}
if (defined($opt_R)) {
    $RAND = $opt_R;
}
if ($opt_m) {
    $mode = $opt_m;
}


while(<>){
	chop;
	if (/^Total:\s+(\d+)/){
		$total = $1;
	} else {
		($dst,$src,$num) = split(/!/);
		if ($dst ne $src) {
			push(@{$feed{$dst}}, [ $src , $num ]);
			push(@border,[$dst,$src,$num]);
			$path{$dst . "!" . $src} = $num;
		}
	}
}

$im_size = [ $image_size->[0], $image_size->[1] - $title_height];

if ($opt_c) {
    @startPoint = ($im_size->[0]/2,$im_size->[1]/2);
} else {
    @startPoint = ($im_size->[0]/2,$im_size->[1]-$im_size->[1]/($feedDepth+1)/2);
}
$exist{$start} = [@startPoint];

@nowNodes = sort {$b->[1] <=> $a->[1];} @{$feed{$start}};
if ($mode == 1) {
    $tmp=0;
    @tmpNodes=();
    foreach $i (@nowNodes) {
	if ($tmp){
	    push(@tmpNodes,$i);
	} else {
	    unshift(@tmpNodes,$i);
	}
	$tmp = 1 - $tmp;
    }
    @nowNodes=(@tmpNodes);
}
for($iy = 1; $iy <= $feedDepth; $iy++){
    @tmpNodes = ();
    $v_num = $#nowNodes +1;
    for($i=0; $i < $v_num; $i++){
	$site = $nowNodes[$i][0];
	if (!$opt_c) {
	    @center = ($im_size->[0]/$v_num*($i+0.5)+rand($RAND)-$RAND/2,
		       $im_size->[1] - $im_size->[1]/($feedDepth+1)*($iy+0.5)+(rand($RAND)-$RAND/2));
	} else {
	    $theta = 2 * 3.14 * ($i / $v_num - 0.25);
	    @center = ($iy * $im_size->[0]/($feedDepth+1)/2*cos($theta)+rand($RAND)-$RAND/2+$startPoint[0],
		       $iy * $im_size->[1]/($feedDepth+1)/2*sin($theta)+rand($RAND)-$RAND/2+$startPoint[1],);
	}
	$exist{$site} = [@center];
	
	push(@tmpNodes,@{$feed{$site}});
    }
    %hoge =();
    for($i=$#tmpNodes;$i >= 0;$i--){
	if (defined($exist{$tmpNodes[$i][0]})) {
	    splice(@tmpNodes,$i,1);
	} else {
	    if (defined($hoge{$tmpNodes[$i][0]})) {
		$hoge{$tmpNodes[$i][0]}->[1] += $tmpNodes[$i][1];
		splice(@tmpNodes,$i,1);
	    } else {
		$hoge{$tmpNodes[$i][0]} = [$tmpNodes[$i][0],$tmpNodes[$i][1]];
	    }
	}
    }
    @nextNodes = sort {$hoge{$b->[0]}->[1] <=> $hoge{$a->[0]}->[1];} @tmpNodes;
    splice(@nextNodes, $feedWidth);
    $iii = 0;
    @nextNodes2 = ();
    $n_nextNodes=$#nextNodes+1;
    $jjj = 0;
    for($ii=0; $ii <= $#nowNodes; $ii++) {
	if ($mode == 0) {
	    for($jj=$jjj; $jj < $n_nextNodes; $jj++) {
		if (defined($path{$nowNodes[$ii][0] . "!" . $nextNodes[$jj][0]})) {
		    $tmp = splice(@nextNodes,$jj,1);
		    splice(@nextNodes,$jjj++,0,$tmp);
		}
	    }
	} else {
	    
	    @tmp=();
	    for($jj=0; $jj <= $#nextNodes; $jj++) {
		if (defined($path{$nowNodes[$ii][0] . "!" . $nextNodes[$jj][0]})) {
		    push(@tmp,splice(@nextNodes,$jj,1));
		    $jj--;
		}
	    }
	    local($node) = int($n_nextNodes/2);
	    local($add) = ($n_nextNodes/2 == int($n_nextNodes/2)) ? -1 : +1;
	    for($jj=0; $jj <= $#tmp; $jj++) {
		$ok = 0;
		while (1) {
		    if ($jjj <= $node &&
			$jjj + $#tmp >= $node ) {
			$nextNodes2[$node] = $tmp[$jj];
			$ok = 1;
		    }
		    $node += $add;
		    $add = -$add;
		    $add += ($add > 0) ? 1: -1;
		    last if $ok;
		}
	    }
	    $jjj += ($#tmp + 1);
	}
    }
    if ($mode == 1){
	@nowNodes = @nextNodes2;
    } else {
	@nowNodes = @nextNodes;
    }
}

#
# Draw Graph
#

$im = new GD::Image(@$im_size);
$white = $im->colorAllocate(255,255,255);
$black = $im->colorAllocate(0,0,0);
$red = $im->colorAllocate(255,0,0);
$blue = $im->colorAllocate(0,0,255);
$yellow = $im->colorAllocate(255,255,0);
$im->transparent($white);

foreach $i (@border) {
    if (defined($exist{$i->[0]}) && defined($exist{$i->[1]})) {
	myline($exist{$i->[0]}[0], $exist{$i->[0]}[1],
	       $exist{$i->[1]}[0], $exist{$i->[1]}[1],
	       $i->[2]);
    }
}

$circle = new GD::Image($radius*2,$radius*2);
$circle_white = $circle->colorAllocate(255,255,255);
$circle_color = $circle->colorAllocate(255,0,0);
$circle->transparent($white);
$circle->arc($radius,$radius,$radius*2,$radius*2,0,360,$circle_color);
$circle->fill($radius,$radius,$circle_color);
foreach $i (@border) {
    foreach $site ($i->[0],$i->[1]) {
	if (defined($exist{$site}) && !defined($drawn{$site})) {
	    $im->copy($circle,$exist{$site}[0]-$radius,$exist{$site}[1]-$radius,
		      $0,0,2*$radius,2*$radius);
	    $drawn{$site} = 1;
	}
    }
}
%drawn=();
foreach $i (@border) {
    foreach $site ($i->[0],$i->[1]) {
	if (defined($exist{$site}) && !defined($drawn{$site})) {
	    $im->string(gdMediumBoldFont,$exist{$site}[0]-(gdMediumBoldFont->width * length($site)/2),
			$exist{$site}[1] - (gdMediumBoldFont->height / 2), $site,$yellow);
	    $drawn{$site} = 1;
	}
    }
}

$out = new GD::Image(@$image_size);
$white = $out->colorAllocate(255,255,255);
$black = $out->colorAllocate(0,0,0);
$out->fill(0,0,$black);
$out->copy($im,0,$title_height,0,0,@$im_size);

$title = $title_pre . $start;

$out->string(gdLargeFont,$image_size->[0]/2-(gdLargeFont->width*length($title)/2),
	     ($title_height- gdLargeFont->height)/2,$title,$white);

@date=localtime(time);
$date=sprintf("%4d.%s.%s",1900+$date[5],$date[4]+1,$date[3]);
@sig0 = split(/[ ,]+/,$version);

@signature=($date,"Created by " . $sig0[1] . " " . $sig0[3]);
$sig_y = $image_size->[1]- gdSmallFont->height -2;
foreach $i (reverse(@signature)){
    $out->string(gdSmallFont,$image_size->[0]-length($i)*gdSmallFont->width-2,$sig_y,
		 $i, $white);
    $sig_y -= gdSmallFont->height;
}

print $out->gif;