ref: 5a728711fa3bd16e4290aed341dc4e903eb27854
parent: c21f681808ae3e464374cb5917b9d4d684a4eedf
author: Halfwit <michaelmisch1985@gmail.com>
date: Fri Nov 25 02:47:31 PST 2016
Formatting
--- a/binpack.c
+++ b/binpack.c
@@ -1,4 +1,4 @@
-/* Simple bin packing algorithm implementation for use in window management */
+/* Simple bin packing algorithm implementation */
#include <stdlib.h>
#include <stdio.h>
@@ -5,7 +5,11 @@
#include <getopt.h>
#include <stdbool.h>
-/* from -x -y -g flags */
+enum {+ MAX_RECTS = 50,
+ LINE_LNG = 50
+};
+
struct mbin {unsigned x, y, gaps;
};
@@ -20,44 +24,54 @@
unsigned long wid;
};
-/* temporary storage of available sub-bins */
struct bins {- unsigned x, y, w, h;
+ /* temporary storage of available sub-bins */
+ unsigned x, y, w, h;
};
size_t
-create_rect(struct input r[]) {- size_t length = 0;
- char line[50] = "";
+binpack_init(struct input r[])
+{+ /* Read from stdin, create each rect */
+ size_t length = 0;
+ char line[LINE_LNG];
for (unsigned i = 0; fgets(line, sizeof(line), stdin); ++i) {sscanf(line, "%d %d %d %d %lx", &r[i].min_w, &r[i].min_h, &r[i].max_w, &r[i].max_h, &r[i].wid);
length++;
}
+
return length;
+
}
-/* (max bin size - blob size) / 2 */
void
-center(const size_t length, struct output r[], struct mbin mb) {+center(const size_t length, struct output r[], struct mbin mb)
+{+
+ /* (max bin size - blob size) / 2 */
unsigned w = 0, h = 0;
for (size_t i = 0; i < length; i++) {if (w < (r[i].w + r[i].x))
w = r[i].w + r[i].x;
+
if (h < (r[i].h + r[i].y))
h = r[i].h + r[i].y;
}
+
for (size_t i = 0; i < length; i++) {r[i].x += (mb.x - w) / 2;
r[i].y += (mb.y - h) / 2;
}
+
}
-/* arrange rectangles smallest to largest w*h */
void
-sort_bins(struct bins b[], size_t *bin_count) {- struct bins temp;
+sort_bins(struct bins b[], size_t *bin_count)
+{+ /* given set of bins, arrange them smallest to largest w*h */
+ struct bins temp;
for (unsigned i = 1; i < *bin_count; i++) { for (unsigned j = 0; j < *bin_count - i; j++) { if ((b[j + 1].w * b[j + 1].h) > (b[j].w * b[j].h)) {@@ -67,45 +81,15 @@
}
}
}
-}
-void
-scrub_bins(struct bins b[], size_t *bin_count) {- if (*bin_count == 1)
- return;
-
- for (unsigned i = 1; i < *bin_count; i++) {- if(b[i].w == 0 || b[i].h == 0)
- continue;
- for (unsigned j = 0; j < *bin_count - 1; j++) {-
- /* Skip if same bin */
- if (i == j)
- continue;
-
- /* Same row */
- if (b[j].y == b[i].y && b[j].h == b[i].h) {- b[j].w += b[i].w;
- b[i].h = 0;
- b[i].w = 0;
- }
-
- /* Same column */
- if (b[j].x == b[i].x && b[j].w == b[i].w) {- b[j].h += b[i].h;
- b[i].h = 0;
- b[i].w = 0;
- }
- }
- }
}
-/* arrange rectangles largest to smallest */
void
sort_input(struct input r[], const size_t length)
{- struct input temp;
+ /* arrange rectangles largest to smallest, normalized some over min/max */
+ struct input temp;
for (size_t i = 1; i < length; i++) { for (size_t j = 0; j < length - i; j++) { if ((r[j + 1].max_w * r[j + 1].min_h) > (r[j].max_w * r[j].min_h)) {@@ -115,12 +99,14 @@
}
}
}
+
}
void
create_bins(struct bins bin[], struct output out[], size_t i, size_t j, size_t *bin_count, struct mbin mb)
{- /* Local variables */
+
+ /* New bins based on subsection of old */
unsigned x, y, w, h;
x = bin[j].x;
y = bin[j].y;
@@ -128,23 +114,23 @@
h = bin[j].h;
/* rect smaller, make two sub bins */
- if (out[i].h <= h && out[i].w <= w) {- bin[*bin_count] = (struct bins){x + out[i].w + mb.gaps, y, w - out[i].w - mb.gaps, h};+ if (out[i].h + mb.gaps < h && out[i].w + mb.gaps < w) {+ bin[*bin_count] = (struct bins){.x = x + out[i].w + mb.gaps, .y = y, .w = w - out[i].w - mb.gaps, .h = h};bin[j].y += (out[i].h + mb.gaps);
bin[j].h -= (out[i].h - mb.gaps);
*bin_count += 1;
}
-
+
/* rect same height */
- else if (out[i].h == h) {+ else if (out[i].h + mb.gaps < h) {bin[j].y += (out[i].h + mb.gaps);
bin[j].h -= (out[i].h - mb.gaps);
}
/* rect same width */
- else if (out[i].w == w) {+ else if (out[i].w + mb.gaps < w) {bin[j].x += (out[i].w + mb.gaps);
- bin[j].w -= (out[i].w - mb.gaps);
+ bin[j].w -= (out[i].w - mb.gaps);
}
/* rect fills space, lose a bin */
@@ -151,122 +137,124 @@
else {bin[j].w = 0;
bin[j].h = 0;
+ *bin_count -= 1;
}
+
}
void
save_rect(struct bins bin[], struct output out[], struct input r[], size_t i, size_t j, struct mbin mb)
{+
/* Store rect x y w h wid */
- out[i] = (struct output){bin[j].x + (mb.gaps / 2), bin[j].y + (mb.gaps / 2), (r[i].min_w + r[i].max_w) / 2, (r[i].min_h + r[i].max_h) / 2, r[i].wid};+ out[i] = (struct output){.x = bin[j].x + (mb.gaps / 2), .y = bin[j].y + (mb.gaps / 2), .w = r[i].min_w, .h = r[i].min_h, .wid = r[i].wid};+
}
bool
-pack_bin(const size_t length, struct output out[], struct mbin mb, struct input r[])
+pack_bin(struct output out[], struct input r[], const size_t length, unsigned *bin_width, unsigned *bin_height, struct mbin mb)
{- /* initialize bins */
- struct bins bin[100];
- for (int i = 0; i < 100; i++) {- bin[i] = (struct bins){0, 0, 0, 0};+
+ /* Main algorithm */
+ struct bins bin[MAX_RECTS];
+
+ for (int i = 0; i < MAX_RECTS; i++) {+ bin[i] = (struct bins){.x = 0, .y = 0, .w = 0, .h = 0};}
/* default bin */
- bin[0] = (struct bins){ 0, 0, mb.x, mb.y};+ bin[0] = (struct bins){ .x = 0, .y = 0, .w = *bin_width + mb.gaps, .h = *bin_height + mb.gaps};+
size_t bin_count = 1;
- size_t packed = 0;
+ bool rect_fits;
/* loop through each rect */
for (size_t i = 0; i < length; i++) {+ rect_fits = false;
/* loop through each bin */
for (size_t j = 0; j < bin_count; j++) {- /* If rect fits bin, store it */
- if ((r[i].min_w + r[i].max_w) / 2 <= bin[j].w && (r[i].min_h + r[i].max_h) / 2 <= bin[j].h) {- packed++;
+ /* rect fits in current bin */
+ if (r[i].min_w + mb.gaps <= bin[j].w && r[i].min_h + mb.gaps <= bin[j].h) {+ rect_fits = true;
save_rect(bin, out, r, i, j, mb);
create_bins(bin, out, i, j, &bin_count, mb);
- scrub_bins(bin, &bin_count);
sort_bins(bin, &bin_count);
break;
}
}
+
+ /* if rect does not fit all bin */
+ if (rect_fits == false) {+
+ /* Grow main bin if possible */
+ if (mb.x > *bin_width)
+ *bin_width += 2;
+
+ if (mb.y > *bin_height)
+ *bin_height += 2;
+
+ return true;
+ }
}
- if (packed == length) {- return true;
- }
+
return false;
+
}
bool
-resizewidth(const size_t length, struct output out[], struct mbin mb, struct input r[])
+resize(struct output out[], struct input r[], const size_t length, unsigned *bin_width, unsigned *bin_height, struct mbin mb, size_t index)
{- size_t packed = 0;
- for (size_t i = 0; i < length; i++) {- /* If we're within 1, bin is fully packed */
- if (r[i].max_w - r[i].min_w < 2) {- packed++;
- continue;
- }
-
- /* In case something goes wonky */
- if (r[i].min_w > r[i].max_w) {- r[i].max_w = r[i].min_w;
- r[i].min_w--;
- }
+ /* When a bin fills all the space available, pack_bin */
+ for (size_t i = index; i < length; i++) {+ unsigned limitcheck = 0;
+ while (pack_bin(out, r, length, bin_width, bin_height, mb)) {+ if (limitcheck == mb.x)
+ return false;
- /* if binpack succeeds, we can grow --> set min as current, else set max as current */
- if(pack_bin(length, out, mb, r)) {- r[i].min_w = (r[i].min_w + r[i].max_w) / 2;
- } else {- r[i].max_w = (r[i].min_w + r[i].max_w) / 2;
+ limitcheck++;
}
- }
- if (packed == length) {- return false;
+ /* If rect can grow */
+ if (out[i].h < r[i].max_h)
+ r[i].min_h += 1;
+
+ if (out[i].w < r[i].max_w)
+ r[i].min_w += 1;
+
+ sort_input(r, length);
}
- return true;
-}
-bool
-resizeheight(const size_t length, struct output out[], struct mbin mb, struct input r[])
-{- size_t packed_bin = 0;
- for (size_t i = 0; i < length; i++) {- /* If we're within 1, bin is fully packed */
- if (r[i].max_h - r[i].min_h < 2) {- packed_bin++;
- continue;
- }
-
+ /* max_h to handle cases of smaller windows */
+ unsigned w = 0, h = 0;
- /* In case something goes wonky */
- if (r[i].min_h > r[i].max_h) {- r[i].max_h = r[i].min_h;
- r[i].min_h--;
- }
-
- /* if binpack succeeds, we can grow --> set min as current, else set max as current */
- if(pack_bin(length, out, mb, r)) {- r[i].min_h = (r[i].min_h + r[i].max_h) / 2;
- } else {- r[i].max_h = (r[i].min_h + r[i].max_h) / 2;
- }
+ for (size_t i = index; i < length; i++) {+ if (w < (out[i].w + out[i].x))
+ w = out[i].w + out[i].x + mb.gaps;
+
+ if (h < (out[i].h + out[i].y))
+ h = out[i].h + out[i].y + mb.gaps;
}
- if (packed_bin == length) {+ if (h >= mb.y + (mb.gaps / 2))
return false;
- }
+
+ if (w >= mb.x + (mb.gaps / 2))
+ return false;
+
return true;
+
}
int
main(int argc, char *argv[])
{+
struct mbin mb;
- mb.gaps = 0;
+ mb.gaps = 0, mb.x = 0, mb.y = 0;
int c;
+
while ((c = getopt(argc, argv, "hg:x:y:")) != -1) { switch (c) {/* read in, all vars unsigned int */
@@ -280,39 +268,64 @@
sscanf(optarg, "%u", &mb.y);
break;
case 'h':
- fprintf(stderr, "Usage: %s -x screen_width -y screen_height -g gaps\n", argv[0]);
+ fputs("Usage: bin_pack -x screen_width -y screen_height -g gaps\n", stderr);return EXIT_SUCCESS;
}
}
- struct input r[100];
- struct output out[100];
+ struct input r[MAX_RECTS];
+ struct output out[MAX_RECTS];
- const size_t length = (create_rect(r));
+ const size_t length = (binpack_init(r));
/* If we have no windows, exit */
- if (length == 0) {+ if (length == 0 || mb.x == 0 || mb.y == 0)
return EXIT_SUCCESS;
- }
sort_input(r, length);
- /* Initial pack to establish out bins */
- pack_bin(length, out, mb, r);
+ unsigned bin_width = mb.x;
+ unsigned bin_height = mb.y;
- int foo = 0;
- while(resizeheight(length, out, mb, r) && resizewidth(length, out, mb, r)) {- printf("%d\n", ++foo);- }
-
- unsigned area = 0;
+ /* If we have no large windows */
+ bool no_large_windows = true;
for (size_t i = 0; i < length; i++) {- area+=out[i].w * out[i].h;
+ struct input temp = r[i];
+ r[i].min_w = r[i].max_w;
+ r[i].min_h = r[i].max_h;
+
+ if (pack_bin(out, r, length, &bin_width, &bin_height, mb)) {+ r[i] = temp;
+ no_large_windows = false;
+ }
}
- /* If we have more windows than space */
- if (area > (mb.x - mb.gaps) * (mb.y - mb.gaps))
- return EXIT_SUCCESS;
+ unsigned limitcheck = 0;
+
+ if (no_large_windows == false) {+ bin_width = r[0].min_w;
+ bin_height = r[0].min_h;
+
+ while (pack_bin(out, r, length, &bin_width, &bin_height, mb)) {+ /* if we've ran this long, something is up */
+ if (limitcheck == mb.x)
+ return EXIT_FAILURE;
+
+ limitcheck++;
+ }
+
+ limitcheck = 0;
+
+ for (size_t i = 0; i < length; i++) {+ /* Square out the blob as best as we can */
+ while (resize(out, r, length, &bin_width, &bin_height, mb, i)) {+ if (limitcheck == mb.x)
+ return EXIT_FAILURE;
+
+ limitcheck++;
+ }
+ }
+ }
center(length, out, mb);