#
# Copyright (c) 2015 NetApp, Inc., All Rights Reserved.
#   Any other use, modification, or distribution is prohibited
#   without prior written consent from NetApp, Inc.
#

## @pod here
## @author dl-nacl-dev@netapp.com
## @summary Utility library for Xgen

=head1 NAME

NACL::Service::Xgen::Util

=head1 SYNOPSIS

 use NACL::Service::Xgen::Util qw(dumper
                                  randomize_array
                                  convert_percent_layout_to_count_layout
                                  get_next_layout_element
                                  positive_filter
                                  populate_distribution_layout
                                 );

=head1 EXPORTED FUNCTIONS

 dumper()
 convert_percent_layout_to_count_layout()
 populate_distribution_layout()
 get_next_layout_element
 positive_filter()
 randomize_array()

=head1 DESCRIPTION

C<NACL::Service::Xgen::Util> is a utility library with convenience routines
for developers of Xgen Configuration Modules that are derived from
L<C<NACL::Service::Xgen::Config>|lib-NACL-Service-Xgen-Config-pm>.

=cut

package NACL::Service::Xgen::Util;

BEGIN {
    require Exporter;
    our @ISA = qw(Exporter);
    our @EXPORT_OK = qw(dumper
                        convert_percent_layout_to_count_layout
                        get_next_layout_element
                        positive_filter
                        convert_percent_layout_to_distribution_layout
                        randomize_array);
}

use strict;
use warnings;
use POSIX;
use NATE::Log qw(log_global);
use Tie::IxHash;
use NATE::Util::DataTypes qw(TRUE FALSE);
use NATE::Exceptions::Argument qw(:try);

my $Log = log_global();
my $may_enter = $Log->may_enter();
my $may_exit  = $Log->may_exit();

=head1 FUNCTIONS

=head2 dumper

This is a helper method that uses Data::Dumper::Dumper to represent a datastructure.

=over

=item Synopsis

 use NACL::Service::Xgen::Util qw(dumper);
 use NATE::Log qw(log_global);

 log_global()->comment(dumper([1,2,3]));

=item Arguments

=over

=item C<< $scalar | @array | %hash | \@arrayref | \%hashref >>

(Required) The datastructure to generate a dumper string for.

=back

=item Return Value

The dumper formatted string of the datastructure.

=back

=cut

sub dumper {
    require Data::Dumper;
    my $dump = Data::Dumper::Dumper(@_);
    $dump =~ s/\n/\n./g;
    $dump = "." . $dump;
    return $dump;
}

=head2 randomize_array

This will randomize the given array reference in place.

=over

=item Synopsis

 use NACL::Service::Xgen::Util qw(randomize_array);

 my @arr = (1,2,3,4);

 # randomize @arr in place
 randomize_array(array => \@arr);

 # @arr should now be randomized

=item Arguments

=over

=item C<< array => \@arrayref >>

(Required) The array reference to randomize.

=back

=item Return Value

None

=back

=cut

sub randomize_array {
    my (%args) = @_;
    $Log->enter() if $may_enter;

    my $array = delete($args{array}) //
        NATE::Exceptions::Argument->throw("'array' is a required parameter");

    for (my $i = scalar(@{$array}) - 1; $i >= 0; $i--) {
        # generate a random index between [0, $i+1)
        my $j = int rand ($i + 1);

        # dont perform the swap if they are the same
        next if ($i == $j);

        # swap the element in $i with the element in $j
        # this will update the array reference in place.
        @$array[$i, $j] = @$array[$j, $i];
    }
    $Log->exit() if $may_exit;
}

=head2 convert_percent_layout_to_count_layout

Given total count and a layout hash reference, where the values of the
keys in the hash reference are whole number percentages, convert the
percentages to their respective total counts and return back a new layout
hash reference. All percentage values in the intial layout should add up
to 100.

=over

=item Synopsis

 use NACL::Service::Xgen::Util qw(convert_percent_layout_to_count_layout);

 my $percent_layout = {foo => 25, bar => 25, baz => 50};
 my $count_layout = convert_percent_to_count_layout(layout => $percent_layout,
                                                    total_objects => 10);

 # $count_layout will look like
 # {foo => 2, bar => 3, baz => 5 }

=item Arguments

=over

=item C<< layout => \%hashref >>

(Required) The hash reference layout of percentage values.

=item C<< total_objects => $scalar >>

