old stuff: algorithms

1 files changed, 263 insertions, 0 deletions

diff --git a/algorithms/bin_packing.cc b/algorithms/bin_packing.cc
new file mode 100644
index 0000000..c4bb383
--- /dev/null
+++ b/algorithms/bin_packing.cc
@@ -0,0 +1,263 @@
+#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;
+}
+