src/threadgenesorter.h

   1 /***************************************************************************
   2  *   Copyright (C) 2008 by Michael Andreen                                 *
   3  *   andreen@student.chalmers.se                                           *
   4  *                                                                         *
   5  *   This program is free software; you can redistribute it and/or modify  *
   6  *   it under the terms of the GNU General Public License as published by  *
   7  *   the Free Software Foundation; either version 2 of the License, or     *
   8  *   (at your option) any later version.                                   *
   9  *                                                                         *
  10  *   This program is distributed in the hope that it will be useful,       *
  11  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
  12  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
  13  *   GNU General Public License for more details.                          *
  14  *                                                                         *
  15  *   You should have received a copy of the GNU General Public License     *
  16  *   along with this program; if not, write to the                         *
  17  *   Free Software Foundation, Inc.,                                       *
  18  *   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA          *
  19  ***************************************************************************/
  20
  21 #ifndef __THREADGENESORTER_H__
  22 #define __THREADGENESORTER_H__
  23
  24 #include "genesorter.h"
  25 #include "geneorder.h"
  26 #include "model.h"
  27
  28 #include <pthread.h>
  29
  30 #include <queue>
  31 #include <vector>
  32 #include <utility>
  33
  34 extern "C" void* t_sorter(void* arg);
  35 extern "C" void* t_worker(void* arg);
  36
  37 /**
  38  * Finding the set of all possible sorting sequences.
  39  *
  40  * \author Michael Andreen
  41  */
  42 class ThreadGeneSorter : public GeneSorter{
  43         friend void* t_sorter(void* arg);
  44         friend void* t_worker(void* arg);
  45         public:
  46
  47                 struct ScoreCmp {
  48                         template<typename T>
  49                                 bool operator()(T s1, T s2){
  50                                         return s1.first < s2.first;
  51                                 }
  52                 };
  53                 typedef std::priority_queue<std::pair<double,ActionList>,std::vector<std::pair<double,ActionList> >, ScoreCmp > SolutionsQueue;
  54
  55                 struct SortUnit{
  56                         double _score;
  57                         GeneOrder _go;
  58                         ActionList _al;
  59                         SortUnit(double score,const GeneOrder& go,const ActionList& al) : _score(score),_go(go),_al(al){}
  60                         bool operator<(const SortUnit& su) const{
  61                                 return _score < su._score;
  62                         }
  63                 };
  64
  65                 /**
  66                  * Creates a new threaded GeneSorter.
  67                  *
  68                  * \param threads The number of worker threads that you want to spawn.
  69                  */
  70                 ThreadGeneSorter(const Model& m, int threads = 2);
  71
  72                 /**
  73                  * Takes a GeneOrder, and Model.
  74                  *
  75                  * Starts the work to find all possible sorting sequences.
  76                  */
  77                 void start(const GeneOrder& go);
  78
  79                 /**
  80                  * Wait for sorter to end.
  81                  */
  82                 void join();
  83
  84                 /**
  85                  * Returns true while the sorter is running.
  86                  */
  87                 bool running();
  88
  89                 /**
  90                  * Tell the sorter to stop execution.
  91                  */
  92                 void stop();
  93
  94                 /**
  95                  * Number of possible solutions.
  96                  */
  97                 size_t size();
  98
  99                 /**
 100                  * Waits for progress.
 101                  *
 102                  * \param time Max time to wait for, in seconds.
 103                  * \param solutions The minimum number of solutions we'll wait for.
 104                  * \return The best score so far.
 105                  */
 106                 double wait(time_t time, size_t solutions = 1);
 107
 108                 /**
 109                  * Get the full list of solutions.
 110                  */
 111                 SolutionsQueue solutions();
 112
 113                 ~ThreadGeneSorter(){};
 114
 115         private:
 116
 117                 void sorter(const GeneOrder& go);
 118                 void worker();
 119
 120                 typedef std::priority_queue<SortUnit> SortQueue;
 121                 //! Queue for possible sort alternatives.
 122                 SortQueue _queue;
 123                 //! List of full sort sequences.
 124                 SolutionsQueue _solutions;
 125
 126                 bool _done;
 127
 128                 int _workers;
 129
 130                 Model _model;
 131
 132                 pthread_mutex_t _queuelock;
 133                 pthread_mutex_t _solutionslock;
 134
 135                 pthread_cond_t _addedSolution;
 136                 pthread_cond_t _waiting;
 137                 pthread_cond_t _addedTask;
 138
 139                 pthread_t _tid;
 140 };
 141
 142 #endif