# module Bio::PopGen::TagHaplotype.pm
#
# Please direct questions and support issues to <bioperl-l@bioperl.org> 
#
# Cared for by Pedro M. Gomez-Fabre <pgf18872-at-gsk-dot-com>
#
# Copyright Pedro M. Gomez-Fabre
#
# You may distribute this module under the same term as perl itself
#

# POD documentation - main docs before the code

=head1 NAME

Bio::PopGen::TagHaplotype.pm - Haplotype tag object.

=head1 SYNOPSIS

    use Bio::PopGen::TagHaplotype;

    my $obj = Bio::PopGen::TagHaplotype -> new($hap);

=head1 DESCRIPTION

This module take as input a haplotype and try toe get the minimal set
of SNP that define the haplotype. This module can be use alone.  But
due to the tagging haplotype process is exponential one. My suggestion
is that before to use this module you pass your data under Select.mp
module also on this folder.  In any case if, you provide an haplotype
the module will try to find the answer to your question.

=head1 CONSTRUCTORS

    my $obj = Bio::PopGen::TagHaplotype -> new($hap);

    were $hap is the reference to an array of array with the haplotype.

    $hap= [[0, 0, 0],
           [1, 0, 0],
           [0, 1, 1]
          ];

=head1 FEEDBACK

=head2 Mailing Lists

User feedback is an integral part of the evolution of this and other
Bioperl modules. Send your comments and suggestions preferably to
the Bioperl mailing list.  Your participation is much appreciated.

  bioperl-l@bioperl.org                  - General discussion
  http://bioperl.org/wiki/Mailing_lists  - About the mailing lists

=head2 Support 

Please direct usage questions or support issues to the mailing list:

I<bioperl-l@bioperl.org>

rather than to the module maintainer directly. Many experienced and 
reponsive experts will be able look at the problem and quickly 
address it. Please include a thorough description of the problem 
with code and data examples if at all possible.

=head2 Reporting Bugs

Report bugs to the Bioperl bug tracking system to help us keep track
of the bugs and their resolution. Bug reports can be submitted via
the web:

  https://redmine.open-bio.org/projects/bioperl/

=head1 AUTHOR - Pedro M. Gomez-Fabre

Email pgf18872-at-gsk-dot-com

=cut


# Let the code begin...

package Bio::PopGen::TagHaplotype;
use strict;

use Data::Dumper;
use Storable qw(dclone);

use base qw(Bio::Root::Root);

my $USAGE = <<EOF
Usage:
    Bio::PopGen::TagHaplotype->new(-haplotype_block => \$hapblockref)

EOF
;

=head2 new

 Title   : new
 Function: constructor of the class.
 Returns : self hash
 Args    : input haplotype (array of array)
 Status  : public

=cut

#------------------------
sub new{
#------------------------
    my ($class, @args) = @_;

    my $self = $class->SUPER::new(@args);

    my ($haplotype_block) = $self->_rearrange([qw(HAPLOTYPE_BLOCK)],@args);

    if ($haplotype_block) {
        $self->haplotype_block($haplotype_block);
    }
    else{
        $self->throw("haplotype has not been supplied\n$USAGE");
    }

    # check that the haplotype block is well formed.
    for (my $i=0; $i<$#$haplotype_block+1; $i++){
	if ( $#{$haplotype_block->[0]} !=
             $#{$haplotype_block->[$i]} ){

            $self->throw("The haplotype matrix is not well formed (Not squared)");
        }
    }

    # make the calculation
    my $tag_list =  _scan_snp( $self ->haplotype_block );

    if ($tag_list){
        $self ->tag_list($tag_list);
    }
    else { 
        $self ->tag_list(undef);
    }

    if ( defined $self->tag_list){
        $self ->tag_length(scalar @{$self->tag_list});
    }
    else {
        $self ->tag_length(0);  #"NO TAGS FOUND!"
    }

    return $self;
}

=head2 haplotype_block

 Title   : haplotype_block
 Usage   : my $haplotype_block = $TagHaplotype->haplotype_block();
 Function: Get the haplotype block for a haplotype tagging selection
 Returns : reference of array
 Args    : reference of array with haplotype pattern


=cut

sub haplotype_block{
    my ($self) =shift;
    return $self->{'_haplotype_block'} = shift if @_;
    return $self->{'_haplotype_block'};
}


=head2 input_block 

 Title   : input_block 
 Usage   : $obj->input_block()
 Function: returns haplotype block. By now will produce the same output than
           $self->haplotype_block. but for compatiblity, this method is kept. 
           This method is deprecated.
 Returns : reference to array of array with the haplotype input value 
 Args    : none 
 Status  : public

=cut

#------------------------
sub input_block{
#------------------------
    my $self = shift;

    $self->warn(ref($self). "::input_block - deprecated method. Use haplotype_block() instead.");
    return $self->haplotype_block;
}

=head2 tag_list

 Title   : tag_list 
 Usage   : $obj->tag_list()
 Function: returns the list of SNPs combination that identify the
           haplotype. All combinations are displayed as arrays
 Returns : reference to array of array. 
 Args    : none
 Status  : public

=cut

#------------------------
sub tag_list{
#------------------------
    my ($self) = shift;
    return $self->{'_tag_list'}= shift if @_;
    return $self->{'_tag_list'};
}