(Required) The total amount of objects to consider when converting percentages
to whole integers.

=back

=item Return Value

This will return a new layout hash with the percentages converted to integers.

=back

=cut

sub convert_percent_layout_to_count_layout {
    my (%args) = @_;

    # The layout of percent.
    # { attribute_value => percent,
    #   attribute_value => percent,}
    my $percent_layout = $args{layout} // NATE::Exceptions::Argument->throw("layout is a required parameter.");
    if (ref($percent_layout) ne 'HASH') {
        NATE::Exceptions::Argument->throw("'layout' must be a hash reference");
    }

    my $total_objects = $args{total_objects} // NATE::Exceptions::Argument->throw("total_objects is a required parameter.");
    my $used_count = 0;
    my $total_percent = 0;
    my %count_layout = %{$percent_layout};
    foreach my $key (keys %count_layout) {
        $count_layout{$key} = floor($count_layout{$key}*.01*$total_objects);
        $used_count += $count_layout{$key};
        $total_percent += $percent_layout->{$key};
    }

    NATE::Exceptions::Argument->throw("'layout' percents must add up to 100") if ($total_percent != 100);

    my $unused_count = $total_objects - $used_count;
    # Loop through and ensure that all total_objects are used.
    while($unused_count) {
        foreach my $key (keys %count_layout) {
            if ($count_layout{$key} == 0) {
                if($percent_layout->{$key} > 0) {
                    $count_layout{$key}++;
                    $unused_count--;
                    # If there are no more unused then end.
                    last unless $unused_count;
                } else {
                    next;
                }
            }
            elsif (($total_objects / $count_layout{$key}) < $percent_layout->{$key}) {
                $count_layout{$key}++;
                $unused_count--;
                # If there are no more unused then end.
                last unless $unused_count;
            } # else go to the next key.
        }
        # If there are no more unused then end.
        last unless $unused_count;
    }

    return \%count_layout;
}

=head2 get_next_layout_element

Given a layout hash reference, return back the next element
in the layout to use. This method will round robin across the
keys in the layout to ensure a proper balance is chosen. It will
produce the same pattern only if the initial layout hash was built
in the exact same way. Every time this method is invoked against a
layout hash reference, the hash reference will be modified in place.

=over

=item Synopsis

 use NACL::Service::Xgen::Util qw(get_next_layout_element);

 my $layout = {foo => 10, bar => 4, baz => 6};

 for (my $i = 0; $i < 20; $i++) {
     # 10 out of the 20 times that this method is called, $next_key will be "foo"
     # 4  out of the 20 times that this method is called, $next_key will be "bar"
     # 6  out of the 20 times that this method is called, $next_key will be "baz"
     my $next_key = get_next_layout_element(layout => $layout, iterator => $i);
     if (defined $next_key) {
         # do something with the key
     }
 }

=item Arguments

=over

=item C<< layout => \%hashref >>

(Required) The hash reference layout to choose a key from. The value of each key
should correspond to the maximum number of times each key can be selected by this method.

=item C<< iterator => $scalar >>

(Optional) This iterator field will be used to control the 'pattern' that the selecting
algorithm will use when choosing keys from the layout. By default, the iterator will be a
the current epoch time.

Default: CORE::time()

=back

=item Return Value

This will return one of the keys in the C<layout> provided.

=back

=cut

sub get_next_layout_element {
    my (%args) = @_;

    my $itr    = delete($args{iterator}) // time;
    my $layout = delete($args{layout})   // NATE::Exceptions::Argument->throw("layout is required");

    while (keys %{$layout}) {
        my @arr = %{$layout};
        my $i = $itr % scalar(keys %{$layout});

        # round $i up to the nearest even number
        while ($i % 2 == 1) {
            $i++;
        }

        # test the key at element $i
        my $key = $arr[$i];
        if ($layout->{$key} > 0) {
            # use this element
            $layout->{$key}--;
            return $key;
        } else {
            # this element is exhausted, delete the key from the layout provided
            delete ($layout->{$key});
            next;
        }
    }
}

=head2 positive_filter

This filter a list of resources based on matching all filters into matches and not mathches.
Filters are regex matches.

=over

