#!/usr/bin/env perl
BEGIN {
    foreach (((getpwuid($<))[7], $ENV{HOME}, $ENV{LOGDIR}, ".")) {
        require "$_/.eagleeye.pm" if (-f "$_/.eagleeye.pm");
    }
}

use Class::DBI::AutoLoader (
    dsn       => 'dbi:SQLite:dbname=ikariam.sqlite',
    options   => { RaiseError => 1 },
    tables    => ['cities', 'island', 'user'],
    use_base  => 'Class::DBI::SQLite',
    namespace => 'Ikariam',
);

package Ikariam::Extractor;
use strict;
use Data::Dumper;
use XML::LibXML;
use IO::Uncompress::Gunzip qw(gunzip $GunzipError) ;
use Carp;
use utf8;

sub new {
    Carp::croak("Options should be key/value pairs, not hash reference") if ref($_[1]) eq 'HASH'; 

    my($class, %conf) = @_;

    my $self = bless {
        doc => undef,
        gzip => 1,
    }, $class;

    $self->{gzip} = $conf{'gzip'} if(defined($conf{'gzip'}));
    $self->parse($conf{'content'}) if(defined($conf{'content'}));

    return $self;
}

# parse($Content);
sub parse {
    my ($self, $content) = @_;
    my $string;
    my $parser = XML::LibXML->new('1.0','utf-8');

    if($self->{gzip} == 1) {
        gunzip \$content => \$string
            or die "gunzip failed: $GunzipError\n";
    } else {
        $string = $content;
    }

    $self->{doc} = $parser->parse_html_string ($string, { suppress_errors => 1 });
    return;
}

# find($XPathQuery);
sub find {
    my $self = shift;
    my $query = shift;
    my $out = [];

    my $result = $self->{doc}->find($query);

    return undef unless defined($result);

    if ( $result->isa( 'XML::LibXML::NodeList' ) ) {
        return undef if($result->size() == 0);
        foreach ( @$result ) {
            # $_ is XML::LibXML::Element, XML::LibXML::Node
            my $literal = $_->to_literal() , "\n";
            utf8::encode($literal);
            # warn $_->toString(1) , "\n";
            return $literal unless wantarray;
            push( @$out, $literal);
        }
    } else {
        Carp::croak("Unsupported data type"); 
    }
    # TODO
    # XML::LibXML::Literal
    # XML::LibXML::Boolean

    return @$out;
}

1;

package Ikariam;
use strict;
use Data::Dumper;
use LWP;
# use LWP::Debug qw(+ -conns -trace -debug);
# use LWP::Debug qw(+trace);
use HTTP::Cookies;
use WWW::Mechanize;
use HTML::TagParser;
use XML::LibXML qw(:encoding);
use IO::Uncompress::Gunzip qw(gunzip $GunzipError) ;
use utf8;

sub new
{
    my ($class, $server, $user, $pass) = @_;

    my $self =
    {
        mech => WWW::Mechanize->new(
            agent => "Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.0.3) Gecko/2008092816 Iceweasel/3.0.1 (Debian-3.0.1-1)",
            timeout => 10,
        ),
        server => $server,
        user => $user,
        pass => $pass,
        buildingIDs => {
            townHall =>  0,
            townhall =>  0,
            port =>  3,
            academy =>  4,
            shipyard =>  5,
            barracks =>  6,
            warehouse =>  7,
            wall =>  8,
            tavern =>  9,
            museum =>  10,
            palace =>  11,
            embassy =>  12,
            branchOffice =>  13,
            workshop =>  15,
            'workshop-army' =>  15,
            'workshop-fleet' =>  15,
            safehouse =>  16,
            palaceColony =>  17,
            resource =>  1,
            tradegood =>  2
        }
    };


    $self->{mech}->cookie_jar(HTTP::Cookies->new(file => "/tmp/ikariam-cookies.txt", autosave => 1));
    $self->{mech}->default_headers->push_header('Accept-Encoding', 'deflate');
 
    return bless $self, $class;
}

