DataStructures.h

Go to the documentation of this file.

/*
        This file is part of the EnergyOptimizatorOfRoboticCells program.

        EnergyOptimizatorOfRoboticCells 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
        (at your option) any later version.

        EnergyOptimizatorOfRoboticCells 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 EnergyOptimizatorOfRoboticCells. If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef HLIDAC_PES_DATASTRUCTURES_H
#define HLIDAC_PES_DATASTRUCTURES_H

#include <vector>
#include <unordered_map>
#include "RoboticLine.h"
#include "Shared/Utils.h"
#include "Shared/Exceptions.h"

/* PROCESS PHASES OF THE PARALLEL SOLVER */

enum Algo {
        LP_INITIAL_PROBLEM = 0, POWER_MODE_HEURISTIC = 1, LOCATION_CHANGE_HEURISTIC = 2, PATH_CHANGE = 4
};

/* GRAPH REPRESENTATION FOR DISTANCE MATRIX COMPUTATION */

struct Edge {
        StaticActivity *f;
        StaticActivity *t;
        uint32_t i;
        uint32_t j;
        double length;
};

struct Graph {
        std::vector<Edge> edges;
        uint32_t startIdent;
        uint32_t endIdent;
        std::vector<StaticActivity*> idToActivity;
        std::vector<std::vector<Edge>> idToSuccessors;
};

/* HAMILTONIAN CIRCUIT REPRESENTATION */

template <class T>
struct HamiltonianCircuit       {
        double minLength;
        std::vector<T*> circuit;
};

struct ShortestCircuit {
        ShortestCircuit() = default;
        ShortestCircuit(const std::vector<StaticActivity*> arg1, const std::vector<Location*>& arg2) : circuit(arg1), fixedLocations(arg2) { }
        bool operator==(const ShortestCircuit& sc) const {
                return circuit == sc.circuit && fixedLocations == sc.fixedLocations;
        }

        std::vector<StaticActivity*> circuit;
        std::vector<Location*> fixedLocations;
};

struct CircuitRecord {
        CircuitRecord(const ShortestCircuit& arg1, const HamiltonianCircuit<Location>& arg2) : sc(arg1), hc(arg2) { }
        bool operator<(const CircuitRecord& cr) const {
                return hc.minLength < cr.hc.minLength;
        }

        ShortestCircuit sc;
        HamiltonianCircuit<Location> hc;
};

/* GENERATED TUPLE - POTENTIALLY FEASIBLE SOLUTION */

struct CircuitTuple {
        std::vector<CircuitRecord> tuple;
};

/* REPRESENTATION OF LP SOLUTION */

struct OptimalTiming {
        double totalEnergy;
        std::vector<std::vector<double>> startLocs;
        std::vector<std::vector<double>> durLocs;
        std::vector<std::vector<double>> startMvs;
        std::vector<std::vector<double>> durMvs;

        std::map<Activity*, std::pair<double, double>> actToStartAndDur;
        std::map<ActivityMode*, std::pair<double, double>> modeToStartAndDur;
};

/* COLLISION RESOLUTION */

struct CollisionResolution      {
        CollisionResolution() : a1(nullptr), a2(nullptr), multiplier(0), intersection(0.0) { }
        Activity *a1;
        Activity *a2;
        int32_t multiplier;
        double intersection;
};

/* POWER SAVING MODE SELECTION */

struct ModeSwitchInfo {
        ModeSwitchInfo() = default;
        ModeSwitchInfo(uint32_t r, uint32_t l, Location* relLoc, RobotPowerMode* f, RobotPowerMode *t, double ee)
                : robotIdx(r), locationIdx(l), loc(relLoc), from(f), to(t), estimatedEnergy(ee) { }

        bool operator<(const ModeSwitchInfo& msi) const {
                return estimatedEnergy < msi.estimatedEnergy;
        }

        uint32_t robotIdx;
        uint32_t locationIdx;
        Location *loc;
        RobotPowerMode *from;
        RobotPowerMode *to;
        double estimatedEnergy;
};