=item Synopsis

 use NACL::Service::Xgen::Util qw(positive_filter);

 my @resources = ();

 for (my $i = 0; $i < 5; $i++) {
    my $resource = NACL::Service::Xgen::Resource->new(name => "res$i");
    unless ($i % 2) {
        $resource->set_private_attributes(foo => 'bar');
    }
    if ($i % 2) {
        $resource->set_private_attributes(foo => 'barino');
    }
    if ($i < 2) {
        $resource->set_private_attributes(efficiency => 1);
    }
    if ($i > 2) {
        $resource->set_private_attributes(efficiency => 3);
    }
    push(@resources,  $resource);
 }

 my $filter1 = NACL::Service::Xgen::Util::positive_filter(resources => \@resources,
                                                         filter => {foo => 'bar'});

 my $filter2 = NACL::Service::Xgen::Util::positive_filter(resources => \@resources,
                                                         filter => {foo => qr/^bar$/});

 my $filter3 = NACL::Service::Xgen::Util::positive_filter(resources => \@resources,
                                                         filter => {efficiency => 1});

 my $filter4 = NACL::Service::Xgen::Util::positive_filter(resources => \@resources,
                                                         filter => {efficiency => undef});

 my $filter5 = NACL::Service::Xgen::Util::positive_filter(resources => \@resources,
                                                         filter => {efficiency => 1,
                                                                    foo => qr/^bar$/});

=item Arguments

=over

=item C<< resources => \@array_of_resources >>

(Required) The array reference to an array of resources to filter.

=item C<< filter => \%filter >>

(Required) The hash reference to a hash of filters of the format
{key => match_value}
match_value can be a string, regex, undef.
string will be a simple regex match  $attribute_value =~ $string.
regex will be a complete regex match $attribute_value =~ $regex.
undef will mean that the $attribute_value is undef.

=back

=item Return Value

A matches hash of the format
{matches    => /@array_of_matches,
not_matches => /@array_of_not_matches}

=back

=cut

sub positive_filter {
    my (%args) = @_;

    # The array of resources to loop over.
    my $resources = $args{resources} // NATE::Exceptions::Argument->throw("resources is a required parameter.");
    if (ref($resources) ne 'ARRAY') {
        NATE::Exceptions::Argument->throw("'resources' must be an array reference");
    }

    # The attributes and details about the attributes to loop over.
    # { attribute_name => { attribute_name => value_filter,
    #                       attribute_name => value_filter,
    #                     }
    my $filter = $args{filter} // NATE::Exceptions::Argument->throw("filter is a required parameter.");
    if (ref($filter) ne 'HASH') {
        NATE::Exceptions::Argument->throw("'filter' must be a hash reference");
    }

    # Array of matches.
    my @matches = ();
    # Array of resources that do not match.
    my @not_matches = ();

    foreach my $resource (@{$resources}) {
        my $match = TRUE;
        foreach my $key (keys %{$filter}) {
            my $value = $filter->{$key};
            my $next = FALSE;
            # the value from the resource correspond to the $key
            my $attribute_value;

            # Try to get the attribute value
            try {
                $attribute_value = $resource->get_attribute($key);
                # If the attribute value is defined but the filter key is
                # undef then this is not a match.
                $match = FALSE if (not defined $filter->{$key});
            } otherwise {
                # If here then we could not find the attribute value.
                # If the filter->key is defined then no match
                if (defined $filter->{$key}) {
                    $match = FALSE;
                } else { # Elsif filter->key is not defined then match
                    $next = TRUE;
                }
            };

            last unless ($match);
            next if ($next);

            # if any of the fields we need to match are not
            # a match, this resource won't be returned

            if (ref($attribute_value) =~ /ARRAY/i) {
                my $found = FALSE;
                foreach my $temp_value (@$attribute_value) {
                    if ($temp_value =~ $value) {
                        $found = TRUE;
                        last;
                    }
                }
                if (not $found) {
                    $match = FALSE;
                    last;
                }
            } elsif ($attribute_value !~ $value) {
                $match = FALSE;
                last;
            }
        }    # end foreach filter key
        if ($match) {
            push (@matches, $resource);
        } else {
            push (@not_matches, $resource);
        }
    } # end foreach resource

    return {matches => \@matches, not_matches => \@not_matches};
}

=head2 populate_distribution_layout

Given a "tied" percent layout hash reference that represents tiers, a "tied" distribution layout
hash reference, and a total item count, this method will populate the distribution
layout with a normal distribution of items that sum up to the total item count. It will use the
percent layout hash as a guide on how to distribute the total item count through the tiers. It is
important to use Tie::IxHash to tie the hashes before passing them into this method,
otherwise the results will not be deterministic/repeatable.

