(       Title:  Single-Ended, Single-Linked Lists
         File:  sslist.fs
      Version:  1.2.3
       Author:  David N. Williams
      License:  LGPL
Last revision:  September 29, 2002
)
\ Copyright (C) 2000-2002  David N. Williams
(
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or at your option any later version.

This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

Please see the file POLITENESS included with this distribution.

ANS Forth compatible except for:
- Case sensitivity.
- REQUIRED loads Forth source if it's not already loaded.
- Assumption that zero does not occur as an address.

Uses LOCALS| from the Locals extension word set.

Please see the file NOTATION.

The only words from the following files that are actually used
here are mentioned in the accompanying comments.  The rest
complete the glossary so that only this file need be loaded for
single-ended, single-linked list applications.
)

s" nodespace.fs" REQUIRED  \ for UNUSE-NODE
s" sendlist.fs"  REQUIRED  \ for CURRENT-LIST
s" snode.fs"     REQUIRED  \ but not used here


\ *** WORDS
(
  SSINSERT-AFTER  SSPREPEND  SSUNLINK-FIRST  SSUNLINK-NEXT
  SSUNUSE-FIRST  SSUNUSE-NEXT
)

\ *** SINGLE-ENDED, SINGLE-LINKED LIST OPERATIONS
(
These words assume that the current list is single-ended and
single-linked, and that all nodes have headers for single
linking and belong to the current node space.
)

: ssinsert-after  ( node node.before -- )
(
Assume that node.before is in the current list, and that node is
unlinked.  Insert node into the list just after node.before.
)
\  ( before) dup @
\  LOCALS| after before node |
\  node before !   \ before -> node
\  after node ! ;  \ node -> after

  ( node before) 2dup @
  ( node after) swap !  \ node -> after
  ( node before) ! ;    \ before -> node

: ssprepend  ( node -- )
(
Assume that node is unlinked.  Prepend it to the beginning of
the list.
)
  current-list ( head) @ ( first)
  over ( first node) !              \ node -> first
  ( node) current-list ( head) ! ;  \ node is new first


\ NOTE:  If the application only builds lists but never removes
\ anything from them, all words beyond this point can be omitted.


: ssunlink-next  ( node.before -- node|0 )
(
Assume that node.before is in the current list.  Unlink and
leave the following node, or just leave zero if node.before is
last in the list.
)
  ( before) dup @
  LOCALS| node before |
  node IF node @ before ! THEN
  node ;

: ssunuse-next  ( node.before -- )
(
Assume that node.before is in the current list.  If there is a
following node, unlink it, and link it into the unused chain in
the current node space.  Otherwise do nothing.
)
  ( before) ssunlink-next ( node|0) unuse-node ;


\ *** STACK OPERATIONS
(
Together with SSPREPEND, the two words SSUNLINK-FIRST and
SSUNUSE-FIRST below implement the basic push, pop, and drop
operations for a stack, i.e., a LIFO list.
)

: ssunlink-first  ( -- node|0 )
(
If the current list is not empty, unlink and leave its first
node.  Otherwise leave zero.
)
  current-list ( head) @ ( first) dup
  ( nonempty?) IF
    ( first) dup @ ( second) current-list ( head) !
  THEN ( first) ;

: ssunuse-first  ( -- )
(
If the current list is not empty, unlink its first node, and
link it into the unused chain in the current node space.  
Otherwise do nothing.
)
  ssunlink-first unuse-node ;