dcl -- Double Linked Cell List

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