#Damian Knopp
#!/usr/bin/perl -w
#Data Structures 336 bintree project
######################################################################
#This program reads from a text file. Then places each word into a binary 
#search tree.It reports the number of letters in a line.The number of
#words  in a line. Frequency of letters in file. It reports number of words and
#letters total in the file.The program does Inorder,postorder,and endorder 
#traversals. It reports the number of leaves,nodes wtih a single child,and nodes
#with 2 childern.When words are read in they are not inserted twice.
#######################################################################
use locale;
@freq=();
%freq=();
open(TD,"test.dat") ||  die "Cannot open file: $!";
for($linenum=1;<TD>;$linenum++){
    $words_in_line=0;
    for $word(split){
       $lcword=lc($word);                    #lower case words 
       if($lcword !~ /^\b([a-z'-]+$)\b/){ 
         chomp $lcword;
         chop $lcword;
         if($lcword =~ /^\b([a-z'-]+$)\b/){
             chomp $lcword;
             insert($root,$lcword);
             while($lcword =~ /(.)/g){
               push(@freq,$1);  
             } 
             $numofwords++;
             $words_in_line++; 
         } 
         else{
           print"$lcword is not a reconized word.\n";}         
          }
    elsif($lcword =~ /^\b([a-z'-]+$)\b/){
          chomp $lcword;
          insert($root,$lcword);
          while ($lcword =~ /(.)/g) {
              push (@freq,$1); 
          }
          #sleep 1;
          $numofwords++;
          $words_in_line++;
    }
print"I have read $numofwords words from the file so far.\n";
print"I have read $words_in_line words in line $linenum.\n";
}}
print "I have read $numofwords words from the file.\n";

print "Pre_order traversal\n";  pre_order($root);  print "\n";
print "In_order traversal\n";   in_order($root);   print "\n";
print "Post_order traversal\n"; post_order($root); print "\n";

print"A sorted list of the frequency of letters read:\n";
foreach $letter(@freq){
         $freq{$letter} +=1;}
foreach $letter (sort { $freq{$b} <=> $freq{$a} } keys %freq){
printf "$letter=%5d, %s\n", $freq{$letter}, $freq;}
print "I have read ", scalar(@freq), " letter from the file\n";
report($root);
print"My remove functions do not work. \n";
print "In_order traversal\n"; in_order($root); print "\n";


#print "What value shall we delete?\n";
#$delete=<STDIN>;
#chomp $delete;
#remove($root,$delete);

#for (print "Search? "; <>;print "Search? ") {
#   chomp;
#   my $found = search($root, $_);
#   if ($found) { print "Found  '$_' at $found, $found->{VALUE}\n"}
#   else        { print "No '$_' in tree\n" }
#}
exit;

#############################
sub insert{
  my($tree,$value)=@_;
  chomp $value;
  unless($tree) {
     $tree={};
     $tree->{VALUE} =$value;
     $tree->{LEFT}  =undef;
     $tree->{RIGHT} =undef;
     $tree->{COUNTER}=1;
     $_[0] =$tree;
     return;
   }
   if     ($tree->{VALUE} gt $value) {insert($tree->{LEFT}, $value) }
   elsif  ($tree->{VALUE} lt $value) {insert($tree->{RIGHT}, $value) }
   else{
     $tree->{COUNTER}++;}
}
#########################
sub inorder{
my($tree)=@_;
return unless $tree;
if ( ! defined $tree->{LEFT} && ! defined $tree->{RIGHT}){
 push (@leaf,$tree->{VALUE});
}
elsif (! defined $tree->{LEFT} || ! defined $tree->{RIGHT}){
 push (@single,$tree->{VALUE});
}
else {
 push (@double,$tree->{VALUE});
}
inorder($tree->{LEFT});
inorder($tree->{RIGHT});
}
#########################
sub in_order {
  my($tree)=@_;
  return unless $tree;
  in_order($tree->{LEFT});
  print $tree->{VALUE}," :was inputed ", $tree->{COUNTER}," time\n";
  in_order($tree->{RIGHT});
}

###########################
sub post_order{
  my($tree)= @_;
  return unless $tree;
  post_order($tree->{LEFT});
  post_order($tree->{RIGHT});
  print $tree->{VALUE}," :was inputed ", $tree->{COUNTER}," time\n";
} 
##########################
sub pre_order{
  my($tree)=@_;
  return unless $tree;
  print $tree->{VALUE}, " :was inputed ", $tree->{COUNTER}," time\n";
  pre_order($tree->{LEFT});
  pre_order($tree->{RIGHT});
}
###############################
sub report{
my ($tree)=@_;
inorder($tree->{LEFT});
inorder($tree->{RIGHT});
print"I have " ,scalar(@leaf)    ," leafs in the tree.\n";
print"I have " ,scalar(@single)  ," nodes in the tree with one child.\n";
print"I have " , scalar(@double) ," nodes in the tree with two childern.\n";
}
#########################
sub search{
  my($tree,$value)=@_;
  return unless $tree;
  #print"Searching for $value current value is $tree->{VALUE} in tree $tree\n";
  if ($tree->{VALUE} eq $value){
    print"Should return $tree found $value = $tree->{VALUE}\n";
    return $tree;
   }
  search($tree->{($value lt $tree->{VALUE}) ? "LEFT" : "RIGHT"}, $value)
}
##############################
sub remove{
my ($tree,$value)=@_;
my $found={};
$found->{RIGHT}=undef;
$found->{LEFT}=undef;
$found->{VALUE}=undef;
   print "Passing search $value in root $tree\n";
   $found=search($tree,$value);
   print "Results from search are '$found->{VALUE}' at '$found'\n"; 
   if ( ! defined $found){
       print "No tree to find\n";
       return;}
   if ( ! defined $found->{LEFT}){
  print"$found has left child '$found->{LEFT}' right child '$found->{RIGHT}'\n";
         $found=$found->{RIGHT};
         print"found is now $found and right is $found->{RIGHT}\n";} 
  elsif ( ! defined $found->{RIGHT}){
         print "$found->{LEFT} has no right child\n";
         $found=$found->{LEFT};} 
   else{
       print"do the hard case\n";} 
}
