#!usr/bin/perl
use OpenGL qw/ :all /;
my %city=(  0=> "A;200:100",
            1=> "B;200:300",
	    2=> "C;500:300",
            3=> "D;500:100",
	    4=> "E;600:200",
            5=> "F;300:100",
            6=> "G;100:200",
            7=> "H;300:200",
	    8=> "K;300:500",
            9=> "L;100:500",
	    10=>"M;200:600",
            11=>"N;800:100",
            12=>"O;120:500",
            13=>"P;21:100",
            14=>"Q;20:40",
            15=>"I;33:201",
            16=>"R;300:50",
            17=>"J;10:50",
            18=>"X;20:60",
            19=>"T;80:10",
            20=>"W;120:50",
            21=>"Z;210:10",
            22=>"J;500:500",
            23=>"X;420:500",
            24=>"T;210:400",
            25=>"W;400:220",
            26=>"Z;431:346"
            );

$gja=900;
$gje=800;
#--the constants for the population
my $population=80;
my @v=keys %city;
my $chromosom_length=@v;
my $best=0,$best_2=0;$worst=-1,$worst_2=-1;
my $gen=0;
my @random_numbers=split(/-/,rand_nums($generations));
my $maxk=0;
my %chromosome;
my %children;
my %cache;
#======================================
sub rand_nums {
my %local_cache; 
my ($length) = @_; 
my $serial = int(rand($length));
$local_cache{$serial} = 1;
for (2..$length) {
my $num = int(rand($length));
redo if exists $local_cache{$num};
$local_cache{$num} = 1;
$serial .= "-$num";
}
rand_nums($length) if exists $cache{$serial};
$cache{$serial}=1;
return $serial;
}

sub init_population{
$clr=$_[0];
for ($i=0;$i<$population;$i++){
  @r=split(/-/,rand_nums($clr)); 
  $chromosome{$i}=join('-',@r);
  print "$chromosome{$i} \n";
  }
}
sub fitnes{
@chromo=split(/-/,$_[0]);
my $r=0;
for($i=0;$i<$chromosom_length-1;$i++){
 $pos=$chromo[$i];
 @d=split(/;/,$city{$pos});
 $name=$d[0];
 @t=split(/:/,$d[1]);
 $x1=$t[0];
 $y1=$t[1];
 #next;
 $pos=$chromo[$i+1];
 @d=split(/;/,$city{$pos});
 $name=$d[0];
 @t=split(/:/,$d[1]);
 $x2=$t[0];
 $y2=$t[1];
 #--------------------
 $t1=$x2-$x1;
 $t2=$y2-$y1;
 #print "$t1 $t2\n";
 $dis=sqrt(($t1*$t1)+($t2*$t2));
 $r+=$dis;
}
return ($r);
}
sub evaluate_population{
foreach (sort{$a<=>$b} keys %chromosome) {
 if ((fitnes($chromosome{$_})<=fitnes($chromosome{$best}))){
  $best_2=$best;
  $best=$_;
  }
 if ((fitnes($chromosome{$_})>=fitnes($chromosome{$worst}))){
   $worst_2=$worst;
   $worst=$_;
   }
 }
}
#-----helper-
sub clean{
@chromo=split(/-/,$_[0]);
@crosoverDNA=split(/-/,$_[1]);
my $nr=0;
foreach(@chromo){
my $vl=$_; 
 foreach(@crosoverDNA){
  $chromo[$nr]="H" if($_==$vl);
  }
$nr++;
}
return(join('-',@chromo));
}

sub replace_holes{
my %lcache;
my $clr=$_[1];
@chromo_vector=split(/-/,$_[0]);
foreach(@chromo_vector){
 $lcache{$_}+=1; 
 }
my @rand_vec=split(/-/,rand_nums($clr));
my $nr=0;
my @t;
  #gjenerimi i nr te ndryshem
  for($i=0;$i<$clr;$i++){
  push @t,$rand_vec[$i] if!(exists $lcache{$rand_vec[$i]});
  }
  #-------
  foreach(@chromo_vector){
    if($_ eq 'H'){
     $chromo_vector[$nr]=shift(@t);
    }
    $nr++;
    }
return(join('-',@chromo_vector));
}

