#include "stdstuff.h"
#include "IntBag.h"

// note that the constructor and size are not mentioned here as their
// implementations are completely specified in the header file

// constructs a bag having count copies of value and count copies
// of value+1.
// Quits if count is less than 0 or greater than MAXVALUES/2.
IntBag::IntBag (int count, int value) {
           
   // first check count
   if (count<0 || 2*count>MAXVALUES) { // or count>MAXVALUES/2 
      *this = IntBag();
      quit("IntBag::Intbag - count must be between 0 and MAXVALUES/2.\n");
   }
      
   // count is good, so initialize fields
   this->count = count*2;

   // add (parameter) count copies of value
   for (int i=0; i<count; i++) {
      data[i] = value;
   }
   // and then add (parameter) count copies of
   // value+1
   for (int i=count; i<count*2; i++) {
      data[i] = value+1;
   }
   
   // alternatively, could add one copy of value,
   // then one copy of value+1, and do that count times
   
   walkInProgress=false;
}
  

// removeOneCopy returns an IntBag with one copy of every different
// element of the bag removed, i.e. if there was one copy, it's gone; if
// there are two or more, just one copy is removed.
IntBag IntBag::removeOneCopy() const {
       
   int value, n;
   bool stillWalking;
   
   IntBag result, copy;
   copy = *this; // make a copy of the original bag
   
   // walk through the copy of the bag (we can't walk
   // through the original as we can't change it)
   for (stillWalking=copy.startWalk(value); stillWalking; 
       stillWalking=copy.continueWalk(value)) {
                                              
      // for each element of our copy, if the value is
      // not already in our result, add it n-1 times,
      // where n is the number of occurrences in the copy.
      // Note that the result will never fill up, as it will
      // have fewer elements than copy.
      if (result.countOccurrences(value)==0) {
         // find out how many times it occurs in copy
         n = copy.countOccurrences(value);
         for(int i=0; i<n-1; i++) {
            result.add(value);
         }
      }
   }
   // return the newBag
   return result; 
}
  
// returns true if bag has more elements than other bag, false otherwise
bool IntBag::operator>(const IntBag &otherBag) const {
   return count>otherBag.count;
}

// adds a value to the bag.  returns true on success (space available)
// and false on failure (bag full)
bool IntBag::add (int value) {

  if (count == MAXVALUES) return false;

  data[count++] = value;
  walkInProgress = false; // scrub any ongoing walk
  return true;

}


// removes one occurance of the specfied value from the bag.  returns
// true on success (value existed) and false on failure (value did not exist)
bool IntBag::remove (int value) {

  int i;

  for (i = 0; i < count; i++) {
    if (data[i] == value) {
      // we've found the data value.
      // overwrite it with the last data value and adjust the count
      // to reflect the fact that there are now one fewer values in
      // the bag.  note that this works even if the value being removed
      // is the last value in the bag.
      data[i] = data[--count];
      walkInProgress = false; // scrub any ongoing walk
      return true;
    }
  }

  return false;

}


// returns the number of times that the specified value occurs in the bag
int IntBag::countOccurrences (int value) const {

  int i, occurrences = 0;

  for (i = 0; i < count; i++) {
    if (data[i] == value) {
      occurrences++;
    }
  }

  return occurrences;

}


bool IntBag::startWalk (int &value) {

  if (count == 0) return false;

  walkInProgress = true; walkPosition = 0;
  value = data[walkPosition];
  return true;

}


// quits if a walk is not in progress
bool IntBag::continueWalk (int &value) {

  if (!walkInProgress) {
    quit("IntBag::continueWalk invalid call\n");
  }
  if (++walkPosition == count) {
    walkInProgress = false; // we've come to the end of the road
    return false;
  }
  value = data[walkPosition];
  return true;

}


// randomly picks and returns one of the values in the bag.
// quits if the bag is empty.
int IntBag::pickRandom () const {

  int i;

  if (count == 0) {
    quit("IntBag::pickRandom bag is empty\n");
  }

  i = (int) ((rand () / (RAND_MAX + 1.0)) * count);
  return data[i];

}