QueueItemBranch.cc

Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 4 -*- */
00002 /* QueueItemBranch.cc
00003  *
00004  * Copyright (C) 2000-2002 Ximian, Inc.
00005  * Copyright (C) 2005 SUSE Linux Products GmbH
00006  *
00007  * This program is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU General Public License,
00009  * version 2, as published by the Free Software Foundation.
00010  *
00011  * This program is distributed in the hope that it will be useful, but
00012  * WITHOUT ANY WARRANTY; without even the implied warranty of
00013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014  * General Public License for more details.
00015  *
00016  * You should have received a copy of the GNU General Public License
00017  * along with this program; if not, write to the Free Software
00018  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
00019  * 02111-1307, USA.
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     // We want to keep the list of possible items sorted for easy comparison later.
00077     for (QueueItemList::iterator pos = _possible_qitems.begin(); pos != _possible_qitems.end(); pos++) {
00078 
00079         if ((*pos)->cmp(subitem) >= 0) {                        // found a larger one
00080             _possible_qitems.insert (pos, subitem);             // insert before
00081             return;
00082         }
00083     }
00084 #endif
00085     _possible_qitems.push_back (subitem);                       // no larger found, subitem must be largest
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     /* For every item inside the possible sub-branch, look for a matching item
00109        in the branch.  If we can't find a match, fail.  (We can do this in one
00110        pass since the possible_qitems lists are sorted)
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         /* Drop any useless branch items */
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         /* Do nothing */
00162 
00163     } else if (branch_count == 1) {
00164 
00165         /* If we just have one possible item, process it. */
00166 
00167         QueueItem_Ptr item = live_branches.front();
00168         did_something = item->process (context, qil);
00169 
00170         /* Set the item pointer to NULL inside of our original branch
00171            item, since our call to rc_queue_item_process is now
00172            responsible for freeing it. */
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         /* Nothing was eliminated, so just pass the branch through. */
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);             // assures equal type
00207     if (cmp != 0)
00208         return cmp;
00209 
00210     QueueItemBranch_constPtr branch = dynamic_pointer_cast<const QueueItemBranch>(item);
00211 
00212     /* First, sort by # of possible items. */
00213     cmp = CMP(_possible_qitems.size(), branch->_possible_qitems.size());
00214     if (cmp != 0)
00215         return cmp;
00216 
00217     /* We can do a by-item cmp since the possible items are kept in sorted order. */
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     /* Both lists should end at the same time, since we initially sorted on length. */
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     };// namespace detail
00256   };// namespace solver
00259 };// namespace zypp
00261 

Generated on Thu Jul 6 00:07:23 2006 for zypp by  doxygen 1.4.6