Depends.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_depends_h
#define _depends_depends_h

#include <algorithm>
#include <cassert>
#include <set>
#include "DAG.h"

namespace Depends
{
        template < typename ValueType >
        class Depends
        {
                // here only so we can use it below
                typedef std::set< ValueType > Storage;
        public :
                typedef typename Storage::iterator iterator;
                typedef typename Storage::const_iterator const_iterator;
                typedef typename Storage::reverse_iterator reverse_iterator;
                typedef typename Storage::const_reverse_iterator const_reverse_iterator;

                typedef typename std::iterator_traits< iterator >::value_type value_type;
                typedef typename std::iterator_traits< iterator >::reference reference;
                typedef typename std::iterator_traits< const_iterator >::reference const_reference;
                typedef typename std::iterator_traits< iterator >::pointer pointer;
                typedef typename std::iterator_traits< iterator >::difference_type difference_type;
                typedef typename Storage::size_type size_type;

                Depends()
                        : selected_(0)
                { /* no-op */ }
                template < typename InputIterator >
                Depends(InputIterator begin, InputIterator end)
                        : selected_(0)
                { insert(begin, end); }

                bool empty() const throw()
                { return storage_.empty(); }
                size_type size() const throw()
                { return storage_.size(); }

                iterator begin()
                { return iterator(storage_.begin()); }
                const_iterator begin() const
                { return const_iterator(storage_.begin()); }
                iterator end()
                { return iterator(storage_.end()); }
                const_iterator end() const
                { return const_iterator(storage_.end()); }
                reverse_iterator rbegin()
                { return reverse_iterator(storage_.rbegin()); }
                const_reverse_iterator rbegin() const
                { return const_reverse_iterator(storage_.rbegin()); }
                reverse_iterator rend()
                { return reverse_iterator(storage_.rend()); }
                const_reverse_iterator rend() const
                { return const_reverse_iterator(storage_.rend()); }

                template < typename V >
                const_iterator find(const V & v) const throw()
                { return storage_.find(v); }
                template < typename V >
                iterator find(const V & v) throw()
                { return storage_.find(v); }

                template < typename InputIterator >
                void insert(InputIterator begin, InputIterator end)
                {
                        for (InputIterator where(begin); where != end; ++where)
                                insert(*where);
                }
                std::pair< iterator, bool > insert( const value_type & v )
                {
                        std::pair< iterator, bool > retval(storage_.insert(v));
                        if (retval.second)
                        {
                                prerequisites_.insert(getPointer(retval.first));
                                dependants_.insert(getPointer(retval.first));
                        }
                        else
                        { /* nothing really inserted */ }

                        return retval;
                }
                iterator insert( const iterator & where, const value_type & what )
                { return insert(what).first; }

                template < typename V >
                size_type erase(const V & v)
                {
                        size_type erased(0);
                        iterator where;
                        while ((where = find(v)) != end())
                        {
                                erase(where);
                                ++erased;
                        }

                        return erased;
                }
                // erase the value at the indicated position
                void erase(iterator where)
                {
                        if (selected_)
                        {
                                if (where == *selected_)
                                        clearSelection();
                                else
                                { /* not erasing the selection */ }
                        }
                        else
                        { /* no selection - nothing to clear */ }
                        pointer p(getPointer(where));
                        bool found_in_blockers(false);
                        typename DAG< pointer >::iterator whence(std::find(dependants_.begin(), dependants_.end(), p));
                        if (whence != dependants_.end())
                        {
                                dependants_.erase(whence);
                                found_in_blockers = true;
                        }
                        else
                        { /* value not in the blockers DAG */ }
                        whence = std::find(prerequisites_.begin(), prerequisites_.end(), p);
                        if (whence != prerequisites_.end())
                        {
                                prerequisites_.erase(whence);
                                assert(found_in_blockers);
                        }
                        else
                        {       // if it's no in the prerequisites_ DAG, it shouldn't have been in the dependants_ DAG either
                                assert(!found_in_blockers);
                        }
                        storage_.erase(where);
                }
                // erase all the values in the given sequence
                void erase(const iterator & begin, const iterator & end)
                {
                        for (iterator where(begin); where != end; erase(where++))
                                ;
                }
                // clear the container
                void clear()
                {
                        clearSelection();
                        dependants_.clear();
                        prerequisites_.clear();
                        storage_.clear();
                }

                void select(const_iterator what)
                {
                        clearSelection();
                        if (what == end())
                                throw std::invalid_argument("Cannot select end");
                        else
                        { /* OK */ }
                        selected_ = new const_iterator(what);
                }
                void select(const value_type & v)
                {
                        select(insert(v).first);
                }

