Skip to content

Instantly share code, notes, and snippets.

@ashelly
Created November 4, 2019 17:58
Show Gist options
  • Save ashelly/041b88aafcb01633ea6d599e3ac42df2 to your computer and use it in GitHub Desktop.
Save ashelly/041b88aafcb01633ea6d599e3ac42df2 to your computer and use it in GitHub Desktop.
Compact binary tree encoding. Solution to https://codegolf.stackexchange.com/q/339/152
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct Node_t
{
int data;
struct Node_t* left;
struct Node_t* right;
} Node;
int treeCompare(Node* n1, Node* n2)
{
if (!n1) return (n2==NULL);
if (!n2 || (n1->data != n2->data)) return 0;
return (treeCompare(n1->left, n2->left) &&
treeCompare(n1->right, n2->right));
}
//utility
int countNodes(Node* n)
{
if (!n) return 0;
return 1+countNodes(n->left)+countNodes(n->right);
}
int* bencodeHelper(Node* n, int* code, int* pos, int* flag)
{
int hasKids = (n->left!=0);
code[*flag/32]|=hasKids<<(*flag&31);
*flag+=1;
if (hasKids) bencodeHelper(n->left, code, pos, flag);
code[*pos]=n->data;
*pos+=1;
if (hasKids) bencodeHelper(n->right, code, pos, flag);
return code;
}
int* bencode(Node* h, int* sizeOut)
{
int nnodes=countNodes(h);
int nflags = (int)ceil(nnodes/32.0);
int pos=nflags+1;
int flag=32;
int* out;
*sizeOut = 1+nnodes+nflags;
out = calloc(*sizeOut, sizeof(int));
if (!h) return out;
out[0]=nflags+1;
return bencodeHelper(h,out,&pos,&flag);
}
Node* bdecodeHelper(int* code, int* pos, int* flag)
{
Node*n = calloc(1, sizeof(Node));
int hasKids = code[*flag/32]>>(*flag&31)&1;
*flag+=1;
if (hasKids) n->left = bdecodeHelper(code, pos, flag);
n->data = code[*pos];
*pos+=1;
if (hasKids) n->right = bdecodeHelper(code, pos, flag);
return n;
}
Node* bdecode(int* code)
{
int flag=32;
int pos=code[0];
if (!pos) return NULL;
return bdecodeHelper(code, &pos, &flag);
}
Node* makeRandomTree(float freq, int maxDepth)
{
Node* n;
n = calloc(1,sizeof(Node));
n->data = rand();
if (maxDepth-- && (rand()/(float)RAND_MAX < freq))
{
n->left = makeRandomTree(freq, maxDepth);
n->right = makeRandomTree(freq, maxDepth);
}
return n;
}
int main(int argc, char* argv[])
{
Node* head = makeRandomTree(0.79,8);
Node* dup;
int i,sz;
int nnodes = countNodes(head);
int* code = bencode(head, &sz);
printf("Tree with %d nodes encodes to %d ints\n",nnodes,sz);
for (i=0;i<sz;++i)
{
printf("%.4x, ",code[i]);
}
puts("\n");
dup = bdecode(code);
if (treeCompare(head,dup)) { puts("Trees Compare Exactly!\n"); }
else {puts("FAILURE\n");}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment