RE: union of times algorithm

        What we have is as stated a union of times. So all I do is take the
timeslices and generate a hash element for each time. I don't check to see
if it is already there, but just set to one. Then I sort the hash down
numerically and total where current minus previous equal 1.  Here is a shot:

use Data::Dumper;

my @timeslices = (
    [4, 9],
    [3, 6],
    [2, 4],
    [11,12],
    [14,14],
    [17,19]
);

my %MyHashCounts = ();

for(my $MyId=0;$MyId<=$#timeslices;$MyId++){
   for($MyId1=$timeslices[$MyId][0];$MyId1<=$timeslices[$MyId][1];$MyId1++)
{
      $MyHashCounts{$MyId1}=1;
    }
 }
print Dumper(\@timeslices);
print Dumper(\%MyHashCounts);

my $MyPrev = -10;
my $MyTotal = 0;
foreach my $MyKeys (sort {$a <=> $b} keys %MyHashCounts) {
   printf "%3d ", $MyKeys;
   $MyTotal++ if ( ($MyKeys - $MyPrev) == 1 );
   $MyPrev = $MyKeys; 
 }
printf "\n";
printf "Total: %4d\n", $MyTotal;

Output:
  2   3   4   5   6   7   8   9  11  12  14  17  18  19
Total:   10

Wags ;)

-----Original Message-----
From: Jonathan E. Paton [mailto:jonathanpaton@xxxxxxxxx]
Sent: Friday, May 31, 2002 01:08
To: beginners@xxxxxxxx
Subject: RE: union of times algorithm


> > I'm trying to come up with an algorithm that seems like it ought to be
> > really easy, but it's turning out to be pretty tough...
> > 
> > Basically I have three pairs of start/stop times, e.g.:
> > 
> >    3, 5
> >    4, 10
> >   15, 20
> > 
> > I want the total time covered by all these ranges.  I can't just say
(5-3
> +
> > 10-4 + 20-15) because the 3,5 and 4,10 ranges overlap.  The desired
answer
> > for this case is 13, 3 to 10 and 15 to 20.  I have the start times in
two
> > arrays, @starts and @stops.
|
| [Insert Jonathan's code and footnotes here]
|
>       I tried your code and it would not work as taken from the email.  I
> used -w and got a large number of entries.  Cleaned a few things up, but
> within @encoded element 0 was always undefined(used Data::Dumper.  So I
> changed 
>      push @encoded, [$item[0], START, $counter]; 
>    to
>      push @encoded, [$item->[0], START, $counter];
> 
>       This cleared up the data.  I am still getting a warning on $current
> only used once.
> 
>       Thought I would stop at that point.
> 
>       Also did not like END, so make START/END as STARTA/ENDA so Perl
> wouldn't complain about END being a keyword.
> 
> Wags ;)

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!

It is still not ideal, as it still has a runtime dependent on the
number of timeslices in use.  This is bad, as it will crawl with
lots - we need a better datastructure (AVL tree?)

I feel this would be useful as a CPAN module, does this already exist?
I envision two objects, as follows:

TimeTable - Manages a tabletable.  Able to answer basic queries like
total time used over a period, time union (as per this question),
active timeslices during a period and at a point in time.

TimeSlice - Stores a start time, stop time, and a set of attributes...
e.g. name and owner.

---

Before I add it to my TODO list (anyone is welcome to take it out of
my TODO list, and take it as their own), we should check it doesn't
already exist on CPAN.  Has anyone checked?

Jonathan Paton

__PERL__

#!/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 = (
    [4, 9],
    [3, 6],
    [2, 4]
);

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->[0], START, $index];
        push @encoded, [$item->[1], STOP,  $index++];
    }

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

sub calculate {
    my @encoded = @{ (shift) };
    my $total    = 0; # Total time used already
    my $previous = 0; # Previous time encountered
    my %active;       # Active timeslots

    foreach my $item (@encoded) {

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

        # END event, remove from hash
        else {
            delete $active{$item->[2]};
        }

        # Add to totals if hash has elements
        if (keys %active != 0) {
            $total += $item->[TIME] - $previous;
        }

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

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

__END__

=====
$_=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

-- 
To unsubscribe, e-mail: beginners-unsubscribe@xxxxxxxx
For additional commands, e-mail: beginners-help@xxxxxxxx