RickCarlino/linked_list.md

## linked_list.md

      
    Raw
  

              linked_list.md
            
          
    Singly Linked List

This snippet provides a generic implementation of a singly linked list.
Each value in the list points forward to the next item.
Currently only supports one list per VM, which is acceptable for my use case.
+------+
|LINK  |---*
+------+   |
|VALUE |   |
+------+   |
+------+ <-*
|LINK  | --,
+------+   |
|VALUE |   |
+------+   |
+------+ <-`
|LINK  |---,
+------+   |
|VALUE |   |
+------+   |
+------+   |
|LINK  | <-` The last link points to 0x0
+------+
|VALUE |
+------+

Head and Tail, First and Last

Because the links point forward (instead of backward),
we need to keep track of the head and tail of the linked list.
We store the start of the list at ll:first.
We also store the most recent item with ll:last.
Null values indicate the list has a size of 0.
#0 'll:first var-n
#0 'll:last  var-n

Node Management

The library defines methods to handle single nodes:

ll:append adds a new node.
ll:next fetches the pointer to the next node in the list. A null value here indicates the final node in the chain.
ll:value fetches the nodes contents. Nodes only store one value. Hint: Use arrays to store more than one value.

{{
  'current-value var
  'current-addr  var

  :set-current-value (s-s) s:keep !current-value $= , ;
  :set-current-addr  (a-)  here !current-addr ;
  :maybe-set-ll:first (-)  @ll:first [ @current-addr !ll:first ] -if ;
  :set-backlink       (-)  @ll:last [ here @ll:last store ] if ;

---reveal---

  :ll:next  (a-) #2 + ;
  :ll:value (a-) n:inc fetch ;
  :ll:append (v-)
    set-current-value
    set-current-addr
    set-backlink
    maybe-set-ll:first
    @current-addr !ll:last
    FALSE , @current-value ,
  ;
}}

Test: Creating a List of Strings

{ 'One 'Two 'Three } &ll:append a:for-each

@ll:first ll:value 'One s:eq?
[ 'Test_1_pass s:put nl     ]
[ 'Test_1_FAIL s:put nl bye ]
choose

@ll:first ll:next 'Two s:eq?
[ 'Test_2_pass s:put nl     ]
[ 'Test_2_FAIL s:put nl bye ]
choose

@ll:last ll:value 'Three s:eq?
[ 'Test_3_pass s:put nl     ]
[ 'Test_3_FAIL s:put nl bye ]
choose


Iteration

Iteration is possible via ll:for-each.
ll:for-each will push a pointer to a linked list node onto
the stack and then execute the provided quotation once for
each node in the linked list.
The diagram below uses the list created in the previous tests
as an example:
3D6D: O
3D6E: n
3D6F: e
3D70: 0x0
3D71: 0x3D77 >---.
3D72: 0x3D6D      \
3D73: T            |
3D74: w            |
3D75: o            |
3D76: 0x0         /
3D77: 0x3D7F <---:
3D78: 0x3D73      \
3D79: T           |
3D7A: h           |
3D7B: r           |
3D7C: e           |
3D7D: e           |
3D7E: 0x0        /
3D7F: 0x0 <-----'
3D80: 0x3D79

Iterating Through the List

With the ability to create a list, we now need a way to iterate
over each item in the list.
We will define a word, ll:for-each, for this purpose.
The word will internally track two things:

A quotation that will be called once per iteration (iterator).
The current node that we need to pass to said iterator (current-node).

I would like to factor these variables out of a future version, but alas,
my stackrobatics are not yet strong enough.
{{
  'iterator     var
  'current-node var

call-iterator does just that- it calls the iterator, and
passes it the address of the current-node:
  :call-iterator   (-)  @current-node @iterator call ;

After we call the iterator, we set current-node to whatever
value is contained in the node's link field. Don't forget that
the last node in the list will have a null link field!
  :fetch-next-node (-)  @current-node fetch !current-node ;

The last private word is iterate, which ties all the pieces together:

Attempts to fetch the current node.
Calls the user's iterator if a node is found.
Leaves TRUE on the stack if the next node in the list is
available.

  :iterate         (-a)
    @current-node
    [ call-iterator fetch-next-node TRUE ]
    [ FALSE ]
    choose
  ;

---reveal---
  :ll:for-each (q(a-)-)
    @ll:first 0;
    !current-node !iterator
    &iterate while
  ;
}}

Each With Index

This word is similar to ll:for-each except that it passes
the current index along with the node address when iterating.
{{
  'quote   var
  'counter var

  :counter:inc (-n) @counter n:inc dup !counter ;
  :iterator    (a-) counter:inc @quote call ;

  ---reveal---

  :ll:each-with-index (q(an-)-)
    !quote
    #-1 !counter
    &iterator ll:for-each
  ;
}}

Tests

The final test will iterate over the prviously defined list of
strings. We will cross check the node's ll:value against its
index. Everything should be in the correct order:
:test4 (s-)
  ll:value 'One s:eq?
  [ 'Test_4_pass s:put nl ]
  [ 'Test_4_FAIL s:put nl s:put nl s:put nl bye ]
  choose
;

:test5 (s-)
  ll:value 'Two s:eq?
  [ 'Test_5_pass s:put nl ]
  [ 'Test_5_FAIL s:put nl bye ]
  choose
;

:test6 (s-)
  ll:value 'Three s:eq?
  [ 'Test_6_pass s:put nl ]
  [ 'Test_6_FAIL s:put nl bye ]
  choose
;

:tests (sn-)
  #0 &test4 case
  #1 &test5 case
  #2 &test6 case
;

&tests ll:each-with-index

Project TODOs / Wishlist


Support more than one list via ll:new
Shave a few bytes of memory usage by removing local vars in favor of stack allocation.