use strict;
use warnings;
use POSIX;

# this function  will  merge the cells with the same property,
# if the cell' left or left neighbour has the same property, it will
# be merged to its neigbour.  This function will scan the cell matrix
# from up tp down and from left to right. It will check its upper and left
# neighbour simultaneously. 
# For simplicity, we assume that the left neigbour
# has more priority than its upper neighbour if it has two neigbours simultaneously.
# After being processed, an integral region will assigned a number, which increases from 
# 0. Also a array will record its corresponding cell style. It has three inputs. 
# The first is cells_style_reference, which is the initial cells property
# the second is cells_merge_reference, which is the processed cells array
# the third is cells_merge_styles_reference, for every index,  its style is stored.
# the fourth is cells_merge_pos_array, which stores the first position of the style
sub merge_cells
{
   my ($cells_matrix_ref, $cells_matrix_merge_ref, $cells_merge_style_array_ref) = @_ ;
   
  # my @cells_matrix = @{$cells_matrix_ref};
  # my @cells_matrix_merge = @{$cells_matrix_merge_ref};
  # my @cells_merge_style_array = @{$cells_merge_style_array_ref};
   
   my $row_num = @{$cells_matrix_ref};
   my $column_num = $#{$cells_matrix_ref->[0]} + 1;
   my $index = 0;

   for(my $row_count=0;$row_count< $row_num;$row_count++)
   {
      for(my $column_count=0;$column_count< $column_num;$column_count++ )
      {
         # if column_count == 0  this is the first row, we couldn't check the upper neighbour
         # if row_count == 0  this is the first column, we couldn't check the left neighbour
         if($column_count==0 and $row_count==0)
         {       
            $cells_matrix_merge_ref->[$row_count][$column_count] = $index;
            $cells_merge_style_array_ref->[$index]=[$cells_matrix_ref->[$row_count][$column_count],$row_count,$column_count];
            $index++;
         }
         
         if($row_count==0 and $column_count!=0)
         {
            if ( $cells_matrix_ref->[$row_count][$column_count] == $cells_matrix_ref->[$row_count][$column_count-1] )
            {
               $cells_matrix_merge_ref->[$row_count][$column_count]=$cells_matrix_merge_ref->[$row_count][$column_count-1];
            }
            else
            { 
               $cells_matrix_merge_ref->[$row_count][$column_count] = $index;
               $cells_merge_style_array_ref->[$index]=[$cells_matrix_ref->[$row_count][$column_count],$row_count,$column_count];
               $index++;           
            }        
         }
         
         if($column_count==0 and $row_count!=0)
         {
            if ( $cells_matrix_ref->[$row_count][$column_count] == $cells_matrix_ref->[$row_count-1][$column_count] )
            {
               $cells_matrix_merge_ref->[$row_count][$column_count]=$cells_matrix_merge_ref->[$row_count-1][$column_count];
            }
            else
            { 
               $cells_matrix_merge_ref->[$row_count][$column_count] = $index;
               $cells_merge_style_array_ref->[$index]=[$cells_matrix_ref->[$row_count][$column_count],$row_count,$column_count];
               $index++;           
            }  
         }
         if($column_count!=0 and $row_count!=0)
         {
            # if the upper and left neighbour has the same style and the same index
            if ( $cells_matrix_ref->[$row_count][$column_count] == $cells_matrix_ref->[$row_count][$column_count-1] and 
                 $cells_matrix_ref->[$row_count][$column_count] == $cells_matrix_ref->[$row_count-1][$column_count] and
                 $cells_matrix_merge_ref->[$row_count][$column_count-1] == $cells_matrix_merge_ref->[$row_count-1][$column_count] )
            {
               $cells_matrix_merge_ref->[$row_count][$column_count]=$cells_matrix_merge_ref->[$row_count][$column_count-1];
            }
            elsif ( $cells_matrix_ref->[$row_count][$column_count] == $cells_matrix_ref->[$row_count][$column_count-1] and 
                 $cells_matrix_ref->[$row_count][$column_count] == $cells_matrix_ref->[$row_count-1][$column_count] and
                 $cells_matrix_merge_ref->[$row_count][$column_count-1] != $cells_matrix_merge_ref->[$row_count-1][$column_count])             
            {
               # merged into left neighbour    44
              $cells_matrix_merge_ref->[$row_count][$column_count]=$cells_matrix_merge_ref->[$row_count][$column_count-1];
               # merged into upper neighbour
               #$cells_matrix_merge_ref->[$row_count][$column_count]=$cells_matrix_merge_ref->[$row_count-1][$column_count];
            }
            elsif ( $cells_matrix_ref->[$row_count][$column_count] != $cells_matrix_ref->[$row_count][$column_count-1] and 
                 $cells_matrix_ref->[$row_count][$column_count] != $cells_matrix_ref->[$row_count-1][$column_count] )         
            {
               $cells_matrix_merge_ref->[$row_count][$column_count] = $index;
               $cells_merge_style_array_ref->[$index]=[$cells_matrix_ref->[$row_count][$column_count],$row_count,$column_count];
               $index++;
            } 
            elsif ( $cells_matrix_ref->[$row_count][$column_count] == $cells_matrix_ref->[$row_count][$column_count-1] and 
                 $cells_matrix_ref->[$row_count][$column_count] != $cells_matrix_ref->[$row_count-1][$column_count] )              
            {
               $cells_matrix_merge_ref->[$row_count][$column_count]=$cells_matrix_merge_ref->[$row_count][$column_count-1];
            }           
            elsif ( $cells_matrix_ref->[$row_count][$column_count] != $cells_matrix_ref->[$row_count][$column_count-1] and 
                 $cells_matrix_ref->[$row_count][$column_count] == $cells_matrix_ref->[$row_count-1][$column_count] )            
            {
               $cells_matrix_merge_ref->[$row_count][$column_count] = $index;
               $cells_merge_style_array_ref->[$index]=[$cells_matrix_ref->[$row_count][$column_count],$row_count,$column_count];
               $index++;
            }
            
         }
         
      }       
   }	
}



