package Stack;
use strict;

##########################################################
# Public interface to class "Stack":
##########################################################

# CONSTRUCTORS
sub new($);	    # basic constructor: $s = Stack->new();
sub copy($);	    # copy constructor:  $s2 = $s1->copy();

# DESTRUCTOR is unneeded: Perl does its own GC for the simple stuff

# INSTANCE METHODS
sub push($@);	    # add to end:        $s->push(3);
sub pop($);         # shorten, return:   $old_top = $s->pop();
sub peek($);	    # look at end:       $cur_top = $s->peek();
sub size($);        # how many items:    $count = $s->size();
sub is_empty($);    # whether size is 0  if ($s1->is_empty()) 

# OVERLOADED OPERATORS 
sub is_equal($$$);    # overload for ==   if ($s1 == $s2) 
sub stringify($);     # overload for ""   print $s;
 
##########################################################
# Private implementation to class "Stack":
##########################################################

####################################################################
#   We'll use for our stack nothing but a simple array reference.  #
#   We could have a {DATA} field, but because no other state	   #
#   is needed that what Perl provides with its own arrays,         #
#   we won't bother.						   #
####################################################################

use Carp;

sub new($) {
    my $class = shift;			
    my $new_stack  = [];		# allocate empty array
    bless($new_stack, $class);		# make it an object
    return $new_stack;
} 

sub copy($) {
    my $self  = shift;
    my $clone = $self->new();
    @$clone = @$self;
    return $clone;
} 

sub push($@) {
    my $self = shift;
    push(@$self, @_);
} 

sub pop($) {
    my $self = shift;
    confess("Stack empty!") unless @$self > 0;
    return pop(@$self);
}

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

sub is_empty($) {
    my $self = shift;
    return scalar(@$self) == 0;
} 

sub peek($) {
    my $self = shift;
    confess("Stack empty!") unless @$self > 0;
    return $self->[-1];		# last element
} 

use overload ('==' => \&is_equal);
sub is_equal($$$) {
    my ($s1, $s2) = @_;

    if ($s1->size() != $s2->size()) {
	return 0;
    } 

    for (my $i = 0; $i < $s1->size(); $i++) {
	if ($s1->[$i] != $s2->[$i]) {
	    return 0;
	} 
    } 

    return 1;
} 

use overload ( '""'  => \&stringify );
sub stringify($) {
    my $self = shift;
    return '[' . join(",", @$self) . "]";
}

1;