Doubly linked lists
Author(s): David Trallero Mena.
This library implements "doubly linked" lists, in the sense that they can be traversed in both directions with good complexity. An index is used for referencing the current element in the list. This index can be modified by the next and prev predicates. The value of the current index can be obtained via the top predicate
Usage and interface
- Library usage:
:- use_module(library(ddlist)). - Exports:
- Predicates:
null_ddlist/1, create_from_list/2, to_list/2, next/2, prev/2, insert/3, insert_top/3, insert_after/3, insert_begin/3, insert_end/3, delete/2, delete_top/2, delete_after/2, remove_all_elements/3, top/2, rewind/2, forward/2, length/2, length_next/2, length_prev/2, ddlist_member/2. - Regular Types:
ddlist/1.
- Predicates:
- Imports:
Documentation on exports
Usage:null_ddlist(A)
NullList is an empty ddlist.
- The following properties should hold at call time:
(term_typing:var/1)A is a free variable. - The following properties should hold upon exit:
(ddlist:ddlist/1)A is a "doubly linked" list.
Usage:create_from_list(List,DDList)
Creates a doubly linked list from normal list List.
- The following properties should hold at call time:
(basic_props:list/1)List is a list.
(term_typing:var/1)DDList is a free variable. - The following properties should hold upon exit:
(ddlist:ddlist/1)DDList is a "doubly linked" list.
Usage:to_list(DDList,List)
Converts from doubly linked list to list.
- The following properties should hold at call time:
(ddlist:ddlist/1)DDList is a "doubly linked" list.
(term_typing:var/1)List is a free variable. - The following properties should hold upon exit:
(basic_props:list/1)List is a list.
Usage:next(OldList,NewList)
NewList is OldList but index is set to the element following the current element of OldList. It satisfies next(A,B), prev(B,A).
- The following properties should hold at call time:
(ddlist:ddlist/1)OldList is a "doubly linked" list.
(ddlist:ddlist/1)NewList is a "doubly linked" list.
Usage:prev(OldList,NewList)
NewList is OldList but index is set to the element before the current element of OldList.
- The following properties should hold at call time:
(ddlist:ddlist/1)OldList is a "doubly linked" list.
(ddlist:ddlist/1)NewList is a "doubly linked" list.
Usage:insert(List,Element,NewList)
NewList is like List but with Element inserted before the current index. It satisfies insert(X , A , Xp) , delete(Xp , X).
- The following properties should hold at call time:
(ddlist:ddlist/1)List is a "doubly linked" list.
(basic_props:term/1)Element is any term.
(ddlist:ddlist/1)NewList is a "doubly linked" list.
Usage:insert_top(List,Element,NewList)
Put Element as new top of NewList and push the rest of elements after it. It satisfies top(NewList , element)
- The following properties should hold at call time:
(ddlist:ddlist/1)List is a "doubly linked" list.
(basic_props:term/1)Element is any term.
(ddlist:ddlist/1)NewList is a "doubly linked" list.
Usage:insert_after(List,Element,NewList)
NewList is like List but with Element inserted after the current index. It satisfies insert_after(X, A, Xp), delete_after(Xp, X).
- The following properties should hold at call time:
(ddlist:ddlist/1)List is a "doubly linked" list.
(basic_props:term/1)Element is any term.
(ddlist:ddlist/1)NewList is a "doubly linked" list.
Usage:insert_begin(List,Element,NewList)
NewList is like List with Element as first element.
- The following properties should hold at call time:
(ddlist:ddlist/1)List is a "doubly linked" list.
(basic_props:term/1)Element is any term.
(ddlist:ddlist/1)NewList is a "doubly linked" list.
Usage:insert_end(List,Element,NewList)
NewList is like List with Element as last element.
- The following properties should hold at call time:
(ddlist:ddlist/1)List is a "doubly linked" list.
(basic_props:term/1)Element is any term.
(ddlist:ddlist/1)NewList is a "doubly linked" list.
Usage:delete(OldList,NewList)
NewList does not have the previous element (top(prev)) of OldList.
- The following properties should hold at call time:
(ddlist:ddlist/1)OldList is a "doubly linked" list.
(ddlist:ddlist/1)NewList is a "doubly linked" list.
Usage:delete_top(OldList,NewList)
NewList does not have the current element (top) of OldList.
- The following properties should hold at call time:
(ddlist:ddlist/1)OldList is a "doubly linked" list.
(ddlist:ddlist/1)NewList is a "doubly linked" list.
Usage:delete_after(OldList,NewList)
NewList does not have next element to current element (top) of OldList.
- The following properties should hold at call time:
(ddlist:ddlist/1)OldList is a "doubly linked" list.
(ddlist:ddlist/1)NewList is a "doubly linked" list.
Usage:remove_all_elements(OldList,E,NewList)
Remove all elements that unify with E from OldList. NewList is the result of this operation. The pointer is not modified unless there it is pointing at element that unifies with E.
- The following properties should hold at call time:
(ddlist:ddlist/1)OldList is a "doubly linked" list.
(term_typing:nonvar/1)E is currently a term which is not a free variable. - The following properties should hold upon exit:
(ddlist:ddlist/1)NewList is a "doubly linked" list.
Usage:top(List,Element)
Element is the element pointed by index.
- The following properties should hold at call time:
(ddlist:ddlist/1)List is a "doubly linked" list.
(basic_props:term/1)Element is any term.
Usage:rewind(OldList,NewList)
NewList is the OldList but index is set to 0.
- The following properties should hold at call time:
(ddlist:ddlist/1)OldList is a "doubly linked" list.
(ddlist:ddlist/1)NewList is a "doubly linked" list.
Usage:forward(OldList,NewList)
NewList is the OldList but index is set to lentgh of NewList.
- The following properties should hold at call time:
(ddlist:ddlist/1)OldList is a "doubly linked" list.
(ddlist:ddlist/1)NewList is a "doubly linked" list.
Usage:length(List,Len)
Len is the length of the List
- The following properties should hold at call time:
(ddlist:ddlist/1)List is a "doubly linked" list.
(basic_props:int/1)Len is an integer.
Usage:length_next(List,Len)
Len is the length from the current index till the end.
- The following properties should hold at call time:
(ddlist:ddlist/1)List is a "doubly linked" list.
(basic_props:int/1)Len is an integer.
Usage:length_prev(List,Len)
Len is the length from the beginning till the current index.
- The following properties should hold at call time:
(ddlist:ddlist/1)List is a "doubly linked" list.
(basic_props:int/1)Len is an integer.
Usage:ddlist_member(X,DDList)
Success if X is member of DDList. X first unifies with elements of the forward list, i.e. from the top till the end, and later with elements from the top to the beginning.
- The following properties should hold at call time:
(basic_props:term/1)X is any term.
(ddlist:ddlist/1)DDList is a "doubly linked" list.
Other information
Two simple examples of the use of the ddlist library package follow.
Using insert_after
:- module( ddl1 , _ , [] ). :- use_module(library(ddlist)). main(A,B):- % L = [] null_ddlist( 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_ddlist( 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 ).
