Module description

dcl -- Double Linked Cell List
The dcl module implements a double linked list that can store cell wide data.

List structure

dcl% ( -- n )
Get the required space for a dcl variable

List creation, initialisation and destruction

dcl-init ( dcl -- )
Initialise the dcl list
dcl-(free) ( dnl -- )
Free the nodes from the heap
dcl-create ( "<spaces>name" -- ; -- dcl )
Create a named dcl list in the dictionary
dcl-new ( -- dcl )
Create a new dcl list on the heap
dcl-free ( dcl -- )
Free the list from the heap, including the nodes

Member words

dcl-empty? ( dcl -- flag )
Check for empty list
dcl-length@ ( dcl -- u )
Get the number of nodes in the list
dcl-compare! ( xt dcl -- )
Set the compare execution token for sorting the list
dcl-compare@ ( dcl -- xt )
Get the compare execution token for sorting the list

List words

dcl-clear ( dnl -- )
Delete all nodes from the list
dcl-append ( x dcl -- )
Append the cell data x in the list
dcl-prepend ( x dcl -- )
Prepend the cell data x in the list

Index words

dcl-index? ( n dcl -- flag )
Check if the index n is valid for the list
dcl-set ( x n dcl -- )
Set the cell data x in the nth node in the list
dcl-get ( n dcl -- x )
Get the cell data x from the nth node from the list
dcl-insert ( x n dcl -- )
Insert cell data x at the nth node in the list
dcl-delete ( n dcl -- x )
Delete the nth node from the list, return the cell data x

Special words

dcl-count ( x dcl -- u )
Count the number of occurrences of the cell data x in the list
dcl-execute ( i*x xt dcl -- j*x )
Execute xt for every cell data in list
dcl-execute? ( i*x xt dcl -- j*x flag )
Execute xt for every cell data in list or until xt returns true, flag is true if xt returned true
dcl-reverse ( dcl -- )
Reverse or mirror the list

Search words

dcl-find ( x dcl -- n )
Find the first index for the cell data x in the list, -1 for not found
dcl-has? ( x dcl -- flag )
Check if the cell data x is present in the list
dcl-remove ( x dcl -- flag )
Remove the first occurrence of the cell data x from the list, return success

Sort words

dcl-insert-sorted ( x dcl -- )
Insert the cell data x sorted in the list
dcl-sort ( xt dcl -- )
Sort the list dcl using mergesort, xt compares the nodes

Inspection

dcl-dump ( dcl -- )
Dump the list

Examples

\ ==============================================================================
\
\    dcl_expl - the cell based double linked list example in the ffl
\
\               Copyright (C) 2010  Dick van Oudheusden
\  
\ This library is free software; you can redistribute it and/or
\ modify it under the terms of the GNU General Public
\ License as published by the Free Software Foundation; either
\ version 2 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
\ General Public License for more details.
\
\ You should have received a copy of the GNU General Public
\ License along with this library; if not, write to the Free
\ Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
\
\ ==============================================================================
\ 
\  $Date: 2008-04-10 16:12:01 $ $Revision: 1.1 $
\
\ ==============================================================================

include ffl/dcl.fs
include ffl/rng.fs


\ Example: sort a cell based double linked list with 1001 random numbers


\ Create the double linked list on the heap

dcl-new value nlist

\ Create the pseudo random generator in the dictionary with seed 9898

9898 rng-create nrng

\ Insert 1001 numbers in the nlist

: nlist-insert     ( n -- = Insert n random numbers in nlist )
  0 DO
    nrng rng-next-number          \ Generate random number and ..
    nlist dcl-append              \ .. append to the list
  LOOP
;

1001 nlist-insert

\ Check the number of numbers out of sequence

: nnode-out-sequence ( n1 n2 flag n3 -- n4 n5 true = Count the number of out of sequence number, n1: count n2:previous number n3: number )
  swap IF
    tuck > IF >r 1+ r> THEN       \ Compare current number with previous number increment counter if out of sequence
  ELSE
    nip                           \ First call, no check
  THEN
  true
;

.( Before sorting there are ) 0 0 false ' nnode-out-sequence nlist dcl-execute 2drop . .( numbers out of sequence. ) cr

\ Sort the list using the <=> word

' <=> nlist dcl-sort

\ Check the number of numbers out of sequence again

.( After sorting there are ) 0 0 false ' nnode-out-sequence nlist dcl-execute 2drop . .( numbers out of sequence. ) cr

\  Reverse the list

nlist dcl-reverse

\ Check the number of out of sequence numbers again

.( After reversing there are ) 0 0 false ' nnode-out-sequence nlist dcl-execute 2drop . .( numbers out of sequence. ) cr

\ Cleanup the list

nlist dcl-free


Generated by fsdocgen 0.1.0