bridge/class-master/depend/pari/src/basemath/volcano.c
/* Return a path of length n along the surface of an L-volcano of height h
 * starting from surface node j0.  Assumes (D|L) = 1 where D = disc End(j0).
 *
 * Actually, if j0's endomorphism ring is a suborder, we return the
 * corresponding shorter path. W must hold space for n + h nodes.
 *
 * TODO: have two versions of this function: one that assumes J has the correct
 * endomorphism ring (hence avoiding several branches in the inner loop) and a
 * second that does not and accordingly checks for repetitions */
Return a path of length n along the surface of an L-volcano of height h
starting from surface node j0.  Assumes (D|L) = 1 where D = disc End(j0).

Actually, if j0's endomorphism ring is a suborder, we return the
corresponding shorter path. W must hold space for n + h nodes.

have two versions of this function: one that assumes J has the correct
endomorphism ring (hence avoiding several branches in the inner loop) and a
second that does not and accordingly checks for repetitions
Return a path of length n along the surface of an L - volcano of height h starting from surface node j0 . Assumes ( D|L ) = 1 where D = disc End ( j0 ) . Actually if j0 ' s endomorphism ring is a suborder we return the corresponding shorter path . W must hold space for n + h nodes . have two versions of this function : one that assumes J has the correct endomorphism ring ( hence avoiding several branches in the inner loop ) and a second that does not and accordingly checks for repetitions
static long
surface_path(
  ulong W[],
  long n, GEN phi, long L, long h, ulong J, const ulong *nJ, ulong p, ulong pi)
{
  pari_sp av = avma, bv;
  GEN T, v;
  long j, k, w, x;
  ulong W0;
  W[0] = W0 = J;
  if (n == 1) return 1;
  T = cgetg(h+2, t_VEC); bv = avma;
  v = get_nbrs(phi, L, J, nJ, p, pi);
  if (nJ) v = gerepileupto(bv, vecsmall_prepend(v, *nJ));
  gel(T,1) = v;
  k = vecsmall_len(v);
  switch (k) {
  case 0: pari_err_BUG("surface_path"); 
  case 1:
    if (h) pari_err_BUG("surface_path");
    W[1] = uel(v, 1);
    avma = av;
    if (W[1] == W[0]) return 1;
    return 2;
  case 2:
    if (L == 2)
    { 
      GEN u = get_nbrs(phi, L, uel(v, 1), &J, p, pi);
      long n = vecsmall_len(u) - !!vecsmall_isin(u, J);
      W[1] = n == 1 ? uel(v,1) : uel(v,2);
      avma = av; return 2;
    }
    if (h) pari_err_BUG("surface_path");
    W[1] = uel(v,1); 
    for (w = 2; w < n; w++)
    {
      v = get_nbrs(phi, L, W[w-1], &W[w-2], p, pi);
      if (vecsmall_len(v) != 1) pari_err_BUG("surface_path");
      W[w] = uel(v, 1);
      avma = av; if (W[w] == W0) return w;
    }
    avma = av; return n;
  }
  if (!h) pari_err_BUG("surface_path"); 
  w = 1;
  for (x = 0;; x++)
  {
    W[w] = umael(T, ((w-1) % h) + 1, x + 1);
    if (W[w] == W0) { avma = av; return w; }
    if (x == k-1 && w == n-1) { avma = av; return n; }
    for (j = w;;)
    {
      long m;
      v = get_nbrs(phi, L, W[j], &W[j-1], p, pi);
      m = vecsmall_len(v);
      if (!m) {
        GEN nbrs = gel(T, ((w-1) % h) + 1);
        gel(T, ((w-1) % h) + 1) = gerepileupto(bv, nbrs);
        break;
      }
      if (m != L) pari_err_BUG("surface_path");
      gel(T, (j % h) + 1) = v;
      W[++j] = uel(v, 1);
      if (j == w + h) {
        ++w;
        if (W[w] == W0) { avma = av; return w; }
        x = 0; k = L;
      }
      if (w == n) { avma = av; return w; }
    }
  }
}
static long surface_path ( ulong W [ ] , long n , GEN phi , long L , long h , ulong J , const ulong * nJ , ulong p , ulong pi ) { pari_sp av = avma , bv ; GEN T , v ; long j , k , w , x ; ulong W0 ; W [ 0 ] = W0 = J ; if ( n == 1 ) return 1 ; T = cgetg ( h + 2 , t_VEC ) ; bv = avma ; v = get_nbrs ( phi , L , J , nJ , p , pi ) ; if ( nJ ) v = gerepileupto ( bv , vecsmall_prepend ( v , * nJ ) ) ; gel ( T , 1 ) = v ; k = vecsmall_len ( v ) ; switch ( k ) { case 0 : pari_err_BUG ( " " ) ; case 1 : if ( h ) pari_err_BUG ( " " ) ; W [ 1 ] = uel ( v , 1 ) ; avma = av ; if ( W [ 1 ] == W [ 0 ] ) return 1 ; return 2 ; case 2 : if ( L == 2 ) { GEN u = get_nbrs ( phi , L , uel ( v , 1 ) , & J , p , pi ) ; long n = vecsmall_len ( u ) - ! ! vecsmall_isin ( u , J ) ; W [ 1 ] = n == 1 ? uel ( v , 1 ) : uel ( v , 2 ) ; avma = av ; return 2 ; } if ( h ) pari_err_BUG ( " " ) ; W [ 1 ] = uel ( v , 1 ) ; for ( w = 2 ; w < n ; w ++ ) { v = get_nbrs ( phi , L , W [ w - 1 ] , & W [ w - 2 ] , p , pi ) ; if ( vecsmall_len ( v ) != 1 ) pari_err_BUG ( " " ) ; W [ w ] = uel ( v , 1 ) ; avma = av ; if ( W [ w ] == W0 ) return w ; } avma = av ; return n ; } if ( ! h ) pari_err_BUG ( " " ) ; w = 1 ; for ( x = 0 ; ; x ++ ) { W [ w ] = umael ( T , ( ( w - 1 ) % h ) + 1 , x + 1 ) ; if ( W [ w ] == W0 ) { avma = av ; return w ; } if ( x == k - 1 && w == n - 1 ) { avma = av ; return n ; } for ( j = w ; ; ) { long m ; v = get_nbrs ( phi , L , W [ j ] , & W [ j - 1 ] , p , pi ) ; m = vecsmall_len ( v ) ; if ( ! m ) { GEN nbrs = gel ( T , ( ( w - 1 ) % h ) + 1 ) ; gel ( T , ( ( w - 1 ) % h ) + 1 ) = gerepileupto ( bv , nbrs ) ; break ; } if ( m != L ) pari_err_BUG ( " " ) ; gel ( T , ( j % h ) + 1 ) = v ; W [ ++ j ] = uel ( v , 1 ) ; if ( j == w + h ) { ++ w ; if ( W [ w ] == W0 ) { avma = av ; return w ; } x = 0 ; k = L ; } if ( w == n ) { avma = av ; return w ; } } } }
Return a path of length n along the surface of an L-volcano of height h
 starting from surface node j0.