sub generate_graph
{
   my ($cells_matrix_merge_ref, $cells_merge_style_array_ref,$geoinfo_ref,$graph_ref) = @_ ;
  
   my $row_num = @{$cells_matrix_merge_ref};
   my $column_num = $#{$cells_matrix_merge_ref->[0]} + 1;
   my $index = 0;
   my $row;
   my $column;
   my $row_beg;
   my $row_end;
   my $column_beg;
   my @element;
   
   foreach $index (0..$#{$cells_merge_style_array_ref})
   {
      my ($style,$row_beg,$column_beg) = @{$cells_merge_style_array_ref->[$index]};
      $row=$row_beg;
      
      # this loop is to find the maximum column number for every row
      while(1)
      {
        $column=$column_beg;
        while(1)
        {
           if($column== ($column_num-1))
           {
              $element[$row]=$column;
              last;
           }
           
           if($cells_matrix_merge_ref->[$row][$column+1]==$cells_matrix_merge_ref->[$row][$column])
           {
              $column++;
           }
           else
           {
              $element[$row]=$column;
              last;
           }
        }
        # print  $row . $row_num . "\n";
        if($row==($row_num-1))
        {
              last;
        }
        if($cells_matrix_merge_ref->[$row][$column_beg]==$cells_matrix_merge_ref->[$row+1][$column_beg])
        {
              $row++;
              next;
        }
        else
        {
              # print "hello2 \n"   ;
              last;
         }
       }
        # print $row . " " . $column . "\n" ;
        #now $row $column store the last row's
        # if($index==0)
        # {
           # print "row $row, column $column, row_beg $row_beg, column $column_beg" . "\n";
        # }
        push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row+1][$column_beg][0] ); 
        # if($index==0)
        # {
           # print $geoinfo_ref->[$row+1][$column_beg][0] ."\n";
           # print "@{$graph_ref->[$index]}" . "\n";
        # }
        push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row+1][$column_beg][1] );
        # if($index==0)
        # {
           # print "@{$graph_ref->[$index]}" . "\n";
        # }
        push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row_beg][$column_beg][0] ); 
        # if($index==0)
        # {
           # print "@{$graph_ref->[$index]}" . "\n";
        # }
        push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row_beg][$column_beg][1] );
        # if($index==0)
        # {
           # print "@{$graph_ref->[$index]}" . "\n";
        # }
        push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row_beg][$element[$row_beg]+1][0] ); 
          # if($index==0)
        # {
           # print "@{$graph_ref->[$index]}" . "\n";
        # }
        push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row_beg][$element[$row_beg]+1][1] );
          # if($index==0)
        # {
           # print "@{$graph_ref->[$index]}" . "\n";
        # }
        
        $row_end = $row;
        $row = $row_beg;
        while(1)
        {
           if($row==$row_end)
           {
              push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row+1][$element[$row]+1][0] ); 
              push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row+1][$element[$row]+1][1] );
              last;
           }
           elsif($element[$row]==$element[$row+1])
           {
              $row++;
           }
           elsif($element[$row]!=$element[$row+1])
           {
              
              push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row+1][$element[$row]+1][0] ); 
              push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row+1][$element[$row]+1][1] );
              push( @{$graph_ref->[$index]} ,  $geoinfo_ref->[$row+1][$element[$row+1]+1][0] ); 
              push( @{$graph_ref->[$index]} ,  $geoinfo_ref->[$row+1][$element[$row+1]+1][1] );
              $row++;
           }
           
        }
        
        push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row+1][$column_beg][0] ); 
        push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row+1][$column_beg][1] );
        
        # if($index==0)
        # {
           # print "@{$graph_ref->[$index]}" . "\n";
        # }  
        
         
      }
}
      
