PRO xlist_base_node__define

struct = {XLIST_BASE_NODE,		$ ; Name of the node structure.
   name:"",				$ ; Name is limited to strings for this object.
   next:PTR_NEW (), 			$ ; Pointer to the next node in the xlist.
   prev:PTR_NEW ()			$ ; Pointer to the previous node in the xlist.
   }

END

; ------------------------------------------------------------------------------------------------

FUNCTION xlist::init

; Set the size of the xlist to 0.  Nothing else to do.

self.size = 0

RETURN, 1

END

; ------------------------------------------------------------------------------------------------

PRO xlist::cleanup

; Just call the clear method to delete all the nodes.

self->clear

; Were done!

RETURN

END

; ------------------------------------------------------------------------------------------------

PRO xlist::clear

; If the xlist is empty, then just return.

IF self.size EQ 0 THEN RETURN

; Set ptr to point to the first node on the xlist.

ptr = self.first

; Loop to move through the entire xlist, deleting each node as it is encountered.

WHILE ptr NE self.null DO BEGIN

; Set tmp to point to subsequent node in the xlist.

   tmp = (*ptr).next

; Free the heap space used by the node.
 
   PTR_FREE, ptr

; Move ptr to point to the next node in the xlist (pointed to by tmp).

   ptr = tmp

ENDWHILE

; Reset size to 0.

self.size = 0

; Reset the first and last pointers.

self.first = self.null
self.last  = self.null
  
; All done. 

RETURN

END

; ------------------------------------------------------------------------------------------------

PRO xlist::add, node

; Make sure that node exists.  If node does not exist, then simply return (silent error).

IF N_ELEMENTS (node) EQ 0 THEN RETURN

; Check if there are any items on the xlist.
; If it is empty then we have to begin the list from scratch.

IF self.size EQ 0 THEN BEGIN

; Empty xlist. Create the node that was passed to us as a parameter will be the first and
; only node on the xlist.

   ptr = PTR_NEW (node)
   (*ptr).next = self.null
   (*ptr).prev = self.null

   self.first = ptr
   self.last  = self.first

ENDIF ELSE BEGIN

; Ok, there are already some nodes.  First check to make sure we are not adding 
; a named node to the xlist with the same name as a node already on the  xlist.  
; If we are then just return.

   IF self->search (node.name) THEN RETURN

; Now decide if need insert the new node at the begining, in the middle or at the end of the
; xlist.  We will first check for an insertion at the start or end of the list.

; Set the flags for first, middle and last to 0 (FALSE).

   first  = 0
   last   = 0
   middle = 0

; Check for insertion at the begining of the xlist.

   IF node.name LT (*self.first).name THEN first = 1

; Check for insertion at the end of the xlist.

   IF node.name GT (*self.last).name  THEN last = 1

; Check if neither first nor last is set.  If neither is, then we have to insert our
; node in the middle of the xlist.

   IF NOT first AND NOT last THEN BEGIN 

; Set the flag middle.

      middle = 1

; Now search through the xlist looking for the correct place to add new node. 
; Begin by setting loc to point to the first node on the xlist.  Also set found 
; to 0, this will cause the loop to exit when the correct location to insert
; the node has been found.

      loc  = self.first
      found = 0

; Loop to move through the entire xlist, checking each node to make sure that it is
; located prior to name according to the ascii collating sequence.

      WHILE NOT found AND loc NE self.null DO BEGIN

; Check if str should lexically come before the node pointed to by ptr.

         IF node.name LT (*loc).name THEN BEGIN

; OK, found where to insert the node.  Move loc back one node.

            loc = (*loc).prev 

; Set found to 1 and get out of the loop.

            found = 1

         ENDIF ELSE BEGIN

; Otherwise, move loc to point to the next node on the list.
 
            loc = (*loc).next

         ENDELSE

      ENDWHILE
  
   ENDIF

; Creat the new node.

   ptr = PTR_NEW (node)
   
; Check where we should insert the the new node (according to which flag is set --
; first, last or middle) and then insert the node in the proper place.

  IF first THEN BEGIN        ; Insert the node at the begining of the xlist. ; 

; Set up the pointers in the new node. 

     (*ptr).next = self.first
     (*ptr).prev = self.null

; Insert the new node at the beginning of the list.

     (*self.first).prev = ptr
     self.first = ptr

  ENDIF 

 IF last THEN BEGIN        ; Insert the node at the end of the xlist.

; Set up the pointers in the new node. 

     (*ptr).next = self.null
     (*ptr).prev = self.last

; Insert the new node at the end of the list.

     (*self.last).next = ptr
     self.last = ptr

  ENDIF 

  IF middle THEN BEGIN      ; Insert the node in the middle of the xlist. 

