SCOUG-Programming Mailing List Archives

Date:	Tue, 19 Apr 2005 07:44:38 PDT7
From:	"Lynn H. Maxson" <lmaxson@pacbell.net >
Reply-To:	scoug-programming@scoug.com
To:	"SCOUG Programming SIG" <scoug-programming@scoug.com >
Subject:	SCOUG-Programming: Progress--Step 4--List Processing

Content Type: text/plain

We need to develop the underpinnings of list processing. To
do that we will use PL/I which does not have a list as a native
construct, but one which you can construct. We start initially
at a low level, establish it, and then build the higher levels.

To begin with any list entity has an anchor point through
which access to a list occurs. A list itself consists of zero,
one, or more entries. Each list entry consists of two parts, a
locator part and a data part. Thus each list entry is a
structure (aggregate), e.g. "dcl 1 list_entry, 2 locator, 3
ptr1,..., 2 data, 3 data1,...;".

A basic list is either one of two types, a single-linked list and
a double-linked list. The same occurs for a list's anchor point,
a single-linked or double-linked anchor. For completion we
mention single-linked and other than illustrate them cease to
have any further use of them.

Let us declare the list anchor. "dcl 1 list_name, 2 first_entry
ptr;" (single-linked) or "dcl 1 list_name, 2 (first_entry,
last_entry) ptr;" (double-linked). This is a somewhat wordy
template that we will shorten as follows: (single linked) "dcl 1
list, 2 first ptr;" and (double linked) "dcl 1 list, 2 (first, last)
ptr;".

Normally when we first declare a list (in this instance its
anchor) we have an "empty" list (no entries). Thus we
initialize the pointers to NULL: "dcl 1 list1, 2 (first, last) ptr
init(null);". As you can see we no longer have an interest in
single-linked anchors.

To create an entry in a list we need to allocate it. In PL/I we
use a based variable. To keep it simple we will use a fixed
length character entry: dcl 1 entry1 based (p1), 2 (prev, next)
ptr, 2 data1 char (20);". This is a double-linked list (prev,
next) instead of a single-linked (next only) one.

To create this entry we use as 'allocate' statement: 'allocate
entry1;'. This allocates space for entry1 as well as set the
starting address of that space in p1 (as specified in the entry
declaration.

To complete processing the first entry we have to set its
address in the anchor:
list1.first, list1.next = p1;

And we have to set the entry's previous and next pointers to
NULL:
entry1.prev, entry1.next = null;

That completes the addressability of this list.

Now how do we know this is the first entry on the list?
Because the anchor's first and last pointers are "null".

If they aren't null, then the list has one or more entries. While
we have no difficulty in determining the processing of the first
list entry, we do have a decision to make regarding additional
entries. We can decide to place them at the "front" of the list
(LIFO--Last In First Out), at the "end" of the list (FIFO--First
In First Out), or in some prescribed order based on a value or
values in the entries themselves (an Ordered list). These
three choices represent the three types of queues: LIFO, FIFO,
and Ordered.

They only differ in the pointer resolution when adding the
second or greater entry in the list and when deleting any
entry. That means that you have one process for adding the
first entry, three "fixed" processes for making additions based
on queue type, and three "fixed" processes for deletions
based on queue type. That makes a total of seven logical
routines. Maybe we should add one to "exchange" or "swap"
positions in the list. For a single-linked list we would need a
similar number of routines.

Each list entry we have discussed thus far consists of a
"sequence" of two parts, a locator part and a data or body
part: . In a double-linked list the locator has
two pointers, one to the previous entry (null if first entry on
list) and one to the next entry (null if last entry on list):
. For the body we can have either an
element or aggregate (array, structure) entry.

Greg, has entered back into this with a deja vu on the
difference between and engineer and programmer. Once more
I need to point out that in open source they are not two
different people, but the same. Otherwise the engineer would
have to rely on some (other) programmer to offer him what
he wants either on an accidental or fee basis. In either case
make himself "dependent" on some other resource. I point out
once again that an "intent" of open source allowed bypassing
of such dependence.

On the other hand we have no reason not to have a FIFOadd,
LIFOadd, and ORDEREDadd;a FIFOdelete, LIFOdelete, and
ORDEREDdelete;and a ExchangeEntry. That covers all the
possibilities for entries in a list that we have covered thus far.

Let us consider those routines necessary to support a FIFO
queue ordering only. In this we add entries to the end and
delete them from the front.

Let's consider how we add (insert) an entry. Let's represent
the entry in an abstract form like ().
When we allocate space for the entry we get an address for
the start of that space, say p1: 'allocate entry1 set(p1);' Thus
p1->() gives us our newly allocated
entry plus its address.

Now we need to add it to the end of the list to satisfy the
rules of a FIFO queue. We have the end of the list stored in
our anchor, i.e. list1.last. Now it starts to get cute. So pay
close attention.

Our "current" last entry has a 'next' address set to null as it is
the "current" end of the list. Now its 'next' address needs to
point to our new entry. We take the "current" last entry
address, list1.last, and use it as an "address qualifier" for the
'next' entry, which we set to p1:
list1.next->next = p1;

Then we set the new entry's 'prev' address to point to the
"current" last enty;

p1->prev = list1.last;

Then finally we change the 'last' address in the anchor to
reflect the new "current" last entry:

list1.last = p1;

Now altogether we have:

allocate entry1 set(p1);
list1.last->next = p1;
p1->prev = list1.last;
list1.last = p1;

A more complete processing would include adding to an
"empty" list as well as one with one or more entries:

allocate entry1 set(p1);
if list1.first = null
then do; /* empty list */
list1.first, list1.last = p1;
end;
else do; /* non-empty list */
list1.last->next = p1;
p1->prev = list1.last;
list1.last = p1;
end;

Now it remains to see how we get from here to LISP and
Python.

=====================================================

To unsubscribe from this list, send an email message
to "steward@scoug.com". In the body of the message,
put the command "unsubscribe scoug-programming".

For problems, contact the list owner at
"postmaster@scoug.com".

=====================================================

Return to [ 19 | April | 2005 ]

SCOUG, Warp Expo West, and Warpfest are trademarks of the Southern California OS/2 User Group. OS/2, Workplace Shell, and IBM are registered trademarks of International Business Machines Corporation. All other trademarks remain the property of their respective owners.