Česky
Kamil Dudka

Non-Uniform CA Designer (C++, GAlib, Boost)

File detail

Name:DownloadCa.h [Download]
Location: nucad > src
Size:10.3 KB
Last modification:2009-07-12 01:46

Source code

/*
 * Copyright (C) 2009 Kamil Dudka <xdudka00@stud.fit.vutbr.cz>
 *
 * This file is part of nucad (Non-Uniform CA Designer).
 *
 * nucad is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * any later version.
 *
 * nucad is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with nucad.  If not, see <http://www.gnu.org/licenses/>.
 */
 
/**
 * @file Ca.h
 * Basic type definitions, classes CaState, CaEvalParams and interfaces
 * ICaRules, IGate and IGateBinding.
 */
 
#ifndef CA_H
#define CA_H
 
#ifndef BUILDING_DOX
#   include <bitset>
#   include <string>
#endif
 
#include <boost/dynamic_bitset.hpp>
 
/**
 * Type used for CA's cells addressing.
 */
typedef signed long TCoord;
 
/**
 * Type used for in/out signals of gate.
 * Consider use of std::bitset if machine does not provide long enough integer.
 */
typedef unsigned long TBus;
 
/**
 * Common state space for cell and neighbors size (Von Neuman's neighborhood).
 */
#define RULE_WIDTH (1 << 5)
 
/**
 * Type for one-cell rule definition (32bit bitset).
 */
typedef std::bitset<RULE_WIDTH> TRule5N;
 
/**
 * Possible direction enumeration.
 * D_NULL is commonly used for the cell self.
 */
enum EDirection {
    D_NULL = 0,
    D_TOP,
    D_RIGHT,
    D_BOTTOM,
    D_LEFT,
    D_ONE_AFTER_LAST
};
 
/**
 * CA cell position.
 */
struct Pos {
    TCoord row;
    TCoord col;
 
    Pos(): row(0), col(0) { }
    Pos(TCoord row_, TCoord col_):
        row(row_),
        col(col_)
    {
    }
};
 
/**
 * Write CA rule in human-readable (colorized if possible) format.
 * @param str Standard output stream to write to.
 * @param rule The CA rule ought to be write.
 */
void writeRule(std::ostream &str, const TRule5N &rule);
 
/**
 * Return position of cell's neighbor.
 * @note There is no range check, no extra and/or intelligent behavior.
 * @param pos Self position of the cell.
 * @param dir Direction to look for neighbor.
 */
inline Pos neighbor(Pos pos, EDirection dir) {
    switch (dir) {
        case D_TOP:     return Pos(pos.row - 1, pos.col);
        case D_RIGHT:   return Pos(pos.row, pos.col + 1);
        case D_BOTTOM:  return Pos(pos.row + 1, pos.col);
        case D_LEFT:    return Pos(pos.row, pos.col - 1);
        default:        return pos;
    }
}
 
/**
 * Simple CA state representation.
 * The CA has fixed size [width = height] and two possible states per cell.
 * Cyclic or hard-zeroed CA's boundary can be switched by the
 * CA_CYCLIC_NEIGHBORHOOD compile-time option.
 */
class CaState {
    public:
        /**
         * @param size Size of 2D CA in @b one direction. It means the CA will
         * have size*size cells in sum.
         */
        CaState(size_t size);
 
        /**
         * Return size of CA in @b one direction.
         */
        size_t size() const;
 
        /**
         * Return cell state at given position (respecting selected boundary
         * settings).
         * @param pos Position of the cell whose state ought be returned.
         */
        bool getCellAtPos(Pos pos) const;
 
        /**
         * Set cell state at given position to given value (respecting selected
         * boundary settings).
         * @param pos Position of the cell whose state is being changed.
         * @param val New value (state) for the selected cell.
         */
        void setCellAtPos(Pos pos, bool val);
 
        bool operator== (const CaState &other) const;
        bool operator!= (const CaState &other) const {
            return !operator== (other);
        }
 
    private:
        size_t size_;
        boost::dynamic_bitset <> bitset_;
};
 
/**
 * Write CA state in human-readable (colorized if possible) format.
 * @param str Standard output stream to write to.
 * @param state The CA state ought to be write.
 */
std::ostream& operator<< (std::ostream &str, const CaState &state);
 
/**
 * Return the result of applied rule.
 * The given CA is not changed at all.
 * @param ca The CA's state to compute new value for.
 * @param pos Position of the cell to compute the new value for.
 * @param rule The rule ought to be applied.
 */
bool applyRule(const CaState &ca, Pos pos, const TRule5N &rule);
 
/**
 * The most generic interface of designed (and/or simulated) circuit, most
 * commonly a logical gate. You want to implement this interface to define
 * your own circuit, usually not directly, but using same abstract base class
 * which implements the common part of your circuit.
 */
class IGate {
    public:
        virtual ~IGate() { }
 
