//
// main.cpp
// Reservoir Sampling
//
// Created by Himanshu on 27/11/22.
//
#include <iostream>
#include <vector>
using namespace std;
void printReservoir (vector<int> reservoir) {
cout<<"Items in the reservoir:"<<endl;
for (int item: reservoir) {
cout<<item<<" ";
}
cout<<endl;
}
bool checkItemPresent (vector<int> reservoir, int x) {
for (int item: reservoir) {
if (item == x) {
return true;
}
}
return false;
}
void selectReservoir (int stream[], int N, int k) {
int i; //current index of elements in stream[]
// reservoir[] vector contain selected items.
// Initialise it with first k elements of stream[]
vector<int> reservoir;
for (i = 0; i < k; i++) {
reservoir.push_back(stream[i]);
}
printReservoir(reservoir);
// N is the number of elements in the stream
while (i < N) {
if (!checkItemPresent(reservoir, stream[i])) {
int j = rand()%k;
reservoir[j] = stream[i];
printReservoir(reservoir);
}
i++;
}
}
void selectReservoirOptimized (int stream[], int N, int k) {
int i; //current index of elements in stream[]
// reservoir[] vector contain selected items.
// Initialise it with first k elements of stream[]
vector<int> reservoir;
for (i = 0; i < k; i++) {
reservoir.push_back(stream[i]);
}
printReservoir(reservoir);
// N is the number of elements in the stream
while (i < N) {
int r = rand()%(i+1);
if (r < k) {
reservoir[r] = stream[i];
}
printReservoir(reservoir);
i++;
}
}
void selectReservoirItem (int stream[], int N) {
int i=0; //current index of elements in stream[]
int x = stream[i];
// N is the number of elements in the stream
while (i < N) {
int r = rand()%(i+1);
if (r == i) {
x = stream[i];
}
cout<<x<<endl;
i++;
}
}
int main () {
int stream[] = {1, 2, 5, 5, 3, 7, 8, 8, 8, 11, 12};
int N = 11;
int k = 4;
cout<<"Reservoir Sampling (Solution I)"<<endl;
selectReservoir(stream, N, k);
cout<<endl<<"Reservoir Sampling Optimised (Solution II)"<<endl;
selectReservoirOptimized(stream, N, k);
cout<<endl<<"Reservoir item (Solution III)"<<endl;
selectReservoirItem(stream, N);
return 0;
}