path: root/indra/llcommon/lldependencies.h

/**
 * @file   lldependencies.h
 * @author Nat Goodspeed
 * @date   2008-09-17
 * @brief  LLDependencies: a generic mechanism for expressing "b must follow a,
 *         but precede c"
 *
 * $LicenseInfo:firstyear=2008&license=viewerlgpl$
 * Second Life Viewer Source Code
 * Copyright (C) 2010, Linden Research, Inc.
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation;
 * version 2.1 of the License only.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 * 
 * Linden Research, Inc., 945 Battery Street, San Francisco, CA  94111  USA
 * $/LicenseInfo$
 */

#if ! defined(LL_LLDEPENDENCIES_H)
#define LL_LLDEPENDENCIES_H

#include <string>
#include <vector>
#include <set>
#include <map>
#include <iosfwd>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/iterator/indirect_iterator.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/function.hpp>
#include <boost/bind.hpp>
#include "llexception.h"

/*****************************************************************************
*   Utilities
*****************************************************************************/
/**
 * generic range transformer: given a range acceptable to Boost.Range (e.g. a
 * standard container, an iterator pair, ...) and a unary function to apply to
 * each element of the range, make a corresponding range that lazily applies
 * that function to each element on dereferencing.
 */
template<typename FUNCTION, typename RANGE>
inline
boost::iterator_range<boost::transform_iterator<FUNCTION,
                                                typename boost::range_const_iterator<RANGE>::type> >
make_transform_range(const RANGE& range, FUNCTION function)
{
    // shorthand for the iterator type embedded in our return type
    typedef boost::transform_iterator<FUNCTION, typename boost::range_const_iterator<RANGE>::type>
        transform_iterator;
    return boost::make_iterator_range(transform_iterator(boost::begin(range), function),
                                      transform_iterator(boost::end(range),   function));
}

/// non-const version of make_transform_range()
template<typename FUNCTION, typename RANGE>
inline
boost::iterator_range<boost::transform_iterator<FUNCTION,
                                                typename boost::range_iterator<RANGE>::type> >
make_transform_range(RANGE& range, FUNCTION function)
{
    // shorthand for the iterator type embedded in our return type
    typedef boost::transform_iterator<FUNCTION, typename boost::range_iterator<RANGE>::type>
        transform_iterator;
    return boost::make_iterator_range(transform_iterator(boost::begin(range), function),
                                      transform_iterator(boost::end(range),   function));
}

/**
 * From any range compatible with Boost.Range, instantiate any class capable
 * of accepting an iterator pair.
 */
template<class TYPE>
struct instance_from_range: public TYPE
{
    template<typename RANGE>
    instance_from_range(RANGE range):
        TYPE(boost::begin(range), boost::end(range))
    {}
};

/*****************************************************************************
*   LLDependencies
*****************************************************************************/
/**
 * LLDependencies components that should not be reinstantiated for each KEY,
 * NODE specialization
 */
class LL_COMMON_API LLDependenciesBase
{
public:
    virtual ~LLDependenciesBase() {}

    /**
     * Exception thrown by sort() if there's a cycle
     */
    struct Cycle: public LLException
    {
        Cycle(const std::string& what): LLException(what) {}
    };

    /**
     * Provide a short description of this LLDependencies instance on the
     * specified output stream, assuming that its KEY type has an operator<<()
     * that works with std::ostream.
     *
     * Pass @a full as @c false to omit any keys without dependency constraints.
     */
    virtual std::ostream& describe(std::ostream& out, bool full=true) const;

    /// describe() to a string
    virtual std::string describe(bool full=true) const;

protected:
    typedef std::vector< std::pair<std::size_t, std::size_t> > EdgeList;
    typedef std::vector<std::size_t> VertexList;
    VertexList topo_sort(int vertices, const EdgeList& edges) const;

    /**
     * refpair is specifically intended to capture a pair of references. This
     * is better than std::pair<T1&, T2&> because some implementations of
     * std::pair's ctor accept const references to the two types. If the
     * types are themselves references, this results in an illegal reference-
     * to-reference.
     */
    template<typename T1, typename T2>
    struct refpair
    {
        refpair(T1 value1, T2 value2):
            first(value1),
            second(value2)
        {}
        T1 first;
        T2 second;
    };
};

