DAG.h

Go to the documentation of this file.
00001 /* Depends: A generic dependency tracker in C++
00002  * Copyright (c) 2004-2007, Ronald Landheer-Cieslak
00003  * All rights reserved
00004  * 
00005  * This is free software. You may distribute it and/or modify it and
00006  * distribute modified forms provided that the following terms are met:
00007  *
00008  * * Redistributions of the source code must retain the above copyright
00009  *   notice, this list of conditions and the following disclaimer;
00010  * * Redistributions in binary form must reproduce the above copyright
00011  *   notice, this list of conditions and the following disclaimer in
00012  *   the documentation and/or other materials provided with the distribution;
00013  * * None of the names of the authors of this software may be used to endorse
00014  *   or promote this software, derived software or any distribution of this 
00015  *   software or any distribution of which this software is part, without 
00016  *   prior written permission from the authors involved;
00017  * * Unless you have received a written statement from Ronald Landheer-Cieslak
00018  *   that says otherwise, the terms of the GNU General Public License, as 
00019  *   published by the Free Software Foundation, version 2 or (at your option)
00020  *   any later version, also apply.
00021  * 
00022  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
00023  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00024  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00025  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
00026  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
00027  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
00028  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
00029  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
00030  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
00031  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
00032  * POSSIBILITY OF SUCH DAMAGE.
00033  */
00039 #ifndef _depends_dag_h
00040 #define _depends_dag_h
00041 
00042 #include <vector>
00043 #include <algorithm>
00044 #include <boost/iterator/indirect_iterator.hpp>
00045 
00046 #if DEPENDS_SUPPORT_SERIALIZATION
00047 namespace boost { namespace serialization { class access; } }
00048 #include "Details/serialization.hpp"
00049 #endif
00050 
00051 #include "Details/Iterator.h"
00052 #include "Details/Node.h"
00053 #include "Details/CircularReferenceException.h"
00054 #include "Details/ScopedFlag.h"
00055 #include "Details/Visitors.h"
00056 #include "Details/SortPred.h"
00057 #include "Details/Unlinker.h"
00058 
00059 namespace Depends
00060 {
00125         template <class ValueType>
00126         class DAG
00127         {
00128         public :
00129                 // standard types for a container
00130                 typedef ValueType value_type;
00131                 typedef ValueType key_type;
00132                 typedef ValueType & reference;
00133                 typedef const ValueType & const_reference;
00134                 typedef ValueType * pointer;
00135                 typedef const ValueType * const_pointer;
00136                 typedef unsigned long score_type;
00137                 typedef Details::Node<ValueType, score_type> node_type;
00138                 typedef std::vector< node_type* > nodes_type;
00139                 typedef Details::Iterator<
00140                         ValueType, 
00141                         const ValueType &, 
00142                         const ValueType *, 
00143                         score_type, 
00144                         typename nodes_type::iterator> iterator;
00145                 typedef Details::Iterator<
00146                         ValueType, 
00147                         const ValueType &,
00148                         const ValueType *,
00149                         score_type,
00150                         typename nodes_type::iterator> const_iterator;
00151                 typedef Details::ReverseIterator<
00152                         ValueType,
00153                         const ValueType &,
00154                         const ValueType *,
00155                         score_type,
00156                         typename nodes_type::reverse_iterator> reverse_iterator;
00157                 typedef Details::ReverseIterator<
00158                         ValueType,
00159                         const ValueType &,
00160                         const ValueType *,
00161                         score_type,
00162                         typename nodes_type::reverse_iterator>
00163                                 const_reverse_iterator;
00164                 typedef typename std::vector<node_type>::difference_type
00165                         difference_type;
00166                 typedef typename std::vector<node_type>::size_type size_type;
00167 
00170                 typedef Details::CircularReferenceException
00171                         circular_reference_exception;
00172 
00174                 DAG()
00175                 { /* no-op */ }
00177                 DAG(const DAG & d)
00178                         : nodes_(d.nodes)
00179                 { /* no-op */ }
00180         
00182 
00188                 template <typename InputIterator>
00189                 DAG(InputIterator first, InputIterator last)
00190                 {
00191                         insert(first, last);
00192                 }
00193         
00195                 DAG & operator=(const DAG & d)
00196                 {
00197                         nodes_ = d.nodes_;
00198                         return *this;
00199                 }
00200 
00201                 ~DAG()
00202                 {
00203                         for (typename nodes_type::iterator iter = nodes_.begin(); iter != nodes_.end(); ++iter)
00204                                 delete *iter;
00205                 }
00206         
00208                 iterator begin() { return iterator(nodes_.begin()); }
00210                 const_iterator begin() const { return const_iterator(nodes_.begin()); }
00212                 reverse_iterator rbegin() { return reverse_iterator(nodes_.rbegin()); }
00214                 const_reverse_iterator rbegin() const { return const_reverse_iterator(nodes_.rbegin()); }
00215 
00217                 iterator end() { return iterator(nodes_.end()); }
00219                 const_iterator end() const { return const_iterator(nodes_.end()); }
00221                 reverse_iterator rend() { return reverse_iterator(nodes_.rend()); }
00223                 const_reverse_iterator rend() const { return const_reverse_iterator(nodes_.rend()); }
00224 
00226                 size_type size() const { return nodes_.size(); }
00228                 size_type max_size() const { return sizeof(score_type) > sizeof(size_type) ? (size_type)~0 : (score_type)~0; }
00229 
00231                 bool empty() const { return nodes_.empty(); }
00233                 void swap(DAG & d) { nodes_.swap(d.nodes_); }
00234 
00236                 bool operator==(const DAG & d) const
00237                 {
00238                         return (nodes_.size() == d.nodes_.size()) && 
00239                                 std::equal(
00240                                         boost::indirect_iterator< typename nodes_type::const_iterator >(nodes_.begin()),
00241                                         boost::indirect_iterator< typename nodes_type::const_iterator >(nodes_.end()),
00242                                         boost::indirect_iterator< typename nodes_type::const_iterator >(d.nodes_.begin()));
00243                         
00244                 }
00246                 bool operator!=(const DAG & d) const
00247                 {
00248                         return !(*this == d);
00249                 }
00250 
00252                 bool operator<(const DAG & d) const
00253                 {
00254                         return std::lexicographical_compare(
00255                                 boost::indirect_iterator< typename nodes_type::const_iterator >(nodes_.begin()),
00256                                 boost::indirect_iterator< typename nodes_type::const_iterator >(nodes_.end()),
00257                                 boost::indirect_iterator< typename nodes_type::const_iterator >(d.nodes_.begin()),
00258                                 boost::indirect_iterator< typename nodes_type::const_iterator >(d.nodes_.end()),
00259                                 Details::CompareNodesByContents< node_type >()
00260                                 );
00261                 }
00263                 bool operator>(const DAG & d) const { return d < *this; }
00264                 
00266                 bool operator<=(const DAG & d) const { return !(d < *this); }
00268                 bool operator>=(const DAG & d) const { return !(*this < d); }
00269 
00278                 std::pair<iterator, bool> insert(const value_type & val)
00279                 {
00280                         if (std::find_if(nodes_.begin(), nodes_.end(), Details::ValueCompare<node_type>(val)) == nodes_.end())
00281                         {
00282                                 nodes_.insert(nodes_.begin(), new node_type(val));
00283                                 return std::make_pair(begin(), true);
00284                         }
00285                         else
00286                                 return std::make_pair(end(), false);
00287                 }
00288 
00292                 template <typename InputIterator>
00293                 void insert(InputIterator first, InputIterator last)
00294                 {
00295                         for ( ; first != last; ++first)
00296                                 insert(*first);
00297                 }
00298         
00305                 void link(iterator source, iterator target)
00306                 {
00307                         {
00308                                 Details::ScopedFlag<node_type> scoped_flag(source.node(), node_type::VISITED);
00309                                 Details::NodeVisitor<node_type>()(target.node());
00310                         }
00311                         source.node()->targets_.push_back(target.node());
00312 
00313                         // GCC 3.3 doesn't like it when I don't use a local variable for this functor..
00314                         Details::IncScoreFunctor dag_node_inc_score_functor;
00315                         Details::NodeVisitor<node_type, Details::IncScoreFunctor, score_type>(dag_node_inc_score_functor, source.node()->score_)(target.node());
00316 
00317                         std::sort(nodes_.begin(), nodes_.end(), Details::SortPred<node_type>());
00318                 }
00319 
00326                 void link(iterator source, value_type target)
00327                 {
00328                         iterator target_iter = std::find(begin(), end(), target);
00329 
00330                         if (target_iter == end())
00331                                 throw std::invalid_argument("value not found");
00332                         link(source, target_iter);
00333                 }
00334 
00341                 void link(value_type source, iterator target)
00342                 {
00343                         iterator source_iter = std::find(begin(), end(), source);
00344 
00345                         if (source_iter == end())
00346                                 throw std::invalid_argument("value not found");
00347                         link(source_iter, target);
00348                 }
00349 
00355                 void link(value_type source, value_type target)
00356                 {
00357                         iterator source_iter = std::find(begin(), end(), source);
00358                         iterator target_iter = std::find(begin(), end(), target);
00359 
00360                         if (source_iter == end() || target_iter == end())
00361                                 throw std::invalid_argument("value not found");
00362                         link(source_iter, target_iter);
00363                 }
00364 
00366                 bool linked(iterator source, iterator target) const
00367                 {
00368                         try
00369                         {
00370                                 Details::ScopedFlag<node_type> scoped_flag(target.node(), node_type::VISITED);
00371                                 Details::NodeVisitor<node_type>()(source.node());
00372                         }
00373                         catch (circular_reference_exception &)
00374                         {
00375                                 return true;
00376                         }
00377 
00378                         return false;
00379                 }
00380 
00382                 bool linked(iterator source, value_type target) const
00383                 {
00384                         iterator target_iter = std::find(begin(), end(), target);
00385 
00386                         if (target_iter == end())
00387                                 return false;
00388                         return linked(source, target_iter);
00389                 }
00390 
00392                 bool linked(value_type source, iterator target) const
00393                 {
00394                         iterator source_iter = std::find(begin(), end(), source);
00395 
00396                         if (source_iter == end())
00397                                 return false;
00398                         return linked(source_iter, target);
00399                 }
00400 
00402                 bool linked(value_type source, value_type target) const
00403                 {
00404                         iterator source_iter = std::find(begin(), end(), source);
00405                         iterator target_iter = std::find(begin(), end(), target);
00406 
00407                         if (source_iter == end() || target_iter == end())
00408                                 return false;
00409                         return linked(source_iter, target_iter);
00410                 }
00411 
00413                 bool unlink(iterator source, iterator target)
00414                 {
00415                         bool rv(true);
00416                         typename node_type::targets_type::iterator where(std::find(source.node()->targets_.begin(), source.node()->targets_.end(), target.node()));
00417                         if (where != source.node()->targets_.end())
00418                                 source.node()->targets_.erase(where);
00419                         else
00420                                 rv = false;
00421 
00422                         // GCC 3.3 doesn't like it when I don't use a local variable for this functor..
00423                         Details::DecScoreFunctor dag_node_dec_score_functor;
00424                         Details::NodeVisitor<node_type, Details::DecScoreFunctor, score_type>(dag_node_dec_score_functor, source.node()->score_)(target.node());
00425 
00426                         std::sort(nodes_.begin(), nodes_.end());
00427 
00428                         return rv;
00429                 }
00430 
00432                 bool unlink(iterator source, value_type target)
00433                 {
00434                         iterator target_iter = std::find(begin(), end(), target);
00435 
00436                         if (target_iter == end())
00437                                 throw std::invalid_argument("value not found");
00438                         return unlink(source, target_iter);
00439                 }
00440 
00442                 bool unlink(value_type source, iterator target)
00443                 {
00444                         iterator source_iter = std::find(begin(), end(), source);
00445 
00446                         if (source_iter == end())
00447                                 throw std::invalid_argument("value not found");
00448                         return unlink(source_iter, target);
00449                 }
00450 
00452                 bool unlink(value_type source, value_type target)
00453                 {
00454                         iterator source_iter = std::find(begin(), end(), source);
00455                         iterator target_iter = std::find(begin(), end(), target);
00456 
00457                         if (source_iter == end() || target_iter == end())
00458                                 throw std::invalid_argument("value not found");
00459                         return unlink(source_iter, target_iter);
00460                 }
00461 
00465                 iterator erase(iterator where)
00466                 {
00467                         while (!where.node()->targets_.empty())
00468                                 unlink(where, (where.node()->targets_[0])->value_);
00469                         std::for_each(nodes_.begin(), nodes_.end(), Details::Unlinker<node_type>(where.node()));
00470 
00471                         delete where.node();
00472                         typename nodes_type::iterator whence(nodes_.erase(where.iter_));
00473 
00474                         return iterator(whence);
00475                 }
00476         
00482                 iterator erase(iterator begin, iterator end)
00483                 {
00484                         iterator retval = begin;
00485                         
00486                         for (iterator where(begin); where != end; ++where)
00487                                 delete where.node();
00488                         return iterator(nodes_.erase(begin.iter_, end.iter_));
00489                 }
00490 
00494                 void clear()
00495                 {
00496                         erase(begin(), end());
00497                 }
00498                 
00499         private :
00500 #if DEPENDS_SUPPORT_SERIALIZATION
00501                 template < typename Archive >
00502                 void serialize( Archive & ar, const unsigned int version )
00503                 {
00504                         ar & boost::serialization::make_nvp("nodes_", nodes_);
00505                 }
00506 #endif
00507 
00508                 mutable nodes_type nodes_;
00509 
00510 #if DEPENDS_SUPPORT_SERIALIZATION
00511                 friend class boost::serialization::access;
00512 #endif
00513         };
00514 }
00515 
00516 #if DEPENDS_USE_DEPRECATED_NAMES
00517 namespace rlc
00518 {
00519         using namespace Depends;
00520         template < typename ValueType >
00521         struct dag : public Depends::DAG< ValueType >
00522         { /* empty veneer */ };
00523 }
00524 #endif
00525 
00526 #endif
00527 

Generated on Sat Aug 11 11:55:55 2007 for Depends by  doxygen 1.5.1