sub viewScore
{
    my $self = shift;
    my $type = shift || 'score';
    my $user = shift || '';
    my $offset = shift || 0;

    my $res = $self->{mech}->post(sprintf("http://%s/index.php", $self->{server}), [
        highscoreType => $type,
        offset => $offset,
        searchUser => $user,
        view => 'highscore'
        ]);

    my $c;
    my $status = gunzip \$res->content => \$c 
        or die "gunzip failed: $GunzipError\n";

    my %users;
    my $html = HTML::TagParser->new($c);
    my ($table) = $html->getElementsByAttribute("class", "table01");
    return %users if(!defined($table));

    my @elems = getElementsByTagName($table, "tr");

    foreach my $elem (@elems) {
        my $e;
        my %user;

        $e = getElementsByAttribute($elem, "class", "action");
        $e = getElementsByTagName($e, "a");

        if(defined ($e) && $e->getAttribute('href') =~ /index\.php\?view=sendMessage&with=(\d+)&oldView=highscore/)
        {
            $user{'id'} = $1;

            $e = getElementsByAttribute($elem, "class", "name");
            $user{'name'} = $e->innerText();

            $e = getElementsByAttribute($elem, "class", "allytag");
            $user{'ally'} = $e->innerText();

            $e = getElementsByTagName($e, "a");
            if($e->getAttribute('href') =~ /\?view=allyPage&allyId=(\d+)/)
            {
                $user{'allyId'} = $1;
            }

            $e = getElementsByAttribute($elem, "class", "score");
            $user{$type} = $e->innerText();
            $user{$type} =~ s/,//g;

            $users{$user{'id'}} = \%user;
        } else {
            next;
        }
    }

    return \%users;
}

sub viewWorldMap
{
    my $self = shift;
    my $x = shift;
    my $y = shift;

    if(!defined($x) && !defined($y))
    {
        die('location required');
    }

    my $res = $self->{mech}->post(sprintf("http://%s/index.php?view=worldmap_iso", $self->{server}), [
            xajax => 'getMapData',
            'xajaxargs[]' => $x,
            'xajaxargs[]' => $y,
            xajaxr => time,
            ]);

    my $c;
    my $status = gunzip \$res->content => \$c 
        or die "gunzip failed: $GunzipError\n";

    my @islands;
    # parsing xjxobj
    while($c =~ /<cmd n="jc" t="addToMap"><xjxobj><e><k>0<\/k><v><!\[CDATA\[(\d+)\]\]><\/v><\/e><e><k>1<\/k><v><!\[CDATA\[(\d+)\]\]><\/v><\/e><e><k>2<\/k><v><!\[CDATA\[(\d+)\]\]><\/v><\/e><e><k>3<\/k><v><!\[CDATA\[(\d+)\]\]><\/v><\/e><e><k>4<\/k><v><!\[CDATA\[(\d+)\]\]><\/v><\/e><e><k>5<\/k><v><!\[CDATA\[(\w+)\]\]><\/v><\/e><e><k>6<\/k><v><!\[CDATA\[(\d+)\]\]><\/v><\/e><e><k>7<\/k><v><!\[CDATA\[(\d+)\]\]><\/v><\/e><\/xjxobj><\/cmd>/g)
    {
        my %island;
        $island{id} = $3;
        $island{x} = $1;
        $island{y} = $2;
        $island{name} = $6;
        $island{tradegood} = $4;
        $island{wonder} = $5;
        # $7 ?
        $island{people} = $8;
        push @islands, \%island;
    }
    return @islands;
}

sub viewHomeMap
{
    my $self = shift;

    my $res = $self->{mech}->get(sprintf("http://%s/index.php?view=worldmap_iso", $self->{server}));

    my $c;
    my $status = gunzip \$res->content => \$c 
        or die "gunzip failed: $GunzipError\n";

    # m[50][36]=new Array(564,1,5,'Risietia', '5', 13);
    # x = 43-57 = 6
    # y = 27-41 = 6
    my @islands;
    while($c =~ /m\[(\d+)\]\[(\d+)\]=new Array\((\d+),(\d+),(\d+),'(\w+)', '(\d+)', (\d+)\);/g)
    {
        my %island;
        $island{id} = $3;
        $island{x} = $1;
        $island{y} = $2;
        $island{name} = $6;
        $island{tradegood} = $4;
        $island{wonder} = $5;
        # $7 ?
        $island{people} = $8;

        #foreach my $i (sort(keys(%island)))
        #{
        #    printf ("%s %s\n", $i, $island{$i});
        #}
        #print("\n");
        push @islands, \%island;
    }
    return @islands;
}