/// describe() helper: for most types, report the type as usual
template<typename T>
inline
std::ostream& LLDependencies_describe(std::ostream& out, const T& key)
{
    out << key;
    return out;
}

/// specialize LLDependencies_describe() for std::string
template<>
inline
std::ostream& LLDependencies_describe(std::ostream& out, const std::string& key)
{
    out << '"' << key << '"';
    return out;
}

/**
 * It's reasonable to use LLDependencies in a keys-only way, more or less like
 * std::set. For that case, the default NODE type is an empty struct.
 */
struct LLDependenciesEmpty
{
    LLDependenciesEmpty() {}
    /**
     * Give it a constructor accepting void* so caller can pass placeholder
     * values such as NULL or 0 rather than having to write
     * LLDependenciesEmpty().
     */
    LLDependenciesEmpty(void*) {}    
};

/**
 * This class manages abstract dependencies between node types of your
 * choosing. As with a std::map, nodes are copied when add()ed, so the node
 * type should be relatively lightweight; to manipulate dependencies between
 * expensive objects, use a pointer type.
 *
 * For a given node, you may state the keys of nodes that must precede it
 * and/or nodes that must follow it. The sort() method will produce an order
 * that should work, or throw an exception if the constraints are impossible.
 * We cache results to minimize the cost of repeated sort() calls.
 */
template<typename KEY = std::string,
         typename NODE = LLDependenciesEmpty>
class LLDependencies: public LLDependenciesBase
{
    typedef LLDependencies<KEY, NODE> self_type;

    /**
     * Internally, we bundle the client's NODE with its before/after keys.
     */
    struct DepNode
    {
        typedef std::set<KEY> dep_set;
        DepNode(const NODE& node_, const dep_set& after_, const dep_set& before_):
            node(node_),
            after(after_),
            before(before_)
        {}
        NODE node;
        dep_set after, before;    
    };
    typedef std::map<KEY, DepNode> DepNodeMap;
    typedef typename DepNodeMap::value_type DepNodeMapEntry;

    /// We have various ways to get the dependencies for a given DepNode.
    /// Rather than having to restate each one for 'after' and 'before'
    /// separately, pass a dep_selector so we can apply each to either.
    typedef boost::function<const typename DepNode::dep_set&(const DepNode&)> dep_selector;

public:
    LLDependencies() {}

    typedef KEY key_type;
    typedef NODE node_type;

    /// param type used to express lists of other node keys -- note that such
    /// lists can be initialized with boost::assign::list_of()
    typedef std::vector<KEY> KeyList;

