http://qs1969.pair.com?node_id=193711
Category: Miscellaneous
Author/Contact Info /msg Zaxo
Description:

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, @_ );
    $self;
}

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

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

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

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

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

1;

__END__


=head1 NAME

Uniqueue - Perl extension providing a FIFO without duplication

=head1 SYNOPSIS

  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;

=head1 DESCRIPTION

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.

=over

=item *
  enqueue LIST

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

=item *
  next

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

=item *
  clear

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

=item *
  peek

  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 *
  count

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

=back

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 Perlmonks.org

Credits to RMGir for suggested cleanup.

=head1 SEE ALSO

L<perl>.

=cut
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:
    $self->{hash}={};
    Are you worried about someone else having a reference to the same hash?
    --
    Mike

      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,
      Zaxo