[LON-CAPA-cvs] cvs: loncom /types HashIterator.pm Queue.pm Stack.pm

[foxr]

foxr		Thu Apr 17 22:40:24 2003 EDT

  Added files:                 
    /loncom/types	HashIterator.pm Queue.pm Stack.pm 
  Log:
  Move these type implementing classes to the mainline cvs from the experimental
  sandbox.
  
  

Index: loncom/types/HashIterator.pm
+++ loncom/types/HashIterator.pm
#
#  Implement iteration over a opaque hash.
#

=pod

=head1 HashIterator

A hash iterator is an object that alows iteration over a hash in a
manner analagous to the way that STL iterators allow iteration over
those containers.  The HashIterator has the effect of hiding the
existence of the hash from the caller and instead presenting an
iteratable collection to the caller.

The intent is for a hash iterator to be an object returned by another
object or class to support iteration over some internal hash
maintained by the object. Passing the hash itself back breaks data
hiding and protection.

=head1 Typical usage:

    use HashIterator;
..

    $i = HashIterator::new(\%myhash);

..

    $i->begin();
    while(! $i->end()) {
	$itemref = $i->get();
	$i->next();
    }


=head1 Member Functions:

=cut

package HashIterator;

=pod

=head2 new(hash)

Create a new HashIterator object and return a reference to it.  Data
members of the HashIterator include:

=over 4

=item Hash

Reference to the hash being iterated over.

=item Keylist

The set of keys in the underlying hash (an anonymous array ref).

=item KeyCount

The number of keys in the underlying hash.

=item Index

Position of the iterator within the keylist/hash table.

=back

=cut

sub new {
    my $class   = shift;	# Class name...
    my $hashref = shift;        # Maintain this hash.
    my @keylist = keys(%$hashref);
    my $keyref= \@keylist;
    my $keycount = scalar @keylist;


    my $self    = {  Hash      => $hashref,
		     Keylist      => $keyref,
		     KeyCount     => $keycount,
		     Index        => 0};
    bless($self, $class);	# Type ourself...

    return $self;
		  
}

=pod

=head2 begin

Reset the iterator to the start of iteration.

=cut

sub begin {
    my $self  = shift;		# Get object...
    $self->{Index} = 0;
  
}

=pod

=head2 end

Return true if the iterator is off the end of the hash.

=cut

sub end {
    my $self = shift;		# Retrieve self as object.
    return ($self->{Index}  >= $self->{KeyCount});
}

=pod

=head2 get

Return the contents of the hash at the current key.  If the key is off
the end of the hash, undef is returned.  What is returned is a copy of
the element.  If the index is off the end of the iteration, undef is
returned.

=cut

sub get {
    my $self = shift;
    if ($self->end()) {
	return undef;
    }
    my $hashref = $self->{Hash};
    my $key     = $self->{Keylist}->[$self->{Index}];
    return $$hashref{$key};
}

=pod

=head2 next

Advances the iterator.

=cut

sub next {
    my $self = shift;		# Get us.
    $self->{Index}  = $self->{Index} + 1;
}

1;

Index: loncom/types/Queue.pm
+++ loncom/types/Queue.pm
#
#  Implement a simple queue in terms of a list.
#

=pod

=head1 Queue

An object oriented implementation of a queue data structure.  queues
are first in last out data structures.

=head1 Member functions:

=cut

package Queue;


=pod

=head2 new 

  Construct a new queue.

=cut

sub new {
    my $class = shift;		# Class name to bless into.
    my $self  = [];		# Our data is a reference to an anon. array.

    bless($self, $class);	# Type this as an object.

    return $self;
}

=pod

=head2 enqueue

   Add an element to the tail of the queue.

=cut

sub enqueue {
    my $self = shift;		# Get object reference.
    my $item = shift;		# Get the item to enqueue...
    push(@$self, $item);		# Push the item to the back of the array.


}

=pod

=head2 dequeue

   Remove an element from the front of the queue.

=cut

sub dequeue {
    my $self = shift;		# Get object reference....
    return shift @$self;		# Remove from the front of the queue.
}


1;

=pod

=head1 Theory

The queue is implemented as an array... enqueue is a thinly disguised
push, and dequeue is a thinly disguised shift.  This is probably quite
in efficient for large queues, but should be fine for reasonably sized
queues.

Note that since Perl is a dynamically typed language, queues can
contain objects of any data type and can even be heterogenously typed.

=cut

Index: loncom/types/Stack.pm
+++ loncom/types/Stack.pm
#
#   Implement a simple stack in terms of a list.
# 

=pod

=head1 Stack 

An object oriented implementation of a Stack data structure.
Stacks are first in last out data structures.

=head1 Member functions:

=cut

package Stack;

=pod

=head2 new  

    Creates a new instance of a stack. 
  
    my $stack = Stack->new();

=cut

sub new {
    my $class = shift;		# Class name.
    my $self  = [];		# Create an empty list to represent the stack.
    bless($self, $class);	# Turn this into an object and..
    return $self;		# Return it.
}

=pod

=head2 push

    takes an item and pushes it onto the back end of the stack.

    my $stack = Stack->new();
    $stack->push(something);

=cut

sub push {
    my $self = shift;		# Gets the list...
    my $item = shift;		# The item to push.
    push(@$self,$item);
}

=pod

=head2 pop

    Returns the item at the top of the stack: does a pop.

    my object = Stack->new();
    my $item = object->pop();

=cut

sub pop {
    my $self = shift;
    return pop(@$self);
}


1;

=pod

=head1 Internal implementation details

Stacks are implemented as lists.  Thus a stack is a thinly disguised
list with push and pop wrappers.  Since PERL is a dynamically typed
language, stacks can contain any data type ... including a
heterogenous collection of types.

=cut