%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%     Perform user input specific consistency checks     %%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The following portion of the program performs consistency checks
that are dependent on the user's input.  This allows additional
testing using different quantiles.

@d User input specific tests @{
int i;
int high = Q[1]-Q[0];
int low =  Q[1]-Q[0];
int size = *(Q.end()) - *(Q.begin());
for ( i = 2; i < size ; i++ ) {
    high = max( Q[i]-Q[i-1],high );
    high = min( Q[i]-Q[i-1],high );
}
assert ( (high - low) < 2 );
  
  
  
cout << "Consistency checks passed." << endl;@}


  @<Hard wired tests@>
  @<User input specific tests@>



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%         Perform hard wired Consistencey Checks       %%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%        %%%%%%%%
@d Hard wired tests @{
D = D0;
vector<container::iterator> R;
quantiles(D.begin(), D.end(), back_inserter(R), 2);
assert (R[1] == Q[2]);
  
D = D0;
vector<container::iterator> S;
quantiles(D.begin(), D.end(), back_inserter(S), 8);
assert (S[2] == Q[1]);
assert (S[6] == Q[3]);
  
Dnew = D0;
vector<container::iterator> T;
quantiles(Dnew.begin(), Dnew.end(), back_inserter(T), 2);
assert ( *(T[1]) == *(Q[2]) );
 
Dnew = D0;
vector<container::iterator> U;
quantiles(Dnew.begin(), Dnew.end(), back_inserter(U), 8);
assert (U[2] == Q[1]);
assert (U[6] == Q[3]);

cout << "Hard wired consistency checks passed." << endl;@}

These checks check both the position of the iterator, as well as the
value that the iterator points to.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%     Perform user input specific consistency checks     %%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The following portion of the program performs consistency checks
that are dependent on the user's input.  This allows additional
testing using different quantiles.

%%%%%%        %%%%%%%%
@d User input specific tests @{
int i;
int high = Q[1]-Q[0];
int low =  Q[1]-Q[0];
int size = *(Q.end()) - *(Q.begin());
for ( i = 2; i < size ; i++ ) {
    high = max( Q[i]-Q[i-1],high );
    high = min( Q[i]-Q[i-1],high );
}
assert ( (high - low) < 2 );
  
  
  
cout << "Consistency checks passed." << endl;@}



%%%%%%    VERBAGE    %%%%%%%%


























//template <typename RandomAccessIterator, typename OutputIterator, typename BinaryPredicate>
//void
// quantiles(RandomAccessIterator first, RandomAccessIterator last, OutputIterator result, int m, BinaryPredicate p =
//      std::less<typename iterator_traits<RandomAccessIterator>::value_type> )

Larry,

> In doing this assignment I was comparing the design of the quantile
> function to the merge, min, and partial sort functions.  It has some
> similarities to each of these.
>
> As a result, I was thinking of putting the Q[0] and Q[max] quantile
> computation inside the function.  Is it ok to do this.

What's the rationale?  (I don't see it from the analogy with the other
functions.)

> Also, I was thinking of adding a BinaryPredicate version of the function.
> Is this also ok to do?

Yes, that's a good idea.

> I was trying to figure out how to integrate the Binary Predicate
> version of the funtion into the original, so I don't have to make 2
> functions with separate prototypes, yet also allow the user to leave
> out the binary predicate.  I think I can default assign it to
> <less> but I am not sure how a user defined type with simply the < defined
> would like this.  Does less convert to < or does it need the <less> binary
> predicate defined for that function.  Or is there a generic version
> already defined that will take any type and use < with it?

That's what less<T> does.  (It gives you a function object f such that
f(T x, T y) computes (x < y), where the < is T::operator<.)
The default parameter idea is worth trying, I think. Something like:

  template <typename RandomAccessIterator, typename BinaryPredicate>
  
  std::vector<typename iterator_traits<RandomAccessIterator>::value_type>
  
  quantiles(RandomAccessIterator first, RandomAccessIterator last, int m,
    BinaryPredicate p =
      std::less<typename iterator_traits<RandomAccessIterator>::value_type>)
  {
   ...
  }

> Also, I thought about allowing the user to construct the whole vector of
> iterators before calling the function, then the function would call a
> version that used assignment instead of push back.  It makes some sense
> because the user always knows the size of the vector if iterators anyway.
> But I decided against that because it is a messier way of doing it, and
> from looking at the stl it seems that it is going away from that
> prototype, and it is not inline with the instructions
> in the homework.  Does that decision make sense?

Yes.

Dave