ref: 1a41bd1a3cb2d74f914ae050b74dc6dd221cdee9
parent: 09530b328b31c8fb68eef21c542e8ab66d17bb36
author: Halfwit <michaelmisch1985@gmail.com>
date: Sun Sep 23 17:40:17 PDT 2018
Most everything except binary binpacking is working Signed-off-by: Halfwit <michaelmisch1985@gmail.com>
--- a/Makefile
+++ b/Makefile
@@ -2,7 +2,6 @@
# See LICENSE file for copyright and license details.
SRC = main.c \
- points.c \
binpack.c \
bin_utils.c
--- a/bin_utils.c
+++ b/bin_utils.c
@@ -3,14 +3,61 @@
#include "binpack.h"
+void
+scrub_output(struct Output out[]) {+ for (unsigned i = 0; i < sizeof(*out)/sizeof(out[0]); i++) {+ out[i].w = 0;
+ out[i].h = 0;
+ out[i].x = 0;
+ out[i].y = 0;
+ out[i].wid = 0;
+ }
+}
+
+struct Current
+pop(struct Current c[]) {+ unsigned offset = sizeof(*c)/sizeof(c[0]) - 1;
+ struct Current tmp;
+ tmp.h = c[offset].h;
+ tmp.w = c[offset].w;
+ tmp.wid = c[offset].wid;
+ c[offset] = c[offset + 1];
+ return tmp;
+}
+
+void
+push(struct Input in[], struct Current temp) {+ unsigned offset = sizeof(*in)/sizeof(in[0]);
+ in[offset].maxw = temp.w;
+ in[offset].maxh = temp.h;
+ in[offset].minw = temp.w;
+ in[offset].minh = temp.h;
+ in[offset].wid = temp.wid;
+}
+
// center all windows on given screen
void center(unsigned width, unsigned height, struct Output out[], unsigned gaps) {- // r = rightmost edge of bins
- // d = bottommost edge of bins
- // Move all windows (width - r) / 2
- // Move all windows (height - d) / 2
- // g = gaps / 2
- // x - g, y + g, w - g, h - g for all windows
+ unsigned edge = 0;
+ unsigned bott = 0;
+ unsigned g = gaps / 2;
+ // Find our edges
+ for (size_t i = 0; i <= sizeof(*out)/sizeof(out[0]); i++) {+ if ((out[i].x + out[i].w) > edge) {+ edge = (out[i].x + out[i].w);
+ }
+ if ((out[i].y + out[i].h) > bott) {+ bott = (out[i].y + out[i].h);
+ }
+ }
+ // Bump over
+ for (size_t i = 0; i <= sizeof(*out)/sizeof(out[0]); i++) {+ out[i].x += ((width - edge) / 2);
+ out[i].y += ((height - bott) / 2);
+ out[i].x -= g;
+ out[i].y += g;
+ out[i].w -= g;
+ out[i].h -= g;
+ }
}
void sort_bins(struct Input r[], const size_t length) {@@ -28,12 +75,16 @@
}
// read from stdin, setting up our initial data
-size_t init_bins(struct Input r[]) {+size_t init_bins(struct Input r[], unsigned gaps) {size_t length = 0;
+ unsigned g = (gaps / 2);
char line[MAX_BIN];
for (unsigned i = 0; fgets(line, sizeof(line), stdin); ++i) {- sscanf(line, "%u %u %u %u %X", &r[i].minw, &r[i].minh, &r[i].maxw, &r[i].maxh, &r[i].wid
-);
+ sscanf(line, "%u %u %u %u %X", &r[i].minw, &r[i].minh, &r[i].maxw, &r[i].maxh, &r[i].wid);
+ r[i].maxw += g;
+ r[i].maxh += g;
+ r[i].minw += g;
+ r[i].minh += g;
length++;
}
return length;
--- a/binpack.c
+++ b/binpack.c
@@ -3,7 +3,6 @@
#include <stdlib.h>
#include "binpack.h"
-#include "points.h"
// Test to see if any bins are already at minimum size, so we can fail gracefully (Insufficient space to draw windows)
bool isminw(struct Input in[], struct Current c[], unsigned count) {@@ -43,7 +42,7 @@
}
// This will iterate through a binary-search style approach, varying the size between the minw/minh and maxw/maxh to try to find the largest set of rectangles to fill the bin
-void binary_bin_pack(unsigned width, unsigned height, struct Output out[], struct Input in[]) {+void binary_bin_pack(unsigned width, unsigned height, struct Output out[], struct Input in[], struct Points points[]) {unsigned count = sizeof(*in)/sizeof(in[0]) + 1;
@@ -56,7 +55,7 @@
}
while (1) {- if (bin_pack(width, height, c, out, count)) {+ if (bin_pack(width, height, c, out, count, points)) { if (ismaxw(in, c, count) && ismaxh(in, c, count)) {break;
}
@@ -93,32 +92,82 @@
}
}
+void
+set_bin(struct Output *out, struct Current c, unsigned x, unsigned y) {+ out->h = c.h;
+ out->w = c.w;
+ out->x = x;
+ out->y = y;
+ out->wid = c.wid;
+}
+
bool
-bin_pack(unsigned width, unsigned height, struct Current c[], struct Output out[], unsigned count) {+set_point(struct Output *out, struct Current c, struct Points p[], unsigned *count, unsigned bounds, unsigned height) {+ unsigned top = 0;
+ unsigned side = 0;
+ // Loop through our points to try to fit
+ for (unsigned i = 0; i < *count; i++) {+ // We could set sentinals here for possible, then collision and set
+ bool potential = false;
+ // Fits beside
+ if (p[i].x + c.w <= bounds) {+ side = p[i].x;
+ potential = true;
+ }
+ else if (p[i].y + c.h <= height) {+ top = p[i].y;
+ // If we're at the last point, side is 0; else our window starts at the greater of either the next point or current.
+ if ((i + 1) != *count) {+ side = (p[i + 1].x > p[i].x) ? p[i + 1].x : p[i].x;
+ } else {+ side = 0;
+ }
+ potential = true;
+
+ }
+ if (!(potential)) {+ top = p[i].y;
+ continue;
+ }
+ // There's a collision, try next point
+ //if (collisions(c, side, top, p)) {+ // continue;
+ //}
+ set_bin(out, c, side, top);
+ return true;
+ }
+ return false;
+}
- // Set first window at (0,0)
- out[0].w = c[0].w;
- out[0].h = c[0].h;
- out[0].x = 0;
- out[0].y = 0;
- out[0].wid = c[0].wid;
+bool
+bin_pack(unsigned width, unsigned height, struct Current c[], struct Output out[], unsigned count, struct Points p[]) {- // And points
- points[0].x = c[0].w;
- points[0].y = 0;
- points[1].x = c[0].w;
- points[1].y = c[0].h;
- points[2].x = 0;
- points[2].y = c[0].h;
+ unsigned p_count = 1;
- // Loop through rest of windows
+ // Set our initial data up
+ p[0].x = c[0].w;
+ p[0].y = c[0].h;
+ set_bin(&out[0], c[0], 0, 0);
+
+ // Set our initial bounding box
+ unsigned bounds = c[0].w;
- for (unsigned i = 0; i < count; i++) {- out[i].w = c[i].w;
- out[i].h = c[i].h;
- out[i].x = 0;
- out[i].y = 0;
- out[i].wid = c[i].wid;
+ // Loop through rest of windows
+ for (unsigned i = 1; i < count; i++) {+ // Walk our points, check if we fit. If we fit, all is well; we can go on to the next
+ if (set_point(&out[i], c[i], p, &p_count, bounds, height)) {+ p_count++;
+ continue;
+ }
+ // Increase our bounds to fit, go from there.
+ if (bounds + c[i].w <= width) {+ bounds += c[i].w;
+ if (set_point(&out[i], c[i], p, &p_count, bounds, height)) {+ continue;
+ }
+ }
+ // Binpack failed
+ return false;
}
return true;
--- a/binpack.h
+++ b/binpack.h
@@ -24,13 +24,19 @@
unsigned wid;
};
-void binary_bin_pack(unsigned width, unsigned height, struct Output out[], struct Input in[]);
-bool bin_pack(unsigned width, unsigned height, struct Current c[], struct Output out[], unsigned count);
+struct Points {+ unsigned x;
+ unsigned y;
+};
+
+void binary_bin_pack(unsigned width, unsigned height, struct Output out[], struct Input in[], struct Points points[]);
+bool bin_pack(unsigned width, unsigned height, struct Current c[], struct Output out[], unsigned count, struct Points points[]);
void split(struct Input *in, struct Input *a, struct Input *b, size_t length);
void center(unsigned width, unsigned height, struct Output out[], unsigned gaps);
void sort_bins(struct Input r[], const size_t length);
void print_bin(struct Output out[], size_t length);
void offset(struct Output out[], unsigned w);
-size_t init_bins(struct Input r[]);
-struct Input pop(struct Input in[]);
-void push(struct Input in[], struct Input temp);
+size_t init_bins(struct Input r[], unsigned gaps);
+struct Current pop(struct Current c[]);
+void push(struct Input in[], struct Current temp);
+void scrub_output(struct Output out[]);
--- a/main.c
+++ b/main.c
@@ -35,7 +35,8 @@
struct Input input[MAX_BIN];
struct Output output[MAX_BIN];
- const size_t length = init_bins(input);
+ const size_t length = init_bins(input, gaps);
+ struct Points points[length];
/* Sanity checks */
if (length == 0 || height == 0 || width == 0)
@@ -51,7 +52,7 @@
/* Normal function */
if (screens == 1) {/* binpack.c */
- binary_bin_pack(width, height, output, input);
+ binary_bin_pack(width, height, output, input, points);
/* bin_utils.c */
center(width, height, output, gaps);
@@ -67,8 +68,8 @@
if (screens == 2) {/* binpack.c */
split(input, in_a, in_b, length);
- binary_bin_pack(width/2, height, out_a, in_a);
- binary_bin_pack(width/2, height, out_b, in_b);
+ binary_bin_pack(width/2, height, out_a, in_a, points);
+ binary_bin_pack(width/2, height, out_b, in_b, points);
/* bin_utils.c */
center(width/2, height, out_a, gaps);
@@ -79,8 +80,6 @@
}
- // TODO: Implement triple head sorting and splitting
- /*
if (screens == 3) {bool bin_switch = true;
@@ -94,26 +93,31 @@
}
// binpack.c
- while (!bin_pack(width/3, height, c, output, count)) {+ while (!bin_pack(width/3, height, c, output, count, points)) {+ scrub_output(output);
temp = pop(c);
(bin_switch) ? push(in_a, temp) : push(in_b, temp);
bin_switch = !bin_switch;
+ count-- ;
}
- // TODO: Guard against empty structs
- binary_bin_pack(width/3, height, out_a, in_a);
- binary_bin_pack(width/3, height, out_b, in_b);
-
+ if (sizeof(out_a) > 0) {+ binary_bin_pack(width/3, height, out_a, in_a, points);
+ center(width/3, height, out_a, gaps);
+ print_bin(out_a, sizeof(out_a)/sizeof(out_a[0]));
+ }
+
+ if (sizeof(out_b) > 0) {+ binary_bin_pack(width/3, height, out_b, in_b, points);
+ center(width/3, height, out_b, gaps);
+ offset(out_b, width*2/3);
+ print_bin(out_b, sizeof(out_b)/sizeof(out_b[0]));
+ }
+
// bin_utils.c
center(width/3, height, output, gaps);
- center(width/3, height, out_a, gaps);
- center(width/3, height, out_b, gaps);
offset(output, width/3);
- offset(out_b, width*2/3);
print_bin(output, sizeof(output)/sizeof(output[0]));
- print_bin(out_a, sizeof(out_a)/sizeof(out_a[0]));
- print_bin(out_b, sizeof(out_b)/sizeof(out_b[0]));
- }*/
-
+ }
}