#!/usr/local/bin/perl
########################################################################
#  By accessing this software, PARSE.PL, you are duly informed of
#  and agree to be bound by the conditions described below in
#  this notice:
#
#  This software product, PARSE.PL, is developed by Bradley Huffaker, and
#  copyrighted(C) 1998 by the University of California, San Diego (UCSD),
#  with all rights reserved.  UCSD administers the NLANR Cache grants,
#  NCR-9796082 and NCR-9616602, under which most of this code was
#  developed.
#
#  PARSE.PL is a free software. You can redistribute it and/or modify it
#  under the terms of the CAIDA/NLANR General Public License v.1 as
#  published by UCSD and is incorporated by reference herein.  PARSE.PL is
#  distributed WITHOUT ANY WARRANTY, IMPLIED OR EXPRESS, OF MERCHANTABILITY
#  OR FITNESS FOR A PARTICULAR PURPOSE or that the use of it will not
#  infringe on any third party's intellectual property rights.
#
#  You should have received a copy of the CAIDA/NLANR General Public
#  License v.1 along with the PARSE.PL program.  If for any reason you
#  have not received a copy, please write to
#
#                       University of California, San Diego
#                       SDSC/CAIDA/NLANR
#                       9500 Gilman Dr., MS-0505
#                       La Jolla, CA 92093 - 0505  USA
#
#  Or contact INFO@NLANR.NET
#######################################################################
# parse.pl [-r root_match] [-f final_file] [-s source_file]
#	root_math - string that the root must contain to match
#	final_file - the output file
#	source_file - the file that is read in to be parsed

$min_num_neighbors = 3;
$num_roots = 5;
$groups_file ="groups.txt";

#$print_all = 1;

#$source_file = "/home/web/Caidants/Manta/Working/Data/data.txt";
$source_file = "data.txt";
#$source_file = "d";
$final_file = "data.fvl";

#------------------ Groups -------------------
$valuesGroup{"node values"} = "1 Node Values";
$values2type{"node values"} = "d";
$fields{"node values"} = "Degree";

$valuesGroup{"tunnel"} = "6 Tunnel Attributes";
$values2type{"tunnel"} = "s";
$fields{"tunnel"} = "Type'Status'Type of Network'Metric'Threshold Symmetry'Threshold Groups";

$valuesGroup{"tunnel values"} = "2 Tunnel Values";
$values2type{"tunnel values"} = "d";
$fields{"tunnel values"} = "Metric'Threshold"; 

($print_all,$source_file,$final_file,$root_match) = getParams();
print "parse: $print_all $source_file $final_file\n";

%group = &processFile($source_file);
PrintFinal($final_file,%group);

sub getParams
{
	foreach $argv (@ARGV)
	{
		$final_file = $argv
			if ($last eq "-f");
		$source_file = $argv
			if ($last eq "-s");
		$root_match = $argv
			if ($last eq "-r");
		$last = $argv;
	}
	$print_all = 1
		if ($final_file || $source_file);
	return ($print_all,$source_file,$final_file,$root_match);
}

