/home/enzo/treballs/fib/pfc/nanocomp/src/simulation.cpp

Go to the documentation of this file.

/*
 *                                                                         *
 *   This program 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 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program 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 this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
                                                                          */

// $Revision: 1.13 $

#include "simulation.hpp"
#include <iostream>
#include <map>

using namespace std;


Simulation::Simulation(SimulationView *view, SimulationManager *controller, Grid initialLayout, list<Rule> *rules, list<ForbiddenPattern> *patterns)
{
    finalLayouts = new list<simulationStep>;
    patternsSimulated = new list<Grid>;
    patternsToSimulate = new list<simulationStep>;
    forbiddenPatternsFound = new list<simulationStep>;
    cycles = new list<simulationStep>;
    simulationStep s;
    s.space = initialLayout;
    patternsToSimulate->push_back(s);
    this->rules = rules;
    this->patterns = patterns;
    this->view = view;
    this->controller = controller;
    view->setGrid(initialLayout, true);
    view->Show(true);
    finished = false;
    simulating = false;
    stillRows = true;
}


Simulation::~Simulation()
{
}



list<coordinate> Simulation::findRule(Grid layout, Rule rule)
{
    list<coordinate> result;
    for (int i = 0; i < layout.getWidth(); i++)
    {
        for (int j = 0; j < layout.getHeight(); j++)
        {
            coordinate c;
            c.x = i;
            c.y = j;
            if (ruleApplicable(layout, c, rule))
            {
                result.push_back(c);
                //cout << "Applies!!!!" << endl;
            }
        }
    }
    return result;
}



list<coordinate> Simulation::findPattern(Grid layout, ForbiddenPattern pattern)
{
    list<coordinate> result;
    for (int i = 0; i < layout.getWidth(); i++)
    {
        for (int j = 0; j < layout.getHeight(); j++)
        {
            coordinate c;
            c.x = i;
            c.y = j;
            if (patternApplicable(layout, c, pattern))
            {
                result.push_back(c);
                //cout << "Applies!!!!" << endl;
            }
        }
    }
    return result;
}



Grid Simulation::applyRule(Grid layout, Rule rule, coordinate position)
{
    //TODO: check the nDONTCARE match with nDISABLED thing
    Grid result(layout);
    for (int i = 0; i < rule.getWidth(); i++)
    {
        for (int j = 0; j < rule.getHeight(); j++)
        {
            if (rule.getFinalGrid()(i, j) != nDONTCARE) //if it's don't care the actual value should stay unchanged
            {
                                //HERE HERE HERE HERE HERE HERE
                if ((rule.getInitialGrid()(i, j) == nDISABLED) && (layout(position.x + i, position.y + j) == nDONTCARE))
                {
                    result(position.x + i, position.y + j) = nDONTCARE;
                }
                else
                {
                    result(position.x + i, position.y + j) = rule.getFinalGrid()(i, j);
                }
            }
        }
    } 
    return result;
}



bool Simulation::ruleApplicable(Grid layout, coordinate position, Rule rule)
{
    if (rule.getWidth() > layout.getWidth() - position.x)
    {
        return false;
    }
    if (rule.getHeight() > layout.getHeight() - position.y)
    {
        return false;
    }
    //First we check if left side of the rule applies
    //Careful, if nDISABLED on rule and nDONTCARE in SPACE
    //we return YES
    //TODO ask jcarmona if this is really what he wants
    //TODO if this is the case modify the rule apply because
    //it will add nDISABLED where there should be
    //nDONTCARE
    for (int i = 0; i < rule.getWidth(); i++)
    {
        for (int j = 0; j < rule.getHeight(); j++)
        {
            //cout << "Comparing (r) " << rule.initial[i][j] << " to (p) " << layout[position.x + i][position.y + j] << endl;
            if (rule.getInitialGrid()(i, j) == nENABLED)
            {
                if (layout(position.x + i, position.y + j) != nENABLED)
                {
                    return false;
                }
            }
            else if (rule.getInitialGrid()(i, j) == nDISABLED)
            {
                //HERE HERE HERE HERE HERE
                if ((layout(position.x + i, position.y + j) != nDISABLED) && (layout(position.x + i, position.y + j) != nDONTCARE))
                {
                    return false;
                }
            }
        }
    }
    return true;
}



void Simulation::printRule(Rule rule)
{
    cout << "Initial" << endl;
    for (int i = 0; i < rule.getWidth(); i++)
    {
        for (int k = 0; k < i; k++)
        {
            cout << "  ";
        }
        for (int j = 0; j < rule.getHeight(); j++)
        {
            cout << rule.getInitialGrid()(i, j) << "  ";
        }
        cout << endl;
    }
    
    cout << endl;
    cout << "Final" << endl;
    for (int i = 0; i < rule.getWidth(); i++)
    {
        for (int k = 0; k < i; k++)
        {
            cout << "  ";
        }
        for (int j = 0; j < rule.getHeight(); j++)
        {
            cout << rule.getFinalGrid()(i, j) << "  ";
        }
        cout << endl;
    }
}