    /**
     * Add a new node. State its dependencies on other nodes (which may not
     * yet have been added) by listing the keys of nodes this new one must
     * follow, and separately the keys of nodes this new one must precede.
     *
     * The node you pass is @em copied into an internal data structure. If you
     * want to modify the node value after add()ing it, capture the returned
     * NODE& reference.
     *
     * @note
     * Actual dependency analysis is deferred to the sort() method, so 
     * you can add an arbitrary number of nodes without incurring analysis
     * overhead for each. The flip side of this is that add()ing nodes that
     * define a cycle leaves this object in a state in which sort() will
     * always throw the Cycle exception.
     *
     * Two distinct use cases are anticipated:
     * * The data used to load this object are completely known at compile
     * time (e.g. LLEventPump listener names). A Cycle exception represents a
     * bug which can be corrected by the coder. The program need neither catch
     * Cycle nor attempt to salvage the state of this object.
     * * The data are loaded at runtime, therefore the universe of
     * dependencies cannot be known at compile time. The client code should
     * catch Cycle.
     * ** If a Cycle exception indicates fatally-flawed input data, this
     * object can simply be discarded, possibly with the entire program run.
     * ** If it is essential to restore this object to a working state, the
     * simplest workaround is to remove() nodes in LIFO order.
     * *** It may be useful to add functionality to this class to track the
     * add() chronology, providing a pop() method to remove the most recently
     * added node.
     * *** It may further be useful to add a restore() method which would
     * pop() until sort() no longer throws Cycle. This method would be
     * expensive -- but it's not clear that client code could resolve the
     * problem more cheaply.
     */
    NODE& add(const KEY& key, const NODE& node = NODE(),
              const KeyList& after = KeyList(),
              const KeyList& before = KeyList())
    {
        // Get the passed-in lists as sets for equality comparison
        typename DepNode::dep_set
            after_set(after.begin(), after.end()),
            before_set(before.begin(), before.end());
        // Try to insert the new node; if it already exists, find the old
        // node instead.
        std::pair<typename DepNodeMap::iterator, bool> inserted =
            mNodes.insert(typename DepNodeMap::value_type(key,
                                                          DepNode(node, after_set, before_set)));
        if (! inserted.second)      // bool indicating success of insert()
        {
            // We already have a node by this name. Have its dependencies
            // changed? If the existing node's dependencies are identical, the
            // result will be unchanged, so we can leave the cache intact.
            // Regardless of inserted.second, inserted.first is the iterator
            // to the newly-inserted (or existing) map entry. Of course, that
            // entry's second is the DepNode of interest.
            if (inserted.first->second.after  != after_set ||
                inserted.first->second.before != before_set)
            {
                // Dependencies have changed: clear the cached result.
                mCache.clear();
                // save the new dependencies
                inserted.first->second.after  = after_set;
                inserted.first->second.before = before_set;
            }
        }
        else                        // this node is new
        {
            // This will change results.
            mCache.clear();
        }
        return inserted.first->second.node;
    }

    /// the value of an iterator, showing both KEY and its NODE
    typedef refpair<const KEY&, NODE&> value_type;
    /// the value of a const_iterator
    typedef refpair<const KEY&, const NODE&> const_value_type;

private:
    // Extract functors
    static value_type value_extract(DepNodeMapEntry& entry)
    {
        return value_type(entry.first, entry.second.node);
    }

    static const_value_type const_value_extract(const DepNodeMapEntry& entry)
    {
        return const_value_type(entry.first, entry.second.node);
    }

    // All the iterator access methods return iterator ranges just to cut down
    // on the friggin' boilerplate!!

    /// generic mNodes range method
    template<typename ITERATOR, typename FUNCTION>
    boost::iterator_range<ITERATOR> generic_range(FUNCTION function)
    {
        return make_transform_range(mNodes, function);
    }

    /// generic mNodes const range method
    template<typename ITERATOR, typename FUNCTION>
    boost::iterator_range<ITERATOR> generic_range(FUNCTION function) const
    {
        return make_transform_range(mNodes, function);
    }

public:
    /// iterator over value_type entries
    typedef boost::transform_iterator<boost::function<value_type(DepNodeMapEntry&)>,
                                      typename DepNodeMap::iterator> iterator;
    /// range over value_type entries
    typedef boost::iterator_range<iterator> range;

    /// iterate over value_type <i>in @c KEY order</i> rather than dependency order
    range get_range()
    {
        return generic_range<iterator>(value_extract);
    }

    /// iterator over const_value_type entries
    typedef boost::transform_iterator<boost::function<const_value_type(const DepNodeMapEntry&)>,
                                      typename DepNodeMap::const_iterator> const_iterator;
    /// range over const_value_type entries
    typedef boost::iterator_range<const_iterator> const_range;

    /// iterate over const_value_type <i>in @c KEY order</i> rather than dependency order
    const_range get_range() const
    {
        return generic_range<const_iterator>(const_value_extract);
    }

    /// iterator over stored NODEs
    typedef boost::transform_iterator<boost::function<NODE&(DepNodeMapEntry&)>,
                                      typename DepNodeMap::iterator> node_iterator;
    /// range over stored NODEs
    typedef boost::iterator_range<node_iterator> node_range;

