Basic Data Structure Experiments with Object::Pad (for The Weekly Challenge #129)

Basic Data Structure Experiments with `Object::Pad`
for The Weekly Challenge #129

If you want to challenge yourself on programming, especially on Perl and/or Raku, go to https://theweeklychallenge.org, code the latest challenges, submit codes on-time (by GitHub or email).

Do tell me, if I am wrong or you strongly oppose my statements!

It's time for challenges in Week #129 !

image info

The four core elements of object-oriented programming are said to be "encapsulation" , "inheritance" , "polymorphism" and "abstraction". Let us see how abstraction is performed via the actively developping Object::Pad module ‐ making a tree (node) class and a linked list class through Object::Pad, for tackling The Weekly Challenge tasks this week. (The version number of Object::Pad here is 0.52.)

Apology: CY hasn't learnt inner classes in OO.

Task 1: Root Distance

The tree node class is essentially about 30 lines:

class TreeNode {
    has $parent :reader :writer :param :Isa(TreeNode) = undef;
    has $list_of_children :reader :writer :param = [];
    has $is_root :reader :param = 0;

    method set_children {
        my $c = $_[0];
        $c->set_parent($self);
        push $list_of_children->@*, $c;
    }

    method root_distance {
        my $p = $self;
        my $d = 0;
        while (!$p->is_root) {
            $p = $p->parent;
            $d++;
        }
        return $d;
    }

    BUILD {
        if (defined($parent)) {
            $parent->set_children($self);
        }
        else {
            $is_root = 1;
        }
    }
}

(By CY's understanding:) The BUILD blocks act like the initializer blocks in Java.

The use of ":reader" or ":writer" can be learnt from the official document. The setter(:writer) are method set_abc and getter(:reader) are method abc.

Come to see how it is being used:

# Example 1

my $n1 = TreeNode->new();
my $n2 = TreeNode->new(parent => $n1);
my $n3 = TreeNode->new(parent => $n1);

my $n4 = TreeNode->new(parent => $n3);
my $n5 = TreeNode->new(parent => $n4);
my $n6 = TreeNode->new(parent => $n4);

ok $n6->root_distance() == 3, "Example 1 - Node 6";
ok $n5->root_distance() == 3, "Example 1 - Node 5";
ok $n2->root_distance() == 1, "Example 1 - Node 2";
ok $n4->root_distance() == 2, "Example 1 - Node 4";

__END__

Tree:
        1
       / \
      2   3
           \
            4
           / \
          5   6

Task 2: Add Linked Lists

ref to 
root
node
 |
 v
+-+-+   +-+-+   +-+-+   +-+-+
|.|.+-> |.|.+-> |.|.+-> |.|.+-> undef
+++-+   +++-+   +++-+   +++-+ 
 |       |       |       | 
 v       v       v       v
 2       3       5       7

diagram info

Read the hint of task description first:

... expecting a class representing linked list. It should have methods to create a linked list given list of single digit positive numbers (I) and a method to add new member. (II) Also have a method that takes 2 linked list objects and returns a new linked list. (III) Finally a method to print the linked list object in a user friendly format. (IV)

So we have to implement at least four methods.

Begin to code! Two classes are defined. The first is LLNode, the second is LinkedList. The implementation of LinkedList chosen is a singly linked list without a known end element.

LLNode:

class LLNode {
    has $next :reader :writer :param :Isa(LLNode) = undef;
    has $val :reader :writer :param = undef;

    method a_copy {
        return LLNode->new(val=>$self->val);
    }
}

LinkedList:

class LinkedList {

    has $head_node :reader :writer :param :Isa(LLNode) = undef;

    method create_list {
        my @digit = @_;
        #skip details
    }

    method append_element {
        # an O(N) operation, seldom used
        my $dgt = $_[0];
        my $p = $head_node;
        while (defined($p->next)) {
            $p = $p->next;
        }
        $p->set_next( LLNode->new(val=>$dgt) );
    }

    method a_reverse_linked_list {
        my $rvrs = LinkedList->new();
        my @stack;
        #details below
        return $rvrs;
    }

    method a_reverse_linked_list_with_carriers {
        my $rvrs = LinkedList->new();
        my @stack;
        #skip details
        return $rvrs;
    }

    method directly_add_another_linked_list {
        my $sum = LinkedList->new();
        my $another = $_[0];
        my $s = $self->head_node;
        my $a = $another->head_node;
        $sum->set_head_node(LLNode->new( val => $s->val + $a->val ));
        my $p = $sum->head_node;
        while (defined($s->next) && defined($a->next)) {
            $s = $s->next;
            $a = $a->next;
            $p->set_next( LLNode->new( val => $s->val + $a->val ) );
            $p = $p->next;
        }
        while (defined($s->next)) {
            $s = $s->next;
            $p->set_next( LLNode->new( val => $s->val ) );
            $p = $p->next;
        }
        while (defined($a->next)) {
            $a = $a->next;
            $p->set_next( LLNode->new( val => $a->val ) );
            $p = $p->next;
        }
        return $sum;
    }

    method wk129_add_another_linked_list {
        #details below
    }

    method print {
        #trivial, skip details
    }

}

As you can see, the requirement (I) is the responsibility of method create_list, the requirement (II) is the that of method append_element, (III) ‐ method wk129_add_another_linked_list, and (IV) ‐ method print (yeah, it has the same name as the built-in print but such naming is legal).

For this task, our "main dish" is (III), so let us see its operations step by step.

In terms of source codes:

method wk129_add_another_linked_list {
    return   $self->a_reverse_linked_list
          ->directly_add_another_linked_list(
              $_[0]->a_reverse_linked_list
            )
          ->a_reverse_linked_list_with_carriers;
}

In words:

make a "reversed version" of the linked list instance;
make a "reversed version" of the other linked list in the argument;
directly add the two linked lists up;
make a "reversed version" of the prior linked list while keep taking care of the "carriers" defined in the task.

Now, we are going to use the two linked lists in Example 2 to illustrate:

my $ex2_L1 = LinkedList->new();
my $ex2_L2 = LinkedList->new();

$ex2_L1->create_list(1,2,3,4,5);
$ex2_L2->create_list(6,5,5);

print " L1: "; $ex2_L1->print;
print " L2: "; $ex2_L2->print;
print "rL1: "; $ex2_L1->a_reverse_linked_list->print;
print "rL2: "; $ex2_L2->a_reverse_linked_list->print;

print "\"directly adding\" rL2 to rL1:\n    ";
$ex2_L1->a_reverse_linked_list->directly_add_another_linked_list($ex2_L2->a_reverse_linked_list)->print;
print "\nfinal\nsum: ";
$ex2_L1->wk129_add_another_linked_list($ex2_L2)->print;

Output:

 L1: 1->2->3->4->5
 L2: 6->5->5
rL1: 5->4->3->2->1
rL2: 5->5->6
"directly adding" rL2 to rL1:
    10->9->9->2->1

final
sum: 1->3->0->0->0

Discussion: the implementation of the reverse of the linked list

Since we don't have a reference to the tail of the linked list, for producing the reverse of the linked list (method a_reverse_linked_list), I choose to use a stack: make a copy (method a_copy) of the LLNode instance which has the same value but hasn't linked to any other LLNode instances, push the newly-baked object into @stack; after all linked list elements are copied, I popped out the elements from @stack so the original tail element can exactly be the head node of the new linked list, and the remaining elements are ordered as we want.

The stack demands extra memory space, but it helps us more convenient to code.

method a_reverse_linked_list {
    my $rvrs = LinkedList->new();
    my @stack;
    my $p = $head_node;
    push @stack, $p->a_copy;
    $p = $p->next;
    while (defined($p)) {
        push @stack, $p->a_copy;
        $p = $p->next;
    }

    my $t = pop @stack;
    $rvrs->set_head_node( $t );
    while (scalar @stack > 0) {
        $t->set_next($stack[-1]);
        $t = pop @stack;
    }
    return $rvrs;
}

The method a_reverse_linked_list_with_carriers goes with a similar logic; just we have to take care of the carriers, the process of the bringing the carriers to the "next" elements can be done during the stack operation.

method a_reverse_linked_list_with_carriers {
    ...
    my @stack;
    my $p = $head_node;
    my $carrier = 0;
    while (defined($p)) {
        my $temp_val = $p->val+$carrier;
        if ($temp_val >= 10) {
            $temp_val -= 10;
            $carrier = 1;
        }
        else {
            $carrier = 0;
        }
        push @stack, LLNode->new(val=>$temp_val);
        $p = $p->next;
    }
    ...
}

Wear your mask, stay alert and healthy! □

The image, as a friend of mine may recognize, is modified from the current header photo of my Twitter account. The photo was taken on 18th November, 2020, on the Eagle Nest Nature Trail in Hong Kong. Modified via GIMP.

The diagram of singly linked list is inspired by diagrams in COMMON LISP: A Gentle Introduction to Symbolic Computation by David S. Touretzky.

Except from images and codes from other personnels, the content of this blogpost is released under a copyleft spirit. One may share (full or partial) content of this blogpost on other platform if you share it under the free and open content spirit.

link for CY's full codes: ch-1.pl, ch-2.pl

Contact on twitter: @e7_87.

Discuss via GitHub issues: here.

Email: fungcheokyin at gmail.com

Created Date: 8th September, 2021. Fix typo 12th Sep.

The Weekly Challenge ‐ Perl and Raku