Return a path of length n along the surface of an L - volcano of height h starting from surface node j0 .
/* Insert known neighbour first */ /* We must always have neighbours */ /* If volcano is not flat, then we must have more than one neighbour */ /* Check for bad endo ring */ /* If L=2 the only way we can have 2 neighbours is if we have a double root
     * which can only happen for |D| <= 16 (Thm 2.2 of Fouquet-Morain)
     * and if it does we must have a 2-cycle. Happens for D=-15. */ /* The double root is the neighbour on the surface, with exactly one
       * neighbour other than J; the other neighbour of J has either 0 or 2
       * neighbours that are not J */ /* Volcano is not flat but found only 2 neighbours for the surface node J */ /* TODO: Can we use the other root uel(v,2) somehow? */ /* A flat volcano must have exactly one non-previous neighbour */ /* Detect cycle in case J doesn't have the right endo ring. */ /* Can't have a flat volcano if k > 2 */ /* At this point, each surface node has L+1 distinct neighbours, 2 of which
   * are on the surface */ /* Get next neighbour of last known surface node to attempt to
     * extend the path. */ /* Detect cycle in case the given J didn't have the right endo ring */ /* If we have to test the last neighbour, we know it's on the
     * surface, and if we're done there's no need to extend. */ /* Walk forward until we hit the floor or finish. */ /* NB: We don't keep the stack clean here; usage is in the order of Lh,
     * i.e. L roots for each level of the volcano of height h. */ /* We must get 0 or L neighbours here. */ /* We hit the floor: save the neighbours of W[w-1] and dump the rest */ /* If we have our path by h nodes, we know W[w] is on the surface */ /* Detect cycle in case the given J didn't have the right endo ring */