4-variable-simplifier/simplifications/new.c

#include <debug.h>

#include <defines/M.h>

#include <typedefs/truthtable_t.h>

#include <expression/struct.h>
#include <expression/unreachable/new.h>
#include <expression/literal/new.h>
#include <expression/variable/new.h>
#include <expression/not/new.h>
#include <expression/or/new.h>
#include <expression/and/new.h>
#include <expression/inc.h>
#include <expression/print.h>
#include <expression/free.h>

#include <scope/foreach.h>

#include <truthtable_set/struct.h>
#include <truthtable_set/new.h>
#include <truthtable_set/add.h>
#include <truthtable_set/is_empty.h>
#include <truthtable_set/discard.h>
#include <truthtable_set/foreach.h>
#include <truthtable_set/free.h>

#include <structs/operators.h>

#include "struct.h"
#include "new.h"

struct simplifications* new_simplifications(
    const struct operators* operators,
    const struct scope* scope)
{
    ENTER;
    
    struct simplifications* this = smalloc(sizeof(*this));
    
    // initialize with unreachable:
    {
        struct expression* unreachable = new_unreachable_expression();
        
        for (int i = 0; i < N; i++)
        {
            this->lookup[i] = inc_expression(unreachable);
        }
        
        free_expression(unreachable);
    }
    
    bool consider(
        truthtable_t truthtable,
        struct expression* expression)
    {
        if (expression->cost < this->lookup[truthtable]->cost)
        {
            struct expression **record = &this->lookup[truthtable];
            
            free_expression(*record);
            
            *record = inc_expression(expression);
            
            return true;
        }
        
        return false;
    }
    
    // consider zero literal:
    {
        struct expression* zero = new_literal_expression(
            /* cost = */ 1,
            /* value = */ 0);
        
        consider(
            /* truthtable: */ 0,
            /* expression: */ zero);
        
        free_expression(zero);
    }
    
    // consider one literal:
    {
        struct expression* one = new_literal_expression(
            /* cost = */ 1,
            /* value = */ 1);
        
        consider(
            /* truthtable: */ M,
            /* expression: */ one);
        
        free_expression(one);
    }
    
    // introduce variables:
    {
        scope_foreach(scope, ({
            void foreach(
                struct string* name,
                truthtable_t value)
            {
                printf("value = %016hb\n", value);
                
                struct expression* variable = new_variable_expression(
                    /* cost: */ 1,
                    /* name: */ name);
                
                consider(
                    /* truthtable: */ value,
                    /* expression: */ variable);
                
                free_expression(variable);
            }
            
            foreach;
        }));
    }
    
    struct truthtable_set* done   = new_truthtable_set();
    struct truthtable_set* queued = new_truthtable_set();
    
    for (unsigned i = 0; i < N; i++)
    {
        truthtable_set_add(queued, (truthtable_t) i);
    }
    
    for (unsigned i = 0; i < N; i++)
    {
        truthtable_t truthtable = 0;
        
        int cost = INT_MAX;
        
        truthtable_set_foreach(queued, ({
            void foreach(truthtable_t element_truthtable)
            {
                int element_cost = this->lookup[element_truthtable]->cost;
                
                if (element_cost < cost)
                {
                    truthtable = element_truthtable;
                    
                    cost = element_cost;
                }
            }
            
            foreach;
        }));
        
        printf("queued.len = %lu\n", queued->n);
        
        if (cost == INT_MAX)
        {
            break;
        }
        
        struct expression* expression = this->lookup[truthtable];
        
        {
            printf("truthtable = 0b%016hb, cost = %i: ", truthtable, cost);
            
            expression_print(expression), puts("");
        }
        
        truthtable_set_discard(queued, truthtable);
        
        // consider 'not':
        {
            struct expression* not = new_not_expression(
                /* cost: */ cost + 1,
                /* subexpression: */ expression);
            
            consider(
                /* truthtable: */ (truthtable_t) ~truthtable,
                /* expression: */ not);
            
            free_expression(not);
        }
        
        // consider 'or' and 'and':
        {
            truthtable_set_foreach(done, ({
                void foreach(truthtable_t other_truthtable)
                {
                    struct expression* const other_expression = \
                        this->lookup[other_truthtable];
                    
                    if (other_expression->cost == INT_MAX)
                        return;
                    
                    int op_cost = 0 \
                                + cost \
                                + 1 \
                                + this->lookup[other_truthtable]->cost;
                    
                    struct expression* or = new_or_expression(
                        /* cost: */ op_cost,
                        /* left: */ expression,
                        /* right: */ other_expression);
                    
                    struct expression* and = new_and_expression(
                        /* cost: */ op_cost,
                        /* left: */ expression,
                        /* right: */ other_expression);
                    
                    consider(
                        /* truthtable: */ truthtable | other_truthtable,
                        /* expression: */ or);
                    
                    consider(
                        /* truthtable: */ truthtable & other_truthtable,
                        /* expression: */ and);
                    
                    free_expression(or);
                    free_expression(and);
                }
                foreach;
            }));
        }
        
        truthtable_set_add(done, truthtable);
    }
    
    free_truthtable_set(done);
    free_truthtable_set(queued);
    
    EXIT;
    return this;
}