=head2 tag_length 

 Title   : tag_length 
 Usage   : $obj->tag_length()
 Function: returns the length of the tag.
 Returns : scalar 
 Args    : none
 Status  : public

=cut

#------------------------
sub tag_length{
#------------------------
    my ($self) =shift;
    return $self ->{'_tag_length'} = shift if @_;
    return $self ->{'_tag_length'};
}

=head2 _scan_snp 

 Title   : _scan_snp 
 Usage   : internal
 Function: scan sets increasing the length until find a non degenerated
           pattern. 
 Returns : scalar
 Args    : none
 Status  : private

=cut

#------------------------
sub _scan_snp{
#------------------------
    my ($hap)=@_;

    my $hap_length = scalar @{$hap->[0]};    ## store the haplotype length

    for my $i(1..$hap_length){

        my $list = _gen_comb($hap_length, $i);

        my $snp_collection = _scan_combinations($hap, $list);

        # if there is any element on the collection.
        # We have reached our goal and 
        # we can stop the calculation.
        if($#$snp_collection>-1){
            return $snp_collection;
        }
    }
}

=head2 _gen_comb

 Title   : _gen_comb 
 Usage   : internal
 Function: we supply the length of the haplotype and the length of the
           word we need to find and the functions returns the possible
           list of combinations.
 Returns : scalar
 Args    : none
 Status  : private

=cut

#------------------------
sub _gen_comb{
#------------------------

    my ($hap_length,$n) = @_;

    my @array = ();    # list with all elements we have to combine

    
    for(0..$hap_length-1){ push @array, $_ };

    #
    # we need some parameters to create the combination list.
    # This parameters can be changed if we can modify the list values
    #

    my $m = -1;      # this parameter start the calculation at value
                     # m+1 on the recursive cicle.

    my $value = [];  ## seems to have not too much sense here, but is
                     ## needed on the recursion and need to be started
                     ## from here
    my $list = [];

    _generateCombinations ( \@array, \$m, \$n, $value, $list);

    return $list;

}

=head2 _generateCombinations 

 Title   : _generateCombinations 
 Usage   : internal
 Function: Recursive function that produce all combinations for a set

           i.e.:

           1, 2, 3, 4

           and word of B<3> will produce:

           1, 2, 3
           1, 2, 4
           1, 3, 4
           2, 3, 4

 Returns :
 Args    : none
 Status  : private

=cut

#------------------------
sub _generateCombinations{
#------------------------
    my ($rarr, $rm, $rn, $rvalue,$rlist)=@_;

    for (my $i = ($$rm+1); $i<scalar @$rarr; $i++){
        push (my @value2,@$rvalue,$rarr->[$i]);
        if (scalar @value2<$$rn){
            _generateCombinations($rarr,\$i, $rn, \@value2, $rlist);
        }
        if (scalar @value2==$$rn){
            push @$rlist, [@value2];
        }
        if(scalar @value2>$$rn){
            last;
        }
    }
}

# take the list of combinations
# i.e.: 1 2 3
#       1 2 4
#       1 3 4
#       2 3 4
#
# generate a sub array from the haplotype with the snp tag for the combination
# and check all haplotypes for these columns.
# if two haplotypes have the same value. we can not define the haplotype
# without ambiguity.
# Will return a list of valid combinations (SNP Tags)
#

=head2 _scan_combinations 

 Title   : _scan_combinations 
 Usage   : internal
 Function: take the haplotype and a list of possible combination
           for that length. Generate a subset and scan it to find if
           the information is enought to define the haplotype set.
 Returns :
 Args    : none
 Status  : private

=cut

#------------------------
sub _scan_combinations {
#------------------------

    my($hap,$list) = @_;

    my $valid_combination = undef;

    # we have to check every snp combinations from the list
    for my $i (0..$#$list){

        # extract from the big array the one we will use for tag calculations
        my $subArray = _get_subArray ($hap, $list->[$i]);

        my $degeneration = _deg_test($subArray);

        if(!$degeneration){
            push @$valid_combination, [@{$list->[$i]}];
        }
    }
    return $valid_combination;
}

# return 1 if two arrays are degenerated (same haplotype)
#------------------------
sub _deg_test{
#------------------------

    my ($hap)= @_;

    # for every sub array we compare each element with the rest
    for my $c1(0..$#$hap){
        for my $c2($c1+1..$#$hap){
            my $degeneration = compare_arrays($hap->[$c1], $hap->[$c2]);
            if ($degeneration){
                # if the two arrays are the same
                return 1;
            }
        }
    }
}

#------------------------
sub _get_subArray {
#------------------------
    my($hap, $combination) =@_;

    my $out = [];    # output array to be tested
 
    for my $i (0..$#$hap){
        foreach(@$combination){
            push @{$out->[$i]}, $hap->[$i][$_];
        }
    }
    return $out;
}

#
# take two arrays and compare their values
# Returns : 1 if the two values are the same
#           0 if the values are different
#

#------------------------
sub compare_arrays {
#------------------------
    my ($first, $second) = @_;
    return 0 unless @$first == @$second;
    for (my $i = 0; $i < @$first; $i++) {
        return 0 if $first->[$i] ne $second->[$i];
    }
    return 1;
}

1;