#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include "randomSum.h"

RandomSum::RandomSum(NumVec * set, int goal, int bound, int iterations) {
  int i;

  srand((int)time(NULL));
  size = set->getSize();

  result = new resultNode[size];
  for(i = 0; i < size; i++) {
    result[i].index = i;
    result[i].value = set->ValueAt(i);
  }

  resultFlags = new boolean[size];
  for(i = 0; i < size; i++) {
    resultFlags[i] = FALSE;
  }

  RandomSum::goal = goal;
  RandomSum::bound = bound;
  RandomSum::iterations = iterations;
  total = 0;
}

RandomSum::~RandomSum() {
  delete result;
  delete resultFlags;
}

boolean RandomSum::Solve(void) {
  int i, j;
  int members = size;
  int currentItem;
  resultNode temp;

  for(i = 0; i < iterations; i++) {
    fprintf(stderr, ".");
    while(members > 0) {
      currentItem = rand()%members;
      if(total+result[currentItem].value > goal+bound) {
	// total is too high, don't use this value
      }
      else if(total+result[currentItem].value < goal-bound) {
	// total is still good, use this value
	resultFlags[result[currentItem].index] = TRUE;
	total += result[currentItem].value;
      }
      else {
	// yes, we have a winner
	resultFlags[result[currentItem].index] = TRUE;
	total += result[currentItem].value;
	break;
      }
      // shrink the result array (swap value to end)
      temp.index = result[currentItem].index;
      temp.value = result[currentItem].value;
      result[currentItem].index = result[members-1].index;
      result[currentItem].value = result[members-1].value;
      result[members-1].index = temp.index;
      result[members-1].value = temp.value;
      members--;
    }

    if(members > 0) {
      // a winner
      break;
    }

    // reinitialize and try again
    total = 0;
    members = size;
    for(j = 0; j < size; j++) { 
      resultFlags[j] = FALSE;
    }
  }
  fprintf(stderr, "\n");

  if(i == iterations) {
    return FALSE;
  }
  return TRUE;
}

int RandomSum::GetSize(void) {
  return size;
}

boolean RandomSum::ValueAt(int location) {
  if(location>size) {
    fprintf(stderr, "Error: illegal array access %d in RandomSum\n", location);
  }
  return resultFlags[location];
}

int RandomSum::GetTotal(void) {
  return total;
}

