;*****************************************************************
;* this class implements a linked list
;* 
;* each node of the list defines the following 2 pointers:
;*  p_val:  points to the node's data
;*  p_next: points to next node or is NULL for the last node
;*
;* the value pointer of the first node, which exists as long as 
;*  the object exists, points to an anonymous structure with the
;*  name (string) and id (int) of the linked list object.
;*
;* written by D. Frieauff on 28. August 1997
;*****************************************************************

;get llist id string
function llist::id_string
  p_val = self.p_val
  id_string = '''' + (*p_val).name + ''' , id: ' + strtrim((*p_val).id, 2)
  return, id_string
  end

;initialize llist
function llist::init, name, id
  self.p_val = ptr_new({name: name, id: id})
  return, 1B
  end

;destroy node content
pro llist::destroy_node, p
  if not ptr_valid(p) then return
  case type(*p) of
    8: begin	;structure
       endcase
    10: begin	;pointer
        ptr_free, *p
        endcase
    11: begin	;object
        obj_destroy, *p
        endcase
    else:
    endcase
  ptr_free, p
  end

;destroy all llist nodes
; destroy node content(s), if keyword "destroy" specified
pro llist::cleanup, destroy = destroy
  p_val = self.p_val
  p_node = self.p_next
  while ptr_valid(p_node) do begin
    if ptr_valid(p_val) and keyword_set(destroy) then $
       self->destroy_node, p_val
    node = *p_node
    ptr_free, p_node
    p_val = node.p_val
    p_node = node.p_next
    endwhile
  if ptr_valid(p_val) then ptr_free, p_val
  end

;print value of all nodes
pro llist::print
  print, 'Dump of linked list ' + self->id_string()
  p_node = self.p_next
  node_cnt = 0L
  while ptr_valid(p_node) do begin
    node = *p_node
    t = ' node: ' + strtrim(node_cnt, 2)
    if ptr_valid(node.p_val) then $
       print, t + ' value: ', *node.p_val $
      else $
       print, t + ' *** invalid value pointer ***'
    p_node = node.p_next
    node_cnt = node_cnt + 1L
    endwhile
  print, 'End of dump'
  print
  end

;collect all value pointers (except from ll head)
function llist::get_pointers, p_arr
  p_arr_ = ptr_new()
  p_node = self.p_next
  while ptr_valid(p_node) do begin
    node = *p_node
    p_arr_ = [p_arr_, node.p_val]
    p_node = node.p_next
    endwhile
  c = n_elements(p_arr_)
  if c gt 1 then p_arr = p_arr_(1:*)
  return, c-1
  end

;append new node with value pointer 'p_val'
pro llist::append, p_val
  p_prev = (p_node = self.p_next)
  while ptr_valid(p_node) do begin
    p_prev = p_node
    p_node = (*p_prev).p_next
    endwhile
  p_new = ptr_new({llist})
  (*p_new).p_val = p_val
  if not ptr_valid(p_prev) then $
     self.p_next = p_new else (*p_prev).p_next = p_new
  end

;insert new node with value pointer 'p_val' on top
pro llist::insert_top, p_val
  p_new = ptr_new({llist})
  (*p_new).p_val = p_val
  (*p_new).p_next = self.p_next
  self.p_next = p_new
  end

;insert new node with value pointer 'p_val'
; behind node with value pointer 'p_ref'
pro llist::insert_behind, p_ref, p_val
  found = 0B
  p_node = self.p_next
  while ptr_valid(p_node) and not found do begin
    found = (*p_node).p_val eq p_ref
    if found then begin
       p_new = ptr_new({llist})
       (*p_new).p_val = p_val
       (*p_new).p_next = (*p_node).p_next
       (*p_node).p_next = p_new
       endif
    p_node = (*p_node).p_next
    endwhile
  end

;remove and destroy first node
pro llist::delete_top, destroy = destroy
  p_node = self.p_next
  if ptr_valid(p_node) then begin
     self.p_next = (*p_node).p_next
     if ptr_valid((*p_node).p_val) and keyword_set(destroy) then $
        self->destroy_node, (*p_node).p_val
     ptr_free, p_node
     endif
  end

;remove and destroy node with value pointer 'p_ref'
pro llist::delete, p_ref, destroy = destroy
  found = 0B
  p_node = self.p_next
  p_prev = ptr_new()
  while ptr_valid(p_node) and not found do begin
    found = (*p_node).p_val eq p_ref
    if not found then begin
       p_prev = p_node
       p_node = (*p_node).p_next
       endif
    endwhile
  if found and ptr_valid(p_node) then begin
     if ptr_valid(p_prev) then $
        (*p_prev).p_next = (*p_node).p_next $
       else $
        self.p_next = (*p_node).p_next
     if ptr_valid((*p_node).p_val) and keyword_set(destroy) then $
        self->destroy_node, (*p_node).p_val
     ptr_free, p_node
     endif
  end

function llist::size
  p_node = self.p_next
  node_cnt = 0L
  while ptr_valid(p_node) do begin
    p_node = (*p_node).p_next
    node_cnt = node_cnt + 1L
    endwhile
  return, node_cnt
  end

;defines the object structure for a linked list object
pro llist__define
  llist = {llist,			$
	   p_val: ptr_new(),		$; pointer to node value
           p_next: ptr_new()		$; pointer to next llist element
           }

  end