struct ActivityModeInfo {
        ActivityModeInfo(ActivityMode* m, double s, double d) : mode(m), curStartTime(s), curDuration(d) { }
        ActivityModeInfo(ActivityMode* m, RobotPowerMode* pm, double e, double s, double d, double minDur, double maxDur)
                : mode(m), pwrm(pm), energy(e), curStartTime(s), curDuration(d), minDuration(minDur), maxDuration(maxDur) { }

        bool operator<(const ActivityModeInfo& ami) const {
                return curStartTime < ami.curStartTime;
        }

        ActivityMode *mode;
        RobotPowerMode *pwrm;
        double energy;
        double curStartTime;
        double curDuration;
        double minDuration;
        double maxDuration;
};

/* TABU LIST */

class TabuList {
        public:
                TabuList(const uint32_t& tabuListSize) : mListIdx(0u), mTabu(tabuListSize) { }

                bool isTabu(Location *l, RobotPowerMode *from, RobotPowerMode *to) const {
                        return std::find(mTabu.cbegin(), mTabu.cend(), Element(l, from, to)) != mTabu.cend();
                }

                void addTabu(Location *l, RobotPowerMode *from, RobotPowerMode *to) {
                        assert(!isTabu(l, from, to) && "Adding already forbidden combination!");
                        if (mListIdx < mTabu.size())    {
                                mTabu[mListIdx++] = {l, from, to};
                                mListIdx = (mListIdx % mTabu.size());
                        } else {
                                throw SolverException(caller(), "Cannot add an element to an empty tabu list!");
                        }
                }

                void diversify() {
                        uint32_t startIdx = mListIdx;
                        int32_t toErase = (int32_t) ceil(0.3*mTabu.size());
                        do {
                                if (!mTabu[startIdx].isEmpty()) {
                                        mTabu[startIdx] = Element();
                                        --toErase;
                                }

                                startIdx = ((startIdx+1) % mTabu.size());

                        } while (startIdx != mListIdx && toErase > 0);
                }
        private:
                struct Element {
                        Element() : loc(nullptr), m1(nullptr), m2(nullptr) { }
                        Element(Location *l, RobotPowerMode *rm1, RobotPowerMode *rm2) : loc(l), m1(rm1), m2(rm2) { }

                        bool isEmpty() const {
                                return loc == nullptr && m1 == nullptr && m2 == nullptr;
                        }
                        bool operator==(const Element& e) const {
                                return loc == e.loc && m1 == e.m1 && m2 == e.m2;
                        }

                        Location *loc;
                        RobotPowerMode *m1;
                        RobotPowerMode *m2;
                };

                uint32_t mListIdx;
                std::vector<Element> mTabu;
};

/* MOVING AVERAGE */

template <class T>
class MovingAverage {
        public:
                MovingAverage(uint32_t length) : mLength(length) {
                        if (mLength <= 0)
                                throw InvalidArgument(caller(), "A positive length is expected!");
                }

                double average() const {
                        if (!mData.empty())
                                return std::accumulate(mData.cbegin(), mData.cend(), T())/mData.size();
                        else
                                return T();
                }
                void addValue(const T& val)     {
                        if (mData.size() < mLength)     {
                                mData.push_back(val);
                        } else {
                                mData.erase(mData.begin());
                                mData.push_back(val);
                        }
                }
                bool filled() const {
                        return mData.size() == mLength;
                }
                void clear() {
                        mData.clear();
                }
        private:
                uint32_t mLength;
                std::vector<T> mData;
};

/* USEFUL SHORTCUTS FOR COMPLEX DATA TYPES */

namespace std {
        template <>
        struct hash<ShortestCircuit> {
                uintptr_t operator() (const ShortestCircuit& sc) const {
                        uintptr_t hash1 = hashOW(sc.circuit);
                        uintptr_t hash2 = hashEW(sc.fixedLocations);
                        return hash1^hash2;
                }
        };
}


using PrecalculatedCircuits = std::unordered_map<ShortestCircuit, HamiltonianCircuit<Location>>;

#endif