DAG.h

Go to the documentation of this file.

/* Depends: A generic dependency tracker in C++
 * Copyright (c) 2004-2007, Ronald Landheer-Cieslak
 * All rights reserved
 * 
 * This is free software. You may distribute it and/or modify it and
 * distribute modified forms provided that the following terms are met:
 *
 * * Redistributions of the source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer;
 * * Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in
 *   the documentation and/or other materials provided with the distribution;
 * * None of the names of the authors of this software may be used to endorse
 *   or promote this software, derived software or any distribution of this 
 *   software or any distribution of which this software is part, without 
 *   prior written permission from the authors involved;
 * * Unless you have received a written statement from Ronald Landheer-Cieslak
 *   that says otherwise, the terms of the GNU General Public License, as 
 *   published by the Free Software Foundation, version 2 or (at your option)
 *   any later version, also apply.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */
#ifndef _depends_dag_h
#define _depends_dag_h

#include <vector>
#include <algorithm>
#include <boost/iterator/indirect_iterator.hpp>

#if DEPENDS_SUPPORT_SERIALIZATION
namespace boost { namespace serialization { class access; } }
#include "Details/serialization.hpp"
#endif

#include "Details/Iterator.h"
#include "Details/Node.h"
#include "Details/CircularReferenceException.h"
#include "Details/ScopedFlag.h"
#include "Details/Visitors.h"
#include "Details/SortPred.h"
#include "Details/Unlinker.h"

namespace Depends
{
        template <class ValueType>
        class DAG
        {
        public :
                // standard types for a container
                typedef ValueType value_type;
                typedef ValueType key_type;
                typedef ValueType & reference;
                typedef const ValueType & const_reference;
                typedef ValueType * pointer;
                typedef const ValueType * const_pointer;
                typedef unsigned long score_type;
                typedef Details::Node<ValueType, score_type> node_type;
                typedef std::vector< node_type* > nodes_type;
                typedef Details::Iterator<
                        ValueType, 
                        const ValueType &, 
                        const ValueType *, 
                        score_type, 
                        typename nodes_type::iterator> iterator;
                typedef Details::Iterator<
                        ValueType, 
                        const ValueType &,
                        const ValueType *,
                        score_type,
                        typename nodes_type::iterator> const_iterator;
                typedef Details::ReverseIterator<
                        ValueType,
                        const ValueType &,
                        const ValueType *,
                        score_type,
                        typename nodes_type::reverse_iterator> reverse_iterator;
                typedef Details::ReverseIterator<
                        ValueType,
                        const ValueType &,
                        const ValueType *,
                        score_type,
                        typename nodes_type::reverse_iterator>
                                const_reverse_iterator;
                typedef typename std::vector<node_type>::difference_type
                        difference_type;
                typedef typename std::vector<node_type>::size_type size_type;

                typedef Details::CircularReferenceException
                        circular_reference_exception;

                DAG()
                { /* no-op */ }
                DAG(const DAG & d)
                        : nodes_(d.nodes)
                { /* no-op */ }
        

                template <typename InputIterator>
                DAG(InputIterator first, InputIterator last)
                {
                        insert(first, last);
                }
        
                DAG & operator=(const DAG & d)
                {
                        nodes_ = d.nodes_;
                        return *this;
                }

                ~DAG()
                {
                        for (typename nodes_type::iterator iter = nodes_.begin(); iter != nodes_.end(); ++iter)
                                delete *iter;
                }
        
                iterator begin() { return iterator(nodes_.begin()); }
                const_iterator begin() const { return const_iterator(nodes_.begin()); }
                reverse_iterator rbegin() { return reverse_iterator(nodes_.rbegin()); }
                const_reverse_iterator rbegin() const { return const_reverse_iterator(nodes_.rbegin()); }

                iterator end() { return iterator(nodes_.end()); }
                const_iterator end() const { return const_iterator(nodes_.end()); }
                reverse_iterator rend() { return reverse_iterator(nodes_.rend()); }
                const_reverse_iterator rend() const { return const_reverse_iterator(nodes_.rend()); }

                size_type size() const { return nodes_.size(); }
                size_type max_size() const { return sizeof(score_type) > sizeof(size_type) ? (size_type)~0 : (score_type)~0; }

                bool empty() const { return nodes_.empty(); }
                void swap(DAG & d) { nodes_.swap(d.nodes_); }

                bool operator==(const DAG & d) const
                {
                        return (nodes_.size() == d.nodes_.size()) && 
                                std::equal(
                                        boost::indirect_iterator< typename nodes_type::const_iterator >(nodes_.begin()),
                                        boost::indirect_iterator< typename nodes_type::const_iterator >(nodes_.end()),
                                        boost::indirect_iterator< typename nodes_type::const_iterator >(d.nodes_.begin()));
                        
                }
                bool operator!=(const DAG & d) const
                {
                        return !(*this == d);
                }

                bool operator<(const DAG & d) const
                {
                        return std::lexicographical_compare(
                                boost::indirect_iterator< typename nodes_type::const_iterator >(nodes_.begin()),
                                boost::indirect_iterator< typename nodes_type::const_iterator >(nodes_.end()),
                                boost::indirect_iterator< typename nodes_type::const_iterator >(d.nodes_.begin()),
                                boost::indirect_iterator< typename nodes_type::const_iterator >(d.nodes_.end()),
                                Details::CompareNodesByContents< node_type >()
                                );
                }
                bool operator>(const DAG & d) const { return d < *this; }
                
                bool operator<=(const DAG & d) const { return !(d < *this); }
                bool operator>=(const DAG & d) const { return !(*this < d); }

