Binary.c

Go to the documentation of this file.

// Encoding binary 11
//                                                                                               ^
//                                                                                               |
//                                                        ZERO                  ONE              |
//                                                          o==================o=================o
//                                                          ^                                  CODE
//                                                          |
//                                                          |
//                                                          |
//                             the      o===================o  the 
//                   ^       smallest   ^                    biggest
//                   |      address is  |                   address is
//                   |         ZERO     |                      ONE
//       the first   |                  |    the second
//        edge is    +--------+---------+     edge is
//         ZERO               |                 ONE
//                            o ROOT
//
 
#include <stdlib.h>
#include "errors.h"
#include "Graph.h"
 
#define BINARY_CLUSTER_LENGTH 3
#define BINARY_BITS_IN_INT ((int)sizeof(int) * 8)
 
struct Binary {
    unsigned int root;
    unsigned int zero;
    unsigned int one;
    struct Graph *graph;
};
 
struct Binary *Binary_construct(unsigned int root, struct Graph *graph, int *error)
{
    struct Binary *this = malloc(sizeof(struct Binary));
 
    if (0 == this) {
        *error = ERROR_NO_MEMORY;
        return 0;
    }
 
    this->root = root;
    this->graph = graph;
 
    unsigned int cluster[BINARY_CLUSTER_LENGTH];
 
    Graph_addCluster(this->graph, BINARY_CLUSTER_LENGTH - 1, cluster, error);
 
    if (*error) {
        return 0;
    }
 
    this->zero = cluster[0];
 
    Graph_addEdge(graph, this->root, this->zero, error);
 
    if (*error) {
        return 0;
    }
 
    Graph_addCluster(this->graph, BINARY_CLUSTER_LENGTH - 1, cluster, error);
 
    if (*error) {
        return 0;
    }
 
    this->one = cluster[0];
 
    Graph_addEdge(graph, this->root, this->one, error);
 
    if (*error) {
        return 0;
    }
 
    return this;
}
 
struct Binary *Binary_destruct(struct Binary *this)
{
    if (0 != this) {
        free(this);
    }
 
    return 0;
}
 
unsigned int Binary_writeCode(struct Binary *this, unsigned int input, int *error)
{
    int offset = 0; // count leading zeroes
 
    for (int index = BINARY_BITS_IN_INT - 1; index >= 0; index--) {
        if ((input >> index) & 1) {
            break;
        }
        offset++;
    }
 
    // traverse clusters
 
    unsigned int bufferA[BINARY_CLUSTER_LENGTH];
    unsigned int *currentCluster = bufferA;
 
    unsigned int bufferB[BINARY_CLUSTER_LENGTH];
    unsigned int *nextCluster = bufferB;
 
    unsigned int *swapper = 0;
 
    currentCluster[BINARY_CLUSTER_LENGTH - 1] = 0;
    if (input & 1) {
        Graph_readCluster(this->graph, this->one, BINARY_CLUSTER_LENGTH, currentCluster, error);
    } else {
        Graph_readCluster(this->graph, this->zero, BINARY_CLUSTER_LENGTH, currentCluster, error);
    }
    
    if (*error) {
        return 0;
    }
 
    int limit = BINARY_BITS_IN_INT - offset - 1;
 
    for (int index = 1; index <= limit; index++) {
 
        nextCluster[BINARY_CLUSTER_LENGTH - 1] = 0; // for checking at the end if already protruded
 
        if ((input >> index) & 1) { // next is one
 
            unsigned int lastTarget = Graph_readLastTarget(this->graph, currentCluster[1], error);
 
            if (*error) {
                return 0;
            }
 
            if (0 == lastTarget) {
 
                Graph_addCluster(this->graph, BINARY_CLUSTER_LENGTH - 1, nextCluster, error);
 
                if (*error) {
                    return 0;
                }
 
                Graph_addEdge(this->graph, currentCluster[1], nextCluster[0], error);
 
                if (*error) {
                    return 0;
                }
 
            } else {
 
                Graph_readCluster(this->graph, lastTarget, BINARY_CLUSTER_LENGTH, nextCluster, error);
 
                if (*error) {
                    return 0;
                }
            }
 
        } else { // next is zero
 
            unsigned int lastTarget = Graph_readLastTarget(this->graph, currentCluster[0], error);
 
            if (*error) {
                return 0;
            }
 
            if (0 == lastTarget) {
 
                Graph_addCluster(this->graph, BINARY_CLUSTER_LENGTH - 1, nextCluster, error);
 
                if (*error) {
                    return 0;
                }
 
                Graph_addEdge(this->graph, currentCluster[0], nextCluster[0], error);
 
                if (*error) {
                    return 0;
                }
 
            } else {
 
                Graph_readCluster(this->graph, lastTarget, BINARY_CLUSTER_LENGTH, nextCluster, error);
 
                if (*error) {
                    return 0;
                }
            }
        }
 
        swapper = currentCluster;
        currentCluster = nextCluster;
        nextCluster = swapper;
    }
 
    // provide last vertex in cluster
 
    if (0 != currentCluster[BINARY_CLUSTER_LENGTH - 1]) {
        return currentCluster[BINARY_CLUSTER_LENGTH - 1];
    } else {
        return Graph_protrudeCluster(this->graph, currentCluster[BINARY_CLUSTER_LENGTH - 2], error);
    }
}
 
unsigned int Binary_readCode(struct Binary *this, unsigned int code, int *error)
{
    unsigned int output = 0;
 
    unsigned int buffer[BINARY_CLUSTER_LENGTH];
    unsigned int *cluster = buffer;
 
    Graph_readCluster(this->graph, code, BINARY_CLUSTER_LENGTH, cluster, error); // reverse order
 
    if (*error) {
        return 0;
    }
    unsigned int first = cluster[1];
    unsigned int second = cluster[2];
    unsigned int swapper = 0;
 
    while (1) {
 
        unsigned int zeroSource = Graph_readLastSource(this->graph, first, error);
 
        if (*error) {
            return 0;
        }
 
        if (zeroSource == this->root) { // finish
 
            if (first == this->one) {
                output++;
            }
 
            return output;
        }
 
        cluster[BINARY_CLUSTER_LENGTH - 1] = 0;
        Graph_readCluster(this->graph, zeroSource, BINARY_CLUSTER_LENGTH, cluster, error); // order unknown
        
        if (*error) {
            return 0;
        }
 
        if (0 == cluster[BINARY_CLUSTER_LENGTH - 1]) { // two vertices
            first = cluster[0];
            second = cluster[1];
        } else { // three vertices
            if (cluster[2] < cluster[0]) { // bound to one
                first = cluster[0];
                second = cluster[2];
            } else { // bound to zero
                first = cluster[0];
                second = cluster[1];
            }
        }
 
        if (first > second) {
            output++;
            output = output << 1;
        } else {
            output = output << 1;
        }
 
        if (first > second) {
            swapper = first;
            first = second;
            second = swapper;
        }
    }
}