# Figure 20.7: DoublyLinkedList.pm
# Implementation of a doubly linked list.

use warnings;
use strict;

package DoublyLinkedListNode;

# DoublyLinkedListNode constructor
sub new 
{
   my $type = shift();
   my $class = ref( $type ) || $type;
   my $self = { previousLink => $_[ 0 ],
                nextLink => $_[ 1 ],
                data => $_[ 2 ] };
                
   bless( $self, $class );
   return $self;
}

package DoublyLinkedList;

# DoublyLinkedList constructor
sub new 
{
   my $type = shift();
   my $class = ref( $type ) || $type;
   my $self = { };

   # head and tail dummy nodes
   $self->{ head } = new DoublyLinkedListNode(); 
   $self->{ head }{ nextLink } = 
      new DoublyLinkedListNode( $self->{ head } );
   $self->{ cursor } = $self->{ head }{ nextLink };

   bless( $self, $class );   
   return $self;
}

# inserts an element before the cursor and 
# sets the cursor to that element.
sub insertNode
{
   my ( $self, $data ) = @_;
   
   if ( !defined( $data ) ) { 
      return; 
   }
   
   my $newnode = new DoublyLinkedListNode( 
      $self->{ cursor }->{ previousLink }, 
      $self->{ cursor }, $data );

   $self->{ cursor }->{ previousLink }->{ nextLink } = $newnode;
   $self->{ cursor }->{ previousLink } = $newnode;
}

# deletes the current cursor element and returns the deleted
# node's data ( or undefined if no node is selected ).
sub deleteNode
{
   my ( $self ) = shift();
   
   if ( !defined( $self->{ cursor }->{ data } ) ) {
      print "You don't have an element selected\n";
      return undef;
   }
   
   $self->{ cursor }->{ previousLink }->{ nextLink } = 
      $self->{ cursor }->{ nextLink };
   $self->{ cursor }->{ nextLink }->{ previousLink } = 
      $self->{ cursor }->{ previousLink };

   my $deleted = $self->{ cursor }->{ data };
   $self->{ cursor } = $self->{ cursor }->{ nextLink };
   
   return $deleted;
}

# moves the cursor to the next node in the list
sub nextNode 
{
   my $self = shift();

   if ( defined( $self->{ cursor }->{ nextLink } ) &&
        defined( $self->{ cursor }{ nextLink }{ data } ) ) {
      $self->{ cursor } = $self->{ cursor }{ nextLink };
      return $self->{ cursor }{ data };
   }
   else {
      print( "Can not go to the next node.\n" );
      return undef;
   }
}

# moves the cursor to the previous node in the list
sub previousNode
{
   my $self = shift();

   unless( defined( $self->{ cursor }{ previousLink } ) && 
      defined( $self->{ cursor }{ previousLink }{ data } ) ) {

      print( "Can not go to the previous node.\n" );
      return;
   }

   $self->{ cursor } = $self->{ cursor }->{ previousLink };
   return $self->{ cursor }->{ data };
}

# moves the cursor to the head of the list
sub gotoHead 
{
   $_[ 0 ]->{ cursor } = $_[ 0 ]->{ head }{ nextLink };
   return $_[ 0 ]->{ cursor }->{ data };
}

# returns the data at the current cursor location
sub data 
{
   return $_[ 0 ]->{ cursor }->{ data };
}

# prints the list contents
sub printAll 
{
   my $self = shift();
   my $current = $self->{ head }{ nextLink };

   if ( !defined( $current->{ data } ) ) { 
      print( "The list is empty.\n\n" );
      return;
   }
   
   print( "HEAD <--> " );

   while ( defined( $current->{ data } ) ) {
      print( "$current->{ data } <--> " );
      $current = $current->{ nextLink };
   }

   print( "TAIL\n" );
}

return 1;

###########################################################################
#  (C) Copyright 2001 by Deitel & Associates, Inc. and Prentice Hall.     #
#  All Rights Reserved.                                                   #
#                                                                         #
#  DISCLAIMER: The authors and publisher of this book have used their     #
#  best efforts in preparing the book. These efforts include the          #
#  development, research, and testing of the theories and programs        #
#  to determine their effectiveness. The authors and publisher make       #
#  no warranty of any kind, expressed or implied, with regard to these    #
#  programs or to the documentation contained in these books. The authors #
#  and publisher shall not be liable in any event for incidental or       #
#  consequential damages in connection with, or arising out of, the       #
#  furnishing, performance, or use of these programs.                     #
###########################################################################