00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030 #ifndef ZYPP_SOLVER_DETAIL_INSTALLORDER_H
00031 #define ZYPP_SOLVER_DETAIL_INSTALLORDER_H
00032
00033 #include <list>
00034 #include <map>
00035
00036 #include "zypp/PoolItem.h"
00037 #include "zypp/ResPool.h"
00038 #include "zypp/CapSet.h"
00039
00040 #include "zypp/solver/detail/Types.h"
00041
00043 namespace zypp
00044 {
00045
00046 namespace solver
00047 {
00048
00049 namespace detail
00050 {
00051
00060 class InstallOrder
00061 {
00062 private:
00063 const ResPool & _pool;
00064 PoolItemSet _toinstall;
00065 PoolItemSet _installed;
00066
00068 typedef std::map<PoolItem_Ref, PoolItemList> Graph;
00069
00071 Graph _graph;
00072
00074 Graph _rgraph;
00075
00076 struct NodeInfo
00077 {
00078 unsigned begintime;
00079 unsigned endtime;
00080 bool visited;
00081 int order;
00082
00083 PoolItem_Ref item;
00084
00085 NodeInfo() : begintime(0), endtime(0), visited(false), order(0) {}
00086 NodeInfo(PoolItem_Ref item) : begintime(0), endtime(0), visited(false), order(0), item(item) {}
00087 };
00088
00089 typedef std::map<PoolItem_Ref, NodeInfo> Nodes;
00090
00091 Nodes _nodes;
00092
00093 unsigned _rdfstime;
00094
00095 PoolItemList _topsorted;
00096
00097 bool _dirty;
00098
00099 unsigned _numrun;
00100
00101 private:
00102 void rdfsvisit (PoolItem_Ref item);
00103
00104 PoolItem_Ref findProviderInSet( const Capability requirement, const PoolItemSet & candidates ) const;
00105 bool doesProvide( const Capability requirement, PoolItem_Ref item ) const;
00106
00107 public:
00108
00115 InstallOrder( const ResPool & pool, const PoolItemSet & toinstall, const PoolItemSet & installed);
00116
00121 PoolItemList computeNextSet();
00122
00127 void setInstalled( PoolItem_Ref item );
00128
00132 void setInstalled( const PoolItemList & list );
00133
00137 void startrdfs();
00138
00143 void init() { startrdfs(); }
00144
00150 const PoolItemList getTopSorted() const;
00151
00152 const void printAdj (std::ostream & os, bool reversed = false) const;
00153 };
00154
00156 };
00159 };
00162 };
00164
00165 #endif // ZYPP_SOLVER_DETAIL_INSTALLORDER_H