SUBROUTINE ADDBOX(CURPTR,BOXPTR,PTR)
C
      IMPLICIT DOUBLE PRECISION (A-H,O-Z)
C
C Written by:
C
C   R. Baker Kearfott
C
C         and
C
C   Manuel Novoa III
C
C   Department of Mathematics
C   U.S.L. Box 4-1010
C   Lafayette, LA 70504
C
C   September 29, 1987
C
C Part of the generalized bisection package
C (linked list and stack operations subpackage).
C
C***********************************************************************
C
C Called by -- ROOTS, DELLST
C
C***********************************************************************
C
C Function --
C
C  This routine inserts a box (with pointer BOXPTR) into a linked
C  list (after the box with pointer CURPTR).
C
C***********************************************************************
C
C Argument declarations --
C
      INTEGER CURPTR, BOXPTR, PTR(2,*)
C
C***********************************************************************
C
C Argument descriptions -- (INPUT  = set on entry and not alterable)
C                          (OUTPUT = to be set by the routine)
C                          (I/O    = set on entry but alterable)
C
C CURPTR    is the pointer of the box in the list after which the new
C           box is to be inserted.
C           (INPUT)
C
C BOXPTR    is the pointer of the box to be inserted.
C           (INPUT)
C
C PTR       contains the pointer values of the previous and next
C           boxes currently in linked lists.
C           (I/O)
C
C***********************************************************************
C
C Internal variable declarations --
C
      INTEGER TMPPTR
C
C***********************************************************************
C
C Common block declarations -- none
C
C***********************************************************************
C
C Fortran-supplied functions and subroutines -- none
C
C***********************************************************************
C
C Package-supplied functions and subroutines -- none
C
C***********************************************************************
C
C User-supplied functions and subroutines -- none
C
C***********************************************************************
C
C I/O functions -- none
C
C***********************************************************************
C
C Internal constant declarations --
C
      INTEGER PREV, NEXT, EOLIST
      DATA PREV/1/, NEXT/2/, EOLIST/0/
C
C***********************************************************************
C
C Internal constant descriptions --
C
C PREV   PTR(PREV,BOXPTR) is the pointer corresponding to the box
C        in the linked list at BOXPTR.
C
C NEXT   PTR(NEXT,BOXPTR) is the pointer corresponding to the box
C        following the box in the linked list at BOXPTR.
C
C EOLIST is the end-of-list pointer.
C
C***********************************************************************
C
C Beginning of executable statements --
C
      TMPPTR = PTR(NEXT,CURPTR)
      PTR(PREV,BOXPTR) = CURPTR
      PTR(NEXT,BOXPTR) = TMPPTR
      PTR(NEXT,CURPTR) = BOXPTR
      IF (TMPPTR.NE.EOLIST) PTR(PREV,TMPPTR) = BOXPTR
C
      RETURN
      END
C***********************************************************************
C***********************************************************************
      SUBROUTINE ALLOC(BOXPTR,MAXLST,UNUSED)
C
      IMPLICIT DOUBLE PRECISION (A-H,O-Z)
C
C Written by:
C
C   R. Baker Kearfott
C
C         and
C
C   Manuel Novoa III
C
C   Department of Mathematics
C   U.S.L. Box 4-1010
C   Lafayette, LA 70504
C
C   September 29, 1987
C
C Part of the generalized bisection package
C (linked list and stack operations subpackage).
C
C***********************************************************************
C
C Called by -- ROOTS, DELLST
C
C***********************************************************************
C
C Function --
C
C  This routine allocates a box from the linked list and passes its
C  pointer back to the calling routine.   If there are is no free
C  space in the list, the routine returns end-of-list pointer.
*
C
C***********************************************************************
C
C Argument declarations --
C
      INTEGER BOXPTR, MAXLST
      LOGICAL UNUSED(MAXLST)
C
C***********************************************************************
C
C Argument descriptions -- (INPUT  = set on entry and not alterable)
C                          (OUTPUT = to be set by the routine)
C                          (I/O    = set on entry but alterable)
C
C BOXPTR    is set to the pointer of the allocated box on return.
C           (OUTPUT)
C
C MAXLST    is the total allowable number of nodes in the linked
C           list.
C           (INPUT)
C
C UNUSED    UNUSED(I) is set to .TRUE. if the list space corresponding
C           to pointer I is not occupied; and UNUSED(I) is set to
C           .FALSE. otherwise.
C           (I/O)
C
C***********************************************************************
C
C Internal variable declarations -- none
C
C***********************************************************************
C
C Common block declarations -- none
C
C***********************************************************************
C
C Fortran-supplied functions and subroutines -- none
C
C***********************************************************************
C
C Package-supplied functions and subroutines -- none
C
C***********************************************************************
C
C User-supplied functions and subroutines -- none
C
C***********************************************************************
C
C I/O functions -- none
C
C***********************************************************************
C
C Internal constant declarations --
C
      INTEGER EOLIST
      DATA EOLIST/0/