void Simulation::printLayout(Grid layout)
{
    for (int i = 0; i < layout.getWidth(); i++)
    {
        for (int k = 0; k < i; k++)
        {
            cout << " ";
        }
        for (int j = 0; j < layout.getHeight(); j++)
        {
            cout << layout(i, j) << " ";
        }
        cout << endl;
    }
}



bool Simulation::find(Grid initialLayout, list<Grid> *processedLayouts)
{
    for (list<Grid>::iterator i = processedLayouts->begin(); i != processedLayouts->end(); i++)
    {
        if (initialLayout == (*i))
        {
            return true;
        }
    }
    return false;
}



bool Simulation::patternApplicable(Grid layout, coordinate position, ForbiddenPattern pattern)
{
    if (pattern.getWidth() > layout.getWidth() - position.x)
    {
        return false;
    }
    if (pattern.getHeight() > layout.getHeight() - position.y)
    {
        return false;
    }

    for (int i = 0; i < pattern.getWidth(); i++)
    {
        for (int j = 0; j < pattern.getHeight(); j++)
        {
            if (pattern.getGrid()(i, j) == nENABLED)
            {
                if (layout(position.x + i, position.y + j) != nENABLED)
                {
                    return false;
                }
            }
            else if (pattern.getGrid()(i, j) == nDISABLED)
            {
                if (layout(position.x + i, position.y + j) != nDISABLED)
                {
                    return false;
                }
            }
            else //DON'T CARE
            {
                if (layout(position.x + i, position.y + j) == nNOSPACE)
                {
                    return false;
                }
            }
        }
    }
    return true;
}



bool Simulation::isFinished()
{
    return finished;
}


//IMPORTANT: this function must NOT BE CALLED
//if the stack is empty
//TODO: check cicles

bool Simulation::nextStep(bool gui)
{
    //"Semaphore" for not calling this method reentrant
    if (simulating)
    {
        return true;
    }
    simulating = true;
    wxStopWatch sw;
    bool result = true;
    bool stable = false;
    if (!finished)
    {
        //We take the layout we have to process from
        //the queue
        simulationStep s = patternsToSimulate->back();
        Grid layout = s.space;
        //Then we eliminate it because it's considered already processed
        //by this step ofc and add it to the processed list
        patternsToSimulate->pop_back();
        patternsSimulated->push_back(layout);
        if (gui)
        {
            view->setGrid(layout, false);
        }
        
        //Time to process: find forbidden patterns
        for (list<ForbiddenPattern>::iterator i = patterns->begin(); i != patterns->end(); i++)
        {
            list<coordinate> tempCoordinates;
            wxStopWatch swPattern;
            tempCoordinates = findPattern(layout, (*i));
            if (gui)
            {
                view->setInfo(wxString::Format(_("The pattern finding took %ldms to execute"), swPattern.Time()));
            }
            if (tempCoordinates.size() > 0) //Found a forbidden pattern
            {
                if (gui)
                {
                    view->setInfo(wxString::Format(_("Forbidden pattern found at %d, %d"), tempCoordinates.front().x, tempCoordinates.front().y));
                }
                finished = true;
                result = false;
                if (gui)
                {
                    updateView();
                }
            }
        }
        
        if (result)
        {
            //Time to find rules to apply
            list<ruleApplying> rulesToApply;
            for (list<Rule>::iterator i = rules->begin(); i != rules->end(); i++)
            {
                list<coordinate> tempCoordinates;
                wxStopWatch swRule;
                tempCoordinates = findRule(layout, (*i));
                if (gui)
                {
                    view->setInfo(wxString::Format(_("The rule finding took %ldms to execute"), swRule.Time()));
                }
                if (tempCoordinates.size() > 0)
                {
                    for (list<coordinate>::iterator j = tempCoordinates.begin(); j != tempCoordinates.end(); j++)
                    {
                        ruleApplying ruleToApply;
                        ruleToApply.rule = &(*i);
                        ruleToApply.c = (*j);
                        rulesToApply.push_back(ruleToApply);
                    }
                }
            }
            
            //Stable layout
            if (gui)
            {
                view->setInfo(wxString::Format(_("Number or applicable rules found: %d"), rulesToApply.size()));
            }

            if (rulesToApply.size() == 0)
            {
                //Stable configuration, we return yes and the stable layout
                finalLayouts->push_back(s);
                if (gui)
                {
                    view->setInfo(_("Reached stable layout"));
                }
                result = true;
                stable = true;
            }
            else
            {
                result = true;
                //We apply the rules we can and add the resulting
                //layout to the queue to be processed
                for(list<ruleApplying>::iterator i = rulesToApply.begin(); i != rulesToApply.end(); i++)
                {
                    //Apply the rule
                    if (gui)
                    {
                        view->setInfo(wxString::Format(_("Applying rule at %d, %d"), (*i).c.x, (*i).c.y));
                    }
                    Grid changedLayout = applyRule(layout, *(*i).rule, (*i).c);
                    
                    //If the resulting layout is in the processed queue
                    //we don't have to simulate it again
                    //TODO: check correctness and cycles here
                    //Cycles
                    //We must try to find the simulated pattern in the 
                    //current path
                    if (find(changedLayout, &(s.path)))
                    {
                        list<Grid> newList = s.path;
                        newList.push_back(layout);
                        simulationStep newStep;
                        newStep.path = newList;
                        newStep.space = changedLayout;
                        cycles->push_back(newStep);
                        if (gui)
                        {
                            view->setInfo(_("Cycle found"));
                        }
                    }
                    if (!find(changedLayout, patternsSimulated))
                    {
                        if (gui)
                        {
                            view->setInfo(_("Adding the resulting space to the queue to be simulated"));
                        }
                        list<Grid> newList = s.path;
                        newList.push_back(layout);
                        simulationStep newStep;
                        newStep.path = newList;
                        newStep.space = changedLayout;
                        patternsToSimulate->push_back(newStep);
                    }
                    else
                    {
                        if (gui)
                        {
                            view->setInfo(_("The resulting space has been already simulated"));
                        }
                    }
                }
                result = true;
            }
        }
        else
        {
            forbiddenPatternsFound->push_back(s);
            controller->finishedRow();
        }
        //Aqui entrem tan si hem trobat patrons prohibits com si no?
        //Si trobem patrons prohibits hauriem de plegar
        //però de moment per fer debugging ja va bé
        //We are finished if there are no more
        //layouts to process
        if (patternsToSimulate->empty())
        {
            if (gui)
            {
                view->setInfo(_("No more spaces to simulate"));
            }
            finished = true;
            result = true;
            controller->finishedRow();
            if (gui)
            {
                updateView();
            }
        }
        else
        {
            if (stable)
            {
                if (gui)
                {
                    view->setInfo(_("Backtracking to a previous applied rule"));
                }
            }
        }
    }
    else
    {
        result = true;
    }
    if (gui)
    {
        view->setInfo(wxString::Format(_("The simulation step took %ldms to execute"), sw.Time()));
    }
    simulating = false;
    return result;
}