    /// iterate over NODE <i>in @c KEY order</i> rather than dependency order
    node_range get_node_range()
    {
        // First take a DepNodeMapEntry and extract a reference to its
        // DepNode, then from that extract a reference to its NODE.
        return generic_range<node_iterator>(
            boost::bind<NODE&>(&DepNode::node,
                               boost::bind<DepNode&>(&DepNodeMapEntry::second, _1)));
    }

    /// const iterator over stored NODEs
    typedef boost::transform_iterator<boost::function<const NODE&(const DepNodeMapEntry&)>,
                                      typename DepNodeMap::const_iterator> const_node_iterator;
    /// const range over stored NODEs
    typedef boost::iterator_range<const_node_iterator> const_node_range;

    /// iterate over const NODE <i>in @c KEY order</i> rather than dependency order
    const_node_range get_node_range() const
    {
        // First take a DepNodeMapEntry and extract a reference to its
        // DepNode, then from that extract a reference to its NODE.
        return generic_range<const_node_iterator>(
            boost::bind<const NODE&>(&DepNode::node,
                                     boost::bind<const DepNode&>(&DepNodeMapEntry::second, _1)));
    }

    /// const iterator over stored KEYs
    typedef boost::transform_iterator<boost::function<const KEY&(const DepNodeMapEntry&)>,
                                      typename DepNodeMap::const_iterator> const_key_iterator;
    /// const range over stored KEYs
    typedef boost::iterator_range<const_key_iterator> const_key_range;
    // We don't provide a non-const iterator over KEYs because they should be
    // immutable, and in fact our underlying std::map won't give us non-const
    // references.

    /// iterate over const KEY <i>in @c KEY order</i> rather than dependency order
    const_key_range get_key_range() const
    {
        // From a DepNodeMapEntry, extract a reference to its KEY.
        return generic_range<const_key_iterator>(
            boost::bind<const KEY&>(&DepNodeMapEntry::first, _1));
    }

    /**
     * Find an existing NODE, or return NULL. We decided to avoid providing a
     * method analogous to std::map::find(), for a couple of reasons:
     *
     * * For a find-by-key, getting back an iterator to the (key, value) pair
     * is less than useful, since you already have the key in hand.
     * * For a failed request, comparing to end() is problematic. First, we
     * provide range accessors, so it's more code to get end(). Second, we
     * provide a number of different ranges -- quick, to which one's end()
     * should we compare the iterator returned by find()?
     *
     * The returned pointer is solely to allow expressing the not-found
     * condition. LLDependencies still owns the found NODE.
     */
    const NODE* get(const KEY& key) const
    {
        typename DepNodeMap::const_iterator found = mNodes.find(key);
        if (found != mNodes.end())
        {
            return &found->second.node;
        }
        return NULL;
    }

    /**
     * non-const get()
     */
    NODE* get(const KEY& key)
    {
        // Use const implementation, then cast away const-ness of return
        return const_cast<NODE*>(const_cast<const self_type*>(this)->get(key));
    }

    /**
     * Remove a node with specified key. This operation is the major reason
     * we rebuild the graph on the fly instead of storing it.
     */
    bool remove(const KEY& key)
    {
        typename DepNodeMap::iterator found = mNodes.find(key);
        if (found != mNodes.end())
        {
            mNodes.erase(found);
            return true;
        }
        return false;
    }

private:
    /// cached list of iterators
    typedef std::vector<iterator> iterator_list;
    typedef typename iterator_list::iterator iterator_list_iterator;

public:
    /**
     * The return type of the sort() method needs some explanation. Provide a
     * public typedef to facilitate storing the result.
     *
     * * We will prepare mCache by looking up DepNodeMap iterators.
     * * We want to return a range containing iterators that will walk mCache.
     * * If we simply stored DepNodeMap iterators and returned
     * (mCache.begin(), mCache.end()), dereferencing each iterator would
     * obtain a DepNodeMap iterator.
     * * We want the caller to loop over @c value_type: pair<KEY, NODE>.
     * * This requires two transformations:
     * ** mCache must contain @c LLDependencies::iterator so that
     * dereferencing each entry will obtain an @c LLDependencies::value_type
     * rather than a DepNodeMapEntry.
     * ** We must wrap mCache's iterators in boost::indirect_iterator so that
     * dereferencing one of our returned iterators will also dereference the
     * iterator contained in mCache.
     */
    typedef boost::iterator_range<boost::indirect_iterator<iterator_list_iterator> > sorted_range;
    /// for convenience in looping over a sorted_range
    typedef typename sorted_range::iterator sorted_iterator;