C
C***********************************************************************
C
C Internal constant descriptions --
C
C  EOLIST   is the end-of-list pointer.
C
C***********************************************************************
C
C Beginning of executable statements --
C
C  Attempt to find an unused location in the linked list;  return
C  with its pointer if one is found.
C
      DO 10 BOXPTR = 1, MAXLST
         IF (UNUSED(BOXPTR)) THEN
            UNUSED(BOXPTR) = .FALSE.
            RETURN
         END IF
  10  CONTINUE
C
C  Return with the end-of-list pointer when no locations are free.
C
      BOXPTR = EOLIST
C
      RETURN
      END
C***********************************************************************
C***********************************************************************
      SUBROUTINE DELBOX(BOXPTR,PTR)
C
      IMPLICIT DOUBLE PRECISION (A-H,O-Z)
C
C Written by:
C
C   R. Baker Kearfott
C
C         and
C
C   Manuel Novoa III
C
C   Department of Mathematics
C   U.S.L. Box 4-1010
C   Lafayette, LA 70504
C
C   September 29, 1987
C
C Part of the generalized bisection package
C (linked list and stack operations subpackage).
C
C***********************************************************************
C
C Called by -- DELLST
C
C***********************************************************************
C
C Function --
C
C  This routine removes the box at pointer BOXPTR from a linked
C  list.
C
C***********************************************************************
C
C Argument declarations --
C
      INTEGER BOXPTR, PTR(2,*)
C
C***********************************************************************
C
C Argument descriptions -- (INPUT  = set on entry and not alterable)
C                          (OUTPUT = to be set by the routine)
C                          (I/O    = set on entry but alterable)
C
C BOXPTR    is the pointer of the box to be removed from the list.
C           (INPUT)
C
C PTR       contains the pointer values of the previous and next
C           boxes currently in linked lists.
C           (I/O)
C
C***********************************************************************
C
C Internal variable declarations --
C
      INTEGER TPTR1, TPTR2
C
C***********************************************************************
C
C Common block declarations -- none
C
C***********************************************************************
C
C Fortran-supplied functions and subroutines -- none
C
C***********************************************************************
C
C Package-supplied functions and subroutines -- none
C
C***********************************************************************
C
C User-supplied functions and subroutines -- none
C
C***********************************************************************
C
C I/O functions -- none
C
C***********************************************************************
C
C Internal constant declarations --
C
      INTEGER PREV, NEXT, EOLIST
      DATA PREV/1/, NEXT/2/, EOLIST/0/
C
C***********************************************************************
C
C Internal constant descriptions --
C
C PREV   PTR(PREV,BOXPTR) is the pointer corresponding to the box
C        in the linked list at BOXPTR.
C
C NEXT   PTR(NEXT,BOXPTR) is the pointer corresponding to the box
C        following the box in the linked list at BOXPTR.
C
C EOLIST is the end-of-list pointer.
C
C***********************************************************************
C
C Beginning of executable statements --
C
      TPTR1 = PTR(PREV,BOXPTR)
      TPTR2 = PTR(NEXT,BOXPTR)
      PTR(NEXT,TPTR1) = TPTR2
      IF (TPTR2.NE.EOLIST) PTR(PREV,TPTR2) = TPTR1
C
      RETURN
      END
C***********************************************************************
C***********************************************************************
      SUBROUTINE FREE(BOXPTR,MAXLST,UNUSED)
C
      IMPLICIT DOUBLE PRECISION (A-H,O-Z)
C
C Written by:
C
C   R. Baker Kearfott
C
C         and
C
C   Manuel Novoa III
C
C   Department of Mathematics
C   U.S.L. Box 4-1010
C   Lafayette, LA 70504
C
C   September 29, 1987
C
C Part of the generalized bisection package
C (linked list and stack operations subpackage).
C
C***********************************************************************
C
C Called by -- DELLST
C
C***********************************************************************
C
C Function --
C
C  This routine sets UNUSED(BOXPTR) to .TRUE. to indicate that
C  the space in the linked list at BOXPTR is not occupied.
C
C***********************************************************************
C
C Argument declarations --
C
      INTEGER BOXPTR, MAXLST
      LOGICAL UNUSED(MAXLST)
