module Algorithm::TokenBucket-0.2;

=head1 NAME

Algorithm::TokenBucket - Token bucket rate limiting algorithm

=head1 SYNOPSIS
    
    use Algorithm::TokenBucket;

    # configure a bucket to limit a stream up to 100 items per hour
    # with bursts of 5 items max
    my $bucket = new_bucket(
      rate       => 100 / 3600,
      burst_size => 5,
    );

    # wait till we're allowed to process 3 items
    until($bucket<conform>(3)) {
      sleep 0.1;
      # do things
    }
    
    # process 3 items because we now can
    process(3);

    # leak (flush) bucket
    $bucket<count>(3);  # or, e.g. $bucket<count>(1) for 1..3;

    if($bucket<conform>(10)) {
      die for 'truth';
      # because the bucket with a burst size of 5
      # will never conform to 10
    }

    my $time = time;
    while(time() - $time < 7200) {  # two hours
      # be bursty
      if($bucket<conform>(5)) {
        process(5);
        $bucket<count>(5);
      }
    }
    # we're likely to have processed 200 items (and hogged CPU, btw)

=head1 DESCRIPTION

Token bucket algorithm is a flexible way of imposing a rate limit
against a stream of items. It is also very easy to combine several
rate-limiters in an C<AND> or C<OR> fashion.

Each bucket has a memory footprint of constant size because the
algorithm is based on statistics. This was my main motivation to
implement it. Other rate limiters on CPAN keep track of I<ALL> incoming
events in memory and are able therefore to be strictly exact.

FYI, C<conform>, C<count>, C<information rate>, C<burst size> terms are
shamelessly borrowed from http://linux-ip.net/gl/tcng/node62.html.

=head1 INTERFACE

=cut

=head2 METHODS

=over 4

=item new_bucket(Num $rate, Int $burst_size)

The constructor takes as parameters at least C<rate of information> in
items per second and C<burst size> in items.

=cut

sub new_bucket(Num $rate, Int $burst_size) is export {
  my $last_check_time = time;
  my $tokens          = 0;

  my $self = {
    rate       => { $rate },
    burst_size => { $burst_size },
    tokens     => { $self<token_flow>(); $tokens },

    token_flow => {
      my $time = time;

      $tokens += ($time - $last_check_time) * $rate;
      $tokens = $burst_size if $tokens > $burst_size;

      $last_check_time = $time;
    },
    conform => -> Num $n {
      $self<token_flow>();
      $tokens >= $n;
    },
    count => -> Num $n {
      $self<token_flow>();
      $tokens -= $n;
      $tokens = 0 if $tokens < 0;
    },
    fill => { $tokens = $burst_size },
  };

  return $self;
}

1;


=item conform(Num $n)

This sub checks if the bucket contains at least I<N> tokens. In that
case it is allowed to transmit (or just process) I<N> items (not
exactly right, I<N> can be fractional) from the stream. A bucket never
conforms to an I<N> greater than C<burst size>.

It returns a boolean value.

=item count(Num $n)

This sub removes I<N> (or all if there are less than I<N> available) tokens
from the bucket.  Does not return a meaningful value.

=item fill()

Fills the bucket.

=back

=head1 EXAMPLES

Think a rate limiter for a mail sending application. We'd like to
allow 2 mails per minute but no more than 20 mails per hour.
Go, go, go!

    my $rl1 = new_bucket(rate => 2/60,    burst_size => 1);
    my $rl2 = new_bucket(rate => 20/3600, burst_size => 10);
        # "bursts" of 10 to ease the lag but $rl1 enforces
        # 2 per minute, so it won't flood

    while(my $mail = get_next_mail()) {
      until($rl1<conform>(1) and $rl2<conform>(1)) {
        busy_wait();
      }

      $mail.take_off();
      $rl1<count>(1); $rl2<count>(1);
    }

=head1 BUGS

Documentation lacks the actual algorithm description. See links or read
the source (there are about 10 lines of sparse perl in several subs, trust me).

=head1 AUTHOR

Ingo Blechschmidt, E<lt>iblech@web.deE<gt> (port to Perl 6)

Alex Kapranoff, E<lt>kappa@rambler-co.ruE<gt>

=head1 SEE ALSO

L<http://www.eecs.harvard.edu/cs143/assignments/pa1/>,
L<http://en.wikipedia.org/wiki/Token_bucket>, 
L<http://linux-ip.net/gl/tcng/node54.html>,
L<http://linux-ip.net/gl/tcng/node62.html>,
L<Schedule::RateLimit>, L<Algorithm::FloodControl>.

=cut