/*
* 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 ¶ms);
~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