ref: 5cee1124022211c00794ce0167f3353b85815fae
parent: 46b3adb7a4861c9b0209421a078b48819b22a8c7
author: Halfwit <michaelmisch1985@gmail.com>
date: Sat Aug 11 17:44:27 PDT 2018
Stash changes
--- a/bin_utils.c
+++ b/bin_utils.c
@@ -33,7 +33,7 @@
size_t length = 0;
char line[MAX_BIN];
for (unsigned i = 0; fgets(line, sizeof(line), stdin); ++i) {- sscanf(line, "%d %d %d %d %lx", &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
);
length++;
}
@@ -72,28 +72,8 @@
void print_bin(struct Output out[], size_t length) { for (size_t i=0; i < length; i++) { if (out[i].w > 0 && out[i].h > 0) {- printf("%d %d %d %d %lx\n", out[i].x, out[i].y, out[i].w, out[i].h, out[i].wid);+ printf("%u %u %u %u 0x%.8X\n", out[i].x, out[i].y, out[i].w, out[i].h, out[i].wid);}
}
}
-// Remove element from array, returning it for use
-struct Input pop(struct Input in[]) {- size_t len = sizeof(*in)/sizeof(in[0]);
- struct Input temp = in[1];
- for (size_t i = 1; i < len - 1; i++) {- in[i] = in[i+1];
- }
- in[len].minw = 0;
- in[len].maxw = 0;
- in[len].minh = 0;
- in[len].maxh = 0;
- in[len].wid = 0;
- return temp;
-}
-
-// append element on to array
-void push(struct Input in[], struct Input temp) {- size_t len = sizeof(*in)/sizeof(in[0]);
- in[len] = temp;
-}
--- a/binpack.c
+++ b/binpack.c
@@ -1,15 +1,124 @@
#include <stdbool.h>
+#include <stdio.h>
#include <stdlib.h>
#include "binpack.h"
+struct Point {+ unsigned x;
+ unsigned y;
+};
+
+// 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) {+ for (unsigned i = 0; i < count; i++) {+ if (in[i].minw >= (c[i].w - 1)) {+ return true;
+ }
+ }
+ return false;
+}
+
+bool isminh(struct Input in[], struct Current c[], unsigned count) {+ for (unsigned i = 0; i < count; i++) {+ if (in[i].minh >= (c[i].h - 1)) {+ return true;
+ }
+ }
+ return false;
+}
+// Test to see if any bins are at our max size after binpack to exit binary loop
+bool ismaxw(struct Input in[], struct Current c[], unsigned count) {+ for (unsigned i = 0; i < count; i++) {+ if (in[i].maxw <= (c[i].w + 1)) {+ return true;
+ }
+ }
+ return false;
+}
+
+bool ismaxh(struct Input in[], struct Current c[], unsigned count) {+ for (unsigned i = 0; i < count; i++) {+ if (in[i].maxh <= (c[i].h + 1)) {+ return true;
+ }
+ }
+ return false;
+}
+
// 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[]) {+
+ unsigned count = sizeof(*in)/sizeof(in[0]) + 1;
+ // Initialise greedily to the maximums
+ struct Current c[count];
+ for (int i = 0; i < count; i++) {+ c[i].w = in[i].maxw;
+ c[i].h = in[i].maxh;
+ c[i].wid = in[i].wid;
+ }
+
+ while (1) {+ if (bin_pack(width, height, c, out, count)) {+ if (ismaxw(in, c, count) && ismaxh(in, c, count)) {+ break;
+ }
+ /* Example
+ minw 450 maxw 500 c.w 450
+ c.w += 500 - 450 / 2
+ c.w += 50 / 2
+ w.c = 475 maxw = 500 minw = 475
+ */
+ for (int i = 0; i < count; i++) {+ in[i].minw = c[i].w;
+ in[i].minh = c[i].h;
+ c[i].w += ((in[i].maxw - c[i].w) / 2);
+ c[i].h += ((in[i].maxh - c[i].h) / 2);
+ }
+
+ } else {+ if (isminw(in, c, count) && isminh(in, c, count)) {+ break;
+ }
+ /* Example
+ minw 450 maxw 500 c.w 500
+ c.w -= 500 - 450 / 2
+ c.w -= 50 / 2
+ c.w = 475 maxw = 500, minw = 450
+ */
+ for (int i = 0; i < count; i++) {+ in[i].maxw = c[i].w;
+ in[i].maxh = c[i].h;
+ c[i].w -= ((c[i].w - in[i].minw) / 2);
+ c[i].h -= ((c[i].h - in[i].minh) / 2);
+ }
+ }
+ }
}
-// Make sure we pass with one or fewer elements
+// Should pass a pointer to the struct here
bool
-bin_pack(unsigned width, unsigned height, struct Output out[], struct Input in[]) {+bin_pack(unsigned width, unsigned height, struct Current c[], struct Output out[], unsigned count) {+
+ // Initialize our output
+ 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;
+ }
+
+ // Initialize points
+
+ // Loop through each member of c
+ // while {+ // check if points need to be removed
+ // tree[n].x = Someholder + width
+ // tree[n].y = Someholder + height
+ // }
+ // minw minh maxw maxh wid
+
return true;
}
--- a/binpack.h
+++ b/binpack.h
@@ -18,8 +18,14 @@
unsigned wid;
};
+struct Current {+ unsigned w;
+ unsigned h;
+ unsigned wid;
+};
+
void binary_bin_pack(unsigned width, unsigned height, struct Output out[], struct Input in[]);
-bool 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);
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);
--- a/main.c
+++ b/main.c
@@ -60,9 +60,9 @@
/* Sort into two bins and pack each seperately */
if (screens == 2) {split(input, in_a, in_b, length);
- for (size_t i = 0; i <= sizeof(*in_a)/sizeof(in_a[0]); i++) {- printf("a %d b %d\n", in_a[i].maxw, in_b[i].maxw);- }
+ //for (size_t i = 0; i <= sizeof(*in_a)/sizeof(in_a[0]); i++) {+ // printf("a %d b %d\n", in_a[i].maxw, in_b[i].maxw);+ //}
/* binpack.c */
binary_bin_pack(width/2, height, out_a, in_a);
binary_bin_pack(width/2, height, out_b, in_b);
@@ -75,21 +75,34 @@
print_bin(out_b, sizeof(out_b)/sizeof(out_b[0]));
}
- /* Ugly logic - while bin_pack fails, move an element into one of two flanking bins, alternating bins each time */
+
+ // TODO: Implement triple head sorting and splitting
+ /*
if (screens == 3) {- struct Input temp;
bool bin_switch = true;
- /* binpack.c */
- while (!bin_pack(width/3, height, output, input)) {- temp = pop(input);
+ struct Current temp;
+ struct Current c[MAX_BIN];
+ unsigned count = sizeof(input)/sizeof(input[0]);
+ for (unsigned i = 0; i < count; i++) {+ c[i].w = input[i].maxw;
+ c[i].h = input[i].maxh;
+ c[i].wid = input[i].wid;
+ }
+
+ // binpack.c
+
+ while (!bin_pack(width/3, height, c, output, count)) {+ temp = pop(c);
(bin_switch) ? push(in_a, temp) : push(in_b, temp);
bin_switch = !bin_switch;
}
+
binary_bin_pack(width/3, height, out_a, in_a);
binary_bin_pack(width/3, height, out_b, in_b);
-
- /* bin_utils.c */
+
+ // bin_utils.c
+
center(width/3, height, output, gaps);
center(width/3, height, out_a, gaps);
center(width/3, height, out_b, gaps);
@@ -98,6 +111,7 @@
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]));
- }
+
+ }*/
}