; Set up the pointers in the new node. 

     (*ptr).next = (*loc).next
     (*ptr).prev = loc

; Insert the new node into the list.

     (*(*loc).next).prev = ptr
     (*loc).next = ptr

  ENDIF

ENDELSE

; Increment the size counter of the list.

self.size = self.size + 1

; Were done! returning...

RETURN

END

; ------------------------------------------------------------------------------------------------

FUNCTION xlist::list, tag, EMPTY = empty

; First, check if the xlist is empty.  If it is then we will just return -1.

IF self.size EQ 0 THEN BEGIN

   IF N_ELEMENTS (empty) NE 0 THEN empty = 1

   return, -1 

ENDIF

; Check if tag is defined.  If it is not defined, then we will set it to
; name, which is a field that must exist.

IF N_ELEMENTS (tag) EQ 0 THEN tag = 'name'

; Get the names of all the tags of the structure being kept in the xlist

tlst = TAG_NAMES (*self.first)

; Check whether tag is a string or a number, we handle it different depending on 
; what type of variable tag is.

s = SIZE (tag) & type = s [s [0] + 1]

; Check if tag is a number. If it is then it must be an index into the structure.

IF type NE 7 THEN BEGIN

; Check that there are enough fields in the structure for tag to properly index it.
; If it is, then copy the value of tag into ind (which is what the rest of the 
; procedure actually uses).

   IF N_TAGS (*self.first) GT tag THEN BEGIN

      ind = tag

   ENDIF ELSE BEGIN

; Otherwise tag referes to a non-existent index.  In this case set ind to be
; index of the name field (which we know must exist).

      ind = WHERE (tlst EQ 'NAME')

   ENDELSE

ENDIF ELSE BEGIN

; OK, tag is a string so it must refer to a field name.  Get the index
; of the field that tag refers to.

   ind =  WHERE (tlst EQ STRUPCASE (tag))

; Make sure that tag refered to valid field.  If it did not, then ind will now be
; set -1.  In this case set ind to be the index of the name field (which we know 
; must exist).

   IF ind [0] EQ -1 THEN ind = WHERE (tlst EQ 'NAME')

ENDELSE

; Make sure ind is a scaler

ind = ind [0]

; Create an array of the correct type to hold the contents of the the requested 
; field from each node in the xlist.

list = REPLICATE ((*self.first).(ind [0]), self.size)

; Now loop through the  entire structure and get the all the name strings. 
; Set ptr to point to the first node on the xlist.
; Use cnt to keep count of which node we are accessing.

ptr = self.first
cnt = 0

; Loop to move through the entire xlist, copy in the name tag from each node into the
; array list.

WHILE ptr NE self.null DO BEGIN

; Copy the string from the node into the array list.

   list [cnt] = (*ptr).(ind)

; Move ptr to point to the next node in the xlist.

   ptr = (*ptr).next

; Increment cnt by 1.

   cnt = cnt + 1

ENDWHILE

; Return the list of values we just extracted.

RETURN, list

END

; ------------------------------------------------------------------------------------------------

FUNCTION xlist::search, val

; If the xlist is empty, then just return 0 (FALSE).

IF self.size EQ 0 THEN RETURN, 0

; Force val to be a string.  In the process, remove leading and trailing blanks.

str = STRTRIM (STRING (val), 1)

; Now we need to search through the xlist looking for the requested string.
; Begin by seting ptr to point to the first node on the xlist.

ptr   = self.first

; Loop to move through the entire xlist, checking to see if its name tag is set to
; the requested string.  The loop ends all nodes have been searched.  Finding a node 
; name tag that would occur prior to the search sting using the the ASCII collating 
; sequence or finding the node that is the target of the search will cause the function 
; to immediately return a result.

WHILE ptr NE self.null DO BEGIN

; Check if search target is contained within the current node.
; If it is then we are done.

   IF str EQ (*ptr).name THEN RETURN, 1

; Check if str should lexically come before the node pointed to by ptr.  If it does,
; then the target is not in the xlist and there is no point in continueing the search.

   IF str LT (*ptr).name THEN RETURN, 0

; Otherwise, move pointer to point to the next node on the list.
 
   ptr = (*ptr).next

ENDWHILE

; Oops. The search failed. Return 0.

RETURN, 0

END

; ------------------------------------------------------------------------------------------------

FUNCTION xlist::get, val

; If the xlist is empty, then just return 0 (FALSE).

IF self.size EQ 0 THEN RETURN, 0

; Force val to be a string.  In the process, remove leading and trailing blanks.

str = STRTRIM (STRING (val), 1)

; Now we need to search through the xlist looking for the requested string.
; Begin by seting ptr to point to the first node on the xlist.

ptr   = self.first

