gistfile1.txt

/* The Computer Language Benchmarks Game
 * http://benchmarksgame.alioth.debian.org/

   contributed by Kevin Carson
   compilation:
       gcc -O3 -fomit-frame-pointer -funroll-loops -static binary-trees.c -lm
       icc -O3 -ip -unroll -static binary-trees.c -lm
*/

#include <malloc.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>


class TreeNode
{
public:
    TreeNode* left;
    TreeNode* right;
    int item;

    TreeNode(TreeNode* left, TreeNode* right, int item)
    {
        this->left = left;
        this->right = right;
        this->item = item;
    }

    int check()
    {
        return left == 0 ? item : left->check() - right->check() + item;
    }
};


TreeNode* BottomUpTree(int item, unsigned depth)
{
    if (depth > 0) {
        return new TreeNode
        (
            BottomUpTree(2 * item - 1, depth - 1),
            BottomUpTree(2 * item, depth - 1),
            item
        );
    }
    return new TreeNode(0, 0, item);
} 

    

void DeleteTree(TreeNode* tree)
{
    if (tree->left != NULL)
    {
        DeleteTree(tree->left);
        DeleteTree(tree->right);
    }
    delete tree;
}

int main(int argc, char* argv[])
{
    unsigned   N, depth, minDepth, maxDepth, stretchDepth;
    TreeNode   *stretchTree, *intLivedTree, *tempTree;

    N = atol(argv[1]);

    minDepth = 4;

    if ((minDepth + 2) > N)
        maxDepth = minDepth + 2;
    else
        maxDepth = N;

    stretchDepth = maxDepth + 1;

    stretchTree = BottomUpTree(0, stretchDepth);
    printf
    (
        "stretch tree of depth %u\t check: %d\n",
        stretchDepth,
        stretchTree->check()
    );

    DeleteTree(stretchTree);

    intLivedTree = BottomUpTree(0, maxDepth);

    for (depth = minDepth; depth <= maxDepth; depth += 2)
    {
        int    i, iterations, check;

        iterations  =  1 << (maxDepth - depth + minDepth);

        check = 0;

        for (i = 1; i <= iterations; i++)
        {
            tempTree = BottomUpTree(i, depth);
            check += tempTree->check();
            DeleteTree(tempTree);

            tempTree = BottomUpTree(-i, depth);
            check += tempTree->check();
            DeleteTree(tempTree);
        } /* for(i = 1...) */

        printf
        (
            "%d\t trees of depth %u\t check: %d\n",
            iterations * 2,
            depth,
            check
        );
    } /* for(depth = minDepth...) */

    printf
    (
        "int lived tree of depth %u\t check: %d\n",
        maxDepth,
        intLivedTree->check()
    );

    return 0;
}