    /**
     * Once we've loaded in the dependencies of interest, arrange them into an
     * order that works -- or throw Cycle exception.
     *
     * Return an iterator range over (key, node) pairs that traverses them in
     * the desired order.
     */
    sorted_range sort() const
    {
        // Changes to mNodes cause us to clear our cache, so empty mCache
        // means it's invalid and should be recomputed. However, if mNodes is
        // also empty, then an empty mCache represents a valid order, so don't
        // bother sorting.
        if (mCache.empty() && ! mNodes.empty())
        {
            // Construct a map of node keys to distinct vertex numbers -- even for
            // nodes mentioned only in before/after constraints, that haven't yet
            // been explicitly added. Rely on std::map rejecting a second attempt
            // to insert the same key. Use the map's size() as the vertex number
            // to get a distinct value for each successful insertion.
            typedef std::map<KEY, std::size_t> VertexMap;
            VertexMap vmap;
            // Nest each of these loops because !@#$%? MSVC warns us that its
            // former broken behavior has finally been fixed -- and our builds
            // treat warnings as errors.
            {
                for (typename DepNodeMap::const_iterator nmi = mNodes.begin(), nmend = mNodes.end();
                     nmi != nmend; ++nmi)
                {
                    vmap.insert(typename VertexMap::value_type(nmi->first, vmap.size()));
                    for (typename DepNode::dep_set::const_iterator ai = nmi->second.after.begin(),
                                                                   aend = nmi->second.after.end();
                         ai != aend; ++ai)
                    {
                        vmap.insert(typename VertexMap::value_type(*ai, vmap.size()));
                    }
                    for (typename DepNode::dep_set::const_iterator bi = nmi->second.before.begin(),
                                                                   bend = nmi->second.before.end();
                         bi != bend; ++bi)
                    {
                        vmap.insert(typename VertexMap::value_type(*bi, vmap.size()));
                    }
                }
            }
            // Define the edges. For this we must traverse mNodes again, mapping
            // all the known key dependencies to integer pairs.
            EdgeList edges;
            {
                for (typename DepNodeMap::const_iterator nmi = mNodes.begin(), nmend = mNodes.end();
                     nmi != nmend; ++nmi)
                {
                    int thisnode = vmap[nmi->first];
                    // after dependencies: build edges from the named node to this one
                    for (typename DepNode::dep_set::const_iterator ai = nmi->second.after.begin(),
                                                                   aend = nmi->second.after.end();
                         ai != aend; ++ai)
                    {
                        edges.push_back(EdgeList::value_type(vmap[*ai], thisnode));
                    }
                    // before dependencies: build edges from this node to the
                    // named one
                    for (typename DepNode::dep_set::const_iterator bi = nmi->second.before.begin(),
                                                                   bend = nmi->second.before.end();
                         bi != bend; ++bi)
                    {
                        edges.push_back(EdgeList::value_type(thisnode, vmap[*bi]));
                    }
                }
            }
            // Hide the gory details of our topological sort, since they shouldn't
            // get reinstantiated for each distinct NODE type.
            VertexList sorted(topo_sort(vmap.size(), edges));
            // Build the reverse of vmap to look up the key for each vertex
            // descriptor. vmap contains exactly one entry for each distinct key,
            // and we're certain that the associated int values are distinct
            // indexes. The fact that they're not in order is irrelevant.
            KeyList vkeys(vmap.size());
            for (typename VertexMap::const_iterator vmi = vmap.begin(), vmend = vmap.end();
                 vmi != vmend; ++vmi)
            {
                vkeys[vmi->second] = vmi->first;
            }
            // Walk the sorted output list, building the result into mCache so
            // we'll have it next time someone asks.
            mCache.clear();
            for (VertexList::const_iterator svi = sorted.begin(), svend = sorted.end();
                 svi != svend; ++svi)
            {
                // We're certain that vkeys[*svi] exists. However, there might not
                // yet be a corresponding entry in mNodes.
                self_type* non_const_this(const_cast<self_type*>(this));
                typename DepNodeMap::iterator found = non_const_this->mNodes.find(vkeys[*svi]);
                if (found != non_const_this->mNodes.end())
                {
                    // Make an iterator of appropriate type.
                    mCache.push_back(iterator(found, value_extract));
                }
            }
        }
        // Whether or not we've just recomputed mCache, it should now contain
        // the results we want. Return a range of indirect_iterators over it
        // so that dereferencing a returned iterator will dereference the
        // iterator stored in mCache and directly reference the (key, node)
        // pair.
        boost::indirect_iterator<iterator_list_iterator>
            begin(mCache.begin()),
            end(mCache.end());
        return sorted_range(begin, end);
    }