=over

=item Synopsis

 use NACL::Service::Xgen::Util qw(populate_distribution_layout);

 # Initialize the layout hashes and tie them using Tie::IxHash
 use Tie::IxHash;
 my $percent_layout = {};
 tie($percent_layout, "Tie::IxHash");
 my $distribution_layout = {};
 tie($distribution_layout, "Tie::IxHash");

 # Define the tiers and their respective percent distributions.
 # These should add up to 100%
 $percent_layout->{tier1} = 25;
 $percent_layout->{tier2} = 35;
 $percent_layout->{tier3} = 15;
 $percent_layout->{tier4} = 15;
 $percent_layout->{tier5} = 10;

 # Initialize the distribution layout
 $distribution_layout->{item1} = 0;
 $distribution_layout->{item2} = 0;
 $distribution_layout->{item3} = 0;
 $distribution_layout->{item4} = 0;
 $distribution_layout->{item5} = 0;
 $distribution_layout->{item6} = 0;

 # populate the distribution layout with a total of 50 items
 # using the percent layout tiers.
 populate_distribution_layout(percent_layout => $percent_layout,
                              distribution_layout => $distribution_layout,
                              total_items => 50);

 use Data::Dumper;
 print Dumper($distribution_layout);

 # This will display the following. Notice how all the items sum up to 50 and a
 # normal distribution has been applied using the percentages of each tier to
 # skew the distribution toward the tier1 and tier2 side (item1, item2, and item3).
 #
 # $VAR1 = {
 #           'item1' => 7,
 #           'item2' => 6,
 #           'item3' => 18,
 #           'item4' => 7,
 #           'item5' => 2,
 #           'item6' => 3
 #         };

 # you can then use the 'get_next_layout_element' method to iterate through the distribution layout

=item Arguments

=over

=item C<< percent_layout => \%hashref >>

(Required) The hash reference layout that defines tiers and percentages. For best
results, it is recommended that this be a "tied" hash.

=item C<< distribution_layout => \%hashref >>

(Required) The hash reference layout that defines the items and how they map to
each tier. For best results, it is recommended that this be a "tied" hash, and that
all values of each key be initialized to 0.

=item C<< total_items => $scalar >>

(Required) This defines how many total items should be distributed into the distribution
layout hash.

=back

=item Return Value

This method does not return anything. Instead, it will modify the C<distribution_layout>
hash reference in place. It will also modify the C<percent_layout> hash reference by replacing the
percentages with their respective item counts.

=back

=cut