sub merge_events_cells
{
   my ($events_matrix_ref, $events_matrix_merge_ref, $events_merge_style_array_ref) = @_ ;
   

   
   my $row_num = @{$events_matrix_ref};
   my $column_num = $#{$events_matrix_ref->[0]} + 1;
   my $index = 0;

   for(my $row_count=0;$row_count< $row_num;$row_count++)
   {
      for(my $column_count=0;$column_count< $column_num;$column_count++ )
      {
         # if column_count == 0  this is the first row, we couldn't check the upper neighbour
         # if row_count == 0  this is the first column, we couldn't check the left neighbour
         if($events_matrix_ref->[$row_count][$column_count] eq "x")
         {
            $events_matrix_merge_ref->[$row_count][$column_count]="x";
            next;
            
         }
         
         if($column_count==0 and $row_count==0)
         {       
            $events_matrix_merge_ref->[$row_count][$column_count] = $index;
            $events_merge_style_array_ref->[$index]=[$events_matrix_ref->[$row_count][$column_count],$row_count,$column_count];
            $index++;
         }
         
         if($row_count==0 and $column_count!=0)
         {
            if ( $events_matrix_ref->[$row_count][$column_count] eq $events_matrix_ref->[$row_count][$column_count-1] )
            {
               $events_matrix_merge_ref->[$row_count][$column_count]=$events_matrix_merge_ref->[$row_count][$column_count-1];
            }
            else
            { 
               $events_matrix_merge_ref->[$row_count][$column_count] = $index;
               $events_merge_style_array_ref->[$index]=[$events_matrix_ref->[$row_count][$column_count],$row_count,$column_count];
               $index++;           
            }        
         }
         
         if($row_count!=0 and $column_count==0)
         {
            if ( $events_matrix_ref->[$row_count][$column_count] eq $events_matrix_ref->[$row_count-1][$column_count] )
            {
               $events_matrix_merge_ref->[$row_count][$column_count]=$events_matrix_merge_ref->[$row_count-1][$column_count];
            }
            else
            { 
               $events_matrix_merge_ref->[$row_count][$column_count] = $index;
               $events_merge_style_array_ref->[$index]=[$events_matrix_ref->[$row_count][$column_count],$row_count,$column_count];
               $index++;           
            }        
         }
         
         if($column_count!=0 and $row_count!=0)
         {
            # print "$events_matrix_merge_ref->[$row_count][$column_count-1]\n";
            # print "$events_matrix_merge_ref->[$row_count-1][$column_count]\n";
            
            # if the upper and left neighbour has the same style and the same index
            if(!defined($events_matrix_merge_ref->[$row_count][$column_count-1]))
            {
               print "row: $row_count " . "column: " . ($column_count-1) . "\n";
            }
            if(!defined($events_matrix_merge_ref->[$row_count-1][$column_count]))
            {
               print "row: " . ($row_count-1) . "column: " . ($column_count) . "\n";
            }
          
            if ( $events_matrix_ref->[$row_count][$column_count] eq $events_matrix_ref->[$row_count][$column_count-1] and 
                 $events_matrix_ref->[$row_count][$column_count] eq $events_matrix_ref->[$row_count-1][$column_count] and
                 $events_matrix_merge_ref->[$row_count][$column_count-1] eq $events_matrix_merge_ref->[$row_count-1][$column_count] )
            {
               $events_matrix_merge_ref->[$row_count][$column_count]=$events_matrix_merge_ref->[$row_count][$column_count-1];
            }
            elsif ( $events_matrix_ref->[$row_count][$column_count] eq $events_matrix_ref->[$row_count][$column_count-1] and 
                 $events_matrix_ref->[$row_count][$column_count] eq $events_matrix_ref->[$row_count-1][$column_count]  and
                 $events_matrix_merge_ref->[$row_count][$column_count-1] ne $events_matrix_merge_ref->[$row_count-1][$column_count])             
            {
               # merged into left neighbour    44
              $events_matrix_merge_ref->[$row_count][$column_count]=$events_matrix_merge_ref->[$row_count][$column_count-1];
               # merged into upper neighbour
               #$cells_matrix_merge_ref->[$row_count][$column_count]=$cells_matrix_merge_ref->[$row_count-1][$column_count];
            }
            elsif ( $events_matrix_ref->[$row_count][$column_count] ne $events_matrix_ref->[$row_count][$column_count-1] and 
                 $events_matrix_ref->[$row_count][$column_count] ne $events_matrix_ref->[$row_count-1][$column_count] )         
            {
               $events_matrix_merge_ref->[$row_count][$column_count] = $index;
               $events_merge_style_array_ref->[$index]=[$events_matrix_ref->[$row_count][$column_count],$row_count,$column_count];
               $index++;
            } 
            elsif ( $events_matrix_ref->[$row_count][$column_count] eq $events_matrix_ref->[$row_count][$column_count-1] and 
                 $events_matrix_ref->[$row_count][$column_count] ne $events_matrix_ref->[$row_count-1][$column_count] )              
            {
               $events_matrix_merge_ref->[$row_count][$column_count]=$events_matrix_merge_ref->[$row_count][$column_count-1];
            }           
            elsif ( $events_matrix_ref->[$row_count][$column_count] ne $events_matrix_ref->[$row_count][$column_count-1] and 
                 $events_matrix_ref->[$row_count][$column_count] eq $events_matrix_ref->[$row_count-1][$column_count] and 
                 $events_matrix_ref->[$row_count][$column_count] eq $events_matrix_ref->[$row_count-1][$column_count-1])            
            {
               $events_matrix_merge_ref->[$row_count][$column_count] = $index;
               $events_merge_style_array_ref->[$index]=[$events_matrix_ref->[$row_count][$column_count],$row_count,$column_count];
               $index++;
            }
            elsif ( $events_matrix_ref->[$row_count][$column_count] ne $events_matrix_ref->[$row_count][$column_count-1] and 
                 $events_matrix_ref->[$row_count][$column_count] eq $events_matrix_ref->[$row_count-1][$column_count] and 
                 $events_matrix_ref->[$row_count][$column_count] ne $events_matrix_ref->[$row_count-1][$column_count-1])            
            {
               $events_matrix_merge_ref->[$row_count][$column_count] = $events_matrix_merge_ref->[$row_count-1][$column_count];

            }
            
         }
         
      }       
   }	
}