	using LLDependenciesBase::describe; // unhide virtual std::string describe(bool full=true) const;

    /// Override base-class describe() with actual implementation
    virtual std::ostream& describe(std::ostream& out, bool full=true) const
    {
        typename DepNodeMap::const_iterator dmi(mNodes.begin()), dmend(mNodes.end());
        if (dmi != dmend)
        {
            std::string sep;
            describe(out, sep, *dmi, full);
            while (++dmi != dmend)
            {
                describe(out, sep, *dmi, full);
            }
        }
        return out;
    }


    /// describe() helper: report a DepNodeEntry
    static std::ostream& describe(std::ostream& out, std::string& sep,
                                  const DepNodeMapEntry& entry, bool full)
    {
        // If we were asked for a full report, describe every node regardless
        // of whether it has dependencies. If we were asked to suppress
        // independent nodes, describe this one if either after or before is
        // non-empty.
        if (full || (! entry.second.after.empty()) || (! entry.second.before.empty()))
        {
            out << sep;
            sep = "\n";
            if (! entry.second.after.empty())
            {
                out << "after ";
                describe(out, entry.second.after);
                out << " -> ";
            }
            LLDependencies_describe(out, entry.first);
            if (! entry.second.before.empty())
            {
                out << " -> before ";
                describe(out, entry.second.before);
            }
        }
        return out;
    }

    /// describe() helper: report a dep_set
    static std::ostream& describe(std::ostream& out, const typename DepNode::dep_set& keys)
    {
        out << '(';
        typename DepNode::dep_set::const_iterator ki(keys.begin()), kend(keys.end());
        if (ki != kend)
        {
            LLDependencies_describe(out, *ki);
            while (++ki != kend)
            {
                out << ", ";
                LLDependencies_describe(out, *ki);
            }
        }
        out << ')';
        return out;
    }

    /// Iterator over the before/after KEYs on which a given NODE depends
    typedef typename DepNode::dep_set::const_iterator dep_iterator;
    /// range over the before/after KEYs on which a given NODE depends
    typedef boost::iterator_range<dep_iterator> dep_range;

    /// dependencies access from key
    dep_range get_dep_range_from_key(const KEY& key, const dep_selector& selector) const
    {
        typename DepNodeMap::const_iterator found = mNodes.find(key);
        if (found != mNodes.end())
        {
            return dep_range(selector(found->second));
        }
        // We want to return an empty range. On some platforms a default-
        // constructed range (e.g. dep_range()) does NOT suffice! The client
        // is likely to try to iterate from boost::begin(range) to
        // boost::end(range); yet these iterators might not be valid. Instead
        // return a range over a valid, empty container.
        static const typename DepNode::dep_set empty_deps;
        return dep_range(empty_deps.begin(), empty_deps.end());
    }

    /// dependencies access from any one of our key-order iterators
    template<typename ITERATOR>
    dep_range get_dep_range_from_xform(const ITERATOR& iterator, const dep_selector& selector) const
    {
        return dep_range(selector(iterator.base()->second));
    }

