summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTom Harley2019-09-10 11:33:33 +0100
committerTom Harley2019-09-10 11:33:33 +0100
commit75777e1fe7a3a96dd530d4ad19e92adda03be8a4 (patch)
treeece481b1959a464de3e2339bda39fcbcac63584c
parentInitial commit (diff)
downloadbinpacker-75777e1fe7a3a96dd530d4ad19e92adda03be8a4.tar.gz
binpacker-75777e1fe7a3a96dd530d4ad19e92adda03be8a4.zip

Initial commit

HEADmaster
-rw-r--r--Makefile4
-rw-r--r--main.c49
2 files changed, 21 insertions, 32 deletions
diff --git a/Makefile b/Makefile
index ada7ff3..c9677ac 100644
--- a/Makefile
+++ b/Makefile
@@ -1,3 +1,5 @@
+.PHONY: default all clean
default: all
-
all: main
+clean:
+ $(RM) main
diff --git a/main.c b/main.c
index a779c74..20c59c0 100644
--- a/main.c
+++ b/main.c
@@ -1,51 +1,38 @@
#include <stdio.h>
-typedef struct { int top; int left; int width; int height; } rect;
-typedef struct node { struct node *left; struct node *right; rect rc; int id;
-} node;
+typedef struct { int w; int h; } rect;
+typedef struct node { struct node *a; struct node *b; rect r; int id; } node;
node *insert(node *n, rect r, node **alloc) {
if (!n->id) {
- if (n->rc.width - r.width < 0 || n->rc.height - r.height < 0) return 0;
- n->left = (*alloc)++;
- n->right = (*alloc)++;
- n->left->rc.top = n->rc.top;
- n->left->rc.left = n->rc.left + r.width;
- n->left->rc.width = n->rc.width - r.width;
- n->left->rc.height = r.height;
- n->right->rc.top = n->rc.top + r.height;
- n->right->rc.left = n->rc.left;
- n->right->rc.width = n->rc.width;
- n->right->rc.height = n->rc.height - r.height;
+ if (n->r.w - r.w < 0 || n->r.h - r.h < 0) return 0;
+ n->a = (*alloc)++;
+ n->b = (*alloc)++;
+ n->a->r = (rect){ .w = n->r.w - r.w, .h = r.h };
+ n->b->r = (rect){ .w = n->r.w, .h = n->r.h - r.h };
return n;
- } else {
- node *new_node = insert(n->left, r, alloc);
- if (new_node) return new_node;
- else return insert(n->right, r, alloc);
}
+ node *new_node = insert(n->a, r, alloc);
+ return new_node ? new_node : insert(n->b, r, alloc);
}
-void print_tree(node *n) {
- if (!n->id) return;
- printf("%i: (%i, %i)\n", n->id, n->rc.left, n->rc.top);
- if (n->left) print_tree(n->left);
- if (n->right) print_tree(n->right);
+void print_tree(node *n, int x, int y) {
+ printf("%i: (%i, %i)\n", n->id, x, y);
+ if (n->a && n->a->id) print_tree(n->a, x + n->r.w - n->a->r.w, y);
+ if (n->b && n->b->id) print_tree(n->b, x, y + n->r.h - n->b->r.h);
}
int main() {
node alloc[100] = {0};
node *np = &alloc[1];
- alloc[0].rc.top = 0;
- alloc[0].rc.left = 0;
- alloc[0].rc.width = 1000;
- alloc[0].rc.height = 1000;
+ alloc[0].r.w = 1000;
+ alloc[0].r.h = 1000;
rect r;
- r.width = 201;
- r.height = 100;
+ r.w = 201;
+ r.h = 100;
for (int i = 0; i < 21; i++) {
insert(&alloc[0], r, &np)->id = i+1;
- printf("\n");
- print_tree(&alloc[0]);
}
+ print_tree(&alloc[0], 0, 0);
}