        /**
         * Each final derivation of IGate has to override this method with
         * self-cloning method to keep the simulator working. If you find
         * a way how to do it generically at the top level, please send
         * a patch to nucad@dudka.cz.
         */
        virtual IGate* clone() const = 0;
 
        /**
         * Override this method to return number of circuit's input signals.
         */
        virtual size_t nInputs() const = 0;
 
        /**
         * Override this method to return number of circuit's output signals.
         */
        virtual size_t nOutputs() const = 0;
 
        /**
         * (the core method of IGate interface) Override it to define circuit's
         * behavior.
         * @param in Input passed to gate.
         * @return Returns corresponding output of the gate to given input.
         */
        virtual TBus operator[] (TBus in) const = 0;
};
 
/**
 * Interface to define a binding between simulated gate and designed CA.
 */
class IGateBinding {
    public:
        virtual ~IGateBinding() { }
 
        /**
         * Each final derivation of IGateBinding has to override this method
         * with self-cloning method to keep the simulator working. If you find
         * a way how to do it generically at the top level, please send
         * a patch to nucad@dudka.cz.
         */
        virtual IGateBinding* clone() const = 0;
 
        /**
         * Projection of given input to CA's state referred.
         * @param state CA state being changed.
         * @param in Input ought to be passed to CA state.
         */
        virtual void setInput(CaState &state, TBus in) const = 0;
 
        /**
         * Projection of given output to CA's state referred.
         * @note Currently used only by visualizer.
         * @param state CA state being changed.
         * @param out Output ought to be passed to CA state.
         */
        virtual void setOutput(CaState &state, TBus out) const = 0;
 
        /**
         * Gather gate's output from CA's state.
         * @param state CA's state to read output from.
         * @return Return the gathered gate's output.
         */
        virtual TBus getOutput(const CaState &state) const = 0;
};
 
/**
 * Interface to define rules of non-uniform CA.
 */
class ICaRules {
    public:
        virtual ~ICaRules() { }
        virtual ICaRules* clone() const = 0;
 
        /**
         * Return the rule at given position.
         * @param pos Position to read the rule from.
         * @param rule Destination to write the rule to.
         */
        virtual void getRuleAtPos(Pos pos, TRule5N &rule) const = 0;
};
 
/**
 * Apply the given rule set on given CA state @b synchronously and check if
 * anything is changed.
 * @param state CA state to apply the rule set on.
 * @param rules The set of rules ought to be applied.
 */
bool applyRules(CaState &state, const ICaRules *rules);
 
/**
 * CA evaluation parameters.
 * @attention There is no default constructor, thus no default initialization.
 * You can define one in a derived class or initialize it manually.
 */
struct CaEvalParams {
    size_t caSize;                  // CA's size in one direction
    size_t nSteps;                  // CA's simulation limit for count of steps
};
 
/**
 * CA evaluator runs the given CA and evaluates its fitness for the desired
 * purpose. Moreover it can gathers various statistics about the CA's run,
 * mostly useful to present the found solution to user.
 */
class CaEvaluator {
    public:
        /**
         * @param gate Gate definition used to compute CA's fitness.
         * @param binding Binding object defining gate-CA signals mapping.
         * @param params Additional evaluation parameters.
         */
        CaEvaluator(
                const IGate &gate,
                const IGateBinding &binding,
                const CaEvalParams &params);
        ~CaEvaluator();
 
        /**
         * Return size of CA in @b one direction.
         */
        size_t caSize() const;
 
        /**
         * Evaluate given CA and compute its fitness.
         * @param ca Non-uniform CA defined by the set of rules.
         * @return Return CA's fitness in the range <0, 1>. 0 means useless,
         * 1 means "solution found".
         */
        float eval(const ICaRules *ca);
 
        /**
         * Simulate given CA and check how much steps it needs to compute
         * the desired result. The maximum is bounded by params.nSteps value
         * given as initialization parameter.
         * @param ca Non-uniform CA defined by the set of rules.
         * @param min Destination to store minimal steps value.
         * @param max Destination to store maximal steps value.
         */
        bool cntSteps(const ICaRules *ca, unsigned &min, unsigned &max);
 
        /**
         * Simulate given CA for given input and dump to stream
         * in human-readable (colorized if possible) format.
         * @param ca Non-uniform CA defined by the set of rules.
         * @param str Standard output stream to dump the output.
         * @param in Desired gate's input to simulate CA for.
         */
        void simulate(const ICaRules *ca, std::ostream &str, TBus in);
 
        /**
         * Simulate given CA for all possible inputs and dump to stream
         * in human-readable (colorized if possible) format.
         * @param str Standard output stream to dump the output.
         * @param ca Non-uniform CA defined by the set of rules.
         */
        void simulate(const ICaRules *ca, std::ostream &str);
 
    private:
        struct Private;
        Private *d;
};
 
#endif // CA_H