; Loop to move through the entire xlist, checking to see if its name tag is set to
; the requested string.  The loop ends all nodes have been searched.  Finding a node 
; name tag that would occur prior to the search sting using the the ASCII collating 
; sequence or finding the node that is the target of the search will cause the function 
; to immediately return a result.

WHILE ptr NE self.null DO BEGIN

; Check if search target is contained within the current node.
; If it is then make a copy of it and return it.

   IF str EQ (*ptr).name THEN RETURN, REPLICATE ((*ptr), 1)

; Check if str should lexically come before the node pointed to by ptr.  If it does,
; then the target is not in the xlist and there is no point in continueing the search.

   IF str LT (*ptr).name THEN RETURN, 0

; Otherwise, move pointer to point to the next node on the list.
 
   ptr = (*ptr).next

ENDWHILE

; Oops. The search failed. Return 0.

RETURN, 0

END

; ------------------------------------------------------------------------------------------------

FUNCTION xlist::unlink, val

; If the xlist is empty, then just return a NULL.

IF self.size EQ 0 THEN RETURN, self.null

; Make sure that val exists.  If val does not exist, then return a NULL

IF N_ELEMENTS (val) EQ 0 THEN RETURN, self.null

; Force val to be a string.  In the process, remove leading and trailing blanks.

str = STRTRIM (STRING (val), 1)

; Now we need to search through the xlist looking for the requested string.
; Begin by seting ptr to point to the first node on the xlist.

ptr = self.first

; Loop to move through the entire xlist, checking to see if its name tag is set to
; the requested string.  The loop ends all nodes have been searched.  Finding a node 
; name tag that would occur prior to the search sting using the the ASCII collating 
; sequence or finding the node that is the target of the search will cause the function 
; to immediately return a result.

WHILE ptr NE self.null DO BEGIN

; Check if search target is contained within the current node.
; If it is then we have to remove it.

   IF str EQ (*ptr).name THEN BEGIN

; Unlink the node from the xlist.  How we handle this task depends on the position
; of the node within the xlist.  Special cases are the node is the first node on the
; list, the last node on the list or there is only one node on the list.  The nominal
; case is that the node is in the middle of the list.  After unlinking the node, we
; will then do an unconditional jump to the part of the routine that cleans up the
; the node and returns a pointer to it.

      IF self.size EQ 1 THEN BEGIN      ; The xlist consist of a single node.

; Unlink the requested node from the the xlist.

         self.first = self.null
         self.last  = self.null

; Jump to the final cleanup and return a pointer to the node.

         GOTO, CLEANUP

      ENDIF 

      IF ptr EQ self.first THEN BEGIN   ; The node is the first node on the list.

; Unlink the requested node from the the xlist.

         self.first = (*ptr).next
         (*self.first).prev = self.null

; Jump to the final cleanup and return a pointer to the node.

         GOTO, CLEANUP

      ENDIF 

      IF ptr EQ self.last THEN  BEGIN   ; The node is the last node on the list.

; Unlink the requested node from the the xlist.

         self.last = (*ptr).prev
         (*self.last).next = self.null

; Jump to the final cleanup and return a pointer to the node.

         GOTO, CLEANUP

      ENDIF 

; Nominal Case                            The node is in the middle of the list. 

; Unlink the requested node from the the xlist.

      (*(*ptr).next).prev = (*ptr).prev
      (*(*ptr).prev).next = (*ptr).next

; Do the final cleanup and return a pointer to the node.

CLEANUP:

; Set the next and prev pointers in the node to NULL.  

      (*ptr).prev = self.null
      (*ptr).next = self.null

; Decreement the count of the number of nodes on the xlist by 1

      self.size = self.size - 1

; Return the pointer to the node we just unlinked.

      RETURN, ptr     

   ENDIF

; Check if str should lexically come before the node pointed to by ptr.  If it does,
; then the target is not in the xlist and there is no point in continueing the search.

   IF str LT (*ptr).name THEN RETURN, self.null

; Otherwise, move pointer to point to the next node on the list.
 
   ptr = (*ptr).next

ENDWHILE

; Oops. The search failed. Return a NULL.

RETURN, self.null

END

; ------------------------------------------------------------------------------------------------

FUNCTION xlist::size 

; Return the number of node in the xlist.

RETURN, self.size

END

; ------------------------------------------------------------------------------------------------

PRO xlist__define

struct = {XLIST, 			$ ; Name of the object structure.
          first: PTR_NEW (),		$ ; Pointer to first node on the xlist.
          last:  PTR_NEW (),		$ ; Pointer to last node on the xlist.
          null:  PTR_NEW (),		$ ; NULL pointer definition
          size: 0			$ ; Number of nodes in the xlist.
         }

END