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