    /// dependencies access from sorted_iterator
    dep_range get_dep_range_from_sorted(const sorted_iterator& sortiter,
                                        const dep_selector& selector) const
    {
        // sorted_iterator is a boost::indirect_iterator wrapping an mCache
        // iterator, which we can obtain by sortiter.base(). Deferencing that
        // gets us an mCache entry, an 'iterator' -- one of our traversal
        // iterators -- on which we can use get_dep_range_from_xform().
        return get_dep_range_from_xform(*sortiter.base(), selector);
    }

    /**
     * Get a range over the after KEYs stored for the passed KEY or iterator,
     * in <i>arbitrary order.</i> If you pass a nonexistent KEY, returns empty
     * range -- same as a KEY with no after KEYs. Detect existence of a KEY
     * using get() instead.
     */
    template<typename KEY_OR_ITER>
    dep_range get_after_range(const KEY_OR_ITER& key) const;

    /**
     * Get a range over the before KEYs stored for the passed KEY or iterator,
     * in <i>arbitrary order.</i> If you pass a nonexistent KEY, returns empty
     * range -- same as a KEY with no before KEYs. Detect existence of a KEY
     * using get() instead.
     */
    template<typename KEY_OR_ITER>
    dep_range get_before_range(const KEY_OR_ITER& key) const;

private:
    DepNodeMap mNodes;
    mutable iterator_list mCache;
};

/**
 * Functor to get a dep_range from a KEY or iterator -- generic case. If the
 * passed value isn't one of our iterator specializations, assume it's
 * convertible to the KEY type.
 */
template<typename KEY_ITER>
struct LLDependencies_dep_range_from
{
    template<typename KEY, typename NODE, typename SELECTOR>
    typename LLDependencies<KEY, NODE>::dep_range
    operator()(const LLDependencies<KEY, NODE>& deps,
               const KEY_ITER& key,
               const SELECTOR& selector)
    {
        return deps.get_dep_range_from_key(key, selector);
    }
};

/// Specialize LLDependencies_dep_range_from for our key-order iterators
template<typename FUNCTION, typename ITERATOR>
struct LLDependencies_dep_range_from< boost::transform_iterator<FUNCTION, ITERATOR> >
{
    template<typename KEY, typename NODE, typename SELECTOR>
    typename LLDependencies<KEY, NODE>::dep_range
    operator()(const LLDependencies<KEY, NODE>& deps,
               const boost::transform_iterator<FUNCTION, ITERATOR>& iter,
               const SELECTOR& selector)
    {
        return deps.get_dep_range_from_xform(iter, selector);
    }
};

/// Specialize LLDependencies_dep_range_from for sorted_iterator
template<typename BASEITER>
struct LLDependencies_dep_range_from< boost::indirect_iterator<BASEITER> >
{
    template<typename KEY, typename NODE, typename SELECTOR>
    typename LLDependencies<KEY, NODE>::dep_range
    operator()(const LLDependencies<KEY, NODE>& deps,
               const boost::indirect_iterator<BASEITER>& iter,
               const SELECTOR& selector)
    {
        return deps.get_dep_range_from_sorted(iter, selector);
    }
};

/// generic get_after_range() implementation
template<typename KEY, typename NODE>
template<typename KEY_OR_ITER>
typename LLDependencies<KEY, NODE>::dep_range
LLDependencies<KEY, NODE>::get_after_range(const KEY_OR_ITER& key_iter) const
{
    return LLDependencies_dep_range_from<KEY_OR_ITER>()(
        *this,
        key_iter,
        boost::bind<const typename DepNode::dep_set&>(&DepNode::after, _1));
}

/// generic get_before_range() implementation
template<typename KEY, typename NODE>
template<typename KEY_OR_ITER>
typename LLDependencies<KEY, NODE>::dep_range
LLDependencies<KEY, NODE>::get_before_range(const KEY_OR_ITER& key_iter) const
{
    return LLDependencies_dep_range_from<KEY_OR_ITER>()(
        *this,
        key_iter,
        boost::bind<const typename DepNode::dep_set&>(&DepNode::before, _1));
}

#endif /* ! defined(LL_LLDEPENDENCIES_H) */