#!/usr/local/bin/perl -w
#
#############################################################################
#
#          kocos.pl (A Component of the Ngrams Statistic Package)
#
#	Finds the kth Order Co-occurrences of a given word from the bigram 
#       count output created by the programs count.pl or statistic.pl of NSP 
#
#############################################################################
#                       ---------------------
#                       COPYRIGHT INFORMATION
#                       ---------------------

# Copyright (c) 2002-2003,
# Amruta Purandare, University of Minnesota, Duluth
# pura0010@d.umn.edu
# Ted Pedersen, University of Minnesota, Duluth
# tpederse@umn.edu
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 2
# of the License, or (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to
#
# The Free Software Foundation, Inc.,
# 59 Temple Place - Suite 330,
# Boston, MA  02111-1307, USA.
#
###############################################################################

#                               THE CODE STARTS HERE

###############################################################################

#                           ================================
#                            COMMAND LINE OPTIONS AND USAGE
#                           ================================

# show minimal usage message if no arguments
if($#ARGV<0)
{
        &showminimal();
        exit;
}

# command line options
use Getopt::Long;
use Set::Scalar;
GetOptions ("help","version","order=i","trace=s");
# show help option
if(defined $opt_help)
{
        $opt_help=1;
        &showhelp();
        exit;
}

# show version information
if(defined $opt_version)
{
        $opt_version=1;
        &showversion();
        exit;
}
#with --order user can specify the 
#value of K for kth order co-occurrences
#by default the program will assume K=1
#and will find the 1st order co-occurrences
if(defined $opt_order)
{
	$order=$opt_order;	
	if($order==1)
        {
                $postfix="st";
        }
	elsif($order==2)
	{
		$postfix="nd";
	}
	elsif($order==3)
        {
                $postfix="rd";
        }
	else
	{
		$postfix="th";
	}
}
else
{
	$order=1;
	$postfix="st";
}

#select this option to see detailed chains
#of the co-occurrences showing how a particular 
#kth order co-occurrence is reached in k steps 
if(defined $opt_trace)
{
	$trace=$opt_trace;
}

#############################################################################

#                       ================================
#                          INITIALIZATION AND INPUT
#                       ================================

#$0 contains the program name along with
#a complete path. Extract just the program
#name and use in error messages
$0=~s/.*\/(.+)/$1/;

if(!defined $ARGV[0])
{
        print STDERR "ERROR($0):
        Please specify the SOURCE file name...\n";
        exit;
}
#accept the input file name
$infile=$ARGV[0];
#check if exists
if(!-e $infile)
{
        print STDERR "ERROR($0):
        Source file <$infile> doesn't exist...\n";
        exit;
}
#open if exists
open(IN,"$infile") || die "Error($0):
        Error(code=$!) in opening <$infile> file.\n";

#check if the target word is specified
if(!defined $ARGV[1])
{
	print STDERR "ERROR($0):
	Please specify the Target Word whose $order$postfix order co-occurrences
	are to be found.\n";
	exit;
}
#accept the target word
$word=$ARGV[1];

#check if order is valid
if($order<0)
{
	print STDERR "ERROR($0):
	The Order should be a non-negative integer K to find Kth order
	co-occurrences.\n";
	exit;
}
#check if --trace is used
if(defined $trace)
{
	$ans="n";
	#check if the TRACE_FILE already exists
	if(-e $trace)
	{
		print STDERR "WARNING($0):
	Trace file <$trace> already exists, overwrite(y/n)? ";
		$ans=<STDIN>;
		if(!$ans=~/y|Y/)
		{
			undef $trace;
		}
	}
	if(!-e $trace || $ans=~/Y|y/)
	{
		#open the TRACE_FILE
		open(TRACE,">$trace") || die "Error($0):
        Error(code=$!) in opening Trace file <$trace>.\n";
	}
}

##############################################################################

$line_num=0;
#creating a coc_store data structure for storing all bigram strings from SOURCE
#so that co-occurrences can be found looking at this data structure
while($line=<IN>)
{
	$line_num++;
        # trimming extra spaces
        chomp $line;
        $line=~s/\s+$//g;
        $line=~s/^\s+//g;
        $line=~s/\s+/ /g;
	# handling blank lines
        if($line=~/^\s*$/)
        {
                next;
        }
	#store the bigram strings before the last <> 
	if($line=~/<>/)
	{
		#checking if the SOURCE is a valid NSP output for Bigrams
		$check_bigram=$line;
		$cnt=0;
		#count how many times <> occurs
		while($check_bigram=~/<>/)
		{
			$cnt++;
			$check_bigram=$';
		}
		#should be 2 for bigrams
		if($cnt!=2)
		{
			print STDERR "ERROR($0):
	SOURCE file <$infile> is not a valid Bigram output of count.pl or 
	statistic.pl of NSP at line <$line_num>.\n";
			exit;
		}
		#part before the last <>
		$line=~s/<>[\d\s\.]*$//;
		#coc_store can referred to know the word co-occurring
		push @coc_store,$line;
	}
}

#'words' contains the words whose co-occurrences are to be found.
#initially it contains the user specified target word.
#in each iteration the co-occurrences of the current iteration
#become the new words whose co-occurrences are found in the 
#next iteration.
push @words,$word;
#call the cocs function K times to get kth order co-occurrences
foreach (1..$order)
{
	#contains co-occurrences of the current order
	@cocs_this=();
	#kth order co-occurrences are the words co-occurring 
	#with the k-1 the order co-occurrences 
	#Hence find the words co-occurring with each word
	#returned by the k-1 th level
	foreach $lookfor_word (@words)
	{
		if($lookfor_word ne "")
		{
			#the function will return the words co-occurring 
			#with the word passed as a parameter 
			@from_cocs=&cocs($lookfor_word);
			if($#from_cocs<0)
			{
				print "ERROR($0):
	Word <$lookfor_word> is not found in the SOURCE file <$infile>.\n";
				exit;
			}
			push @cocs_this,@from_cocs;
			#stores the co-occurrences of the current word
			@{$look_up_table{$lookfor_word}}=@from_cocs;
		}
	}
	#find unique co-occurrences
        foreach (@cocs_this)
        {
              $cocs_this{$_}=1;
        }
	@words=();
	#the co-occurring words of the current stage become the 
	#input parameters to the cocs subroutine in the next stage 
	foreach (keys %cocs_this)
	{
		push @words,$_;
		delete $cocs_this{$_};
	}
}

#call a recursive function to identify and print 
#the kth order co-occurrences from the created 
#lookup table 
&trace($word,[],0);
if(!defined $got)
{
     print "No co-occurrences at $order$postfix level.\n"; 
}

##############################################################################

#                      ==========================
#                          SUBROUTINE SECTION
#                      ==========================

#-----------------------------------------------------------------------------

#----------------
#Subroutine cocs
#----------------
#returns all words co-occurring with a given word
sub cocs
{
	my $word=$_[0];	
	#string from the coc_store
	my $coc_string="";	
	#array of unique co-occurrences of the word
	my @return_cocs=();
	#to find the unique co-occurrences of the word
	my %return_hash;
	foreach $coc_string (@coc_store)
	{
		#find those bigrams which contain the target word 
		#and find the other word that co-occurs this word
		if($coc_string=~/^$word<>(.*)$/ || $coc_string=~/^(.*)<>$word$/)
		{
			$return_hash{$1}=1;
		}
	}
	#form an array of these co-occurrences
	foreach (keys %return_hash)
	{
		push @return_cocs,$_;
	}
	return @return_cocs;
}

#------------------
# Subroutine trace
#------------------
#algorithm to find all words at the specified order along with the paths to
#reach a particular word from the target word

#We imagine a word as a node and a graph with each node (word) connected to 
#all its co-occurrences. For simplicity of the algorithm, we assume the 
#co-occurrence graph as a co-occurrence tree making a separate entry for each 
#occurrence of a word. Imagine this as a tree with each node connected to all 
#its co-occurring words having distinct nodes for distinct occurrences of a word
 
#-----------------------------
#co-occurrence tree traversal
#-----------------------------
#we can imagine the problem of finding all words at the specified order along 
#with the paths to reach a word from the target word equivalent to traversing 
#the co-occurrence tree in depth first manner

#The target word specified by the user whose co-occurrences are to be found can 
#be imagined as the root and then we call a recursive function to look up an 
#entry for each child node of this root and continue this to find the paths 
#by which a leaf node can be reached from the root node

#recursive subroutine to find the Kth order co-occurrences and to trace the 
#paths of these Kth order co-occurrences from the target word 
sub trace
{
	#word whose co-occurrences are to be traced 
	my $look_up_word=$_[0];
	#stores all the nodes traveled so far from the root
	my @path=@{$_[1]};
	#the order of the current look_up word 
	my $level=$_[2];
	#adding a new node to the path
	push @path,$look_up_word;
	#if the current order matches with the specified order
	if($level==$order)
	{
		#print to the trace file
		if(defined $trace)
		{
			$chain_str=join "->",@path;
			print TRACE "$chain_str\n";
		}
		#checking unique occurrence of a word 
		#on the horizontal level
		$v=Set::Scalar->new(@{$cocs_at[$level]});
		if(!$v->has($look_up_word))
		{
			#print to stdout
			print "$look_up_word<>\n";
			push @{$cocs_at[$level]},$look_up_word;
		}
		#at least one word is found at this level
		$got=1;
	}
	#the word is a leaf node  
	if(!defined @{$look_up_table{$look_up_word}})
	{
		return;
	}
	else
	{
		#call function with each child node of the 
		#current node
		foreach (@{$look_up_table{$look_up_word}})
		{
			#call only if the word doesn't appear in the 
			#current chain from root to the current node. 
			#checking uniqueness on vertical path 
			my $s=Set::Scalar->new(@path);
			if(!$s->has($_))
			{
				&trace($_,[@path],$level+1);
			}
		}
	}
	return;
}

#-----------------------------------------------------------------------------
#show minimal usage message
sub showminimal()
{
        print "Usage: kocos.pl [OPTIONS] SOURCE WORD";
        print "\nTYPE kocos.pl --help for help\n";
}

#-----------------------------------------------------------------------------
#show help
sub showhelp()
{
	print "Usage:  kocos.pl [OPTIONS] SOURCE WORD
Displays the kth order Co-occurrences of a given WORD to standard output. 

SOURCE 
	A list of bigrams formatted like the output (extended or normal) 
	of count.pl or statistic.pl of NSP. If SOURCE is not created by 
	NSP, please consult the README of NSP for description of this format.
WORD 
	Specify a WORD whose kth order co-occurrences are to be found. 

OPTIONS:
--order K 
	Specify the value of K greater than or equal to 0 to find the kth 
	order co-occurrences of a WORD. A Kth order co-occurrence is a 
	word that co-occurs with a (K-1)th order co-occurrence of WORD.  
	By default, the value of K is set to 1 which simply lists all 
	words that co-occur with WORD. When K is 2, all the words that 
	co-occur with the words that co-occur with WORD are listed, etc. 
	[Note- 0th order co-occurrence of WORD is the WORD itself !] 
 
--trace TRACE_FILE
	Specify the name of a TRACE_FILE to see a detailed trace report 
	showing  the chains of co-occurrences. A chain shows how each Kth 
	order co-occurrence is reached as a sequence of words in K steps.  	
		e.g. WORD->First->Second->Third..->Kth 
	shows that the First was the first order co-occurrence of WORD,  	
	Second was the second order co-occurrence of WORD which co-occurs 
	with first. Third is the third order co-occurrence of WORD which  
	co-occurs with second and so on until K is reached. 
--help
        To display this message.

--version
        To display the version information.\n";
}

#------------------------------------------------------------------------------
#version information
sub showversion()
{
        print "kocos.pl       -        version 0.01\n";
        print "A Component of the NSP, version 0.53\n";
        print "Copyright (C) 2002-2003, Ted Pedersen and Amruta Purandare\n";
        print "Date of Last Update: 1/12/2003\n";
}

#############################################################################

