c
c     http://www.netlib.org/fmm/spline.f
c
      subroutine spline(n, x, y, b, c, d)
      integer n
      double precision x(n), y(n), b(n), c(n), d(n)
c
      integer nmi, ib, i
      double precision t
c
      nmi = n-1
      if ( n .lt. 2 ) return
      if ( n .lt. 3 ) goto 50
c
      d(1) = x(2) - x(1)
      c(2) = ( y(2) - y(1) ) / d(1)
      do 10 i = 2,nmi
        d(i) = x(i+1) - x(i)
        b(i) = 2.0*(d(i-1)+d(i))
        c(i+1) = (y(i+1)-y(i))/d(i)
        c(i) = c(i+1)-c(i)
   10 continue
c
      b(1) = -d(1)
      b(n) = -d(n-1)
      c(1) = 0.0
      c(n) = 0.0
      if ( n .eq. 3 ) goto 15
      c(1) = c(3) / (x(4)-x(2)) - c(2)/(x(3)-x(1))
      c(n) = c(n-1)/(x(n)-x(n-2)) - c(n-2)/(x(n-1)-x(n-3))
      c(1) = c(1)*d(1)**2/(x(4)-x(1))
      c(n) = -c(n)*d(n-1)**2/(x(n)-x(n-3))
c
   15 do 20 i = 2, n
      t = d(i-1)/b(i-1)
      b(i) = b(i) - t*d(i-1)
      c(i) = c(i) - t*c(i-1)
   20 continue
c
      c(n) = c(n)/b(n)
      do 30 ib = 1, nmi
        i = n - ib
        c(i) = (c(i) - d(i)*c(i+1))/b(i)
   30 continue
c
      b(n) = (y(n) - y(nmi))/d(nmi) + d(nmi)*(c(nmi) + 2.0*c(n))
      do 40 i = 1, nmi
        b(i) = (y(i+1) - y(i))/d(i) - d(i)*(c(i+1) + 2.0*c(i))
        d(i) = (c(i+1)-c(i))/d(i)
        c(i) = 3.0*c(i)
   40 continue
      c(n) = 3.0*c(n)
      d(n) = d(n-1)
      return
c
   50 b(i) = (y(2)-y(1))/(x(2)-x(1))
      c(1) = 0.0
      d(1) = 0.0
      b(2) = b(1)
      c(2) = 0.0
      d(2) = 0.0
      return
      end
c
      double precision function seval(n, u, x, y, b, c, d)
      integer n
      double precision u, x(n), y(n), b(n), c(n), d(n)
c
      integer i, j, k
      double precision dx
      data i/1/
      if ( i .ge. n ) i = 1
      if ( u .lt. x(i) ) goto 10
      if ( u .le. x(i+1) ) goto 30
   10 i = 1
      j = n + 1
   20 k = (i+j)/2
      if ( u .lt. x(k) ) j = k
      if ( u .ge. x(k) ) i = k
      if ( j .gt. i+1 ) goto 20
c
   30 dx = u - x(i)
      seval = y(i) + dx*(b(i) + dx*(c(i) + dx*d(i)))
      return
      end

c same but returns interpolation segment index
c side effect: f=f(u) and fp=f'(u)
      integer function seval1(n, u, x, y, b, c, d, f, fp)
      integer n
      double precision u, x(n), y(n), b(n), c(n), d(n)
      double precision f, fp
c
      integer i, j, k
      double precision dx
      data i/1/
      if ( i .ge. n ) i = 1
      if ( u .lt. x(i) ) goto 10
      if ( u .le. x(i+1) ) goto 30
   10 i = 1
      j = n + 1
   20 k = (i+j)/2
      if ( u .lt. x(k) ) j = k
      if ( u .ge. x(k) ) i = k
      if ( j .gt. i+1 ) goto 20
c
   30 dx = u - x(i)
      f = y(i) + dx*(b(i) + dx*(c(i) + dx*d(i)))
      fp = b(i)+dx*(c(i)*2+dx*(d(i)*3))
      seval1 = i
      return
      end
