// FILE: bag1.cxx
// CLASS IMPLEMENTED: bag (see bag1.h for documentation)
// INVARIANT for the bag class:
//   1. The number of items in the bag is in the member variable used;
//   2. For an empty bag, we do not care what is stored in any of data; for a
//      non-empty bag the items in the bag are stored in data[0] through
//      data[used-1], and we don't care what's in the rest of data.

#include "bag.h"
#include <algorithm> // Provides copy function
#include <cassert>   // Provides assert function
#include <functional>
#include <iostream>
#include <limits>
using namespace std;

namespace main_savitch_3 {
const bag::size_type bag::CAPACITY;

bag::size_type bag::erase(const value_type &target) {
  size_type index = 0;
  size_type many_removed = 0;

  while (index < used) {
    if (data[index] == target) {
      --used;
      data[index] = data[used];
      ++many_removed;
    } else
      ++index;
  }

  return many_removed;
}

bool bag::erase_one(const value_type &target) {
  size_type index; // The location of target in the data array

  // First, set index to the location of target in the data array,
  // which could be as small as 0 or as large as used-1. If target is not
  // in the array, then index will be set equal to used.
  index = 0;
  while ((index < used) && (data[index] != target))
    ++index;

  if (index == used)
    return false; // target isn't in the bag, so no work to do.

  // When execution reaches here, target is in the bag at data[index].
  // So, reduce used by 1 and copy the last item onto data[index].
  --used;
  data[index] = data[used];
  return true;
}

void bag::insert(const value_type &entry)
// Library facilities used: cassert
{
  assert(size() < CAPACITY);

  data[used] = entry;
  ++used;
}

void bag::operator+=(const bag &addend)
// Library facilities used: algorithm, cassert
{
  assert(size() + addend.size() <= CAPACITY);

  copy(addend.data, addend.data + addend.used, data + used);
  used += addend.used;
}

bag::size_type bag::count(const value_type &target) const {
  size_type answer;
  size_type i;

  answer = 0;
  for (i = 0; i < used; ++i)
    if (target == data[i])
      ++answer;
  return answer;
}

bag::value_type bag::smallest() const {
  bag::value_type smallest = this->data[0];

  for (int i = 1; i < used; ++i)
    if (this->data[i] < smallest)
      smallest = this->data[i];

  return smallest;
}

bag::value_type bag::average() const {
  bag::value_type sum = 0;

  for (int i = 0; i < this->used; ++i)
    sum += this->data[i];

  // I'll use an arithmetic average since once isn't specified. This
  // self-rounds since `value_type` is `int`.
  return sum / this->used;
}

void bag::sort() const {
  bag bag;

  for (int i = 0; i < this->size(); ++i)
    bag.insert(this->data[i]);

  for (int i = 0; i < bag.used - 1; ++i)
    for (int j = 0; j < bag.used - i - 1; ++j)
      if (bag.data[j] > bag.data[j + 1])
        std::swap(bag.data[j], bag.data[j + 1]);

  for (int i = 0; i < bag.size(); ++i)
    std::cout << bag.data[i] << std::endl;
}

bool bag::operator==(const bag &bag_2) {
  bag bag_this_sorted = *this;
  bag bag_2_sorted = bag_2;
  // Typically I'd make this a member function since it could be reused in
  // `sort`, but it seems out of the scope of what's asked.
  std::function<void(bag &)> sort_bag = [](bag &bag) {
    for (int i = 0; i < bag.used - 1; ++i)
      for (int j = 0; j < bag.used - i - 1; ++j)
        if (bag.data[j] > bag.data[j + 1])
          std::swap(bag.data[j], bag.data[j + 1]);
  };

  sort_bag(bag_this_sorted);
  sort_bag(bag_2_sorted);

  for (int i = 0; i < this->used; ++i)
    if (bag_this_sorted.data[i] != bag_2_sorted.data[i])
      return false;

  return true;
}

bag operator+(const bag &b1, const bag &b2)
// Library facilities used: cassert
{
  bag answer;

  assert(b1.size() + b2.size() <= bag::CAPACITY);

  answer += b1;
  answer += b2;
  return answer;
}
} // namespace main_savitch_3