void Simulation::updateView()
{
    if (finished)
    {
        if (controller->nextRow())
        {
            view->setResults(false);
            view->setNextRow(true);
            view->enableSimulation(false);
        }
        else
        {
            view->setResults(true);
            view->setNextRow(false);
            view->enableSimulation(false);
        }
    }
}


void Simulation::nextRow()
{
    if (controller->nextRow())
    {
        controller->simulateRow();
        view->setResults(false);
        view->setNextRow(false);
        view->enableSimulation(true);
    }
    else
    {
        view->setResults(true);
        view->setNextRow(false);
        view->enableSimulation(true);
    }
}


void Simulation::results()
{
    controller->results();
}



list<simulationStep> Simulation::getStableLayouts()
{
    list<simulationStep> result;
    for (list<simulationStep>::iterator i = finalLayouts->begin(); i != finalLayouts->end(); i++)
    {
        result.push_back((*i));
    }
    return result;
}



list<Grid> Simulation::getProcessedLayouts()
{
    list<Grid> result;
    for (list<Grid>::iterator i = patternsSimulated->begin(); i != patternsSimulated->end(); i++)
    {
        result.push_back((*i));
    }
    return result;
}



list<simulationStep> Simulation::getForbiddenLayouts()
{
    list<simulationStep> result;
    for (list<simulationStep>::iterator i = forbiddenPatternsFound->begin(); i != forbiddenPatternsFound->end(); i++)
    {
        result.push_back((*i));
    }
    return result;
}



list<simulationStep> Simulation::getCycles()
{
    list<simulationStep> result;
    for (list<simulationStep>::iterator i = cycles->begin(); i != cycles->end(); i++)
    {
        result.push_back((*i));
    }
    return result;
}



void Simulation::resetSimulation(SimulationView *view, SimulationManager *controller, Grid initialLayout, list<Rule> *rules, list<ForbiddenPattern> *patterns)
{
    //cout << "Resetting simulation" << endl;
    finalLayouts->clear();
    patternsSimulated->clear();
    patternsToSimulate->clear();
    forbiddenPatternsFound->clear();
    cycles->clear();
    simulationStep s;
    s.space = initialLayout;
    patternsToSimulate->push_back(s);
    this->rules = rules;
    this->patterns = patterns;
    this->view = view;
    this->controller = controller;
    view->setGrid(initialLayout, true);
    view->Show(true);
    finished = false;
    stillRows = true;
    view->Enable(true);
    view->stopSimulation();
}




void Simulation::simulateAll()
{
    view->enableSimulation(false);
    view->setNextRow(false);
    view->setResults(false);
    while (stillRows)
    {
        while (!finished)
        {
            nextStep(false);
        }
        if (controller->nextRow())
        {
            controller->simulateRow();
        }
        else
        {
            stillRows = false;
        }
    }
    view->setResults(true);
}

---