sub viewIsland
{
    my $self = shift;
    my $island = shift;

    my $res = $self->{mech}->get(sprintf("http://%s/index.php?view=island&id=%s", $self->{server}, $island));

    my $c;
    my $status = gunzip \$res->content => \$c 
        or die "gunzip failed: $GunzipError\n";

    my $html = HTML::TagParser->new($c);

    # find inactivity and vacation
    my %status;
    foreach my $class (qw/inactivity vacation/)
    {
        my @elems = $html->getElementsByAttribute("class", $class);
        foreach my $elem (@elems) {
            if($elem->innerText() =~ /^(.*?) \((\w)\)/) {
                $status{$1} = $2;
                # printf("%s\n", $elem->innerText());
            }
        }
    }

    # find content
    my @elems = $html->getElementsByClassName( "cityinfo" );
    my @cities;
    foreach my $elem (@elems) {
        my %info;

        my @e = getElementsByTagName($elem, "li");
        $info{'cityname'} = substr($e[0]->innerText(), 8);
        $info{'citylevel'} = substr($e[1]->innerText(), 14);
        $info{'owner'} = substr($e[2]->innerText(), 8);
        $info{'ally'} = substr($e[3]->innerText(), 8);
        delete($info{'ally'}) if($info{'ally'} eq '-');

        @e = getElementsByAttribute($elem, "class", "messageSend");
        if ( $e[0]->getAttribute("href") =~ /with=(\d+)&destinationCityId=(\d+)/)
        {
            $info{'user'} = $1;
            $info{'cityId'} = $2;
        }

        # update status;
        if(defined($status{$info{'cityname'}})) {
            $info{'status'} = $status{$info{'cityname'}};
        } else {
            $info{'status'} = undef;
        }
        # print(Dumper(\%info));
        push @cities, \%info;
    }

    return @cities;
}

sub increaseTransporter {
    my $self = shift;
    my $param = shift;
    my $cityId = shift;

    # TODO: 應該扣除買船之黃金, 以免誤計
    # TODO: 加上所有之船隻
    # my @cargoCost = qw/160 244 396 812 1240 1272 1832 1888 3848 3972 5204 5384 6868 7120 8864 9200 11268 11712 14108 14680 23320 24288 28664 29880 34956 36468 42348 44212 51024 53308 61236 64024 73096 76468 87020 91088 103224 116524 122072 137432 180060 202132 211964 237444 249108 278276 292076 306623 321963 338138 355198 373191 392171 412195 433320 455612 479135 503962 530166 557828 587031 617863 650420 684802 721113 759466 799981 842783 888005 935790 986286 1039654 1096062 1155689 1218724 1285369 1355837 1430353 1509159 1592508 1680670 1773932 1872597 1976989 2087448 2204338 2328045 2458976 2597567 2744276 2899594 3064040 3238163 3422550 3617820 3824635 4043693 4275738 4521561 4782000 5057946 5350345 5660202 5988585 6336630 6705540 7096598 7511164 7950683 8416694 8910828 9434823 9990523 10579889 11205006 11868090 12571498 13317734 14109462 14949514/;
    # $city->{transporters}->{sum}
 
    # TODO: 找買船最便宜之城市
    my @locations = @{$self->{'cities'}->{$cityId}->{locations}};
    foreach (1..2) {
        if($locations[$_] eq 'port') {
            my $res = $self->{mech}->get(sprintf('http://%s/index.php?action=CityScreen&function=increaseTransporter&id=%s&position=%s', 
                    $self->{server}, $cityId, $_));
        }
    }
}

