00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #include <map>
00021 #include <list>
00022 #include <iosfwd>
00023
00024 #include <y2pm/PMSolvablePtr.h>
00025 #include <y2pm/PkgSet.h>
00026
00027
00035 class InstallOrder
00036 {
00037 public:
00038 typedef std::list<constPMSolvablePtr> SolvableList;
00039
00040 private:
00041 PkgSet _toinstall;
00042 PkgSet _installed;
00043
00045 typedef std::map<constPMSolvablePtr,SolvableList> Graph;
00046
00048 Graph _graph;
00049
00051 Graph _rgraph;
00052
00053 struct NodeInfo
00054 {
00055 unsigned begintime;
00056 unsigned endtime;
00057 bool visited;
00058 int order;
00059
00060 PMSolvablePtr solvable;
00061
00062 NodeInfo() : begintime(0), endtime(0), visited(false), order(0) {}
00063 NodeInfo(PMSolvablePtr ptr) : begintime(0), endtime(0), visited(false), order(0), solvable(ptr) {}
00064 };
00065
00066 typedef std::map<constPMSolvablePtr,NodeInfo> Nodes;
00067
00068 Nodes _nodes;
00069
00070 unsigned _rdfstime;
00071
00072 SolvableList _topsorted;
00073
00074 bool _dirty;
00075
00076 unsigned _numrun;
00077
00078 private:
00079 void rdfsvisit(constPMSolvablePtr node);
00080
00081 public:
00082
00089 InstallOrder(const PkgSet& toinstall, const PkgSet& installed);
00090
00095 SolvableList computeNextSet();
00096
00101 void setInstalled( constPMSolvablePtr ptr );
00102
00106 void setInstalled( const SolvableList& list );
00107
00108
00112 void startrdfs();
00113
00118 void init() { startrdfs(); }
00119
00125 const SolvableList& getTopSorted() const;
00126
00127 const void printAdj(std::ostream& os, bool reversed = false) const;
00128 };