RE: union of times algorithm

> Okay, I've repaired it - it now works fine under warnings and strict.
> Almost all my code is written for strictures, I just posted my code
> in an intermediate form without having debugged it.  I think it still
> isn't working right, as the answer given is 6 but I reckon it should
> be 7!

Hi guys,

Can we have a comment on whether we are spamming the list too much
with this thread?  I do think it is a valuable discussion, but perhaps
not as valuable to the beginners.  I suppose there has been lots of
off-topic stuff without comments made.

I have just eliminated the Last Bug (tm), the algorithm that follows
is hand tested and should be tested further before deploying it.  It
has GOOD complexity analysis, although I'm too lazy to actually do it.

To squeeze performance, sort the arrays by 0th element only... and then
use a single bubble sort pass.  The 2nd element and the $active hash can
be exchanged for a more basic incrementing/decrementing counter of the
number of active elements.

Can someone look in their Knuth books, and tell me if I've just
reinvented the wheel - if not I'll write the research papers and make
the publications :)

Anyway, here goes:

#!/usr/bin/perl -w

use strict;

use constant START => 0;
use constant STOP  => 1;

use constant TIME  => 0;
use constant TYPE  => 1;
use constant ID    => 2;

# Test data
my @timeslices = (
    [2, 9],
    [4, 11]
);

sub encode {
    my @timeslices = @{ (shift) };
    my $index = shift || 0;
    my @encoded;

    # Encode the timeslices into a 3 element pair
    foreach my $item (@timeslices) {
        push @encoded,
            [$item->[START], START, $index  ],
            [$item->[STOP],  STOP,  $index++];
    }

    # Sort the three element pair, and return it as
    # an array reference
    return [ sort { $a->[TIME] <=> $b->[TIME]
                               ||
                    $a->[TYPE] <=> $b->[TYPE]
                  } @encoded
    ];
}

sub calculate {
    my @encoded = @{ (shift) };
    my ($previous, %active);
    my $total   = 0;

    foreach my $item (@encoded) {

        # Add if previous to current time was active
        unless (keys %active == 0 or not defined $previous) {
            $total += $item->[TIME] - $previous;
        }

        # START event, add to hash
        if ($item->[TYPE] == START) {
            $active{$item->[ID]}++;
        }

        # END event, remove from hash
        if ($item->[TYPE] == STOP) {
            delete $active{$item->[ID]};
        }

        $previous = $item->[TIME];
    }
    return $total;
}

# Display total covered
print "Total: " . calculate(encode(\@timeslices)) . "\n";

__END__

I believe this to be working fully, and quickly... please tell
me if there is any further problems.

Jonathan Paton

=====
$_=q|.,&@$$. ,.@$&@$. .&$$@. ,,$ ....!$_=$p.'&$@.',y'&$@' .,';for(/\S+/g){
!|.q| .$ .,@, ,$, .,.. @, ,$ ,,@ .,,.!++$.<22?${'y'.$_}=chr$.+64:[$$=${'y'
!|.q| ,@$@&.,. $$$&, ..@&&$,,, $., ..!.$_},$y.=($.=~/22\|26\|3(3\|7)/x?' '
!|.q|. @  ., ,.&,,, , .$..&. .,$  .,,!.$$:"\l$$")]};$y=~/ (.*)/;warn"$1\n"
!|.q|. $ .,. .,$$&&$...&., @.,.&@$@ .|,map{-$|--?$r:$p.=$_}split'!';eval$r

__________________________________________________
Do You Yahoo!?
Everything you'll ever need on one web page
from News and Sport to Email and Music Charts
http://uk.my.yahoo.com