sub build {
    my $self = shift;
    my $type = shift;
    my $cityId = shift;

    die ("we don't know about this city") unless(defined($self->{'cities'}->{$cityId}));

    my $position = -1;
    my @locations = @{$self->{'cities'}->{$cityId}->{locations}};
    foreach (0..$#locations) {
        $position = $_ if($locations[$_] eq $type);
    }

    if($position == -1)
    {
        foreach (0..$#locations) {
            next if($_ <= 2 && ($self->{buildingIDs}->{$type} ne "workshop-fleet" &&
                    $self->{buildingIDs}->{$type} ne "shipyard"));
            if($locations[$_] eq undef) {
                my $res = $self->{mech}->get(sprintf('http://%s/index.php?action=CityScreen&function=build&id=%s&position=%s&building=%d', 
                        $self->{server}, $cityId, $_, $self->{buildingIDs}->{$type} ));
                last;
            }
        }
    } else {
        $self->{mech}->add_header( Referer =>  
            sprintf("http://%s/index.php?view=%s&id=%s&position=%d", $self->{server}, $type, $cityId, $position));
        my $res = $self->{mech}->post(sprintf('http://%s/index.php', $self->{server}), [
            action => 'CityScreen',
            'function' => 'upgradeBuilding',
            id => $cityId,
            position => $position,
            level => $self->{'cities'}->{$cityId}->{buildings}->{$type},
            oldView => $type,
            ]);
#        my $content;
#        gunzip \$res->content => \$content 
#            or die "gunzip failed: $GunzipError\n";
#        print ($content);
    }
}

sub run {
    my $self = shift;
    # defense.
    die("Not implemented");
}

sub research
{
    my $self = shift;
    my $type = shift;
    my $cityId = shift;

    # check if we are researching the same stuff
    my $res =  $self->{mech}->get(sprintf('http://%s/index.php?action=CityScreen&function=changeResearch&id=%s&researchType=%s', $self->{server}, $cityId, $type));

#    my $content;
#    gunzip \$res->content => \$content 
#        or die "gunzip failed: $GunzipError\n";
#
#    print ($content);
}

sub checkResearch {
    my $self = shift;
    my $cityId = shift;

    my $res = $self->{mech}->get(sprintf('http://%s/index.php?view=researchOverview&id=%s', $self->{server}, $cityId));
    
    my @urls = Ikariam::Extractor->new(content => $res->content)->find('//ul[@class="explored"]//a/@href');
    my $out = {};
    foreach(@urls) {
        if(/view=researchDetail&id=\d+&position=\d+&researchId=(\d+)$/) {
            # we ignore the chinese name of technology researched.
            @$out{$1} = 1;
        }
    }
    return $out;
}

sub checkCity {
    my $self = shift;
    my $cityId = shift;

    # search for goods
    my $res = $self->{mech}->get(sprintf("http://%s/index.php?view=city&id=%d", $self->{server}, $cityId));
    my $extractor = new Ikariam::Extractor(content => $res->content);

    $self->{'cities'}->{$cityId}->{resources}->{gold} = $extractor->find('//span[@id="value_gold"]/text()');
    $self->{'cities'}->{$cityId}->{resources}->{gold} =~ s/,//g;

    $self->{'cities'}->{$cityId}->{name} = $extractor->find('//span[@class="city"]/text()');

    $self->{'cities'}->{$cityId}->{construction} = defined($extractor->find('//*[@class="constructionSite"]')) ? 1 : 0;

    # maxCapacity
    my $page = $extractor->{doc}->toString(1);
    if($page =~ /maxCapacity : {\s+wood: (\d+),\s+wine: (\d+),\s+marble: (\d+),\s+crystal: (\d+),\s+sulfur: (\d+)\s+}/s) {
        $self->{'cities'}->{$cityId}->{maxCapacity}->{wood} = $1;
        $self->{'cities'}->{$cityId}->{maxCapacity}->{wine} = $2;
        $self->{'cities'}->{$cityId}->{maxCapacity}->{marble} = $3;
        $self->{'cities'}->{$cityId}->{maxCapacity}->{crystal} = $4;
        $self->{'cities'}->{$cityId}->{maxCapacity}->{sulfur} = $5;
    }

    foreach my $good (qw/wood wine marble crystal sulfur/) {
        $self->{'cities'}->{$cityId}->{resources}->{$good} = $extractor->find(sprintf('//span[@id="value_%s"]', $good));
        $self->{'cities'}->{$cityId}->{resources}->{$good} =~ s/,//g;
    }

    foreach my $i (0..14) {
        my @buildings = $extractor->find(sprintf('//*[@id="position%s"]/@class', $i));
        foreach my $building (@buildings) {
            if (!($building =~ /buildingGround/) && !($building =~ /townhall/)) {
                $self->{'cities'}->{$cityId}->{locations}[$i] = $building;

                my $span;
                if($building eq 'townHall') {
                    # this is stupid, the new vession give two cityTown information.
                    $span = ($extractor->find(sprintf('//*[@id="position%s"]//span[@class="textLabel"]/text()', $i)))[1];
                } else {
                    $span = $extractor->find(sprintf('//*[@id="position%s"]//span[@class="textLabel"]/text()', $i));
                }
                my (undef, undef, $level) = split(/ /, $span);
                $self->{'cities'}->{$cityId}->{buildings}->{$building} = $level;
            }
        }
    }

    $self->{'cities'}->{$cityId}->{transporters}->{avail} = $extractor->find('//span[@id="value_transAvail"]/text()');
    $self->{'cities'}->{$cityId}->{transporters}->{sum} = $extractor->find('//span[@id="value_transSum"]/text()');
    $self->{'cities'}->{$cityId}->{transporters}->{sum} =~ s/[\(|\)]//g;
    $self->{'cities'}->{$cityId}->{maxActionPoints} = $extractor->find('//span[@id="value_maxActionPoints"]');;
}


