%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Copyright (c) 2014 Scott Laufer                                              %
%                                                                              %
% Permission is hereby granted, free of charge, to any person obtaining a copy %
% of this software and associated documentation files (the "Software"), to     %
% deal in the Software without restriction, including without limitation the   % 
% rights to use, copy, modify, merge, publish, distribute, sublicense, and/or  %
% sell copies of the Software, and to permit persons to whom the Software is   %
% furnished to do so, subject to the following conditions:                     %
%                                                                              %
% The above copyright notice and this permission notice shall be included in   %
% all copies or substantial portions of the Software.                          %
%                                                                              %
% THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR   %
% IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,     %
% FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE  %
% AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER       %
% LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING      %
% FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS %
% IN THE SOFTWARE                                                              %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% list - A PostScript linked list library modeled after the C++ STL list
%
% Function arguments and return values are listed in standard PostScript
% reference style, i.e.:
%
%	<arg1> ... <argn> FUNCTION <ret1> ... <retn>
%
% WARNING: DO NOT ATTEMPT TO PRINT THE LIST OR ITERATOR STRUCTURES USING == OR
% PSTACK, THIS WILL RESULT IN AN INFINITE LOOP CAUSING A CRASH OR STACK OVERFLOW

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% LIST FUNCTIONS MANUAL                                                        %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% list:create <list> - creates an empty list
%
% <list> list:getcount <count>
%% returns the number of members in <list>
%
% <list> list:length <count>
%% alias for list:getcount
%
% <list> <it> list:first
%% points iterator <it> to first member of <list>. for empty lists, this will
%% point to the ending beyond-the-end node. (i.e. <it> list:it:is_end will
%% return true)
%
% <list> <it> list:last
%% points iterator <it> to last member of <list>. for empty lists, this will
%% point to the beginning beyond-the-end node. (i.e. <it> list:it:is_begin will
%% return true)
%
% <list> <any> list:push_back
%% inserts <any> at the end of <list> as a new member.
%
% <list> <any> list:push_front
%% inserts <any> at the beginning of <list> as a new member.
%
% <list> list:pop_back
%% removes the last member of <list>. be sure that the list is not empty before
%% using this function, or it will break your list.
%
% <list> list:pop_front
%% removes the first member of <list>. be sure that the list is not empty before
%% using this function, or it will break your list.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ITERATOR FUNCTIONS MANUAL                                                    %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% First, a few rules:
% - When using list:pop_front or list:pop_back, any iterators pointing to the
%   removed member are invalidated.
% - When using list:it:delete, all iterators pointing to the removed member
%   EXCEPT the iterator passed as an argument are invalidated.
% - Invalidated iterators should be destroyed or reinitialized before being used
%   again.
% - Be certain that the iterator is not pointing to the beginning or ending 
%   beyond-the-end members before using list:delete. This can be tested using
%   list:it:is_begin and/or list:it:is_end.
%
% list:it:create <it>
%% creates an uninitialized iterator
%
% <it> list:it:getdata <any>
%% returns value <any> of member pointed to by <it>
%
% <it> list:it:get <any>
%% alias for list:it:getdata
%
% <it> <any> list:it:setdata
%% sets value of member pointed to by <it> to <any>
%
% <it> <any> list:it:set
%% alias for list:it:setdata
%
% <it> list:it:next
%% move <it> to next member
%
% <it> list:it:prev
%% move <it> to previous member
%
% <it> list:it:is_begin <bool>
%% returns <bool> indicating if <it> is pointing to beginning past-the-end
%% member.
%
% <it> list:it:is_end <bool>
%% returns <bool> indicating if <it> is pointing to ending past-the-end member.
%
% <it> <any> list:it:insert
%% inserts a new member containing <any> after the member pointed to by <it>
%
% <it> list:it:delete
%% deletes the member pointed to by <it>, moving <it> to prevous member
%
% <it1> <it2> list:it:same <bool>
%% returns <bool> indicating whether or not <it1> and <it2> are pointing at the
%% same member, regardless of value

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% LIST MEMBER IMPLEMENTATION                                                   %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Structure: [ data prev next ]

/list:member:create { [ exch null null ] } bind def

/list:member:getdata { 0 get } bind def
/list:member:getprev { 1 get } bind def
/list:member:getnext { 2 get } bind def