sub processFile
{
	my ($filename) = @_;
	print "processing:'$filename'\n";
	open(IN, "<$filename") || print "Uanble to open file $filename:$!\n";
	($datafile) = ($filename =~ /(.*)\.txt/);
	
	$linknum = 0;
	$T = 0;
	while ($line = <IN>) 
	{
		$line =~ s/\n//g;
		($key,$first,$second,$ip,$isp,$lat,$long) = split /\s+/,$line;
		if (($key eq "*" || $key eq "?" || $key eq ":") && $first)
		{
			$num_not_reached++;
			$name = "$second($ip)";
			$key2nodes{$first} = $name;
			$key2ips{$first} = $ip;
			$nodes2key{$name} = $first;
			$key2latlong{$first} = "$lat $long"
				if ($lat && $long && $key eq "*");
		}
		if (($key eq ">" || $key eq "<") && $first && $second)
		{
			$T++;
			$key2nodes{$first} = 1
				if (!$key2nodes{$first});
			$key2nodes{$second} = 1
				if (!$key2nodes{$second});
			$Nneighbors{$first}++;
			$Nneighbors{$second}++;
			$node2neighbors{$first} .="\0"
				if($node2neighbors{$first});
			$node2neighbors{$first} .=$second;
			$node2neighbors{$second} .="\0"
				if($node2neighbors{$second});
			$node2neighbors{$second} .=$first;
			
			$mapping = "$first\0$second";
			$twoWay{$mapping} = 1
				if ($key eq "<");
			push(@links,$mapping);
			if ($line=~/\[.*pim.*\]/)
			{
				$tunnel_value = "pim";
				$type_network = "PIM-";
			}
			else
			{
				$tunnel_value = "dvmrp";
				$type_network = "DVMRP-";
			}

			if ($line=~/\[.*tunnel.*\]/)
			{
				$type_network .= "tunnel-";
			}
			else
			{
				$type_network .= "nontunnel-";
			}
if (0)
{
			$first_ip = &convertIP($key2ips{$first});
			$second_ip = &convertIP($key2ips{$second});
#print STDOUT "$first_ip:",($first_ip & $mask_3)," $second_ip:"
	#,($second_ip & $mask_3),"\n";
			if ($first_ip & $mask_3 == $second_ip & $mask_3)
			{
				$type_network .= "LAN";
			}
			elsif ($first_ip & $mask_2 == $second_ip & $mask_2)
			{
				$type_network .= "MAN";
			}
			else
			{
				$type_network .= "WAN";
			}
}
			@first_ips = split /\./,$key2ips{$first};
			@second_ips = split /\./,$key2ips{$second};
			if ($first_ips[0] eq $second_ips[0]
				&& $first_ips[1] eq $second_ips[1])
			{
				if ($first_ips[2] eq $second_ips[2])
				{
					$type_network .= "LAN";
				}
				else
				{
					$type_network .= "MAN";
				}
			}
			else
			{
				$type_network .= "WAN";
			}

			if ($line=~/\[.*down.*\]/)
			{
				$tunnel_value .= "'Down";
			}
			elsif ($line=~/\[.*disabled.*\]/)
			{
				$tunnel_value .= "'Down";
			}
			elsif ($key eq ">")
			{
				$tunnel_value .= "'Unidirectional";
			}
			else
			{
				if ($line=~/\[.*tunnel.*\]/)
				{
					$tunnel_value .= "'tunnel";
				}
				else
				{
					$tunnel_value .= "'native";
				}
			}
			($metric1,$threshold1) =($line=~/\[(\d+)\/(\d+)/);
			($metric2,$threshold2) =($line=~/\[.+\[(\d+)\/(\d+)/);

			$tunnel_value .= "'".$type_network;

			if ($metric1 == 1 || $metric == 1)
			{
				$tunnel_value .= "'metric 1";
			}
			else
			{
				$tunnel_value .= "'metric not 1";
			}
			$tunnel_value .= 
				&handleThreshold($threshold1,$threshold2);
				
			$tunnel{$mapping} = $tunnel_value;
			$tunnel_values{$mapping} = "$metric1'$threshold1";
		}
	}
	close IN;

	%num2node;
        foreach $node (keys %Nneighbors) {
                $value = $Nneighbors{$node};
                $num2node{$value} .= "\0"
                        if($num2node{$value});
                $num2node{$value} .=$node;
        }
	

	my @nodes = keys %key2nodes;
	my %roots;
	my %reached;
	my %groups;
	my $largest_size =0;
	my %largest_group;
	$temp = 0;

	print "processing connects\n";
	do 
	{
                $node = shift @nodes;
		if (!$reached{$node} && $node)
		{
			undef %group;
			$reached{$node} = 1;
			$group{$node} = 1;
			$size = 1;
			my @neighbors = split /\0/, $node2neighbors{$node};
			while ($#neighbors > -1)
			{
				$current = shift @neighbors;
				if (!$reached{$current})
				{
					$size++;
					$reached{$current} = 1;
					$group{$current} = 1;
					my @more_neighbors 
					 = split /\0/, $node2neighbors{$current};
					foreach $each (@more_neighbors)
					{
						push (@neighbors, $each)
							if (!$reached{$each});
					}
					
				}
			}
			if ($size > $largest_size)# && $size < 1000)
			{
				%largest_group = %group;
				$largest_size = $size;
			}
			$size2group{$size}++;
			foreach $each (keys %group)
			{
				$groups{$size} .= $each."\n";
			}
			$groups{$size} .= "\n";
		}
		else
		{
		}
        } while ($#nodes > -1);
	
	open (OUT, ">$groups_file") || die("Unable to open groups_file:$!");
	foreach $size (sort numerically keys %groups)
	{
		print OUT "--------------- $size ------------------------\n";
		print OUT $groups{$size};
	}
	close OUT;
	
	print "size of Group: frequencey\n";
	foreach $size (sort numerically keys %size2group)
	{
		print "$size : ",$size2group{$size},"\n";
	}
	if ($print_all)
	{
		return %key2nodes;
	}
	else
	{
		return %largest_group;
	}
}

sub convertIP
{
	my ($ip_string) = @_;
#print STDOUT " $ip_string:";
	my $scalar = 256*256*256;
	my $ip;
	foreach $num (split /\./,$ip_string)
	{
		$ip += $num*$scalar;
		$scalar = $scalar/256;
	}
#print STDOUT $ip,"\n";
	return $ip;
}

sub handleThreshold
{
	my ($threshold1, $threshold2) = @_;
	my $output;
	if ($threshold1 == $theshold2)
	{
		$output = "'symmetric";
	}
	else
	{
		$output = "'assymmetric";
	}
	@bounds = (1,8,16,32,48,64,128);
	my $bucket;
	my $last = 0;
	foreach $bound (@bounds)
	{
			
		$bucket = "'".addZeros($last)." - ".&addZeros($bound)
			if (!$bucket && $threshold1 < $bound);
		$last = $bound+1;
	}
	$bucket = "'$last - infinity"
		if (!$bucket);
	$output .= $bucket;
	return $output;
}

sub addZeros
{
	my ($number) = @_;
	my $extrea = 3 - length("$number");
	my $count = 0;
	while ($count < $extrea)
	{
		$number = "0".$number; 
		$count++;
	}
	return $number;
}

sub PrintFinal
{
	($filename,%group) = @_;
	print "Printing $filename\n";
	my @local_nodes;
	my $index = 0;
print $#group,"\n";
	
	print "searching for roots\n";
	if (!$root_match)
	{
		my @nums = sort numerically keys %num2node;
		my $num_roots_found = 0;
		my @working;
		while ($num_roots > 0 && $#nums > -1)
		{
			if ($#working < 0)
			{
				$num = pop @nums;
				@working = split /\0/,$num2node{$num};
	print "$#working\n";
			}
			$node = shift @working;
			if ($group{$node})
			{
	print "root:$node\n";
				$root{$node} = 1;
				$num_roots--;
			} 
		}
	}
	else
	{
		undef %root;
		foreach $node (keys %key2nodes)
		{
			$name = $key2nodes{$node};
			$root{$node} = 1
				if ($name =~ /$root_match/);
		}
	}

	# Create the valuesGroup to index mapping
	$index = 0;
	foreach $key (sort keys %valuesGroup)
	{
		$valuesGroupStuff .= "g $index ".$values2type{$key}." "
			.$valuesGroup{$key}."\n"
			."f $index ".$fields{$key}."\n";
		$values2index{$key} = $index;
		$index++;
	}
		
	# Create the node to index mapping
	$index = 0;
	foreach $key (keys %group)
	{
		if ($key2latlong{$key})
		{
			$output = "N $index ".$key2latlong{$key}
				." ".$key2nodes{$key};	
		}
		else
		{
			$output = "? $index $key2nodes{$key}";
		}
		$output .= " r"
			if ($root{$key});
		$output .= "\n";
		$output .= "v ".$index." ".$values2index{"node values"}
			." ".$Nneighbors{$key}."\n";
		push(@local_nodes,$output);
		$key2index{$key} = $index++;
	}
	
	# Create the links that are in the group
	# with the correct index
	my @local_links;
	$index = 0;
	foreach $link (@links)
	{
		my ($from,$to) = split "\0",$link;
		if ($group{$from} && $group{$to})
		{
			$from_index = $key2index{$from};
			$to_index = $key2index{$to};
			if ($twoWay{$link}) 
			{
				$output = "L";
			}
			else 
			{
				$output = "l";
			}
			$output .= " $index $from_index $to_index\n"
				."V $index ".$values2index{"tunnel"}." "
				.$tunnel{$link}."\n"
				."V $index ".$values2index{"tunnel values"}." "
				.$tunnel_values{$link}."\n";
			push(@local_links,$output);
			$index++;
		}
	}

	open (OUT, ">$filename") || die ("Unable to open $filename, $!");
	print OUT &header();
	print OUT $valuesGroupStuff;
	print OUT "t ",$#local_nodes+1,"\n";
	print OUT "T ",$#local_links+1,"\n";
	foreach $node (@local_nodes)
	{
		print OUT $node;
	}
	foreach $link (@local_links)
	{
		print OUT $link;
	}
	close OUT;
}

sub numerically { $a <=> $b; }

sub header
{
return<<EOP;
#       For a SNMP soon to be named tool
#       by Bradley Huffaker 3/18/98
#       t number
#               (total number of nodes)
#               Must be at the beginning of the file.
#               number the number of nodes to follow. (int)
#       T number
#               (total number of links)
#               Must be at the beginning of the file.
#               number  the nubmer of links that will used (int)
#
#       n node_index x y name
#       N node_index lat long name
#       ? node_index name
#               (node)
#               node_index      - unqueue node identifier (int)
#               site_index      - identifier node's site (int)
#		x		- the x location on map (positive int)
#		y		- the y location on map (positive int)
#               lat             - latitude (float)
#               long            - longitude (float)
#               name            - name of the node (string no spaces)
#
#       g group_index d|s num_enters discription
#               (group_gory)
#               group_index     - unqueue ValuesGroup identifier (int)
#               num_enters      - number of entries (int)
#               discription     - discription of ValuesGroup (string up to \\n)
#               d               - group contains floats
#               s               - group contains strings
#
#       f group_index string[:i|o]'string2[:i|o]'string3[:i|o]'....
#               (fields of each ValuesGroup)
#               group_index     - identifier for the ValuesGroup which has
#                               these fields (int)
#               string1[:i|o]'  - a list of strings of any number that begins
#                               string1 - field header (string upto :)
#                               i - option mean into node or from first node
#                               o - option mean out of node or into first node
#                               may have either i or o, but not both
#                               This allows for possible future fields
#
#       v node_index|site_index group_index value1'value2'value3 ...
#       V link_index group_index value1'value2'value3 ...
#               (values for the ValuesGroup)
#               node_index|site_index - identifier for the node (int)
#                               both nodes and site share the same
#                               domain of index so n reference to either
#                               a node or a site
#               link_index      - identifier for the link (int)
#               group_index     - identifier for the ValuesGroup which holds
#                               these values (int)
#               value1          - values for each colomn (float)
#
#       l linkidx n_idx1 n_idx2
#       L linkidx n_idx1 n_idx2
#               (link)
#		l - unidirectional";
#		L - bidirectional";
#               linkidx   the index of this link into an array
#               bandwidth the bandwidth of the link
#               nidx1     the index of the node that is the client
#               nidx2     the index of the node that is the server
EOP
} 