sub checkMilitaryAdvisorMilitaryMovements  {
    my $self = shift;
    # TODO
    # http://s2.ikariam.tw/index.php?view=militaryAdvisorMilitaryMovements
    my $res = $self->{mech}->get(sprintf('http://%s/index.php?view=militaryAdvisorMilitaryMovements', $self->{server}));
}

sub checkMilitaryAdvisorCombatReports {
    my $self = shift;
    my $content;
    my $res = $self->{mech}->get(sprintf('http://%s/index.php?view=militaryAdvisorCombatReports', $self->{server}));
    gunzip \$res->content => \$content 
        or die "gunzip failed: $GunzipError\n";

    # TODO
    # military
    $self->{'military'}->{wars}->{attacks} = 0;
    $self->{'military'}->{wars}->{wars} = 0;
    # $self->{'cities'}->{$cityId}->{wars}->{attacks} = $1 if($content =~ /敵人攻擊: (\d+)/);
    # $self->{'cities'}->{$cityId}->{wars}->{wars} = $1 if($content =~ /我方軍隊行程: (\d+)/);

    # list down reports.
    # /index.php?view=militaryAdvisorReportView&amp;combatId=1887662
    # //form[@id='finishedReports']//a
}

sub checkTownHall {
    my $self = shift;
    my $cityId = shift;

    my $res = $self->{mech}->get(sprintf('http://%s/index.php?view=townHall&id=%d', $self->{server}, $cityId));
    my $extractor = new Ikariam::Extractor(content => $res->content);

    # //div[@id='SatisfactionOverview']//div[@class='value']
    # //div[@id='SatisfactionOverview']//div[@class='text']
    $self->{"cities"}->{$cityId}->{happiness} = $extractor->find('//div[@id="SatisfactionOverview"]//div[@class="value"]');

    # 取 SatisfactionOverview 中的其他值
    # 一個城鎮的市民滿意度結合了多方面的因素
    # check happiness
    # Happiness = Basic bonuses (196 + Capital Bonus + Holiday Bonus(25)) + 
    #             Wine (Tavern Base(12*level) + 
    #             Tavern Bonus(80*step)) + 
    #             Culture (Museum Base(20*level) + 
    #             Cultural Goods Bonus(50*Cultural Goods)) - 
    #             Population (population) - 
    #             Corruption (Corruption rate * population)
    #
    # Growth Rate = Happiness * 0.02

    # Space, 房屋數
    $self->{'cities'}->{$cityId}->{"space"} = {};
    $self->{'cities'}->{$cityId}->{"space"}->{'total'} = $extractor->find('//span[@class="value total"]/text()');
    $self->{'cities'}->{$cityId}->{"space"}->{'occupied'} = $extractor->find('//span[@class="value occupied"]/text()');

    my @values = $extractor->find('//div[@id="CityOverview"]//span[@class="value"]');
    $self->{'cities'}->{$cityId}->{"growth"} = $values[0];
    $self->{'cities'}->{$cityId}->{"incomegold"} = $values[1];

    $self->{'cities'}->{$cityId}->{corruption} = $extractor->find('//li[@class="corruption"]//span[@title="目前腐敗程度"]');
    $self->{'cities'}->{$cityId}->{corruption} =~ s/%//g;

    my @citizens_type = qw/citizens woodworkers specialworkers scientists/;
    @values = $extractor->find('//div[@id="PopulationGraph"]//span[@class="count"]');
    foreach my $i (0..$#citizens_type)
    {
        $self->{'cities'}->{$cityId}->{'citizens'}->{$citizens_type[$i]} = $values[$i];
        $self->{'cities'}->{$cityId}->{'citizens'}->{total} += $values[$i];
    }
}


sub checkArmies
{
    my $self = shift;
    my $cityId = shift;
    my %force_types;

    $force_types{'army'} = [ qw/undef undef Slinger Swordsman Phalanx Ram Archer Catapult Gunsman Mortar SteamGiant Gyrocopter Bombardier Doctor Cook/ ];
    $force_types{'fleet'} = [ qw/undef undef Ram-Ship BallistaShip Flamethrower CatapultShip MortarShip PaddleWheelRam DivingBoat/ ];

    foreach my $x (qw/army fleet/) {
        $self->{'cities'}->{$cityId}->{$x} = {};
        my $res = $self->{mech}->get(sprintf('http://%s/index.php?view=cityMilitary-%s&id=%d', $self->{server}, $x, $cityId));
        my @numbers = Ikariam::Extractor->new(content => $res->content)->find('//table//tr/td');
        foreach my $j (0..$#{$force_types{$x}}) {
            if ($numbers[$j] == '-') {
                $self->{'cities'}->{$cityId}->{$x}->{$force_types{$x}[$j]} = 0;
            } else {
                $self->{'cities'}->{$cityId}->{$x}->{$force_types{$x}[$j]} = $numbers[$j];
            }
        }
    }
}

sub check
{
    my $self = shift;

    # MilitaryAdvisor
    $self->checkMilitaryAdvisorMilitaryMovements();
    $self->checkMilitaryAdvisorCombatReports();

    # looking for cities
    foreach my $cityId (keys(%{$self->{'cities'}})) 
    {
        $self->checkCity($cityId);
        $self->checkTownHall($cityId);
        $self->checkArmies($cityId);
        $self->{'cities'}->{$cityId}->{'research'} = $self->checkResearch($cityId);
    }
    print Dumper($self->{'cities'});
    return $self->{'cities'};
}

sub logout
{
    my $self = shift;
    $self->{mech}->get(sprintf('http://%s/index.php?action=loginAvatar&function=logout', $self->{server}));
}

sub login
{
    my $self = shift;

    my $res = $self->{mech}->post(sprintf("http://%s/index.php?action=loginAvatar&function=login", $self->{server}), [
        name => $self->{user},
        password => $self->{pass},
        ]);

    my $c;
    my $status = gunzip \$res->content => \$c 
        or die "gunzip failed: $GunzipError\n";

    if($c =~ /錯誤！/)
    {
        die ("password error\n");
    } else {
        my $result = XML::LibXML->new('1.0','utf-8')
                                 ->parse_html_string ($c, { suppress_errors => 1 })
                                 ->find( '//option[@class="avatarCities coords"]' );

        if ( $result->isa( 'XML::LibXML::NodeList' ) ) {
            foreach ( @$result ) {
                $self->{'cities'}->{$_->getAttribute('value')} = {};
            }
        }
    }
}

sub getElementsByTagName {
    my $element = shift;
    my $tagname = lc(shift);
    my ( $flat, $cur ) = @$element;

    my $out = [];
    for( ; $cur <= $#$flat ; $cur++ ) {
        last if ($flat->[ $cur + 1 ]->[001] eq $element->tagName() );
        next if ($flat->[$cur]->[001] ne $tagname );
        next if $flat->[$cur]->[000]; # close

        my $elem = HTML::TagParser::Element->new( $flat, $cur );
        return $elem unless wantarray;
        push( @$out, $elem );
    }
    return unless wantarray;
    @$out;
}

sub getElementsByAttribute {
    my $element = shift;
    my $key  = lc(shift);
    my $val  = shift;
    my ( $flat, $cur ) = @$element;

    my $out  = [];
    for ( ; $cur <= $#$flat ; $cur++ ) {
        next if $flat->[$cur]->[000];    # close
        my $elem = HTML::TagParser::Element->new( $flat, $cur );
        my $attr = $elem->attributes();
        next unless exists $attr->{$key};
        next if ( $attr->{$key} ne $val );
        return $elem unless wantarray;
        push( @$out, $elem );
    }
    return unless wantarray;
    @$out;
}

1;