                void addPrerequisite(const_iterator whence)
                {
                        assert(selected_);
                        prerequisites_.link(getPointer(*selected_), getPointer(whence));
                        dependants_.link(getPointer(whence), getPointer(*selected_));
                }
                void addPrerequisite(const value_type & v)
                {
                        addPrerequisite(insert(v).first);
                }
                void removePrerequisite(const_iterator whence)
                {
                        assert(selected_);
                        if (whence == end())
                                return;
                        else
                        { /* dependency could exist */ }
                        bool was_prereq(prerequisites_.unlink(getPointer(*selected_), getPointer(whence)));
                        bool was_dep(dependants_.unlink(getPointer(whence), getPointer(*selected_)));
                        assert((was_dep && was_prereq) || (!was_dep && !was_prereq));
                }
                void removePrerequisite(const value_type & value)
                {
                        removePrerequisite(find(value));
                }
                std::set< value_type > getPrerequisites(bool all = false) const
                {
                        std::set< value_type > retval;
                        typename DAG< pointer >::const_iterator selected(std::find(prerequisites_.begin(), prerequisites_.end(), getPointer(*selected_)));
                        const typename DAG< pointer >::node_type * selected_node(selected.node());
                        if (all)
                        {
                                typedef Details::NodeVisitor< typename DAG< pointer >::node_type, Details::RetrieveTargets, std::set< pointer > * > Visitor;
                                std::set< pointer > temp;
                                Visitor visitor(Details::RetrieveTargets(), &temp);
                                std::for_each(
                                        selected_node->targets_.begin(),
                                        selected_node->targets_.end(),
                                        visitor);
                                std::copy(
                                        boost::indirect_iterator< typename std::set< pointer >::const_iterator >(temp.begin()),
                                        boost::indirect_iterator< typename std::set< pointer >::const_iterator >(temp.end()),
                                        std::inserter(retval, retval.begin()));
                        }
                        else
                        {
                                typename DAG< pointer >::node_type::targets_type::const_iterator end(selected_node->targets_.end());
                                typename DAG< pointer >::node_type::targets_type::const_iterator where(selected_node->targets_.begin());
                                while (where != end)
                                {
                                        retval.insert(*((*where)->value_));
                                        ++where;
                                }
                        }

                        return retval;
                }

                void addDependant(const_iterator whence)
                {
                        assert(selected_);
                        dependants_.link(getPointer(*selected_), getPointer(whence));
                        prerequisites_.link(getPointer(whence), getPointer(*selected_));
                }
                void addDependant(const value_type & v)
                {
                        addDependant(insert(v).first);
                }
                void removeDependant(const_iterator whence)
                {
                        assert(selected_);
                        if (whence == end())
                                return;
                        else
                        { /* dependency could exist */ }
                        dependants_.unlink(getPointer(*selected_), getPointer(whence));
                        prerequisites_.unlink(getPointer(whence), getPointer(*selected_));
                }
                void removeDependant(const value_type & value)
                {
                        removeDependant(find(value));
                }
                std::set< value_type > getDependants(bool all = false) const
                {
                        std::set< value_type > retval;
                        typename DAG< pointer >::const_iterator selected(std::find(dependants_.begin(), dependants_.end(), getPointer(*selected_)));
                        const typename DAG< pointer >::node_type * selected_node(selected.node());
                        if (all)
                        {
                                typedef Details::NodeVisitor< typename DAG< pointer >::node_type, Details::RetrieveTargets, std::set< pointer > * > Visitor;
                                std::set< pointer > temp;
                                Visitor visitor(Details::RetrieveTargets(), &temp);
                                std::for_each(
                                        selected_node->targets_.begin(),
                                        selected_node->targets_.end(),
                                        visitor);
                                std::copy(
                                        boost::indirect_iterator< typename std::set< pointer >::const_iterator >(temp.begin()),
                                        boost::indirect_iterator< typename std::set< pointer >::const_iterator >(temp.end()),
                                        std::inserter(retval, retval.begin()));
                        }
                        else
                        {
                                typename DAG< pointer >::node_type::targets_type::const_iterator end(selected_node->targets_.end());
                                typename DAG< pointer >::node_type::targets_type::const_iterator where(selected_node->targets_.begin());
                                while (where != end)
                                {
                                        retval.insert(*((*where)->value_));
                                        ++where;
                                }
                        }

                        return retval;
                }


                bool depends(const_iterator target, const_iterator source) const
                {
                        if (target == end() || source == end())
                                return false;
                        else
                        { /* such a dependency could exist */ }

                        // target depends on source if target is a dependant of source
                        // in which case source should also be a prerequisite of target
#ifndef NDEBUG
                        assert(
                                (dependants_.linked(getPointer(source), getPointer(target)) && prerequisites_.linked(getPointer(target), getPointer(source))) ||
                                ((!dependants_.linked(getPointer(source), getPointer(target))) && (!prerequisites_.linked(getPointer(target), getPointer(source)))));
#endif
                        return dependants_.linked(getPointer(source), getPointer(target));
                }
                bool depends(const_iterator target, const value_type & source) const
                {
                        return depends(target, find(source));
                }
                bool depends(const value_type & target, const_iterator source) const
                {
                        return depends(find(target), source);
                }
                bool depends(const value_type & target, const value_type & source) const
                {
                        return depends(find(target), find(source));
                }

        private :
                // Neither CopyConstructible nor Assignable
                Depends(const Depends &);
                Depends & operator=(const Depends &);

                void clearSelection()
                {
                        delete selected_;
                        selected_ = 0;
                }

                static pointer getPointer(const_iterator i)
                {
                        return const_cast< pointer >(&(*i));
                }

#if DEPENDS_SUPPORT_SERIALIZATION
                template < typename Archive >
                void serialize( Archive & ar, const unsigned int version )
                {
                        ar & boost::serialization::make_nvp("storage_", storage_)
                           & boost::serialization::make_nvp("dependants_", dependants_)
                           & boost::serialization::make_nvp("prerequisites_", prerequisites_)
                           ;
                }
#endif

                Storage storage_;
                DAG< pointer > dependants_;
                DAG< pointer > prerequisites_;
                const_iterator * selected_;

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

#endif

---