Applying "while(a[++i] < v )" in R

Question

The following C code searches an array, a[], from a given left index and from a given right index, for the two indices (i and j) where every array value between the left index and i is less than v, and every array value between j and the right index is greater than v:

i= leftindex - 1 ;
j = rightindex ;
while(TRUE) { 
while( a[++i] < v) ;
while( a[--j] > v) ;
if (i >= j ) { break }
... }

This construct can be seen in various implementations of the quick sort algorithm.

My question is this: is the following the most efficient way to accomplish the same thing in the language R when a is a vector?

i = leftindex - 1 ;
j = rightindex ;
v = a[rightindex]
while(TRUE) {
  while (a[i <- i+1] < v ) { }  # R doesn't get the ++ operator
  while (a[j <- j-1] > v) { }   # R doesn't get the -- operator
  if (i >= j ) { break }
  ... 
} 

So, as an example, if 'a' is:

 a <- c('a','s','o','r','t','i','n','g','e','x','a','m','p','l','e') 

... and

left.index = 1; right.index = 15 

... then after this code runs I would expect the values of v, i and j to be:

v = e
i = 2
j = 11

I can't find anything that defines the operator "++" or "--" in R.

Does precedence in R guarantee the order of calculation of "a[i<-i+1] < v" or did I get lucky with my RStudio implementation?

I was toying with applying an anonymous function (decrement and compare) to the vector a at the appropriate places but this was simpler to write.

Any ideas would be appreciated.

Answer 1

As I understand it, you're trying to replace the following lines with R versions:

while( a[++i] < v);
while( a[--j] > v);

A simple way to write these two lines would be:

i <- i + min(which(a[(i+1):length(a)] >= v))
j <- max(which(a[1:(j-1)] <= v))

In each case, the which function is computing all the indices in which some subset of a has the appropriate value, so it's likely less efficient than just looping in custom C/C++ code until you find the first such entry.

If efficiency is important to you, you could write a very simple Rcpp function for this operation. Here, I've defined increment and decrement which do the two operations, taking particular care to convert i and j, which I assume are 1-indexed in the R code, to a 0-indexed value in the C++ code:

library(Rcpp)
increment <- cppFunction("
  int increment(NumericVector a, int i, const double v) {
    while( a[(++i)-1] < v) ;
    return i;
  }")

decrement <- cppFunction("
  int decrement(NumericVector a, int j, const double v) {
    while( a[(--j)-1] > v) ;
    return j;
  }")

Then you could convert your two lines to i <- increment(a, i, v) and j <- decrement(a, j, v).