Double linked list

Author(s): David Trallero Mena.

Version: 1.11#222 (2004/5/24, 13:8:7 CEST)

Version of last change: 1.9#116 (2003/12/1, 22:4:57 CET)

This library allows the user to work with double linked lists. An index is used for referencing the current element in the list. Such index can be modified by next and prev predicated. The value of the current index can be obtained with top predicate

• Usage and interface (ddlist)
• Documentation on exports (ddlist)
• Other information (ddlist)

Usage and interface (ddlist)

Documentation on exports (ddlist)

PREDICATE: null_list/1:

Usage: null_list(NullList)

• Description: NullList is an empty list
• The following properties should hold at call time: A is a free variable. (term_typing:var/1)
• The following properties should hold upon exit: A is double linked list (ddlist:ddlist/1)

PREDICATE: next/2:

Usage: next(ddlist(OldList), ddlist(NewList))

• Description: NewList is OldList but index is set to next element of current element of OldList. It satisfies next(A,B),prev(B,A)

PREDICATE: prev/2:

Usage: prev(ddlist(OldList), ddlist(NewList))

• Description: NewList is OldList but index is set to previous element of current element of OldListop) of OldList

PREDICATE: insert/3:

Usage: insert(ddlist(List), Element, ddlist(NewList))

• Description: NewList is like List but with Element inserted _BEFORE_ the current index It satisfies insert( X , A , Xp ) , delete( Xp , X ).

PREDICATE: insert_top/3:

Usage: insert_top(ddlist(List), Element, ddlist(NewList))

• Description: Put Element as new top of NewList and push the rest of elements after it. It satisfies top( NewList , element )

PREDICATE: insert_after/3:

Usage: insert_after(ddlist(List), Element, ddlist(NewList))

• Description: NewList is like List but with Element inserted _AFTER_ the current index It satisfies insert_after( X , A , Xp ) , delete_after( Xp , X ).

PREDICATE: delete/2:

Usage: delete(ddlist(OldList), ddlist(NewList))

• Description: NewList does not have the previous element (top(prev)) of OldList

PREDICATE: delete_top/2:

Usage: delete_top(ddlist(OldList), ddlist(NewList))

• Description: NewList does not have the current element (top) of OldList

PREDICATE: delete_after/2:

Usage: delete_after(ddlist(OldList), ddlist(NewList))

• Description: NewList does not have next element to current element (top) of OldList

PREDICATE: top/2:

Usage: top(ddlist(List), Element)

• Description: Element is the element pointed by index

PREDICATE: rewind/2:

Usage: rewind(ddlist(OldList), ddlist(NewList))

• Description: NewList is the OldList but index is set to 0

PREDICATE: forward/2:

Usage: forward(ddlist(OldList), ddlist(NewList))

• Description: NewList is the OldList but index is set to lentgh of NewList

PREDICATE: length/2:

Usage: length(ddlist(List), Len)

• Description: Len is the length of the List

PREDICATE: length_next/2:

Usage: length_next(ddlist(List), Len)

• Description: Len is the length from the current index till the end

PREDICATE: length_prev/2:

Usage: length_prev(ddlist(List), Len)

• Description: Len is the length from the beginning till the current index

REGTYPE: ddlist/1:

Usage: ddlist(X)

• Description: X is double linked list

Other information (ddlist)

Two simple examples of the use of the ddlist library package follow.

• Using insert_after
• More Complex example

Using insert_after

:- module( ddl1 , _ , [] ).

:- use_module( library(ddlist) ).

main(A,B):-
        % L = []
        null_list( L ),
        % L = [1]
        insert_after( L  , 1 , L1 ),
        % L = [1,2]
        insert_after( L1 , 2 , L2 ),
        % L = [1,3,2]
        insert_after( L2 , 3 , L3 ),
        % L = [1,3,2] => A = [1]
        top( L3 , A ),
        % L = [3,2]
        next( L3 , PL3 ),
        % L = [3,2] => A = [3]
        top( PL3 , B ).

More Complex example

:- module( ddl2 , _ , [] ).

:- use_module( library(ddlist) ).

main(A,B):-
        % L = []
        null_list( L ),
        % L = [1]
        insert_after( L  , 1 , L1 ),
        % L = [1,2]
        insert_after( L1 , 2 , L2 ),
        % L = [1,2]
        insert( L2 , 3 , L3 ),
        % L = [3,1,2]
        prev( L3 , PL3 ),
        % L = [],
        forward( PL3 , FOR ),
        % L = [2]
        prev( FOR , FOR1 ),
        % L = [2] => A = 2
        top( FOR1 , A ),
        % L = [1,2]
        prev( FOR1 , FOR2 ),
        % L = [2]
        delete_after( FOR2 , FOR3 ),
        % L = [3,2]
        prev( FOR3, FOR4 ),
        % L = [3,2] => B = 3
        top( FOR4 , B ).

Go to the first, previous, next, last section, table of contents.