#!/usr/bin/perl

use 5.010;
use strict;
use warnings;


sub busca_binaria_rec{
    my ($conjunto,$elemento,$primero,$cuantos)=@_;
    my $izquierda=$primero;
    my $derecha=$cuantos;
    my $medio=($izquierda+$derecha)>>1;
    if($izquierda>$derecha){
        return (-1);
    }
    else{
      if((@{$conjunto}[$medio])==$elemento){
        return($medio);
        }
      if(@{$conjunto}[$medio]<$elemento){
        $medio+=1;
        busca_binaria_rec((\@{$conjunto}),$elemento,$medio,$derecha);
      }else{
        $medio-=1;
        busca_binaria_rec((\@{$conjunto}),$elemento,$izquierda,$medio);
        }
    }
}
    #pido el tamaño del conjunto 1, lo declaro y lleno (también el que usaré para guardar en binario)
    my ($cuantos1,$cuantos2,$cuantosU,$elemento,$tamanioreal, $conj1bin,$conj2bin,$interbin,$cuantos_inte);
    $conj1bin=0;
    $conj2bin=0;
    $elemento=0;
    print "Escribe el tamanio del conjunto 1 (maximo 65535)\n";
    $cuantos1=<STDIN>;
    my @conjunto1;
    
    

    #pedir_conjunto(\@conjunto1,$cuantos1);
    print "\nIngresa los $cuantos1 numeros del conjunto seguidos por un enter :) \n";
    for(my $i=0;$i<$cuantos1;$i++)
    {
        $conjunto1[$i]=<STDIN>;
    }
    print "\n";
    

    #ordenar(\@conjunto1,$cuantos1); #ordenamos conjunto para hacer más facil la vida
    my $temp=0;
    for(my $e=0;$e<$cuantos1;$e++){
        for(my $j=0;$j<$cuantos1;$j++){
            if($conjunto1[$e]<$conjunto1[$j]){
                $temp=$conjunto1[$e];
                $conjunto1[$e]=$conjunto1[$j];
                $conjunto1[$j]=$temp;
            }
        }
    }
    

    
    #pedimos el tamaño,declaramos y llenamos el 2do conjunto
    print"\nEscribe el tamanio del conjunto 2(maximo 65535)\n";
    $cuantos2=<STDIN>;
    my @conjunto2;
    
    #pedir_conjunto(\@conjunto2,$cuantos2);
    print "\nIngresa los $cuantos2 numeros del conjunto seguidos por un enter :) \n";
    for(my $f=0;$f<$cuantos2;$f++)
    {
        $conjunto2[$f]=<STDIN>;
    }
    print "\n";
    
    #ordenar(\@conjunto2,$cuantos2);#lo ordeno para hacer más sencilla la búsqueda
    my $tempo=0;
    for(my $k=0;$k<$cuantos2;$k++){
        for(my $j=0;$j<$cuantos2;$j++){
            if($conjunto2[$k]<$conjunto2[$j]){
                $tempo=$conjunto2[$k];
                $conjunto2[$k]=$conjunto2[$j];
                $conjunto2[$j]=$tempo;
            }
        }
    }
    
    #una vez que sabemos el tamaño de los conjuntos 1 y 2, vamos a declarar el conjunto universo y el vector donde guardaremos la intersección
    $cuantosU=$cuantos1+$cuantos2;
    if($cuantos1<$cuantos2?1:0){#el tamaño máximo de la intersección es el tamaño del conjunto más pequeño 
        $cuantos_inte=$cuantos1;
    }
    else{
        $cuantos_inte=$cuantos2;
    }
    my (@universo,@internum);
    
    #$tamanioreal=(crear_universo(\@universo,\@conjunto1,$cuantos1,\@conjunto2,$cuantos2,$cuantosU)); #crea el conjunto universo y nos dice el tamaño real para que no imprima basura
    my $cont=0;
    for(my $e=0;$e<$cuantos1;$e++){
        $universo[$e]=$conjunto1[$e];#meto todos los datos del 1er conjunto en el universo
    }
    for(my $n=0;$n<$cuantos2;$n++){
        $elemento=$conjunto2[$n];
        if(busca_binaria_rec(\@universo,$elemento,0,$cuantos1-1)==-1){#veo si los datos del 2do conjunto están, y si no, los agrego
            $universo[$cuantos1+$cont]=$elemento;
            $cont++;
        }
    }
        $tamanioreal=($cuantos1+$cont);#regresa el tamaño total del universo para evitar imprimir basura

    
    #ordenar 
    my $tempor=0;
    for(my $h=0;$h<$tamanioreal;$h++){
        for(my $j=0;$j<$tamanioreal;$j++){
            if($universo[$h]<$universo[$j]){
                $tempor=$universo[$h];
                $universo[$h]=$universo[$j];
                $universo[$j]=$tempor;
            }
        }
    }

    
    print"\nLa union de los conjuntos es:\n";
    #imprimir_conjunto(\@universo,$tamanioreal); #imprime la unión del conjunto
     print"\n";
    for(my $u=0;$u<$tamanioreal;$u++)
    {
        print "$universo[$u] \t";
    }
    print"\n";
    
    #ahora vemos la intersección con el universo de cada conjunto uno en bits
    #$conj1bin = phi(\@universo,$tamanioreal,\@conjunto1,$cuantos1,$conj1bin);
    $conj1bin=0;
	for(my $e=0;$e<$tamanioreal;$e++){
	    $conj1bin<<=1;
	    for(my $p=0;$p<$cuantos1;$p++){
	       if($universo[$e]==$conjunto1[$p]){
		  $conj1bin|=1;
		  $p=$cuantos1;
	       }
	    }
	   }  

    #$conj2bin = phi(\@universo,$tamanioreal,\@conjunto2,$cuantos2,$conj2bin);
    $conj2bin=0;
	for(my $e=0;$e<$tamanioreal;$e++){
	    $conj2bin<<=1;
	    for(my $m=0;$m<$cuantos2;$m++){
	       if($universo[$e]==$conjunto2[$m]){
		  $conj2bin|=1;
		  $m=$cuantos2;
	       }
	    }
	   }  
    

    #ya que tenemos los conjuntos en binario, sacamos la intersección entre ellos sobre bits :) 
    $interbin=($conj1bin & $conj2bin);
    
    #aplicamos la función phi inversa :D ~(*u*)~
    #$cuantos_inte=phi_inv(\@universo,$tamanioreal,\@internum,$cuantos_inte,$interbin);
    my $m=0;
	my $corre=$interbin;
	for(my $n=$tamanioreal-1;$n>=0;$n--)
	{
	    if(($corre&1)==1){
		$internum[$m]=$universo[$n];
		$m++;
	    }
	    $corre>>=1;
	}
	#ordenar((\@{$internum}),$cuantos_inte);
	$temp=0;
    for(my $q=0;$q<$cuantos_inte;$q++){
        for(my $j=0;$j<$cuantos_inte;$j++){
            if($internum[$q]<$internum[$j]){
                $temp=$internum[$q];
                $internum[$q]=$internum[$j];
                $internum[$j]=$temp;
            }
        }
    }
	$cuantos_inte=$m;
	  
    print "\nLa interseccion de los conjuntos es:\n";
   #imprimir_conjunto(\@internum,$cuantos_inte);
    print"\n";
    for(my $i=0;$i<$cuantos_inte;$i++)
    {
        print "$internum[$i] \t";
    }
    print"\n";
    
    #la resta de conj 1 y conj2
    my $restbin=($conj1bin & ~$conj2bin);
    
    
    #$cuantos_inte=phi_inv(\@universo,$tamanioreal,\@internum,$cuantos1,$restbin);
    my $g=0;
	$corre=$restbin;
	for(my $n=$tamanioreal-1;$n>=0;$n--)
	{
	    if(($corre&1)==1){
		$internum[$m]=$universo[$n];
		$g++;
	    }
	    $corre>>=1;
	}
	#ordenar($internum),$cuantos1);
	 $temp=0;
	 for(my $i=0;$i<$cuantos1;$i++){
		for(my $j=0;$j<$cuantos1;$j++){
		    if($internum[$i]<$internum[$j]){
			$temp=$internum[$i];
			$internum[$i]=$internum[$j];
			$internum[$j]=$temp;
            }
        }
    }
	$cuantos_inte=$g;
 
    print"\nLa diferencia entre el conjunto1 y el conjunto2 es:\n";
    #imprimir_conjunto(\@internum,$cuantos_inte);
     print"\n";
    for(my $i=0;$i<$cuantos_inte;$i++)
    {
        print "$internum[$i] \t";
    }
    print"\n";