summaryrefslogtreecommitdiff
path: root/indra/llcommon/lldependencies.h
blob: e0294e271ba472c050d82c87a0212cb684549eaf (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
/**
 * @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 <stdexcept>
#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>

/*****************************************************************************
*   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 std::runtime_error
    {
        Cycle(const std::string& what): std::runtime_error(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<int, int> > EdgeList;
    typedef std::vector<int> 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, int> 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) */