C
C***********************************************************************
C
C Argument descriptions -- (INPUT  = set on entry and not alterable)
C                          (OUTPUT = to be set by the routine)
C                          (I/O    = set on entry but alterable)
C
C BOXPTR    is set to the pointer of the box to be removed.
C           (INPUT)
C
C MAXLST MAXLST - 2 is the maximum number of root-containing boxes which
C        can be stored.
C           (INPUT)
C
C UNUSED    UNUSED(I) is set to .TRUE. if the list space corresponding
C           to pointer I is not occupied; and UNUSED(I) is set to
C           .FALSE. otherwise.
C           (I/O)
C
C***********************************************************************
C
C Internal variable declarations -- none
C
C***********************************************************************
C
C Common block declarations -- none
C
C***********************************************************************
C
C Fortran-supplied functions and subroutines -- none
C
C***********************************************************************
C
C Package-supplied functions and subroutines -- none
C
C***********************************************************************
C
C User-supplied functions and subroutines -- none
C
C***********************************************************************
C
C I/O functions -- none
C
C***********************************************************************
C
C Internal constant declarations --
C
      INTEGER EOLIST
      DATA EOLIST/0/
C
C***********************************************************************
C
C Internal constant descriptions --
C
C  EOLIST   is the end-of-list pointer.
C
C***********************************************************************
C
C Beginning of executable statements --
C
      IF ( (BOXPTR.GT.0) .AND. (BOXPTR.LE.MAXLST) ) THEN
         UNUSED(BOXPTR) = .TRUE.
      END IF
C
      RETURN
      END
C***********************************************************************
C***********************************************************************
      SUBROUTINE POP(N,BOX,MAXDP,DEPTH,LEVEL,STACK,STKLVL,ERRFLG,ERRVAL)
C
      IMPLICIT DOUBLE PRECISION (A-H,O-Z)
C
C Written by:
C
C   R. Baker Kearfott
C
C         and
C
C   Manuel Novoa III
C
C   Department of Mathematics
C   U.S.L. Box 4-1010
C   Lafayette, LA 70504
C
C   September 29, 1987
C
C Part of the generalized bisection package
C (linked list and stack operations subpackage).
C
C***********************************************************************
C
C Called by -- ROOTS
C
C***********************************************************************
C
C Function --
C
C  This routine pops a box from the stack of boxes which are still
C  to be considered, and adjusts the depth of the stack accordingly.
C
C***********************************************************************
C
C Argument declarations --
C
      INTEGER N
      DOUBLE PRECISION BOX(2,N)
      INTEGER MAXDP, DEPTH, LEVEL
      DOUBLE PRECISION STACK(2,N,MAXDP)
      INTEGER STKLVL(MAXDP), ERRFLG, ERRVAL
C
C***********************************************************************
C
C Argument descriptions -- (INPUT  = set on entry and not alterable)
C                          (OUTPUT = to be set by the routine)
C                          (I/O    = set on entry but alterable)
C
C N      is the number of equations and variables.
C        (INPUT)
C
C BOX    On return, BOX(1,I) will contain the left endpoint of the I-th
C        coordinate interval and BOX(2,I) will contain the right
C        endpoint of the I-th coordinate interval of the box taken
C        from the stack, for I between 1 and N.
C        (OUTPUT)
C
C MAXDP  is the maximum allowable depth of the stack.
C        (INPUT)
C
C DEPTH  is the current depth of the stack.
C        (I/O)
C
C LEVEL  is the current level in the binary subdivision tree.
C        (I/O)
C
C STACK  STACK(*,*,I) contains the box at depth I-1 in the stack
C        of boxes the algorithm has not yet processed.
C        (I/O)
C
C STKLVL STKLVL(I) contains the level in the binary search tree
C        corresponding to the box in STACK(*,*,I).
C        (I/O)
C
C ERRFLG Upon return, ERRFLG is set to 11 if the stack is empty,
C        and is set to 0 otherwise.
C        (OUTPUT)
C
C ERRVAL contains additional error information.
C        (OUTPUT)
C
C***********************************************************************
C
C Internal variable declarations -- none
C
C***********************************************************************
C
C Common block declarations -- none
C
C***********************************************************************
C
C Fortran-supplied functions and subroutines -- none
C
C***********************************************************************
C
C Package-supplied functions and subroutines --
C
C  DCOPY (from LINPACK)
C
C***********************************************************************
C
C User-supplied functions and subroutines -- none
C
C***********************************************************************
C
C I/O functions -- none
C
C***********************************************************************
C
C Internal constant declarations --
C
      INTEGER NTTWO
