fork(2) download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4.  
  5.  
  6. typedef struct Node_t
  7. {
  8.    int data;
  9.    struct Node_t* left;
  10.    struct Node_t* right;
  11. } Node;
  12.  
  13. int treeCompare(Node* n1, Node* n2)
  14. {
  15.    if (!n1) return (n2==NULL);
  16.    if (!n2 || (n1->data != n2->data)) return 0;
  17.    return (treeCompare(n1->left, n2->left) &&
  18.             treeCompare(n1->right, n2->right));
  19. }
  20.  
  21.  
  22.  
  23. //utility
  24. int countNodes(Node* n)
  25. {
  26.    if (!n) return 0;
  27.    return 1+countNodes(n->left)+countNodes(n->right);
  28. }
  29.  
  30.  
  31.  
  32. int* bencodeHelper(Node* n, int* code, int* pos, int* flag)
  33. {
  34.    int hasKids = (n->left!=0);
  35.    code[*flag/32]|=hasKids<<(*flag&31);
  36.    *flag+=1;
  37.    if (hasKids) bencodeHelper(n->left, code, pos, flag);
  38.    code[*pos]=n->data;
  39.    *pos+=1;
  40.    if (hasKids) bencodeHelper(n->right, code, pos, flag);
  41.    return code;
  42. }
  43.  
  44.  
  45. int* bencode(Node* h, int* sizeOut)
  46. {
  47.    int nnodes=countNodes(h);
  48.    int nflags = (int)ceil(nnodes/32.0);
  49.    int pos=nflags+1;
  50.    int flag=32;
  51.    int* out;
  52.    *sizeOut = 1+nnodes+nflags;
  53.    out = calloc(*sizeOut, sizeof(int));
  54.    if (!h) return out;
  55.    out[0]=nflags+1;
  56.    return bencodeHelper(h,out,&pos,&flag);
  57. }
  58.  
  59.  
  60.  
  61. Node* bdecodeHelper(int* code, int* pos, int* flag)
  62. {
  63.    Node*n = calloc(1, sizeof(Node));
  64.    int hasKids = code[*flag/32]>>(*flag&31)&1;
  65.    *flag+=1;
  66.    if (hasKids) n->left = bdecodeHelper(code, pos, flag);
  67.    n->data = code[*pos];
  68.    *pos+=1;
  69.    if (hasKids) n->right = bdecodeHelper(code, pos, flag);
  70.    return n;
  71. }
  72.  
  73. Node* bdecode(int* code)
  74. {
  75.    int flag=32;
  76.    int pos=code[0];
  77.    if (!pos) return NULL;
  78.    return bdecodeHelper(code, &pos, &flag);
  79. }
  80.  
  81.  
  82. Node* makeRandomTree(float freq, int maxDepth)
  83. {
  84.    Node* n;
  85.    n = calloc(1,sizeof(Node));
  86.    n->data = rand();
  87.    if (maxDepth-- && (rand()/(float)RAND_MAX < freq))
  88.    {
  89.       n->left = makeRandomTree(freq, maxDepth);
  90.       n->right = makeRandomTree(freq, maxDepth);
  91.    }
  92.    return n;
  93. }
  94.  
  95. int main(int argc, char* argv[])
  96. {
  97.    Node* head = makeRandomTree(0.79,8);
  98.    Node* dup;
  99.    int i,sz;
  100.    int nnodes = countNodes(head);
  101.    int* code = bencode(head, &sz);
  102.    printf("Tree with %d nodes encodes to %d ints\n",nnodes,sz);
  103.    for (i=0;i<sz;++i)
  104.    {
  105.       printf("%.4x, ",code[i]);
  106.    }
  107.    puts("\n");
  108.    dup = bdecode(code);
  109.    if (treeCompare(head,dup)) { puts("Trees Compare Exactly!\n"); }
  110.    else {puts("FAILURE\n");}
  111. }
  112.  
Success #stdin #stdout 0s 1852KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Tree with 61 nodes encodes to 64 ints
0003, 72c4e37d, 43265e2, 643c9869, 6b8b4567, 79e2a9e3, 2eb141f2, 216231b, 12200854, 1f16e9e8, 515f007c, 1190cde7, 3d1b58ba, 41a7c4c9, 7fdcc233, 6b68079a, 109cf92e, 519b500d, 4e6afb66, 431bd7b7, 140e0f76, 3f2dba31, 238e1f29, 333ab105, 436c6125, 6763845e, 2443a858, 8edbdab, 257130a3, 836c40e, 71f32454, 2901d82, 189a769b, 1e7ff521, 3a95f874, 7c3dbd3d, 4353d0cd, 737b8ddc, 2ae8944a, 3804823e, 440badfc, 2463b9ea, 7724c67e, 5e884adc, 419ac241, 3855585c, 580bd78f, 70a64e2a, 51ead36b, 1d4ed43b, 6a2342ec, 725a06fb, 3006c83e, 542289ec, 7a6d8d3c, 38437fdb, 2cd89a32, 32fff902, 22221a70, 579478fe, 74b0dc51, 79a1deaa, 3dc240fb, 12e685fb, 

Trees Compare Exactly!
https://ideone.com/28w6L
language:
C99 (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!