News Uni Dev Res Blag

SEPPLES -EWSE-

2010/09/17 - 13:57

/* some kind of binary tree implememtation
 * Copyright (C) 2010  ed <irc.rizon.net>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License, version 2, as
 * published by the Free Software Foundation.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, please refer to the following URL:
 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
 */
   My thoughts regarding all the whitespace

makefile

just do it yourself you lazy cunt

btnode.h

class BTNode
{
    public:
        int var;
        BTNode *left;
        BTNode *right;
        BTNode(int i);
        ~BTNode();
        int count();
        bool add(int i);
        int get(int *a, int indice, int level, int restraint);
};

bintree.h

#include "btnode.cpp"

class Bintree
{
    public:
        Bintree();
        ~Bintree();
        BTNode *root;
        int count();
        bool add(int v);
        void get(int *a);
        bool add(int *v, int n);
        void slice(int *a, int level);
};

btnode.cpp

#include "cmath"
#include "btnode.h"

BTNode::BTNode(int i)
{
    var = i;
    left = 0;
    right = 0;
}

BTNode::~BTNode()
{
    if (left != 0) {
        delete left;
    }
    if (right != 0) {
        delete right;
    }
    // MEMORY USAGE (ps -eo pid,args,rss)
    // //////////////////////////////////
    //     Initial start    944p
    //     1'000 entries    980p
    // 1'000'000 entries  16644p
    //             flush  16648p
    // 1'000'000 entries  16648p
    // 1'100'000 entries  18212p
    // //////////////////////////////////
    // indicates that everything works
}

bool BTNode::add(int i)
{
    //if (i == var) {
    //    return false;
    //}
    if (i < var)
    {
        if (left == 0)
        {
            left = new BTNode(i);
        }
        else
        {
            return left->add(i);
        }
    }
    else
    {
        if (right == 0)
        {
            right = new BTNode(i);
        }
        else
        {
            return right->add(i);
        }
    }
    return true;
}

int BTNode::count()
{
    int ret = 1;
    if (left != 0)
    {
        ret += left->count();
    }
    if (right != 0)
    {
        ret += right->count();
    }
    return ret;
}

/* Uten metode for visning av treets struktur:
 * 
 * int BTNode::get(int *a, int i) {
 *     if (left != 0) i += indice = left->get(a, i);
 *     a[i++] = var;
 *     if (right != 0) i += indice = right->get(a, i);
 *     return i;
 * }
 */

int BTNode::get(int *a, int indice, int level, int restraint)
{
    if (restraint != level) {
        // We either have no restraint, or
        // the restraint affects another level
        if (left != 0)
        {
            // Have a node to the left, iterate it
            indice = left->get(a, indice, level+1, restraint);
        }
        else if (restraint >= 0)
        {
            // No node to the left, restraint enabled;
            // padding to compensate for missing values
            int incr = restraint-level;
            indice += pow(2, incr - 1);
        }
    }
    if (restraint < 0 || restraint == level)
    {
        a[indice++] = var;
    }
    if (restraint != level)
    {
        if (right != 0)
        {
            indice = right->get(a, indice, level+1, restraint);
        }
        else if (restraint >= 0)
        {
            indice += pow(2, (level-restraint)-1);
        }
    }
    return indice;
}

bintree.cpp

#include "bintree.h"

Bintree::Bintree()
{
    root = 0;
}
Bintree::~Bintree()
{
    if (root != 0) {
        delete root;
    }
}

bool Bintree::add(int v)
{
    if (root == 0)
    {
        root = new BTNode(v);
    }
    else
    {
        return root->add(v);
    }
    return true;
}

bool Bintree::add(int *v, int n)
{
    bool ok = true;
    for (int a = 0; a < n; a++)
    {
        if (!add(v[a]))
        {
            ok = false;
        }
    }
    return ok;
}

void Bintree::get(int *a)
{
    if (root == 0) {
        return;
    }
    root->get(a, 0, 0, -1);
}

int Bintree::count()
{
    if (root == 0) {
        return 0;
    }
    return root->count();
}

void Bintree::slice(int *a, int level) {
    if (root == 0) {
        return;
    }
    root->get(a, 0, 0, level);
}

main.cpp

#include <cmath>     //pow
#include <cstdio>    //printf
#include <ctime>     //randomizer
#include <cstdlib>   //randomizer
#include <climits>   //int_min
#include <cstring>   //strspn
#include <iostream>
#include "bintree.cpp"
using namespace std;

int main(int argc, char **argv)
{
    Bintree *oak = new Bintree();
    srand(time(0));
    while (true)
    {
        cout << endl;
        cout << "   the oak has " << oak->count() << " branches." << endl;
        cout << "a) Input values manually" << endl;
        cout << "b) Generate example input" << endl;
        cout << "c) Print tree contents" << endl;
        cout << "d) Show tree structure" << endl;
        cout << "e) Flush tree" << endl;
        cout << "f) Exit" << endl;
        cout << "?) ";
        char opt;
        cin >> opt;
        cout << endl;
        
        if (opt == 'a')
        {
            char buf[16];
            char *good = (char *)"1234567890";
            cout << "Terminate input with any letter." << endl;
            while (true)
            {
                cin >> buf;
                if (strspn(buf, good))
                {
                    oak->add(atoi(buf));
                }
                else break;
            }
        }
        
        else if (opt == 'b')
        {
            int ant;
            cout << "How many numbers? ";
            cin >> ant;
            
            int lim;
            cout << "Upper value limit? ";
            cin >> lim;
            
            for (int a = 0; a < ant; a++)
            {
                oak->add(rand()%lim);
            }
        }
        
        else if (opt == 'c')
        {
            int n = oak->count();
            int *o = new int[n];
            oak->get(o);
            
            cout << "Low -> High: ";
            for (int a = 0; a < n; a++)
            {
                cout << o[a] << ", ";
            }
            cout << endl;
            cout << "High -> Low: ";
            for (int a = n; a > 0; a--)
            {
                cout << o[a-1] << ", ";
            }
            cout << endl;
        }
        
        else if (opt == 'd')
        {
            int sliceCount = 6;
            for (int a = 0; a < sliceCount; a++)
            {
                int sliceSize = pow(2, a);
                int padding = 128 / sliceSize;         // MUST BE POWER OF TWO
                int *slice = new int[sliceSize];
                for (int b = 0; b < sliceSize; b++)
                {
                    slice[b] = INT_MIN;
                }
                oak->slice(slice, a);
                int pad = padding/2 + padding%2;
                for (int b = 0; b < sliceSize; b++)
                {
                    if (slice[b] > INT_MIN)
                    {
                        printf("%*d%*c", pad, slice[b], pad, ' ');
                    }
                    else
                    {
                        printf("%*c", padding, ' ');
                    }
                }
                cout << "\n\n\n\n\n";
                delete(slice);
            }
        }
        
        else if (opt == 'e')
        {
            delete oak;
            oak = new Bintree();
        }
        
        else if (opt == 'f')
        {
            break;
        }
    }
}

Copyright © 2010 Ed Edland