Double linked list

Author(s): David Trallero Mena.

Version: 1.10#7 (2006/4/26, 19:22:13 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(OldList, 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)
• Call and exit should be compatible with: OldList is double linked list (ddlist:ddlist/1) NewList is double linked list (ddlist:ddlist/1)

PREDICATE: prev/2:

Usage: prev(OldList, NewList)

• Description: NewList is OldList but index is set to previous element of current element of OldListop) of OldList
• Call and exit should be compatible with: OldList is double linked list (ddlist:ddlist/1) NewList is double linked list (ddlist:ddlist/1)

PREDICATE: insert/3:

Usage: insert(List, Element, NewList)

• Description: NewList is like List but with Element inserted _BEFORE_ the current index It satisfies insert( X , A , Xp ) , delete( Xp , X ).
• Call and exit should be compatible with: List is double linked list (ddlist:ddlist/1) NewList is double linked list (ddlist:ddlist/1)

PREDICATE: insert_top/3:

Usage: insert_top(List, Element, NewList)

• Description: Put Element as new top of NewList and push the rest of elements after it. It satisfies top( NewList , element )
• Call and exit should be compatible with: List is double linked list (ddlist:ddlist/1) NewList is double linked list (ddlist:ddlist/1)

PREDICATE: insert_after/3:

Usage: insert_after(List, Element, 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 ).
• Call and exit should be compatible with: List is double linked list (ddlist:ddlist/1) NewList is double linked list (ddlist:ddlist/1)

PREDICATE: delete/2:

Usage: delete(OldList, NewList)

• Description: NewList does not have the previous element (top(prev)) of OldList
• Call and exit should be compatible with: OldList is double linked list (ddlist:ddlist/1) NewList is double linked list (ddlist:ddlist/1)

PREDICATE: delete_top/2:

Usage: delete_top(OldList, NewList)

• Description: NewList does not have the current element (top) of OldList
• Call and exit should be compatible with: OldList is double linked list (ddlist:ddlist/1) NewList is double linked list (ddlist:ddlist/1)

PREDICATE: delete_after/2:

Usage: delete_after(OldList, NewList)

• Description: NewList does not have next element to current element (top) of OldList
• Call and exit should be compatible with: OldList is double linked list (ddlist:ddlist/1) NewList is double linked list (ddlist:ddlist/1)

PREDICATE: top/2:

Usage: top(List, Element)

• Description: Element is the element pointed by index
• Call and exit should be compatible with: List is double linked list (ddlist:ddlist/1)

PREDICATE: rewind/2:

Usage: rewind(OldList, NewList)

• Description: NewList is the OldList but index is set to 0
• Call and exit should be compatible with: OldList is double linked list (ddlist:ddlist/1) NewList is double linked list (ddlist:ddlist/1)

PREDICATE: forward/2:

Usage: forward(OldList, NewList)

• Description: NewList is the OldList but index is set to lentgh of NewList
• Call and exit should be compatible with: OldList is double linked list (ddlist:ddlist/1) NewList is double linked list (ddlist:ddlist/1)

PREDICATE: length/2:

Usage: length(List, Len)

• Description: Len is the length of the List
• Call and exit should be compatible with: List is double linked list (ddlist:ddlist/1)

PREDICATE: length_next/2:

Usage: length_next(List, Len)

• Description: Len is the length from the current index till the end
• Call and exit should be compatible with: List is double linked list (ddlist:ddlist/1)

PREDICATE: length_prev/2:

Usage: length_prev(List, Len)

• Description: Len is the length from the beginning till the current index
• Call and exit should be compatible with: List is double linked list (ddlist:ddlist/1)

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.