reservoir sampling

reservoir_sampling.java

T add(T item) {
    T old = null;
    if(position < numSamples) {// reservoir not yet full, just append
        samples[position] = item;
    } else {// find a item to replace
        int replaceIndex = rand.nextInt(position + 1);
        if(replaceIndex < numSamples) {// replacement opportunity decreases over a time
            old = samples[replaceIndex];
            samples[replaceIndex] = item;
        }
    }
    position++;
    return old;
}