C
C***********************************************************************
C
C Beginning of executable statements --
C
      NTTWO = N * 2
C
      IF ((DEPTH.LT.0).OR.(DEPTH.GT.MAXDP)) THEN
         ERRFLG = 13
         ERRVAL = DEPTH
      ELSE
         IF (DEPTH.EQ.0) THEN
            ERRFLG = 11
            ERRVAL = DEPTH
         ELSE
            ERRFLG = 0
            CALL DCOPY(NTTWO,STACK(1,1,DEPTH),1,BOX,1)
            LEVEL = STKLVL(DEPTH)
            DEPTH = DEPTH - 1
         END IF
      END IF
C
      RETURN
      END
C***********************************************************************
C***********************************************************************
      SUBROUTINE PUSH(N,BOX,MAXDP,DEPTH,LEVEL,STACK,STKLVL,ERRFLG,
     1                ERRVAL)
C
      IMPLICIT DOUBLE PRECISION (A-H,O-Z)
C
C Written by:
C
C   R. Baker Kearfott
C
C         and
C
C   Manuel Novoa III
C
C   Department of Mathematics
C   U.S.L. Box 4-1010
C   Lafayette, LA 70504
C
C   September 29, 1987
C
C Part of the generalized bisection package
C (linked list and stack operations subpackage).
C
C***********************************************************************
C
C Called by -- ROOTS AND FTESTH
C
C***********************************************************************
C
C Function --
C
C  This routine places a box onto the stack of boxes the algorithm needs
C  to process later.  It also stores the level in the binary
C  subdivision tree corresponding to this box.
C
C***********************************************************************
C
C Argument declarations --
C
      INTEGER N
      DOUBLE PRECISION BOX(2,N)
      INTEGER MAXDP, DEPTH, LEVEL
      DOUBLE PRECISION STACK(2,N,MAXDP)
      INTEGER STKLVL(MAXDP), ERRFLG, ERRVAL
C
C***********************************************************************
C
C Argument descriptions -- (INPUT  = set on entry and not alterable)
C                          (OUTPUT = to be set by the routine)
C                          (I/O    = set on entry but alterable)
C
C N      is the number of equations and variables.
C        (INPUT)
C
C BOX    BOX(1,I) contains the left endpoint of the I-th coordinate
C        interval and BOX(2,I) will contain the right endpoint of
C        the I-th coordinate interval of the box to be placed on the
C        the stack, for I between 1 and N.
C        (OUTPUT)
C
C MAXDP  is the maximum allowable depth of the stack.
C        (INPUT)
C
C DEPTH  is the current depth of the stack.
C        (I/O)
C
C LEVEL  is the current level in the binary subdivision tree.
C        (I/O)
C
C STACK  STACK(*,*,I) contains the box at depth I-1 in the stack
C        of boxes the algorithm has not yet processed.
C        (I/O)
C
C STKLVL STKLVL(I) contains the level in the binary search tree
C        corresponding to the box in STACK(*,*,I).
C        (I/O)
C
C ERRFLG On return, ERRFLG is set to 10 if a stack overflow occurs;
C        ERRFLG is set to 0 otherwise.
C        (OUTPUT)
C
C ERRVAL contains additional error information.
C        (OUTPUT)
C
C***********************************************************************
C
C Internal variable declarations -- none
C
C***********************************************************************
C
C Common block declarations -- none
C
C***********************************************************************
C
C Fortran-supplied functions and subroutines -- none
C
C***********************************************************************
C
C Package-supplied functions and subroutines --
C
C  DCOPY (from LINPACK)
C
C***********************************************************************
C
C User-supplied functions and subroutines -- none
C
C***********************************************************************
C
C I/O functions -- none
C
C***********************************************************************
C
C Internal constant declarations --
C
      INTEGER NTTWO
C
C***********************************************************************
C
C Beginning of executable statements --
C
      NTTWO = N * 2
C
      IF ((DEPTH.LT.0).OR.(DEPTH.GE.MAXDP)) THEN
         ERRFLG = 12
         ERRVAL = DEPTH
      ELSE
         IF (DEPTH.EQ.MAXDP-1) THEN
            ERRFLG = 10
            ERRVAL = MAXDP
         ELSE
            ERRFLG = 0
         END IF
         DEPTH = DEPTH + 1
         CALL DCOPY(NTTWO,BOX,1,STACK(1,1,DEPTH),1)
         STKLVL(DEPTH) = LEVEL
      END IF
C
      RETURN
      END