/list:member:setdata { 0 exch put } bind def
/list:member:setprev { 1 exch put } bind def
/list:member:setnext { 2 exch put } bind def

% <prev> <new> list:member:insert - inserts new after prev
/list:member:insert {
	1 index list:member:getnext % get next node (prev new next)
	2 copy list:member:setnext % set link new -> next (prev new next)
	1 index list:member:setprev % set link new <- next (prev new)
	2 copy list:member:setnext % set link prev -> new (prev new)
	exch list:member:setprev % set link prev <- new ()
} bind def

% <member> list:member:delete - unlinks member from the list
% causes member to be garbage collected if it is not referenced elsewhere
/list:member:delete {
	dup list:member:getprev % get previous node (member prev)
	exch list:member:getnext % get next node (prev next)
	2 copy list:member:setnext % link prev -> next
	exch list:member:setprev % link prev <- next
} bind def

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% LIST IMPLEMENTATION                                                          %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Structure: [ begin end count ] 

/list:create {
	[ 
		/list:begin list:member:create % create begin node
		/list:end list:member:create % create end node
		2 copy list:member:setnext % link begin node to end node
		2 copy exch list:member:setprev % link end node to begin node
		0 % set count
	]
} bind def

/list:getbegin { 0 get } bind def
/list:getend { 1 get } bind def
/list:getcount { 2 get } bind def
/list:length //list:getcount def % length is an alias for getcount

/list:setcount { 2 exch put } bind def

/list:inccount { dup list:getcount 1 add list:setcount } bind def
/list:deccount { dup list:getcount 1 sub list:setcount } bind def

/list:first {
	exch 2 copy % reorder and duplicate args (it list it list)
	list:getbegin list:member:getnext % get first member (it list it first)
	list:it:setpos % set iterator position (it list)
	list:it:setlist % set iterator list ()
} bind def

/list:last {
	exch 2 copy % reorder and duplicate args (it list it list)
	list:getend list:member:getprev % get last member (it list it last)
	list:it:setpos % set iterator position (it list)
	list:it:setlist % set iterator list () 
} bind def

/list:push_back {
	exch dup list:inccount % increment count (data list)
	list:getend list:member:getprev exch % get member end-1 (end-1 data)
	list:member:create % create a new member with data value (end-1 new)
	list:member:insert % insert new member after end-1
} bind def

/list:push_front {
	exch dup list:inccount % increment count (data list)
	list:getbegin exch % get member begin (begin data)
	list:member:create % create a new member with data value (begin new)
	list:member:insert % insert new member after begin
} bind def

/list:pop_back {
	dup list:deccount % decrement count (list)
	list:getend list:member:getprev % get last data member (end-1)
	list:member:delete % delete member ()
} bind def

/list:pop_front {
	dup list:deccount % decrement count (list)
	list:getbegin list:member:getnext % get first data member (begin+1)
	list:member:delete % delete member ()
} bind def

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% LIST ITERATOR IMPLEMENTATION                                                 %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Structure: [ pos list ]

/list:it:create { [ null null ] } bind def
/list:it:getpos { 0 get } bind def
/list:it:getlist { 1 get } bind def
/list:it:getdata { list:it:getpos list:member:getdata } bind def
/list:it:get //list:it:getdata def

/list:it:setpos { 0 exch put } bind def
/list:it:setlist { 1 exch put } bind def
/list:it:setdata { exch list:it:getpos exch list:member:setdata } bind def
/list:it:set //list:it:setdata def

/list:it:next { dup list:it:getpos list:member:getnext list:it:setpos } bind def
/list:it:prev { dup list:it:getpos list:member:getprev list:it:setpos } bind def

/list:it:is_begin { list:it:getdata /list:begin eq } bind def
/list:it:is_end { list:it:getdata /list:end eq } bind def

/list:it:same { list:it:getpos exch list:it:getpos eq } bind def

/list:it:insert {
	1 index list:it:getlist list:inccount % increment count (it data)
	list:member:create % create new member from data (it member)
	exch list:it:getpos exch % get position (pos member)
	list:member:insert % insert new member ()
} bind def

/list:it:delete {
	dup list:it:getlist list:deccount % increment count (it)
	dup list:it:getpos % get position (it pos)
	dup list:member:getprev % get prev position (it pos prev)
	exch list:member:delete % delete iterator position (it prev)
	list:it:setpos % set new position ()
} bind def