Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling


by Zaxo (Archbishop)
on Aug 29, 2002 at 09:29 UTC ( [id://193711] : sourcecode . print w/replies, xml ) Need Help??
Category: Miscellaneous
Author/Contact Info /msg Zaxo

This is an implementation of a FIFO with unique elements. It was suggested by BrowserUK's RFC and debugging tips, though it does not share all properties of his uFIFO class. In particular, it is not rewindable and uniqueness is only enforced for elements presently on the queue.

Further description is in the pod.

Update: Version 0.03 -- constructor new rewritten in terms of enqueue to allow easier subclassing. Override enqueue in the child class and new will initialize using the child's version.


package Uniqueue;
use vars qw($VERSION);
$VERSION = 0.03;

sub new {
    my $class = shift;
    my $self = bless { queue => [], hash =>{}}, $class;
    enqueue ( $self, @_ );

sub enqueue : locked {
    my $self = shift;
    my $count = 0;
    for (@_) {
        next if exists $self->{'hash'}{$_};
        push @{$self->{'queue'}}, $_;

sub next : locked {
    my $self = shift;
    my $val = shift @{$self->{'queue'}};
    defined $val and delete $self->{'hash'}{$val};

sub clear : locked {
    my $self = shift;
    $self->{'hash'} = {};
    my @vals = @{$self->{'queue'}};
    $self->{'queue'} = [];

sub peek {
    my $self = shift;
    return wantarray
      ? @{$self->{'queue'}}
        : $self->{'queue'}[0];

sub count {
    my $self = shift;
    scalar @{$self->{'queue'}};



=head1 NAME

Uniqueue - Perl extension providing a FIFO without duplication


  use Uniqueue;

  my $fifo = Uniqueue->new ( @foo );

  $fifo->enqueue( @bar )

  my @queued = $fifo->peek;
  my $look = $fifo->peek;

  my $next = $fifo->next;

  my @former = $fifo->clear;


Uniqueue is an object class which provides a FIFO without
duplication. Adding an element to the queue is prevented if
another like it is already present. 'Like it' means that
stringification produces identical results.

The class constructor is named 'new'. It optionally takes a list
of arguments which will be pushed onto the queue with duplicates
omitted. The leftmost example of duplicates establishes position
in the queue, whose head is to the left of the argument list.

Instances of Uniqueue have five methods available to them.


=item *
  enqueue LIST

  Adds the unique and unrepresented elements
  of LIST to the tail of the queue. Returns the number of
  elements added.

=item *

  Removes and returns one item from the head of the queue.

=item *

  Empties the queue, returning the entire queue as a list.

=item *

  Inspects the queue without modifying its state. 
  Returns the entire queue as a list in list context, or
  the head element in scalar context.

=item *

  Inspects the queue without modifying its state. 
  Returns the number of items in the queue.


The methods which modify state have the locked attribute, an
attempt to protect the state from corruption if shared by
threads. The author admits to the cargo-cult nature of this and
welcomes instruction.

Uniqueue should be subclassable simply by overriding enqueue, next, an
+d perhaps clear. Initialization in new is
handled by calling enqueue push constructor arguments onto 
the empty queue, so the default new will suffice for 
subclassed Uniqueues.

=head1 AUTHOR

Zaxo, /msg Zaxo on

Credits to RMGir for suggested cleanup.

=head1 SEE ALSO


Replies are listed 'Best First'.
Re: Uniqueue
by RMGir (Prior) on Aug 29, 2002 at 19:05 UTC
    I'm curious, why did you use delete instead of overwriting the hash ref? This:
    delete @{$self->{'hash'}}{ keys %{$self->{'hash'}} };
    must be less efficient than this:
    Are you worried about someone else having a reference to the same hash?

      Heh, even brand new code has cruft. That was a leftover which had been the last line, providing the list of values to return. I decided that was no good without keeping their order, but the delete line never got changed. Thanks!

      The line in question, #38 in the clear method, is replaced with RMGir's suggested one. That makes the hash values no longer significant, so assignments to them have been changed to a ++ bump. $VERSION incremented and RMGir credited.

      After Compline,