#include <iostream>
#include <fstream>
#include <stdlib.h>

using namespace std;


int
cmp(const void* a, const void* b)
{
  int* arg1 = (int*) a;
  int* arg2 = (int*) b;
  if (*arg1<*arg2) return 1;
  else if (*arg1 == *arg2) return 0;
  else return -1;
}

class Bins
{
  public:
    Bins(int max_bins, int bin_height) {
      k  = bin_height;
      bc = 0;
      lo = 0;
      mb = max_bins;
      b  = new int[mb];
    }

    ~Bins() {
      delete[] b;
    }

    void add_bin() {
      b[bc] = k;
      bc++;
    }

    void alloc_at(int i, int s) {
      b[i] -= s;
      lo = i;
     }

    int get_alloc_at(int i) {
      return b[i];
    }

     int get_bin_count() {
      return bc;
    }

    int get_last_bin_opened() {
      return lo;
    }

    void reset() {
      delete[] b;
      b = new int[mb];
      bc = 0;
      lo = 0;
    }

    void print() {
      for (int i=0; i < bc; i++) {
        cout << "Bin "<< i << ": " << k-get_alloc_at(i) << "/" << k << endl;
      }
    }

  private:
    int* b;
    int bc;
    int k;
    int lo;
    int mb;
};

/*
 * First-Fit
 *
 */
int
first_fit(int* S, int N, Bins* B)
{
  int in;

  B->add_bin();
  for (int i=0; i<N; i++) {
    in=-1;
    for (int j=0; j<B->get_bin_count(); j++) {
      if (S[i]<=B->get_alloc_at(j)) {
        in = j;
        break;
      }
    }
    if (in==-1) {
      B->add_bin();
      B->alloc_at(B->get_bin_count()-1, S[i]);
    } else {
      B->alloc_at(in, S[i]);
    }
  }

  return B->get_bin_count();
}

/*
 * Next-Fit
 *
 */
int
next_fit(int* S, int N, Bins* B)
{
  B->add_bin();
  for (int i=0; i<N; i++) {
    if (S[i]<=B->get_alloc_at(B->get_last_bin_opened())) {
      B->alloc_at(B->get_last_bin_opened(), S[i]);
    } else {
      B->add_bin();
      B->alloc_at(B->get_bin_count()-1, S[i]);
    }
  }

  return B->get_bin_count();
}

/*
 * Max-Rest
 *
 */
int
max_rest(int* S, int N, Bins* B) {
  int mr, mri;

  B->add_bin();
  for (int i=0; i<N; i++) {
    mr = 0;
    mri = -1;
    for (int j=0; j<B->get_bin_count(); j++) {
      if (S[i]<=B->get_alloc_at(j)) {
        if (B->get_alloc_at(j)>mr) {
          mr = B->get_alloc_at(j);
          mri = j;
        }
      }
    }
    if (mri == -1) {
      B->add_bin();
      B->alloc_at(B->get_bin_count()-1, S[i]);
    } else {
      B->alloc_at(mri, S[i]);
    }
  }

  return B->get_bin_count();
}


/*
 * Best-Fit
 *
 */
int
best_fit(int* S, int N, int K, Bins* B) {
  int best;

  for (int i=0; i<N; i++) {
    best=-1;
    for (int j=0; j<B->get_bin_count(); j++) {
      if (S[i]==B->get_alloc_at(j)) {
        best = j;
        break;
      }
    }
    if (best==-1) {
      for (int l=1; l<=K-S[i]; l++) {
        for (int j=0; j<B->get_bin_count(); j++) {
          if (S[i]+l==B->get_alloc_at(j)) {
            best = j;
            break;
          }
        }
        if (best!=-1) break;
      }
    }
    if (best==-1) {
      B->add_bin();
      B->alloc_at(B->get_bin_count()-1, S[i]);
    } else {
      B->alloc_at(best, S[i]);
    }
  }

  return B->get_bin_count();
}


int
main (int argc, char* const argv[]) {
  if (!argv[1]||argv[2]) {
    cout << "Usage: " << argv[0] << " <filename>" << endl;
    return 1;
  }

  int i, j=0, sum=0, N, K;
  int* S;
  Bins* B;

  ifstream f;
  string line;
  f.open(argv[1]);
  if (!f) {
    cout << "File '" << argv[1] << "' not found." << endl;
    return 1;
  }
  while (getline(f, line)) {
    if (line!="") {
      i = atoi(line.c_str());
      if (j==0) N = i;
      else if (j==1) { K=i; S=new int[N]; }
      else { S[j-2] = i; sum+=i; }
    }
    j++;
  }
  f.close();

  B = new Bins(N, K);

  cout << endl;
  cout << "Bin Packing heuristics (declined)" << endl;
  cout << "=================================" << endl;
  cout << endl;
  cout << "Number of items: " << N << endl;
  cout << "Sum of sizes: " << sum << endl;
  cout << "Bin capacity: " << K << endl;
  cout << endl;

  int ff, nf, bf, mr, ffd, nfd;
  ff=first_fit(S,N,B);
  B->reset();
  nf=next_fit(S,N,B);
  B->reset();
  bf= best_fit(S,N,K,B);
  B->reset();
  mr=max_rest(S,N,B);
  B->reset();
  qsort(S, N, sizeof(int), cmp);
  ffd=first_fit(S,N,B);
  B->reset();
  nfd=next_fit(S,N,B);

  cout << "Max Rest:\t\t\t" << mr << " bins" << endl;
  cout << "First Fit:\t\t\t" << ff << " bins" << endl;
  cout << "Frist Fit Dec:\t\t" << ffd << " bins" << endl;
  cout << "Next Fit:\t\t\t" << nf << " bins" << endl;
  cout << "Next Fit Dec:\t\t" << nfd << " bins" << endl;
  cout << "Best Fit:\t\t\t" << bf << " bins" << endl;
  cout << endl;

  delete[] S;
  delete B;

  return 0;
}