00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "zypp/solver/detail/Types.h"
00023 #include "zypp/solver/detail/QueueItemBranch.h"
00024 #include "zypp/solver/detail/QueueItem.h"
00025 #include "zypp/solver/detail/Resolver.h"
00026 #include "zypp/base/Logger.h"
00027
00029 namespace zypp
00030 {
00031
00032 namespace solver
00033 {
00034
00035 namespace detail
00036 {
00037
00038 using namespace std;
00039
00040 IMPL_PTR_TYPE(QueueItemBranch);
00041
00042
00043
00044 std::ostream &
00045 QueueItemBranch::dumpOn( std::ostream & os ) const
00046 {
00047 os << "[Branch: ";
00048 if (!_label.empty()) {
00049 os << _label;
00050 }
00051 os << ", " << _possible_qitems.size() << " items." << endl << "\t";
00052 os << _possible_qitems << endl << "\t";
00053 os << "]";
00054 return os;
00055 }
00056
00057
00058
00059 QueueItemBranch::QueueItemBranch (const ResPool & pool)
00060 : QueueItem (QUEUE_ITEM_TYPE_BRANCH, pool)
00061 {
00062 }
00063
00064
00065 QueueItemBranch::~QueueItemBranch()
00066 {
00067 }
00068
00069
00070
00071 void
00072 QueueItemBranch::addItem (QueueItem_Ptr subitem)
00073 {
00074 assert (static_cast<QueueItem*>(this) != subitem);
00075 #if 0
00076
00077 for (QueueItemList::iterator pos = _possible_qitems.begin(); pos != _possible_qitems.end(); pos++) {
00078
00079 if ((*pos)->cmp(subitem) >= 0) {
00080 _possible_qitems.insert (pos, subitem);
00081 return;
00082 }
00083 }
00084 #endif
00085 _possible_qitems.push_back (subitem);
00086
00087 return;
00088 }
00089
00090
00091 bool
00092 QueueItemBranch::contains (QueueItem_Ptr possible_subbranch)
00093 {
00094 QueueItemBranch_Ptr branch = dynamic_pointer_cast<QueueItemBranch>(possible_subbranch);
00095
00096 if (branch == NULL
00097 || !branch->isBranch()) {
00098 return false;
00099 }
00100
00101 if (_possible_qitems.size() < branch->_possible_qitems.size()) {
00102 return false;
00103 }
00104
00105 QueueItemList::iterator iter = _possible_qitems.begin();
00106 QueueItemList::iterator iter_sub = branch->_possible_qitems.begin();
00107
00108
00109
00110
00111
00112 while (iter_sub != branch->_possible_qitems.end()) {
00113
00114 while (iter != _possible_qitems.end()
00115 && (*iter)->cmp (*iter_sub)) {
00116 iter++;
00117 }
00118
00119 if (iter == _possible_qitems.end())
00120 return false;
00121
00122 iter++;
00123 iter_sub++;
00124 }
00125
00126 return true;
00127 }
00128
00129
00130
00131 bool
00132 QueueItemBranch::process (ResolverContext_Ptr context, QueueItemList & qil)
00133 {
00134 _XDEBUG("QueueItemBranch::process(" << *this << ")");
00135
00136 QueueItemList live_branches;
00137 unsigned int branch_count;
00138 bool did_something = true;
00139
00140 for (QueueItemList::const_iterator iter = _possible_qitems.begin(); iter != _possible_qitems.end(); iter++) {
00141
00142 QueueItem_Ptr item = *iter;
00143 _XDEBUG("_possible_qitem " << *item);
00144 if (item->isSatisfied (context)) {
00145 _XDEBUG("is satisfied");
00146 goto finished;
00147 }
00148
00149
00150 if (! item->isRedundant (context)) {
00151 _XDEBUG("not redundant");
00152 live_branches.push_front (item);
00153 }
00154 }
00155
00156 branch_count = live_branches.size();
00157 _XDEBUG("branch_count " << branch_count);
00158
00159 if (branch_count == 0) {
00160
00161
00162
00163 } else if (branch_count == 1) {
00164
00165
00166
00167 QueueItem_Ptr item = live_branches.front();
00168 did_something = item->process (context, qil);
00169
00170
00171
00172
00173
00174 for (QueueItemList::iterator iter = _possible_qitems.begin(); iter != _possible_qitems.end(); iter++) {
00175 if (*iter == item) {
00176 _possible_qitems.erase (iter);
00177 break;
00178 }
00179 }
00180
00181 } else if (branch_count == _possible_qitems.size()) {
00182 _XDEBUG("Nothing was eliminated");
00183
00184
00185 qil.push_front (this);
00186 did_something = false;
00187
00188 } else {
00189 _XDEBUG("rebranching");
00190 QueueItemBranch_Ptr new_branch = new QueueItemBranch (pool());
00191 for (QueueItemList::const_iterator iter = live_branches.begin(); iter != live_branches.end(); iter++) {
00192 new_branch->addItem ((*iter)->copy());
00193 }
00194 qil.push_front (new_branch);
00195 }
00196
00197 finished:
00198
00199 return did_something;
00200 }
00201
00202
00203 int
00204 QueueItemBranch::cmp (QueueItem_constPtr item) const
00205 {
00206 int cmp = this->compare (item);
00207 if (cmp != 0)
00208 return cmp;
00209
00210 QueueItemBranch_constPtr branch = dynamic_pointer_cast<const QueueItemBranch>(item);
00211
00212
00213 cmp = CMP(_possible_qitems.size(), branch->_possible_qitems.size());
00214 if (cmp != 0)
00215 return cmp;
00216
00217
00218 QueueItemList::const_iterator ia = _possible_qitems.begin();
00219 QueueItemList::const_iterator ib = branch->_possible_qitems.begin();
00220
00221 while (ia != _possible_qitems.end() && ib != branch->_possible_qitems.end()) {
00222 if (*ia && *ib) {
00223 cmp = (*ia)->cmp (*ib);
00224 if (cmp != 0) {
00225 return cmp;
00226 }
00227 }
00228 ia++;
00229 ib++;
00230 }
00231
00232
00233 assert (ia == _possible_qitems.end() && ib == branch->_possible_qitems.end());
00234
00235 return 0;
00236 }
00237
00238
00239 QueueItem_Ptr
00240 QueueItemBranch::copy (void) const
00241 {
00242 QueueItemBranch_Ptr new_branch = new QueueItemBranch (pool());
00243 new_branch->QueueItem::copy(this);
00244 for (QueueItemList::const_iterator iter = _possible_qitems.begin(); iter != _possible_qitems.end(); iter++) {
00245 QueueItem_Ptr cpy = (*iter)->copy();
00246 new_branch->_possible_qitems.push_front (cpy);
00247 }
00248
00249 return new_branch;
00250 }
00251
00253 };
00256 };
00259 };
00261