sub generate_events_graph
{
   my ($events_matrix_merge_ref, $events_merge_style_array_ref,$geoinfo_ref,$graph_ref) = @_ ;
  
   my $row_num = @{$events_matrix_merge_ref};
   my $column_num = $#{$events_matrix_merge_ref->[0]} + 1;
   my $index = 0;
   my $row;
   my $column;
   my $row_beg;
   my $row_end;
   my $column_beg;
   my @element;
   
   foreach $index (0..$#{$events_merge_style_array_ref})
   {
      my ($style,$row_beg,$column_beg) = @{$events_merge_style_array_ref->[$index]};
      $row=$row_beg;
      
      # this loop is to find the maximum column number for every row
      while(1)
      {
        $column=$column_beg;
        while(1)
        {
           if($column== ($column_num-1))
           {
              $element[$row]=$column;
              last;
           }
           
           if($events_matrix_merge_ref->[$row][$column+1] eq $events_matrix_merge_ref->[$row][$column])
           {
              $column++;
           }
           else
           {
              $element[$row]=$column;
              last;
           }
        }
        # print  $row . $row_num . "\n";
        if($row==($row_num-1))
        {
              last;
        }
        if($events_matrix_merge_ref->[$row][$column_beg] eq $events_matrix_merge_ref->[$row+1][$column_beg])
        {
              $row++;
              next;
        }
        else
        {
              # print "hello2 \n"   ;
              last;
         }
       }
        # print $row . " " . $column . "\n" ;
        #now $row $column store the last row's
        # if($index==0)
        # {
           # print "row $row, column $column, row_beg $row_beg, column $column_beg" . "\n";
        # }
        push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row+1][$column_beg][0] ); 
        # if($index==0)
        # {
           # print $geoinfo_ref->[$row+1][$column_beg][0] ."\n";
           # print "@{$graph_ref->[$index]}" . "\n";
        # }
        push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row+1][$column_beg][1] );
        # if($index==0)
        # {
           # print "@{$graph_ref->[$index]}" . "\n";
        # }
        push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row_beg][$column_beg][0] ); 
        # if($index==0)
        # {
           # print "@{$graph_ref->[$index]}" . "\n";
        # }
        push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row_beg][$column_beg][1] );
        # if($index==0)
        # {
           # print "@{$graph_ref->[$index]}" . "\n";
        # }
        push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row_beg][$element[$row_beg]+1][0] ); 
          # if($index==0)
        # {
           # print "@{$graph_ref->[$index]}" . "\n";
        # }
        push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row_beg][$element[$row_beg]+1][1] );
          # if($index==0)
        # {
           # print "@{$graph_ref->[$index]}" . "\n";
        # }
        
        $row_end = $row;
        $row = $row_beg;
        while(1)
        {
           if($row==$row_end)
           {
              push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row+1][$element[$row]+1][0] ); 
              push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row+1][$element[$row]+1][1] );
              last;
           }
           elsif($element[$row]==$element[$row+1])
           {
              $row++;
           }
           elsif($element[$row]!=$element[$row+1])
           {
              
              push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row+1][$element[$row]+1][0] ); 
              push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row+1][$element[$row]+1][1] );
              push( @{$graph_ref->[$index]} ,  $geoinfo_ref->[$row+1][$element[$row+1]+1][0] ); 
              push( @{$graph_ref->[$index]} ,  $geoinfo_ref->[$row+1][$element[$row+1]+1][1] );
              $row++;
           }
           
        }
        
        push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row+1][$column_beg][0] ); 
        push( @{$graph_ref->[$index]} , $geoinfo_ref->[$row+1][$column_beg][1] );
        
        # if($index==0)
        # {
           # print "@{$graph_ref->[$index]}" . "\n";
        # }  
        
         
      }
}

1;