;+
; $Id: chain_link_utilities.pro,v 1.2 2010/01/08 15:37:00 nathan Exp $
;
; Collection of utilities for dealing with a chain (linked list).
; The user should only ever need the "add" and "delete" functions.
; The "add" function will also create a new chain.
; The "delete" function runs depointer.pro
; All functions accept a pointer to any link in the chain.
;
; Each link in the chain has 3 elements as tags in a struture:
;	prev, points to previous link, null if beginning of chain.
;	next, points to the next link, null if end of chain.
;	data, points to whatever.
;
; written by jeffrey.r.hall@jpl.nasa.gov
;
; "Copyright 2009, by the California Institute of Technology. 
; ALL RIGHTS RESERVED. United States Government Sponsorship 
; acknowledged. Any commercial use must be negotiated with the 
; Office of Technology Transfer at the California Institute of 
; Technology.
;
; This software may be subject to U.S. export control laws. 
; By accepting this software, the user agrees to comply with 
; all applicable U.S. export laws and regulations. User has 
; the responsibility to obtain export licenses, or other 
; export authority as may be required before exporting such 
; information to foreign countries or providing access to 
; foreign persons."
;
; $Log: chain_link_utilities.pro,v $
; Revision 1.2  2010/01/08 15:37:00  nathan
; committed sunloop_20091117
;
;-

@depointer.pro

function chain_start_finder, chainlinkptr
	; Find 1st link in chain.

	if ptr_valid( chainlinkptr ) then $
		while ptr_valid( (*chainlinkptr).prev ) do $
			chainlinkptr = (*chainlinkptr).prev
	return, chainlinkptr
end

function chain_end_finder, chainlinkptr
	; Find last link in chain.

	while ptr_valid( (*chainlinkptr).next ) do chainlinkptr = (*chainlinkptr).next
	return, chainlinkptr
end

function chain_integrety, chainlinkptr
	; Check to make sure the next link's prev points to current.

	integrety = 1
	currentlink = chain_start_finder( chainlinkptr )
	while ptr_valid( (*currentlink).next ) do begin
		nextlink = (*currentlink).next
		if (*nextlink).prev ne currentlink then integrety = 0
		currentlink = nextlink
	endwhile
	return, integrety
end

function chain_link_counter, chainlinkptr
	; Count all links in chain.

	count = 0					; If no valid links found, return 0.
	if ptr_valid( chainlinkptr ) then begin
		count = 1				; At least 1 link exists.
		current = chain_start_finder( chainlinkptr )
		while ptr_valid( (*current).next ) do begin
			current = (*current).next	; Next link ok, increment count.
			count = count + 1
		endwhile
	endif
	return, count
end

function chain_death, chainlinkptr
	; Run depointer.pro on every link in the entire chain.  Kill the whole thing.

	endlink = chain_end_finder( chainlinkptr )
	while ptr_valid( endlink ) do begin
		prevlink = (*endlink).prev
		(*endlink).prev = ptr_new()	; Prevent depointer from going into an endless loop.
		result = depointer( endlink )
		endlink = prevlink
	endwhile
	return, result
end

function chain_link_delete, chainlinkptr, VERBOSE=verbose
	; Remove a link from anywhere in the chain and repair chain where removal occured.

	IF SIZE(verbose,/TYPE) GT 0 THEN verbose=verbose ELSE verbose=0

	if ptr_valid( (*chainlinkptr).prev ) then begin
		if ptr_valid( (*chainlinkptr).next ) then begin
			; Rejoin the chain eliminating the link to be deleted.
			prev = (*chainlinkptr).prev
			next = (*chainlinkptr).next
			(*prev).next = next
			(*next).prev = prev
			; Depointer the link to be deleted.
			(*chainlinkptr).next = ptr_new()
			(*chainlinkptr).prev = ptr_new()
			result = depointer( chainlinkptr )
			IF VERBOSE THEN print, 'deleted link in middle of chain'
			chainlinkptr = chain_start_finder( next )
		endif else begin
			; Terminate the new end of the chain.
			prev = (*chainlinkptr).prev
			(*prev).next = ptr_new()
			; Depointer the link to be deleted.
			(*chainlinkptr).prev = ptr_new()
			result = depointer( chainlinkptr )
			IF VERBOSE THEN print, 'deleted link at end of multilink chain'
			chainlinkptr = chain_start_finder( prev )
		endelse
	endif else begin
		if ptr_valid( (*chainlinkptr).next ) then begin
			; Terminate the new beginning of the chain.
			next = (*chainlinkptr).next
			(*next).prev = ptr_new()
			; Depointer the link to be deleted.
			(*chainlinkptr).next = ptr_new()
			result = depointer( chainlinkptr )
			IF VERBOSE THEN print, 'deleted link at beginning of multilink chain'
			chainlinkptr = chain_start_finder( next )
		endif else begin
			; Depointer the link to be deleted.
			result = depointer( chainlinkptr )
			IF VERBOSE THEN print, 'deleted the only link in the chain'
			chainlinkptr = PTR_NEW()
		endelse
	endelse
	return, chainlinkptr
end

function chain_link_add, chainlinkptr, data, VERBOSE=verbose
	; chainlinkptr can be any link in the chain.

	IF SIZE(verbose,/TYPE) GT 0 THEN verbose=verbose ELSE verbose=0

	if chain_link_counter( chainlinkptr ) eq 0 then begin
		; Start new chain.
		IF VERBOSE THEN print,'start new chain'
		newlink = { $
			prev	: ptr_new(), $
			next	: ptr_new(), $
			data	: ptr_new() }
		newend = ptr_new( newlink )			; , /NO_COPY )
		(*newend).data = ptr_new( data )		; , /NO_COPY )
	endif else begin
		; Create new link and append to end of existing chain.
		newlink = { $
			prev	: ptr_new(), $
			next	: ptr_new(), $
			data	: ptr_new() }
		newend = ptr_new( newlink )			; , /NO_COPY )
		oldend = chain_end_finder( chainlinkptr )
		(*oldend).next = newend
		(*newend).prev = oldend

		; Set newlink data tag to data.
		(*newend).data = ptr_new( data )		; , /NO_COPY )
	endelse

	return, newend
end