## 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 !*

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

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.