sub mutate{
@individ=split(/-/,$_[0]);
my $crl=$_[1];
$c1=int(rand(time()*$$) % $crl);
$c2=int(rand(time()*$$^2) % $crl);
$t=$individ[$c1];
$individ[$c1]=$individ[$c2];
$individ[$c2]=$t;
return(join('-',@individ));
}
sub kopjo{
@v= split(/-/,$_[0]);
$p1=$_[1];
$p2=$_[2];
my @r;
for($i=$p1;$i<=$p2;$i++){
 push @r,$v[$i];
 }
return(join('-',@r));
}
#------------
sub reproduct_population{
print_population();
print "gjenerate $gen best $chromosome{$best} best fitnes nr $best:".fitnes($chromosome{$best})."\n";
my $fathernr=int(rand(time()^$$*2)) % $population;
#my $fathernr=$best;
#my $mothernr=rand($$*time^5) % $population;
#my $mothernr=$best_2; 
foreach(sort{$a<=>$b} keys %chromosome){
  $mothernr=$_;
  my $cnr=0;
  if ($mothernr!=$fathernr){
    my @father_vector=split(/-/,$chromosome{$fathernr});
    my @mother_vector=split(/-/,$chromosome{$mothernr});
    my $nr=0,@temp;
    if(int(rand(time()^$$)) % 100<20){
          do{
	  $c1=int(rand(time^$$)) % $chromosom_length;
	  $c2=int(rand(2*$$*time())) % $chromosom_length;
          #$c2=$chromosom_length;
          }while(($c1==0)||($c2==0));
          if ($c2>$c1){  
          $cx=&kopjo(join('-',@father_vector),$c1,$c2);
	  $cy=&kopjo(join('-',@mother_vector),$c1,$c2);
       	  $father_c =&clean(join('-',@father_vector),$cy);
	  $mother_c =&clean(join('-',@mother_vector),$cx);
          $c1x=&kopjo($father_c,0,$c1-1);
	  $c2x=&kopjo($father_c,$c2+1,$chromosom_length);
	  $c1y=&kopjo($mother_c,0,$c1-1);
	  $c2y=&kopjo($mother_c,$c2+1,$chromosom_length);
          $child_1=$c1x."-".$cy."-".$c2x;
	  $child_2=$c1y."-".$cx."-".$c2y;
          }else{
          $cx=&kopjo(join('-',@father_vector),$c2,$c1);
          $cy=&kopjo(join('-',@mother_vector),$c2,$c1);
          $father_c =&clean(join('-',@father_vector),$cy);
          $mother_c =&clean(join('-',@mother_vector),$cx);
          $c1x=&kopjo($father_c,0,$c2-1);
          $c2x=&kopjo($father_c,$c1+1,$chromosom_length);
          $c1y=&kopjo($mother_c,0,$c2-1);
          $c2y=&kopjo($mother_c,$c1+1,$chromosom_length);
          $child_1=$c1x."-".$cy."-".$c2x;
          $child_2=$c1y."-".$cx."-".$c2y; 
          } 
	  $child1=&replace_holes($child_1,$chromosom_length);
	  $child2=&replace_holes($child_2,$chromosom_length);
           if (fitnes($child1)<fitnes($child2)){ 
              if(! exists $cache{$child1}){
               $chromosome{$_}=$child1 if(fitnes($child1)<fitnes($chromosome{$_}));
               $cache{$child1}=1;
               }
           }else{
              if(! exists $cache{$child2}){
               $chromosome{$_}=$child2 if(fitnes($child2)<fitnes($chromosome{$_}));
               $cache{$child2}=1; 
           }
         }
        }#crosover
          if(int(rand(time()^$$)) % 100<101){
          $m=mutate($chromosome{$_},$chromosom_length);
          if((!exists $cache{$m})&&(fitnes($m)<fitnes($chromosome{$_}))){
               $chromosome{$_}=$m;
               $cache{$m}=1;
               }
        } 
          
    }
   }
#print_population();
}
sub print_population{
foreach (sort{$a<=>$b} keys %chromosome) {
print "$_ -> $chromosome{$_} \n";
}
}
sub ourPrintString
{
  my ($font, $str) = @_;
  my @c = split '', $str;

  for(@c)
  {
    glutBitmapCharacter($font, ord $_);
  }
}

