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

Documentation on exports

PREDICATE

Usage: null_ddlist(A)

  • Description: 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.

PREDICATE

Usage: create_from_list(List,DDList)

  • Description: 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.

PREDICATE

Usage: to_list(DDList,List)

  • Description: 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.

PREDICATE

Usage: next(OldList,NewList)

  • Description: 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.

PREDICATE

Usage: prev(OldList,NewList)

  • Description: 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.

PREDICATE

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).
  • 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.

PREDICATE

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)
  • 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.

PREDICATE

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).
  • 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.

PREDICATE

Usage: insert_begin(List,Element,NewList)

  • Description: 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.

PREDICATE

Usage: insert_end(List,Element,NewList)

  • Description: 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.

PREDICATE

Usage: delete(OldList,NewList)

  • Description: 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.

PREDICATE

Usage: delete_top(OldList,NewList)

  • Description: 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.

PREDICATE

Usage: delete_after(OldList,NewList)

  • Description: 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.

PREDICATE

Usage: remove_all_elements(OldList,E,NewList)

  • Description: 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.

PREDICATE

Usage: top(List,Element)

  • Description: 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.

PREDICATE

Usage: rewind(OldList,NewList)

  • Description: 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.

PREDICATE

Usage: forward(OldList,NewList)

  • Description: 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.

PREDICATE

Usage: length(List,Len)

  • Description: 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.

PREDICATE

Usage: length_next(List,Len)

  • Description: 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.

PREDICATE

Usage: length_prev(List,Len)

  • Description: 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.

REGTYPE

Usage: ddlist(X)

  • Description: X is a "doubly linked" list.

PREDICATE

Usage: ddlist_member(X,DDList)

  • Description: 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 ).