sub populate_distribution_layout {
    my (%args) = @_;

    my $distribution_layout = $args{distribution_layout} // NATE::Exceptions::Argument->throw("Missing required parameter 'distribution_layout'");
    my $percent_layout      = $args{percent_layout}      // NATE::Exceptions::Argument->throw("Missing required parameter 'percent_layout'");
    my $total_items         = $args{total_items}         // NATE::Exceptions::Argument->throw("Missing required parameter 'total_items'");

    my $remainder = 0.0;
    my $max_value;
    my $max_key;

    foreach my $key (keys %{$percent_layout}) {
        $remainder += (($percent_layout->{$key} * $total_items) % 100) / 100;

        my $value = floor(($percent_layout->{$key} * $total_items) / 100);
        if (!$value) {
            $value = 1;
            $remainder--;
        }

        if (!$max_value or $value > $max_value) {
            $max_key = $key;
            $max_value = $value;
        }

        $percent_layout->{$key} = $value;
    }

    # if negative remainder, trim from the highest
    if ($remainder < 0) {
        $percent_layout->{$max_key} += $remainder;
    }

    $remainder = ceil($remainder);

    OUTER: while ($remainder > 0) {
        last if (!scalar keys %{$percent_layout});
        foreach my $key (keys %{$percent_layout}) {
            $percent_layout->{$key}++;
            $remainder--;
            last OUTER if $remainder <= 0;
        }
    }

    my @values = ();
    # they are the same size, overlay the two layouts on top of each other
    if (scalar(keys %{$distribution_layout}) eq scalar(keys %{$percent_layout})) {
        @values = values %{$percent_layout};
        foreach my $key (keys %{$distribution_layout}) {
            $distribution_layout->{$key} = shift @values;
        }
    } elsif (scalar(keys %{$distribution_layout}) < scalar(keys %{$percent_layout})) {
        # number of categories in the percent layout is greater than the distribution layout

        # work from the outside->in on the distribution layout
        my @layout_keys = keys %{$percent_layout};
        my @result_keys = keys %{$distribution_layout};
        my $last_left_r;
        my $last_right_r;
        my $i = 0;
        while (@layout_keys) {
            my $left  = shift @layout_keys;
            my $right = pop @layout_keys;

            my $left_r  = shift @result_keys;
            my $right_r = pop @result_keys;

            if (!defined($left_r)) {
                # there are no more results left, we need to use the last left_r
                # we saved from the previous loop
                $distribution_layout->{$last_left_r} += $percent_layout->{$left};
                if (defined($right)) {
                    # if we have a right side layout entry, add that in to the left
                    # on odd iterations and add it to the right on even iterations
                    if (defined $last_right_r and $i % 2) {
                        $distribution_layout->{$last_right_r} += $percent_layout->{$right};
                    } else {
                        $distribution_layout->{$last_left_r} += $percent_layout->{$right};
                    }
                }
            } elsif (!defined($right_r)) {
                # we have a left r but not a right r,
                $distribution_layout->{$left_r} += $percent_layout->{$left};
                if (defined($right)) {
                    # if we have a right side layout entry, add that in to the left
                    $distribution_layout->{$left_r} += $percent_layout->{$right};
                }
                $last_left_r = $left_r;
            } else {
                # we have both a left r and a right r, we must have a left and right
                $distribution_layout->{$left_r}  += $percent_layout->{$left};
                $distribution_layout->{$right_r} += $percent_layout->{$right};
                $last_left_r = $left_r;
                $last_right_r = $right_r
            }
            $i++;
        }
    } else {
        # number of categories in the percent layout is less than the distribution layout

        # work from the outside of the result hash
        my @layout_keys = keys %{$percent_layout};
        my @result_keys = keys %{$distribution_layout};
        my $max_num_members_per_layout = ceil(scalar(@result_keys)/scalar(@layout_keys));

        my $last_left_r;
        my $last_right_r;
        while (@layout_keys) {
            my $left  = shift @layout_keys;
            my $right = pop @layout_keys;

            my @left_r;
            my @right_r;
            for (my $i = 0; $i < $max_num_members_per_layout; $i++) {
                if (scalar(@result_keys)) {
                    push(@left_r, shift @result_keys);
                }
                if (scalar(@result_keys)) {
                    push(@right_r, pop @result_keys);
                }
            }
            # take the value of $percent_layout $left and evenly distribute it into all the result members of @left_r
            my $value = $percent_layout->{$left};
            my $remainder = 0.0;
            if (scalar(@left_r)) {
                $remainder += $value % scalar(@left_r);
                $value =  floor($value / scalar(@left_r));
                foreach my $lmember (@left_r) {
                    $distribution_layout->{$lmember} += $value;
                }
                while ($remainder > 0) {
                    foreach my $lmember (@left_r) {
                        $distribution_layout->{$lmember} += 1;
                        $remainder--;
                        last if ($remainder <= 0);
                    }
                }
                # store the last left r
                $last_left_r = $left_r[-1];
            }

            # if right is defined:
            # take the value of $percent_layout $right and evenly distribute it into all the result members of @right_r
            if (defined($right)) {
                my $value = $percent_layout->{$right};
                my $remainder = 0.0;

                # if there is no right r array, then use the left one
                if (scalar(@right_r)) {
                    $remainder += $value % scalar(@right_r);
                    $value =  floor($value / scalar(@right_r));
                    foreach my $lmember (@right_r) {
                        $distribution_layout->{$lmember} += $value;
                    }
                    while ($remainder > 0) {
                        foreach my $lmember (@right_r) {
                            $distribution_layout->{$lmember} += 1;
                            $remainder--;
                            last if ($remainder <= 0);
                        }
                    }
                    # store the last right r
                    $last_right_r = $right_r[-1];
                } else {
                    # dont have any more right r's to add to.
                    # once solution could be to take this value and smash it into
                    # the last left r.
                    $distribution_layout->{$last_left_r} += $value;
                }
            }
        }

    }
}

1;

__END__

=head1 AUTHOR/MAINTAINER

=over

=item NACL Development (dl-nacl-dev@netapp.com)

=back

=cut