                std::pair<iterator, bool> insert(const value_type & val)
                {
                        if (std::find_if(nodes_.begin(), nodes_.end(), Details::ValueCompare<node_type>(val)) == nodes_.end())
                        {
                                nodes_.insert(nodes_.begin(), new node_type(val));
                                return std::make_pair(begin(), true);
                        }
                        else
                                return std::make_pair(end(), false);
                }

                template <typename InputIterator>
                void insert(InputIterator first, InputIterator last)
                {
                        for ( ; first != last; ++first)
                                insert(*first);
                }
        
                void link(iterator source, iterator target)
                {
                        {
                                Details::ScopedFlag<node_type> scoped_flag(source.node(), node_type::VISITED);
                                Details::NodeVisitor<node_type>()(target.node());
                        }
                        source.node()->targets_.push_back(target.node());

                        // GCC 3.3 doesn't like it when I don't use a local variable for this functor..
                        Details::IncScoreFunctor dag_node_inc_score_functor;
                        Details::NodeVisitor<node_type, Details::IncScoreFunctor, score_type>(dag_node_inc_score_functor, source.node()->score_)(target.node());

                        std::sort(nodes_.begin(), nodes_.end(), Details::SortPred<node_type>());
                }

                void link(iterator source, value_type target)
                {
                        iterator target_iter = std::find(begin(), end(), target);

                        if (target_iter == end())
                                throw std::invalid_argument("value not found");
                        link(source, target_iter);
                }

                void link(value_type source, iterator target)
                {
                        iterator source_iter = std::find(begin(), end(), source);

                        if (source_iter == end())
                                throw std::invalid_argument("value not found");
                        link(source_iter, target);
                }

                void link(value_type source, value_type target)
                {
                        iterator source_iter = std::find(begin(), end(), source);
                        iterator target_iter = std::find(begin(), end(), target);

                        if (source_iter == end() || target_iter == end())
                                throw std::invalid_argument("value not found");
                        link(source_iter, target_iter);
                }

                bool linked(iterator source, iterator target) const
                {
                        try
                        {
                                Details::ScopedFlag<node_type> scoped_flag(target.node(), node_type::VISITED);
                                Details::NodeVisitor<node_type>()(source.node());
                        }
                        catch (circular_reference_exception &)
                        {
                                return true;
                        }

                        return false;
                }

                bool linked(iterator source, value_type target) const
                {
                        iterator target_iter = std::find(begin(), end(), target);

                        if (target_iter == end())
                                return false;
                        return linked(source, target_iter);
                }

                bool linked(value_type source, iterator target) const
                {
                        iterator source_iter = std::find(begin(), end(), source);

                        if (source_iter == end())
                                return false;
                        return linked(source_iter, target);
                }

                bool linked(value_type source, value_type target) const
                {
                        iterator source_iter = std::find(begin(), end(), source);
                        iterator target_iter = std::find(begin(), end(), target);

                        if (source_iter == end() || target_iter == end())
                                return false;
                        return linked(source_iter, target_iter);
                }

                bool unlink(iterator source, iterator target)
                {
                        bool rv(true);
                        typename node_type::targets_type::iterator where(std::find(source.node()->targets_.begin(), source.node()->targets_.end(), target.node()));
                        if (where != source.node()->targets_.end())
                                source.node()->targets_.erase(where);
                        else
                                rv = false;

                        // GCC 3.3 doesn't like it when I don't use a local variable for this functor..
                        Details::DecScoreFunctor dag_node_dec_score_functor;
                        Details::NodeVisitor<node_type, Details::DecScoreFunctor, score_type>(dag_node_dec_score_functor, source.node()->score_)(target.node());

                        std::sort(nodes_.begin(), nodes_.end());

                        return rv;
                }

                bool unlink(iterator source, value_type target)
                {
                        iterator target_iter = std::find(begin(), end(), target);

                        if (target_iter == end())
                                throw std::invalid_argument("value not found");
                        return unlink(source, target_iter);
                }

                bool unlink(value_type source, iterator target)
                {
                        iterator source_iter = std::find(begin(), end(), source);

                        if (source_iter == end())
                                throw std::invalid_argument("value not found");
                        return unlink(source_iter, target);
                }

                bool unlink(value_type source, value_type target)
                {
                        iterator source_iter = std::find(begin(), end(), source);
                        iterator target_iter = std::find(begin(), end(), target);

                        if (source_iter == end() || target_iter == end())
                                throw std::invalid_argument("value not found");
                        return unlink(source_iter, target_iter);
                }

                iterator erase(iterator where)
                {
                        while (!where.node()->targets_.empty())
                                unlink(where, (where.node()->targets_[0])->value_);
                        std::for_each(nodes_.begin(), nodes_.end(), Details::Unlinker<node_type>(where.node()));

                        delete where.node();
                        typename nodes_type::iterator whence(nodes_.erase(where.iter_));

                        return iterator(whence);
                }
        
                iterator erase(iterator begin, iterator end)
                {
                        iterator retval = begin;
                        
                        for (iterator where(begin); where != end; ++where)
                                delete where.node();
                        return iterator(nodes_.erase(begin.iter_, end.iter_));
                }

                void clear()
                {
                        erase(begin(), end());
                }
                
        private :
#if DEPENDS_SUPPORT_SERIALIZATION
                template < typename Archive >
                void serialize( Archive & ar, const unsigned int version )
                {
                        ar & boost::serialization::make_nvp("nodes_", nodes_);
                }
#endif

                mutable nodes_type nodes_;

#if DEPENDS_SUPPORT_SERIALIZATION
                friend class boost::serialization::access;
#endif
        };
}

#if DEPENDS_USE_DEPRECATED_NAMES
namespace rlc
{
        using namespace Depends;
        template < typename ValueType >
        struct dag : public Depends::DAG< ValueType >
        { /* empty veneer */ };
}
#endif

#endif

---