sub vizato_reth{
$NPOINTS=24;
$TWOPI=2*3.14159268;
$STEP=$TWOPI/$NPOINTS;
glBegin(GL_LINE_LOOP);
for($angle=0;$angle<$TWOPI;$angle+=$STEP){
 glVertex2f(0.5 * cos($angle), 0.5* sin($angle));
 }
glEnd();
}

sub print_interpretation_of_vector{
@v=split(/-/,$chromosome{$best});
$nr=0;
glLoadIdentity();
glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT);#Aktivizo Bufferat
#glTranslatef(10,10,1);#pergatit matricen e Skenes per futje te nje elementi ose transformimi 
glPushMatrix();
glBegin(GL_LINE_LOOP);#start drawing a line loop
 foreach(@v){
 my $q1=$_;
  foreach(@v){
   my $q2=$_;
   @data=split(/;/,$city{$q1});
   @cord=split(/:/,$data[1]);
   $x=$cord[0];
   $y=$cord[1]; 
   glColor3f(0.3,0.3,0.3);
   glVertex2f("$x.0","$y.0");
   @data=split(/;/,$city{$q2});
   @cord=split(/:/,$data[1]);
   $x=$cord[0];
   $y=$cord[1];
   glVertex2f("$x.0","$y.0");

  }
 }
#glVertex2f(100.0,100.0);
#glVertex2f(100.0,200.0);
glEnd();
glPopMatrix();
glPushMatrix();
glBegin(GL_LINE_LOOP);#start drawing a line loop
$r="";
 foreach(@v){
   @data=split(/;/,$city{$_});
   @cord=split(/:/,$data[1]);
   $x=$cord[0];
   $y=$cord[1];
   glColor3f(0,1,0);
   glVertex2f("$x.0","$y.0");
   $r.='glRasterPos2i('.$x.','.$y.');ourPrintString(GLUT_BITMAP_HELVETICA_12,":'.$data[0].'");';
   }
#glVertex2f(100.0,100.0);
#glVertex2f(100.0,200.0);
glEnd();
eval($r);
glPopMatrix();
glutPostRedisplay();
glutSwapBuffers();#Ruhen ndryshimet ne framebuffer
return($r);
}
sub init{
glClearColor(0,0,0,0);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glOrtho(0,$gja,0,$gje,-1.0,1.0);
glDisable(GL_DEPTH_TEST);#Aktivizo sensin e thellesise
glMatrixMode(GL_MODELVIEW);
}
sub idle{
$gen++;
&reproduct_population();
&evaluate_population();
}


#----main simualtion
&init_population($chromosom_length);
&evaluate_population();
#&print_population();
glutInit();#rutine inicializimi e glut
glutInitWindowSize($gja,$gje); #permasat e dritares
glutInitWindowPosition(10,10);#pozicione ne dritaren e sistemit operativ
glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);#Aktivizo bufferin e thellesise
glutCreateWindow("OPENTSP");
init();
glutDisplayFunc(\&print_interpretation_of_vector);#funksioni callback qe vizaton ekranin
glutIdleFunc(\&idle);#Kur ske cfare te besh aktivizo kete funksion
glutSetOption(GLUT_ACTION_ON_WINDOW_CLOSE,GLUT_ACTION_GLUTMAINLOOP_RETURNS);
glutMainLoop();#ripersrit ciklin