function test_level = cc_abscissa_level_1d ( level_max, test_num, test_val )

%% CC_ABSCISSA_LEVEL_1D: first level at which given abscissa is generated.
%
%  Discussion:
%
%    The Clenshaw Curtis abscissas are the cosines of angles, and hence
%    are somewhat raggedy real values between -1 and 1.  However,
%    it is sometimes convenient to think of them as being equally
%    spaced integers, particularly if we are mainly concerned with the
%    nesting property.  The question this routine can answer is, if
%    we are going to generate a sequence of nested Clenshaw Curtis
%    rules up to a given maximum level, on what level does a particular
%    abscissa first show up?
%
%    Consider the sequence of numbers from 0 to 2**LEVEL_MAX.  Suppose
%    that we organize them into levels.  The first two levels are
%    somewhat arbitrary:
%
%      Level 0:  2**(LEVEL_MAX-1)
%      Level 1:  0, 2**LEVEL_MAX
%
%    But after that, the generation rule for the next level is simply
%    to generate a new value BETWEEN every consecutive pair of values
%    that have already been generated ( and these new values are simply
%    the averages of the consecutive pair.)
%
%    Thus, if our current set of values is 0, 8 and 16, on the next
%    level we generate 4 and 12 to make a new set of 0, 4, 8, 12, 16.
%    We continue this operation, level by level, until we have filled in
%    all 2**LEVEL_MAX+1 values.
%
%    This routine returns, for any value I and maximum level LEVEL_MAX,
%    the level on which the value I will first be produced.
%
%    For example, for LEVEL_MAX = 5, the numbers we are considering
%    are 0 through 32, and they will be produced as follows:
%
%      Level
%      0:                                 16
%      1:  0                                                              32
%      2:                  8                              24
%      3:          4              12              20              28
%      4:      2       6      10      14      18      22      26      30
%      5:    1   3   5   7   9  11  13  15  17  19  21  23  25  27  29  31
%
%    Here is the list of levels for 0 through 32:
%
%          1 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 0 5 4 5 3 5 4 5 2 5 4 5 3 5 4 5 1
%
%    The purpose of this routine is, given the value 20 and the
%    maximum level 5, to return level = 3, indicating that the value 20
%    will first be generated on the 3rd level for a grid that ultimately
%    reaches an order of 2**5+1 values.
%
%    The need for this routine arises from the necessity of understanding
%    nested Clenshaw Curtis grids.  In particular, if we see a grid of
%    17 points, this is the fifth in a series of nested grids, and 8 of
%    the points are new, created specifically for the level 4 grid, while
%    9 of the points arose earlier.  This routine can report exactly when
%    each value was created.
%
%    The real need for this routine arises in multidimensional sparse grids,
%    where we essentially have a fixed "budget" of levels we are allowed to
%    use.  When we generate a multidimensional point, we determine its
%    level in each single dimensional grid, add them up, and this value
%    must be no greater than our budgeted value for the point to be included
%    in the sparse grid.
%
%    Except for the behavior of the first two levels, it is true that
%    the level of a value I is LEVEL_MAX minus the number of times I can be
%    divided evenly by 2.  Because of a peculiarity of the definition of
%    the grids, if this formula gives a level of 0 or 1, then the level
%    should be replaced by 1 or 0, respectively.
%
%    Again, except for the first two levels, the calculation is equivalent
%    to computing the location of the "first" nonzero bit in the representation
%    of a number, and subtracting that from LEVEL_MAX.  This is why all the
%    odd numbers, which have their first 1 bit in the 0-th position,
%    are assigned a level of LEVEL_MAX.
%
%    This routine can also be called for values that lie outside the standard
%    range of 0 through 2**LEVEL_MAX.  In that case, a MOD operation is
%    applied first, to make a sensible result.
%
%  Licensing:
%
%    This code is distributed under the GNU LGPL license.
%
%  Modified:
%
%    23 March 2007
%
%  Author:
%
%    John Burkardt
%
%  Parameters:
%
%    Input, integer LEVEL_MAX, determines the number of points in the grid as
%    2**LEVEL_MAX + 1.
%
%    Input, integer TEST_NUM, the number of points to be tested.
%
%    Input, integer TEST_VAL(TEST_NUM), the values of the points to be tested.
%    Normally, each value would be between 0 and 2**LEVEL_MAX+1.
%
%    Output, integer TEST_LEVEL(TEST_NUM), the level at which the
%    point would first be generated, assuming that a standard sequence of
%    nested grids is used.
%
  order = 2^level_max + 1;

  for i = 1 : test_num

    t = round ( test_val(i) );
%
%  The following MOD operation is only needed to handle cases where
%  T is not in the expected range.
%
    t = i4_modp ( t, order );

    if ( t == 0 )

      level = 0;

    else

      level = level_max;

      while ( mod ( t, 2 ) == 0 )
        t = floor ( t / 2 );
        level = level - 1;
      end

    end

    if ( level == 0 )
      level = 1;
    elseif ( level == 1 )
      level = 0;
    end

    test_level(i) = level;

  end

  return
end