boost/boost/iterator_adaptors.hpp

   1 // (C) Copyright David Abrahams 2000. Permission to copy, use,
   2 // modify, sell and distribute this software is granted provided this
   3 // copyright notice appears in all copies. This software is provided
   4 // "as is" without express or implied warranty, and with no claim as
   5 // to its suitability for any purpose.
   6 //
   7 // (C) Copyright Jeremy Siek 2000. Permission to copy, use, modify,
   8 // sell and distribute this software is granted provided this
   9 // copyright notice appears in all copies. This software is provided
  10 // "as is" without express or implied warranty, and with no claim as
  11 // to its suitability for any purpose.
  12
  13 //  See http://www.boost.org/libs/utility/iterator_adaptors.htm for documentation.
  14
  15 // Revision History:
  16
  17 // 01 Feb 2002   Jeremy Siek
  18 //      Added more comments in default_iterator_policies.
  19 // 08 Jan 2001   David Abrahams
  20 //      Moved concept checks into a separate class, which makes MSVC
  21 //      better at dealing with them.
  22 // 07 Jan 2001   David Abrahams
  23 //      Choose proxy for operator->() only if the reference type is not a reference.
  24 //      Updated workarounds for __MWERKS__ == 0x2406
  25 // 20 Dec 2001   David Abrahams
  26 //      Adjusted is_convertible workarounds for __MWERKS__ == 0x2406
  27 // 03 Nov 2001   Jeremy Siek
  28 //      Changed the named template parameter interface and internal.
  29 // 04 Oct 2001   Jeremy Siek
  30 //      Changed projection_iterator to not rely on the default reference,
  31 //      working around a limitation of detail::iterator_traits.
  32 // 04 Oct 2001   David Abrahams
  33 //      Applied indirect_iterator patch from George A. Heintzelman <georgeh@aya.yale.edu>
  34 //      Changed name of "bind" to "select" to avoid problems with MSVC.
  35 // 26 Sep 2001   David Abrahams
  36 //      Added borland bug fix
  37 // 08 Mar 2001   Jeremy Siek
  38 //      Added support for optional named template parameters.
  39 // 19 Feb 2001   David Abrahams
  40 //      Rolled back reverse_iterator_pair_generator again, as it doesn't
  41 //      save typing on a conforming compiler.
  42 // 18 Feb 2001   David Abrahams
  43 //      Reinstated reverse_iterator_pair_generator
  44 // 16 Feb 2001   David Abrahams
  45 //      Add an implicit conversion operator to operator_arrow_proxy
  46 //      as CW and BCC workarounds.
  47 // 11 Feb 2001   David Abrahams
  48 //      Switch to use of BOOST_STATIC_CONSTANT where possible
  49 // 11 Feb 2001   Jeremy Siek
  50 //      Removed workaround for older MIPSpro compiler. The workaround
  51 //        was preventing the proper functionality of the underlying
  52 //        iterator being carried forward into the iterator adaptor.
  53 //        Also added is_bidirectional enum to avoid EDG compiler error.
  54 // 11 Feb 2001   David Abrahams
  55 //      Borland fixes up the wazoo. It finally works!
  56 // 10 Feb 2001   David Abrahams
  57 //      Removed traits argument from iterator_adaptor<> and switched to
  58 //        explicit trait specification for maximum ease-of-use.
  59 //      Added comments to detail::iterator_defaults<>
  60 //      Began using detail::iterator_defaults<> unconditionally for code clarity
  61 //      Changed uses of `Iterator' to `Base' where non-iterators can be used.
  62 //
  63 // 10 Feb 2001   David Abrahams
  64 //      Rolled in supposed Borland fixes from John Maddock, but not seeing any
  65 //        improvement yet
  66 //      Changed argument order to indirect_ generator, for convenience in the
  67 //        case of input iterators (where Reference must be a value type).
  68 //      Removed derivation of filter_iterator_policies from
  69 //        default_iterator_policies, since the iterator category is likely to be
  70 //        reduced (we don't want to allow illegal operations like decrement).
  71 //      Support for a simpler filter iterator interface.
  72 //
  73 // 09 Feb 2001   David Abrahams
  74 //      Improved interface to indirect_ and reverse_ iterators
  75 //      Rolled back Jeremy's new constructor for now; it was causing
  76 //        problems with counting_iterator_test
  77 //      Attempted fix for Borland
  78 //
  79 // 09 Feb 2001   Jeremy Siek
  80 //      Added iterator constructor to allow const adaptor
  81 //        from non-const adaptee.
  82 //      Changed make_xxx to pass iterators by-value to
  83 //        get arrays converted to pointers.
  84 //      Removed InnerIterator template parameter from
  85 //        indirect_iterator_generator.
  86 //      Rearranged parameters for make_filter_iterator
  87 //
  88 // 07 Feb 2001   Jeremy Siek
  89 //      Removed some const iterator adaptor generators.
  90 //      Added make_xxx_iterator() helper functions for remaining
  91 //        iterator adaptors.
  92 //      Removed some traits template parameters where they
  93 //        where no longer needed thanks to detail::iterator_traits.
  94 //      Moved some of the compile-time logic into enums for
  95 //      EDG compatibility.
  96 //
  97 // 07 Feb 2001  David Abrahams
  98 //      Removed iterator_adaptor_pair_generator and
  99 //        reverse_iterator_pair_generator (more such culling to come)
 100 //      Improved comments
 101 //      Changed all uses of std::iterator_traits as default arguments
 102 //        to boost::detail::iterator_traits for improved utility in
 103 //        non-generic contexts
 104 //      Fixed naming convention of non-template parameter names
 105 //
 106 // 06 Feb 2001   David Abrahams
 107 //      Produce operator-> proxy objects for InputIterators
 108 //      Added static assertions to do some basic concept checks
 109 //      Renamed single-type generators -> xxx_generator
 110 //      Renamed const/nonconst iterator generators -> xxx_pair_generator
 111 //      Added make_transform_iterator(iter, function)
 112 //      The existence of boost::detail::iterator_traits allowed many
 113 //        template arguments to be defaulted. Some arguments had to be
 114 //        moved to accomplish it.
 115 //
 116 // 04 Feb 2001  MWERKS bug workaround, concept checking for proper
 117 //              reference types (David Abrahams)
 118
 119 #ifndef BOOST_ITERATOR_ADAPTOR_DWA053000_HPP_
 120 # define BOOST_ITERATOR_ADAPTOR_DWA053000_HPP_
 121
 122 # include <boost/iterator.hpp>
 123 # include <boost/utility.hpp>
 124 # include <boost/compressed_pair.hpp>
 125 # include <boost/concept_check.hpp>
 126 # include <boost/type.hpp>
 127 # include <boost/static_assert.hpp>
 128 # include <boost/type_traits.hpp>
 129 # include <boost/type_traits/conversion_traits.hpp>
 130 # include <boost/detail/iterator.hpp>
 131 # include <boost/detail/select_type.hpp>
 132 # include <boost/detail/workaround.hpp>
 133
 134 # if BOOST_WORKAROUND(__GNUC__, == 2) && __GNUC_MINOR__ <= 96 && !defined(__STL_USE_NAMESPACES)
 135 #  define BOOST_RELOPS_AMBIGUITY_BUG 1
 136 # endif
 137
 138 namespace boost {
 139
 140 //============================================================================
 141 // Concept checking classes that express the requirements for iterator
 142 // policies and adapted types. These classes are mostly for
 143 // documentation purposes, and are not used in this header file. They
 144 // merely provide a more succinct statement of what is expected of the
 145 // iterator policies.
 146
 147 template <class Policies, class Adapted, class Traits>
 148 struct TrivialIteratorPoliciesConcept
 149 {
 150   typedef typename Traits::reference reference;
 151   void constraints() {
 152     function_requires< AssignableConcept<Policies> >();
 153     function_requires< DefaultConstructibleConcept<Policies> >();
 154     function_requires< AssignableConcept<Adapted> >();
 155     function_requires< DefaultConstructibleConcept<Adapted> >();
 156
 157     const_constraints();
 158   }
 159   void const_constraints() const {
 160     reference r = p.dereference(x);
 161     b = p.equal(x, x);
 162     ignore_unused_variable_warning(r);
 163   }
 164   Policies p;
 165   Adapted x;
 166   mutable bool b;
 167 };
 168
 169 // Add InputIteratorPoliciesConcept?
 170
 171 template <class Policies, class Adapted, class Traits>
 172 struct ForwardIteratorPoliciesConcept
 173 {
 174   typedef typename Traits::iterator_category iterator_category;
 175   void constraints() {
 176     function_requires<
 177       TrivialIteratorPoliciesConcept<Policies, Adapted, Traits>
 178       >();
 179
 180     p.increment(x);
 181     std::forward_iterator_tag t = iterator_category();
 182     ignore_unused_variable_warning(t);
 183   }
 184   Policies p;
 185   Adapted x;
 186   iterator_category category;
 187 };
 188
 189 template <class Policies, class Adapted, class Traits>
 190 struct BidirectionalIteratorPoliciesConcept
 191 {
 192   typedef typename Traits::iterator_category iterator_category;
 193   void constraints() {
 194     function_requires<
 195       ForwardIteratorPoliciesConcept<Policies, Adapted, Traits>
 196       >();
 197
 198     p.decrement(x);
 199     std::bidirectional_iterator_tag t = iterator_category();
 200     ignore_unused_variable_warning(t);
 201   }
 202   Policies p;
 203   Adapted x;
 204 };
 205
 206 template <class Policies, class Adapted, class Traits>
 207 struct RandomAccessIteratorPoliciesConcept
 208 {
 209   typedef typename Traits::difference_type DifferenceType;
 210   typedef typename Traits::iterator_category iterator_category;
 211   void constraints() {
 212     function_requires<
 213       BidirectionalIteratorPoliciesConcept<Policies, Adapted, Traits>
 214       >();
 215
 216     p.advance(x, n);
 217     std::random_access_iterator_tag t = iterator_category();
 218     const_constraints();
 219     ignore_unused_variable_warning(t);
 220   }
 221   void const_constraints() const {
 222     n = p.distance(x, x);
 223   }
 224   Policies p;
 225   Adapted x;
 226   mutable DifferenceType n;
 227   mutable bool b;
 228 };
 229
 230
 231 //============================================================================
 232 // Default policies for iterator adaptors. You can use this as a base
 233 // class if you want to customize particular policies.
 234 struct default_iterator_policies
 235 {
 236     // Some of the member functions were defined static, but Borland
 237     // got confused and thought they were non-const. Also, Sun C++
 238     // does not like static function templates.
 239     //
 240     // The reason some members were defined static is because there is
 241     // not state (data members) needed by those members of the
 242     // default_iterator_policies class. If your policies class member
 243     // functions need to access state stored in the policies object,
 244     // then the member functions should not be static (they can't be).
 245
 246     template <class Base>
 247     void initialize(Base&)
 248         { }
 249
 250     template <class IteratorAdaptor>
 251     typename IteratorAdaptor::reference dereference(const IteratorAdaptor& x) const
 252         { return *x.base(); }
 253
 254     template <class IteratorAdaptor>
 255     void increment(IteratorAdaptor& x)
 256         { ++x.base(); }
 257
 258     template <class IteratorAdaptor>
 259     void decrement(IteratorAdaptor& x)
 260         { --x.base(); }
 261
 262     template <class IteratorAdaptor, class DifferenceType>
 263     void advance(IteratorAdaptor& x, DifferenceType n)
 264         { x.base() += n; }
 265
 266     template <class IteratorAdaptor1, class IteratorAdaptor2>
 267     typename IteratorAdaptor1::difference_type
 268     distance(const IteratorAdaptor1& x, const IteratorAdaptor2& y) const
 269         { return y.base() - x.base(); }
 270
 271     template <class IteratorAdaptor1, class IteratorAdaptor2>
 272     bool equal(const IteratorAdaptor1& x, const IteratorAdaptor2& y) const
 273         { return x.base() == y.base(); }
 274 };
 275
 276 // putting the comparisons in a base class avoids the g++
 277 // ambiguous overload bug due to the relops operators
 278
 279 #ifdef BOOST_RELOPS_AMBIGUITY_BUG
 280 template <class Derived, class Base>
 281 struct iterator_comparisons : Base { };
 282
 283 template <class D1, class D2, class Base1, class Base2>
 284 inline bool operator==(const iterator_comparisons<D1,Base1>& xb,
 285                        const iterator_comparisons<D2,Base2>& yb)
 286 {
 287         const D1& x = static_cast<const D1&>(xb);
 288     const D2& y = static_cast<const D2&>(yb);
 289     return x.policies().equal(x, y);
 290 }
 291
 292 template <class D1, class D2, class Base1, class Base2>
 293 inline bool operator!=(const iterator_comparisons<D1,Base1>& xb,
 294                        const iterator_comparisons<D2,Base2>& yb)
 295 {
 296     const D1& x = static_cast<const D1&>(xb);
 297     const D2& y = static_cast<const D2&>(yb);
 298     return !x.policies().equal(x, y);
 299 }
 300
 301 template <class D1, class D2, class Base1, class Base2>
 302 inline bool operator<(const iterator_comparisons<D1,Base1>& xb,
 303                       const iterator_comparisons<D2,Base2>& yb)
 304 {
 305     const D1& x = static_cast<const D1&>(xb);
 306     const D2& y = static_cast<const D2&>(yb);
 307     return x.policies().distance(y, x) < 0;
 308 }
 309
 310 template <class D1, class D2, class Base1, class Base2>
 311 inline bool operator>(const iterator_comparisons<D1,Base1>& xb,
 312                       const iterator_comparisons<D2,Base2>& yb)
 313 {
 314     const D1& x = static_cast<const D1&>(xb);
 315     const D2& y = static_cast<const D2&>(yb);
 316     return x.policies().distance(y, x) > 0;
 317 }
 318
 319 template <class D1, class D2, class Base1, class Base2>
 320 inline bool operator>=(const iterator_comparisons<D1,Base1>& xb,
 321                        const iterator_comparisons<D2,Base2>& yb)
 322 {
 323     const D1& x = static_cast<const D1&>(xb);
 324     const D2& y = static_cast<const D2&>(yb);
 325     return x.policies().distance(y, x) >= 0;
 326 }
 327
 328 template <class D1, class D2, class Base1, class Base2>
 329 inline bool operator<=(const iterator_comparisons<D1,Base1>& xb,
 330                        const iterator_comparisons<D2,Base2>& yb)
 331 {
 332     const D1& x = static_cast<const D1&>(xb);
 333     const D2& y = static_cast<const D2&>(yb);
 334     return x.policies().distance(y, x) <= 0;
 335 }
 336 #endif
 337
 338 namespace detail {
 339
 340   // operator->() needs special support for input iterators to strictly meet the
 341   // standard's requirements. If *i is not a reference type, we must still
 342   // produce a (constant) lvalue to which a pointer can be formed. We do that by
 343   // returning an instantiation of this special proxy class template.
 344
 345   template <class T>
 346   struct operator_arrow_proxy
 347   {
 348       operator_arrow_proxy(const T& x) : m_value(x) {}
 349       const T* operator->() const { return &m_value; }
 350       // This function is needed for MWCW and BCC, which won't call operator->
 351       // again automatically per 13.3.1.2 para 8
 352       operator const T*() const { return &m_value; }
 353       T m_value;
 354   };
 355
 356   template <class Iter>
 357   inline operator_arrow_proxy<typename Iter::value_type>
 358   operator_arrow(const Iter& i, std::input_iterator_tag) {
 359     typedef typename Iter::value_type value_t; // VC++ needs this typedef
 360     return operator_arrow_proxy<value_t>(*i);
 361   }
 362
 363   template <class Iter>
 364   inline typename Iter::pointer
 365   operator_arrow(const Iter& i, std::forward_iterator_tag) {
 366     return &(*i);
 367   }
 368
 369   template <class Value, class Reference, class Pointer>
 370   struct operator_arrow_result_generator
 371   {
 372       typedef operator_arrow_proxy<Value> proxy;
 373       // Borland chokes unless it's an actual enum (!)
 374       enum { use_proxy = !boost::is_reference<Reference>::value };
 375
 376       typedef typename boost::detail::if_true<(use_proxy)>::template
 377       then<
 378         proxy,
 379    // else
 380         Pointer
 381       >::type type;
 382   };
 383
 384
 385 # if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) || defined(BOOST_NO_STD_ITERATOR_TRAITS)
 386
 387    // Select default pointer and reference types for adapted non-pointer
 388    // iterators based on the iterator and the value_type. Poor man's partial
 389    // specialization is in use here.
 390    template <bool is_pointer>
 391    struct iterator_defaults_select
 392    {
 393        template <class Iterator,class Value>
 394        struct traits
 395        {
 396            // The assumption is that iterator_traits can deduce these types
 397            // properly as long as the iterator is not a pointer.
 398            typedef typename boost::detail::iterator_traits<Iterator>::pointer pointer;
 399            typedef typename boost::detail::iterator_traits<Iterator>::reference reference;
 400        };
 401    };
 402
 403    // Select default pointer and reference types for adapted pointer iterators
 404    // given a (possibly-const) value_type.
 405    template <>
 406    struct iterator_defaults_select<true>
 407    {
 408        template <class Iterator,class Value>
 409        struct traits
 410        {
 411            typedef Value* pointer;
 412            typedef Value& reference;
 413        };
 414    };
 415
 416    // Consolidate selection of the default pointer and reference type
 417    template <class Iterator,class Value>
 418    struct iterator_defaults
 419    {
 420        BOOST_STATIC_CONSTANT(bool, is_ptr = boost::is_pointer<Iterator>::value);
 421
 422        typedef typename iterator_defaults_select<is_ptr>::template traits<Iterator,Value> traits;
 423        typedef typename traits::pointer pointer;
 424        typedef typename traits::reference reference;
 425    };
 426 # else
 427    template <class Iterator,class Value>
 428    struct iterator_defaults : iterator_traits<Iterator>
 429    {
 430        // Trying to factor the common is_same expression into an enum or a
 431        // static bool constant confused Borland.
 432        typedef typename if_true<(
 433                ::boost::is_same<Value,typename iterator_traits<Iterator>::value_type>::value
 434            )>::template then<
 435                 typename iterator_traits<Iterator>::pointer,
 436                 Value*
 437        >::type pointer;
 438
 439        typedef typename if_true<(
 440                ::boost::is_same<Value,typename iterator_traits<Iterator>::value_type>::value
 441            )>::template then<
 442                 typename iterator_traits<Iterator>::reference,
 443                 Value&
 444        >::type reference;
 445
 446    };
 447 # endif
 448
 449   //===========================================================================
 450   // Specify the defaults for iterator_adaptor's template parameters
 451
 452   struct default_argument { };
 453   // This class template is a workaround for MSVC.
 454   struct dummy_default_gen {
 455     template <class Base, class Traits>
 456     struct select { typedef default_argument type; };
 457   };
 458   // This class template is a workaround for MSVC.
 459   template <class Gen> struct default_generator {
 460     typedef dummy_default_gen type;
 461   };
 462
 463   struct default_value_type {
 464     template <class Base, class Traits>
 465     struct select {
 466       typedef typename boost::detail::iterator_traits<Base>::value_type type;
 467     };
 468   };
 469   template <> struct default_generator<default_value_type>
 470   { typedef default_value_type type; }; // VC++ workaround
 471
 472   struct default_difference_type {
 473     template <class Base, class Traits>
 474     struct select {
 475       typedef typename boost::detail::iterator_traits<Base>::difference_type type;
 476     };
 477   };
 478   template <> struct default_generator<default_difference_type>
 479   { typedef default_difference_type type; }; // VC++ workaround
 480
 481   struct default_iterator_category {
 482     template <class Base, class Traits>
 483     struct select {
 484       typedef typename boost::detail::iterator_traits<Base>::iterator_category type;
 485     };
 486   };
 487   template <> struct default_generator<default_iterator_category>
 488   { typedef default_iterator_category type; }; // VC++ workaround
 489
 490   struct default_pointer {
 491     template <class Base, class Traits>
 492     struct select {
 493       typedef typename Traits::value_type Value;
 494       typedef typename boost::detail::iterator_defaults<Base,Value>::pointer
 495         type;
 496     };
 497   };
 498   template <> struct default_generator<default_pointer>
 499   { typedef default_pointer type; }; // VC++ workaround
 500
 501   struct default_reference {
 502     template <class Base, class Traits>
 503     struct select {
 504       typedef typename Traits::value_type Value;
 505       typedef typename boost::detail::iterator_defaults<Base,Value>::reference
 506         type;
 507     };
 508   };
 509   template <> struct default_generator<default_reference>
 510   { typedef default_reference type; }; // VC++ workaround
 511
 512 } // namespace detail
 513
 514
 515   //===========================================================================
 516   // Support for named template parameters
 517
 518 struct named_template_param_base { };
 519
 520 namespace detail {
 521   struct value_type_tag { };
 522   struct reference_tag { };
 523   struct pointer_tag { };
 524   struct difference_type_tag { };
 525   struct iterator_category_tag { };
 526
 527   // avoid using std::pair because A or B might be a reference type, and g++
 528   // complains about forming references to references inside std::pair
 529   template <class A, class B>
 530   struct cons_type {
 531     typedef A first_type;
 532     typedef B second_type;
 533   };
 534
 535 } // namespace detail
 536
 537 template <class Value> struct value_type_is : public named_template_param_base
 538 {
 539   typedef detail::cons_type<detail::value_type_tag, Value> type;
 540 };
 541 template <class Reference> struct reference_is : public named_template_param_base
 542 {
 543   typedef detail::cons_type<detail::reference_tag, Reference> type;
 544 };
 545 template <class Pointer> struct pointer_is : public named_template_param_base
 546 {
 547   typedef detail::cons_type<detail::pointer_tag, Pointer> type;
 548 };
 549 template <class Difference> struct difference_type_is
 550   : public named_template_param_base
 551 {
 552   typedef detail::cons_type<detail::difference_type_tag, Difference> type;
 553 };
 554 template <class IteratorCategory> struct iterator_category_is
 555   : public named_template_param_base
 556 {
 557   typedef detail::cons_type<detail::iterator_category_tag, IteratorCategory> type;
 558 };
 559
 560 namespace detail {
 561
 562   struct end_of_list { };
 563
 564   // Given an associative list, find the value with the matching key.
 565   // An associative list is a list of key-value pairs. The list is
 566   // built out of cons_type's and is terminated by end_of_list.
 567
 568 # if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) || BOOST_WORKAROUND(__BORLANDC__, != 0)
 569   template <class AssocList, class Key>
 570   struct find_param;
 571
 572   struct find_param_continue {
 573     template <class AssocList, class Key2> struct select {
 574       typedef typename AssocList::first_type Head;
 575       typedef typename Head::first_type Key1;
 576       typedef typename Head::second_type Value;
 577       typedef typename if_true<(is_same<Key1, Key2>::value)>::template
 578       then<Value,
 579         typename find_param<typename AssocList::second_type, Key2>::type
 580       >::type type;
 581     };
 582   };
 583   struct find_param_end {
 584     template <class AssocList, class Key>
 585     struct select { typedef detail::default_argument type; };
 586   };
 587   template <class AssocList> struct find_param_helper1
 588   { typedef find_param_continue type; };
 589   template <> struct find_param_helper1<end_of_list>
 590   { typedef find_param_end type; };
 591
 592   template <class AssocList, class Key>
 593   struct find_param {
 594     typedef typename find_param_helper1<AssocList>::type select1;
 595     typedef typename select1::template select<AssocList, Key>::type type;
 596   };
 597 # else
 598   template <class AssocList, class Key> struct find_param;
 599
 600   template <class Key>
 601   struct find_param<end_of_list, Key> { typedef default_argument type; };
 602
 603   // Found a matching Key, return the associated Value
 604   template <class Key, class Value, class Rest>
 605   struct find_param<detail::cons_type< detail::cons_type<Key, Value>, Rest>, Key> {
 606     typedef Value type;
 607   };
 608
 609   // Non-matching keys, continue the search
 610   template <class Key1, class Value, class Rest, class Key2>
 611   struct find_param<detail::cons_type< detail::cons_type<Key1, Value>, Rest>, Key2> {
 612     typedef typename find_param<Rest, Key2>::type type;
 613   };
 614 # endif
 615
 616   struct make_named_arg {
 617     template <class Key, class Value>
 618     struct select { typedef typename Value::type type; };
 619   };
 620   struct make_key_value {
 621     template <class Key, class Value>
 622     struct select { typedef detail::cons_type<Key, Value> type; };
 623   };
 624
 625   template <class Value>
 626   struct is_named_parameter
 627   {
 628       enum { value = is_convertible< typename add_reference< Value >::type, add_reference< named_template_param_base >::type >::value };
 629   };
 630
 631 # if BOOST_WORKAROUND(__MWERKS__, <= 0x2407) // workaround for broken is_convertible implementation
 632   template <class T> struct is_named_parameter<value_type_is<T> > { enum { value = true }; };
 633   template <class T> struct is_named_parameter<reference_is<T> > { enum { value = true }; };
 634   template <class T> struct is_named_parameter<pointer_is<T> > { enum { value = true }; };
 635   template <class T> struct is_named_parameter<difference_type_is<T> > { enum { value = true }; };
 636   template <class T> struct is_named_parameter<iterator_category_is<T> > { enum { value = true }; };
 637 # endif
 638
 639   template <class Key, class Value>
 640   struct make_arg {
 641 # if BOOST_WORKAROUND(__BORLANDC__, > 0)
 642     // Borland C++ doesn't like the extra indirection of is_named_parameter
 643     typedef typename
 644       if_true<(is_convertible<Value,named_template_param_base>::value)>::
 645       template then<make_named_arg, make_key_value>::type Make;
 646 # else
 647     enum { is_named = is_named_parameter<Value>::value };
 648     typedef typename if_true<(is_named)>::template
 649       then<make_named_arg, make_key_value>::type Make;
 650 # endif
 651     typedef typename Make::template select<Key, Value>::type type;
 652   };
 653
 654   // Mechanism for resolving the default argument for a template parameter.
 655
 656   template <class T> struct is_default { typedef type_traits::no_type type; };
 657   template <> struct is_default<default_argument>
 658   { typedef type_traits::yes_type type; };
 659
 660   struct choose_default {
 661     template <class Arg, class DefaultGen, class Base, class Traits>
 662     struct select {
 663       typedef typename default_generator<DefaultGen>::type Gen;
 664       typedef typename Gen::template select<Base,Traits>::type type;
 665     };
 666   };
 667   struct choose_arg {
 668     template <class Arg, class DefaultGen, class Base, class Traits>
 669     struct select {
 670       typedef Arg type;
 671     };
 672   };
 673
 674   template <class UseDefault>
 675   struct choose_arg_or_default { typedef choose_arg type; };
 676   template <> struct choose_arg_or_default<type_traits::yes_type> {
 677     typedef choose_default type;
 678   };
 679
 680   template <class Arg, class DefaultGen, class Base, class Traits>
 681   class resolve_default {
 682     typedef typename choose_arg_or_default<typename is_default<Arg>::type>::type
 683       Selector;
 684   public:
 685     typedef typename Selector
 686       ::template select<Arg, DefaultGen, Base, Traits>::type type;
 687   };
 688
 689   template <class Base, class Value, class Reference, class Pointer,
 690             class Category, class Distance>
 691   class iterator_adaptor_traits_gen
 692   {
 693     // Form an associative list out of the template parameters
 694     // If the argument is a normal parameter (not named) then make_arg
 695     // creates a key-value pair. If the argument is a named parameter,
 696     // then make_arg extracts the key-value pair defined inside the
 697     // named parameter.
 698     typedef detail::cons_type< typename make_arg<value_type_tag, Value>::type,
 699       detail::cons_type<typename make_arg<reference_tag, Reference>::type,
 700       detail::cons_type<typename make_arg<pointer_tag, Pointer>::type,
 701       detail::cons_type<typename make_arg<iterator_category_tag, Category>::type,
 702       detail::cons_type<typename make_arg<difference_type_tag, Distance>::type,
 703                 end_of_list> > > > > ArgList;
 704
 705     // Search the list for particular parameters
 706     typedef typename find_param<ArgList, value_type_tag>::type Val;
 707     typedef typename find_param<ArgList, difference_type_tag>::type Diff;
 708     typedef typename find_param<ArgList, iterator_category_tag>::type Cat;
 709     typedef typename find_param<ArgList, pointer_tag>::type Ptr;
 710     typedef typename find_param<ArgList, reference_tag>::type Ref;
 711
 712     typedef boost::iterator<Category, Value, Distance, Pointer, Reference>
 713       Traits0;
 714
 715     // Compute the defaults if necessary
 716     typedef typename resolve_default<Val, default_value_type, Base, Traits0>::type
 717       value_type;
 718     // if getting default value type from iterator_traits, then it won't be const
 719     typedef typename resolve_default<Diff, default_difference_type, Base,
 720       Traits0>::type difference_type;
 721     typedef typename resolve_default<Cat, default_iterator_category, Base,
 722       Traits0>::type iterator_category;
 723
 724     typedef boost::iterator<iterator_category, value_type, difference_type,
 725       Pointer, Reference> Traits1;
 726
 727     // Compute the defaults for pointer and reference. This is done as a
 728     // separate step because the defaults for pointer and reference depend
 729     // on value_type.
 730     typedef typename resolve_default<Ptr, default_pointer, Base, Traits1>::type
 731       pointer;
 732     typedef typename resolve_default<Ref, default_reference, Base, Traits1>::type
 733       reference;
 734
 735   public:
 736     typedef boost::iterator<iterator_category,
 737       typename remove_const<value_type>::type,
 738       difference_type, pointer, reference> type;
 739   };
 740
 741   // This is really a partial concept check for iterators. Should it
 742   // be moved or done differently?
 743   template <class Category, class Value, class Difference, class Pointer, class Reference>
 744   struct validator
 745   {
 746       BOOST_STATIC_CONSTANT(
 747           bool, is_input_or_output_iter
 748           = (boost::is_convertible<Category*,std::input_iterator_tag*>::value
 749              | boost::is_convertible<Category*,std::output_iterator_tag*>::value));
 750
 751       // Iterators should satisfy one of the known categories
 752       BOOST_STATIC_ASSERT(is_input_or_output_iter);
 753
 754       // Iterators >= ForwardIterator must produce real references
 755       // as required by the C++ standard requirements in Table 74.
 756       BOOST_STATIC_CONSTANT(
 757           bool, forward_iter_with_real_reference
 758           = ((!boost::is_convertible<Category*,std::forward_iterator_tag*>::value)
 759              | boost::is_same<Reference,Value&>::value
 760              | boost::is_same<Reference,typename add_const<Value>::type&>::value));
 761
 762       BOOST_STATIC_ASSERT(forward_iter_with_real_reference);
 763   };
 764
 765   template <class T, class Result> struct dependent
 766   {
 767     typedef Result type;
 768   };
 769
 770 } // namespace detail
 771
 772
 773
 774 // This macro definition is only temporary in this file
 775 # if !BOOST_WORKAROUND(BOOST_MSVC, <= 1300)
 776 #  define BOOST_ARG_DEPENDENT_TYPENAME typename
 777 # else
 778 #  define BOOST_ARG_DEPENDENT_TYPENAME
 779 # endif
 780
 781 //============================================================================
 782 //iterator_adaptor - Adapts a generic piece of data as an iterator. Adaptation
 783 //      is especially easy if the data being adapted is itself an iterator
 784 //
 785 //   Base - the base (usually iterator) type being wrapped.
 786 //
 787 //   Policies - a set of policies determining how the resulting iterator
 788 //      works.
 789 //
 790 //   Value - if supplied, the value_type of the resulting iterator, unless
 791 //      const. If const, a conforming compiler strips constness for the
 792 //      value_type. If not supplied, iterator_traits<Base>::value_type is used
 793 //
 794 //   Reference - the reference type of the resulting iterator, and in
 795 //      particular, the result type of operator*(). If not supplied but
 796 //      Value is supplied, Value& is used. Otherwise
 797 //      iterator_traits<Base>::reference is used.
 798 //
 799 //   Pointer - the pointer type of the resulting iterator, and in
 800 //      particular, the result type of operator->(). If not
 801 //      supplied but Value is supplied, Value* is used. Otherwise
 802 //      iterator_traits<Base>::pointer is used.
 803 //
 804 //   Category - the iterator_category of the resulting iterator. If not
 805 //      supplied, iterator_traits<Base>::iterator_category is used.
 806 //
 807 //   Distance - the difference_type of the resulting iterator. If not
 808 //      supplied, iterator_traits<Base>::difference_type is used.
 809 template <class Base, class Policies,
 810     class Value = ::boost::detail::default_argument,
 811     class Reference = ::boost::detail::default_argument,
 812     class Pointer = ::boost::detail::default_argument,
 813     class Category = ::boost::detail::default_argument,
 814     class Distance = ::boost::detail::default_argument
 815          >
 816 struct iterator_adaptor :
 817 #ifdef BOOST_RELOPS_AMBIGUITY_BUG
 818     iterator_comparisons<
 819           iterator_adaptor<Base,Policies,Value,Reference,Pointer,Category,Distance>,
 820     typename detail::iterator_adaptor_traits_gen<Base,Value,Reference,Pointer,Category, Distance>::type
 821  >
 822 #else
 823     detail::iterator_adaptor_traits_gen<Base,Value,Reference,Pointer,Category,Distance>::type
 824 #endif
 825 {
 826     typedef iterator_adaptor<Base,Policies,Value,Reference,Pointer,Category,Distance> self;
 827  public:
 828     typedef detail::iterator_adaptor_traits_gen<Base,Value,Reference,Pointer,Category,Distance> TraitsGen;
 829     typedef typename TraitsGen::type Traits;
 830
 831     typedef typename Traits::difference_type difference_type;
 832     typedef typename Traits::value_type value_type;
 833     typedef typename Traits::pointer pointer;
 834     typedef typename Traits::reference reference;
 835     typedef typename Traits::iterator_category iterator_category;
 836
 837     typedef Base base_type;
 838     typedef Policies policies_type;
 839
 840  private:
 841     typedef detail::validator<
 842         iterator_category,value_type,difference_type,pointer,reference
 843         > concept_check;
 844
 845  public:
 846     iterator_adaptor()
 847     {
 848     }
 849
 850     explicit
 851     iterator_adaptor(const Base& it, const Policies& p = Policies())
 852         : m_iter_p(it, p) {
 853         policies().initialize(base());
 854     }
 855
 856     template <class Iter2, class Value2, class Pointer2, class Reference2>
 857     iterator_adaptor (
 858         const iterator_adaptor<Iter2,Policies,Value2,Reference2,Pointer2,Category,Distance>& src)
 859             : m_iter_p(src.base(), src.policies())
 860     {
 861         policies().initialize(base());
 862     }
 863
 864 #if BOOST_WORKAROUND(BOOST_MSVC, <= 1300) || BOOST_WORKAROUND(__BORLANDC__, > 0)
 865     // This is required to prevent a bug in how VC++ generates
 866     // the assignment operator for compressed_pair
 867     iterator_adaptor& operator= (const iterator_adaptor& x) {
 868         m_iter_p = x.m_iter_p;
 869         return *this;
 870     }
 871 #endif
 872     reference operator*() const {
 873          return policies().dereference(*this);
 874     }
 875
 876 #if BOOST_WORKAROUND(BOOST_MSVC, > 0)
 877 # pragma warning(push)
 878 # pragma warning( disable : 4284 )
 879 #endif
 880
 881     typename boost::detail::operator_arrow_result_generator<value_type,reference,pointer>::type
 882     operator->() const
 883         { return detail::operator_arrow(*this, iterator_category()); }
 884
 885 #if BOOST_WORKAROUND(BOOST_MSVC, > 0)
 886 # pragma warning(pop)
 887 #endif
 888
 889     template <class diff_type>
 890     typename detail::dependent<diff_type, value_type>::type operator[](diff_type n) const
 891         { return *(*this + n); }
 892
 893     self& operator++() {
 894 #if !BOOST_WORKAROUND(__MWERKS__, <  0x2405)
 895         policies().increment(*this);
 896 #else
 897         // Odd bug, MWERKS couldn't  deduce the type for the member template
 898         // Workaround by explicitly specifying the type.
 899         policies().increment<self>(*this);
 900 #endif
 901         return *this;
 902     }
 903
 904     self operator++(int) { self tmp(*this); ++*this; return tmp; }
 905
 906     self& operator--() {
 907 #if !BOOST_WORKAROUND(__MWERKS__, <  0x2405)
 908         policies().decrement(*this);
 909 #else
 910         policies().decrement<self>(*this);
 911 #endif
 912         return *this;
 913     }
 914
 915     self operator--(int) { self tmp(*this); --*this; return tmp; }
 916
 917     self& operator+=(difference_type n) {
 918         policies().advance(*this, n);
 919         return *this;
 920     }
 921
 922     self& operator-=(difference_type n) {
 923         policies().advance(*this, -n);
 924         return *this;
 925     }
 926
 927     base_type const& base() const { return m_iter_p.first(); }
 928
 929     // Moved from global scope to avoid ambiguity with the operator-() which
 930     // subtracts iterators from one another.
 931     self operator-(difference_type x) const
 932         { self result(*this); return result -= x; }
 933 private:
 934     compressed_pair<Base,Policies> m_iter_p;
 935
 936 public: // implementation details (too many compilers have trouble when these are private).
 937     base_type& base() { return m_iter_p.first(); }
 938     Policies& policies() { return m_iter_p.second(); }
 939     const Policies& policies() const { return m_iter_p.second(); }
 940 };
 941
 942 template <class Base, class Policies, class Value, class Reference, class Pointer,
 943     class Category, class Distance1, class Distance2>
 944 iterator_adaptor<Base,Policies,Value,Reference,Pointer,Category,Distance1>
 945 operator+(
 946     iterator_adaptor<Base,Policies,Value,Reference,Pointer,Category,Distance1> p,
 947     Distance2 x)
 948 {
 949     return p += x;
 950 }
 951
 952 template <class Base, class Policies, class Value, class Reference, class Pointer,
 953     class Category, class Distance1, class Distance2>
 954 iterator_adaptor<Base,Policies,Value,Reference,Pointer,Category,Distance1>
 955 operator+(
 956     Distance2 x,
 957     iterator_adaptor<Base,Policies,Value,Reference,Pointer,Category,Distance1> p)
 958 {
 959     return p += x;
 960 }
 961
 962 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
 963     class Reference1, class Reference2, class Pointer1, class Pointer2, class Category,
 964     class Distance>
 965 typename iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>::difference_type
 966 operator-(
 967     const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
 968     const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
 969 {
 970   typedef typename iterator_adaptor<Iterator1,Policies,Value1,Reference1,
 971     Pointer1,Category,Distance>::difference_type difference_type;
 972   return x.policies().distance(y, x);
 973 }
 974
 975 #ifndef BOOST_RELOPS_AMBIGUITY_BUG
 976 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
 977     class Reference1, class Reference2, class Pointer1, class Pointer2,
 978     class Category, class Distance>
 979 inline bool
 980 operator==(
 981     const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
 982     const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
 983 {
 984     return x.policies().equal(x, y);
 985 }
 986
 987 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
 988     class Reference1, class Reference2, class Pointer1, class Pointer2,
 989     class Category, class Distance>
 990 inline bool
 991 operator<(
 992     const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
 993     const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
 994 {
 995     return x.policies().distance(y, x) < 0;
 996 }
 997
 998 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
 999     class Reference1, class Reference2, class Pointer1, class Pointer2,
1000     class Category, class Distance>
1001 inline bool
1002 operator>(
1003     const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
1004     const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
1005 {
1006     return x.policies().distance(y, x) > 0;
1007 }
1008
1009 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
1010     class Reference1, class Reference2, class Pointer1, class Pointer2,
1011     class Category, class Distance>
1012 inline bool
1013 operator>=(
1014     const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
1015     const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
1016 {
1017     return x.policies().distance(y, x) >= 0;
1018 }
1019
1020 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
1021     class Reference1, class Reference2, class Pointer1, class Pointer2,
1022     class Category, class Distance>
1023 inline bool
1024 operator<=(
1025     const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
1026     const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
1027 {
1028     return x.policies().distance(y, x) <= 0;
1029 }
1030
1031 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
1032     class Reference1, class Reference2, class Pointer1, class Pointer2,
1033     class Category, class Distance>
1034 inline bool
1035 operator!=(
1036     const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
1037     const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
1038 {
1039     return !x.policies().equal(x, y);
1040 }
1041 #endif
1042
1043 //=============================================================================
1044 // Transform Iterator Adaptor
1045 //
1046 // Upon deference, apply some unary function object and return the
1047 // result by value.
1048
1049 template <class AdaptableUnaryFunction>
1050 struct transform_iterator_policies : public default_iterator_policies
1051 {
1052     transform_iterator_policies() { }
1053     transform_iterator_policies(const AdaptableUnaryFunction& f) : m_f(f) { }
1054
1055     template <class IteratorAdaptor>
1056     typename IteratorAdaptor::reference
1057     dereference(const IteratorAdaptor& iter) const
1058         { return m_f(*iter.base()); }
1059
1060     AdaptableUnaryFunction m_f;
1061 };
1062
1063 template <class AdaptableUnaryFunction, class Iterator>
1064 class transform_iterator_generator
1065 {
1066     typedef typename AdaptableUnaryFunction::result_type value_type;
1067 public:
1068     typedef iterator_adaptor<Iterator,
1069       transform_iterator_policies<AdaptableUnaryFunction>,
1070         value_type, value_type, value_type*, std::input_iterator_tag>
1071       type;
1072 };
1073
1074 template <class AdaptableUnaryFunction, class Iterator>
1075 inline typename transform_iterator_generator<AdaptableUnaryFunction,Iterator>::type
1076 make_transform_iterator(
1077     Iterator base,
1078     const AdaptableUnaryFunction& f = AdaptableUnaryFunction())
1079 {
1080     typedef typename transform_iterator_generator<AdaptableUnaryFunction,Iterator>::type result_t;
1081     return result_t(base, f);
1082 }
1083
1084 //=============================================================================
1085 // Indirect Iterators Adaptor
1086
1087 // Given a pointer to pointers (or iterator to iterators),
1088 // apply a double dereference inside operator*().
1089 //
1090 // We use the term "outer" to refer to the first level iterator type
1091 // and "inner" to refer to the second level iterator type.  For
1092 // example, given T**, T* is the inner iterator type and T** is the
1093 // outer iterator type. Also, const T* would be the const inner
1094 // iterator.
1095
1096 // We tried to implement this with transform_iterator, but that required
1097 // using boost::remove_ref, which is not compiler portable.
1098
1099 struct indirect_iterator_policies : public default_iterator_policies
1100 {
1101     template <class IteratorAdaptor>
1102     typename IteratorAdaptor::reference dereference(const IteratorAdaptor& x) const
1103         { return **x.base(); }
1104 };
1105
1106 namespace detail {
1107 # if !BOOST_WORKAROUND(BOOST_MSVC, <= 1300) // strangely instantiated even when unused! Maybe try a recursive template someday ;-)
1108   template <class T>
1109   struct traits_of_value_type {
1110       typedef typename boost::detail::iterator_traits<T>::value_type outer_value;
1111       typedef typename boost::detail::iterator_traits<outer_value>::value_type value_type;
1112       typedef typename boost::detail::iterator_traits<outer_value>::reference reference;
1113       typedef typename boost::detail::iterator_traits<outer_value>::pointer pointer;
1114   };
1115 # endif
1116 }
1117
1118 template <class OuterIterator,      // Mutable or Immutable, does not matter
1119           class Value
1120 #if !BOOST_WORKAROUND(BOOST_MSVC, <= 1300)
1121                 = BOOST_ARG_DEPENDENT_TYPENAME detail::traits_of_value_type<
1122                         OuterIterator>::value_type
1123 #endif
1124           , class Reference
1125 #if !BOOST_WORKAROUND(BOOST_MSVC, <= 1300)
1126                 = BOOST_ARG_DEPENDENT_TYPENAME detail::traits_of_value_type<
1127                         OuterIterator>::reference
1128 #else
1129                 = Value &
1130 #endif
1131           , class Category = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<
1132                         OuterIterator>::iterator_category
1133           , class Pointer
1134 #if !BOOST_WORKAROUND(BOOST_MSVC, <= 1300)
1135                 = BOOST_ARG_DEPENDENT_TYPENAME detail::traits_of_value_type<
1136                         OuterIterator>::pointer
1137 #else
1138                 = Value*
1139 #endif
1140          >
1141 struct indirect_iterator_generator
1142 {
1143     typedef iterator_adaptor<OuterIterator,
1144         indirect_iterator_policies,Value,Reference,Pointer,Category> type;
1145 };
1146
1147 template <class OuterIterator,      // Mutable or Immutable, does not matter
1148           class Value
1149 #if !BOOST_WORKAROUND(BOOST_MSVC, <= 1300)
1150                 = BOOST_ARG_DEPENDENT_TYPENAME detail::traits_of_value_type<
1151                         OuterIterator>::value_type
1152 #endif
1153           , class Reference
1154 #if !BOOST_WORKAROUND(BOOST_MSVC, <= 1300)
1155                 = BOOST_ARG_DEPENDENT_TYPENAME detail::traits_of_value_type<
1156                         OuterIterator>::reference
1157 #else
1158                 = Value &
1159 #endif
1160           , class ConstReference = Value const&
1161           , class Category = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<
1162                 OuterIterator>::iterator_category
1163           , class Pointer
1164 #if !BOOST_WORKAROUND(BOOST_MSVC, <= 1300)
1165                 = BOOST_ARG_DEPENDENT_TYPENAME detail::traits_of_value_type<
1166                         OuterIterator>::pointer
1167 #else
1168                 = Value*
1169 #endif
1170           , class ConstPointer = Value const*
1171            >
1172 struct indirect_iterator_pair_generator
1173 {
1174   typedef typename indirect_iterator_generator<OuterIterator,
1175     Value, Reference,Category,Pointer>::type iterator;
1176   typedef typename indirect_iterator_generator<OuterIterator,
1177     Value, ConstReference,Category,ConstPointer>::type const_iterator;
1178 };
1179
1180 #if !BOOST_WORKAROUND(BOOST_MSVC, <= 1300)
1181 template <class OuterIterator>
1182 inline typename indirect_iterator_generator<OuterIterator>::type
1183 make_indirect_iterator(OuterIterator base)
1184 {
1185     typedef typename indirect_iterator_generator
1186         <OuterIterator>::type result_t;
1187     return result_t(base);
1188 }
1189 #endif
1190
1191 //=============================================================================
1192 // Reverse Iterators Adaptor
1193
1194 struct reverse_iterator_policies : public default_iterator_policies
1195 {
1196     template <class IteratorAdaptor>
1197     typename IteratorAdaptor::reference dereference(const IteratorAdaptor& x) const
1198         { return *boost::prior(x.base()); }
1199
1200     template <class BidirectionalIterator>
1201     void increment(BidirectionalIterator& x) const
1202         { --x.base(); }
1203
1204     template <class BidirectionalIterator>
1205     void decrement(BidirectionalIterator& x) const
1206         { ++x.base(); }
1207
1208     template <class BidirectionalIterator, class DifferenceType>
1209     void advance(BidirectionalIterator& x, DifferenceType n) const
1210         { x.base() -= n; }
1211
1212     template <class Iterator1, class Iterator2>
1213     typename Iterator1::difference_type distance(
1214         const Iterator1& x, const Iterator2& y) const
1215         { return x.base() - y.base(); }
1216
1217     template <class Iterator1, class Iterator2>
1218     bool equal(const Iterator1& x, const Iterator2& y) const
1219         { return x.base() == y.base(); }
1220 };
1221
1222 template <class BidirectionalIterator,
1223     class Value = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<BidirectionalIterator>::value_type,
1224     class Reference = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_defaults<BidirectionalIterator,Value>::reference,
1225     class Pointer = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_defaults<BidirectionalIterator,Value>::pointer,
1226     class Category = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<BidirectionalIterator>::iterator_category,
1227     class Distance = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<BidirectionalIterator>::difference_type
1228          >
1229 struct reverse_iterator_generator
1230 {
1231     typedef iterator_adaptor<BidirectionalIterator,reverse_iterator_policies,
1232         Value,Reference,Pointer,Category,Distance> type;
1233 };
1234
1235 template <class BidirectionalIterator>
1236 inline typename reverse_iterator_generator<BidirectionalIterator>::type
1237 make_reverse_iterator(BidirectionalIterator base)
1238 {
1239     typedef typename reverse_iterator_generator<BidirectionalIterator>::type result_t;
1240     return result_t(base);
1241 }
1242
1243 //=============================================================================
1244 // Projection Iterators Adaptor
1245
1246 template <class AdaptableUnaryFunction>
1247 struct projection_iterator_policies : public default_iterator_policies
1248 {
1249     projection_iterator_policies() { }
1250     projection_iterator_policies(const AdaptableUnaryFunction& f) : m_f(f) { }
1251
1252     template <class IteratorAdaptor>
1253     typename IteratorAdaptor::reference dereference(IteratorAdaptor const& iter) const {
1254         return m_f(*iter.base());
1255     }
1256
1257     AdaptableUnaryFunction m_f;
1258 };
1259
1260 template <class AdaptableUnaryFunction, class Iterator>
1261 class projection_iterator_generator {
1262     typedef typename AdaptableUnaryFunction::result_type value_type;
1263     typedef projection_iterator_policies<AdaptableUnaryFunction> policies;
1264 public:
1265     typedef iterator_adaptor<Iterator,policies,value_type,value_type&,value_type*> type;
1266 };
1267
1268 template <class AdaptableUnaryFunction, class Iterator>
1269 class const_projection_iterator_generator {
1270     typedef typename AdaptableUnaryFunction::result_type value_type;
1271     typedef projection_iterator_policies<AdaptableUnaryFunction> policies;
1272 public:
1273     typedef iterator_adaptor<Iterator,policies,value_type,const value_type&,const value_type*> type;
1274 };
1275
1276 template <class AdaptableUnaryFunction, class Iterator, class ConstIterator>
1277 struct projection_iterator_pair_generator {
1278     typedef typename projection_iterator_generator<AdaptableUnaryFunction, Iterator>::type iterator;
1279     typedef typename const_projection_iterator_generator<AdaptableUnaryFunction, ConstIterator>::type const_iterator;
1280 };
1281
1282
1283 template <class AdaptableUnaryFunction, class Iterator>
1284 inline typename projection_iterator_generator<AdaptableUnaryFunction, Iterator>::type
1285 make_projection_iterator(
1286     Iterator iter,
1287     const AdaptableUnaryFunction& f = AdaptableUnaryFunction())
1288 {
1289     typedef typename projection_iterator_generator<AdaptableUnaryFunction, Iterator>::type result_t;
1290     return result_t(iter, f);
1291 }
1292
1293 template <class AdaptableUnaryFunction, class Iterator>
1294 inline typename const_projection_iterator_generator<AdaptableUnaryFunction, Iterator>::type
1295 make_const_projection_iterator(
1296     Iterator iter,
1297     const AdaptableUnaryFunction& f = AdaptableUnaryFunction())
1298 {
1299     typedef typename const_projection_iterator_generator<AdaptableUnaryFunction, Iterator>::type result_t;
1300     return result_t(iter, f);
1301 }
1302
1303 //=============================================================================
1304 // Filter Iterator Adaptor
1305
1306 template <class Predicate, class Iterator>
1307 class filter_iterator_policies
1308 {
1309 public:
1310     filter_iterator_policies() { }
1311
1312     filter_iterator_policies(const Predicate& p, const Iterator& end)
1313         : m_predicate(p), m_end(end) { }
1314
1315     void initialize(Iterator& x) {
1316         satisfy_predicate(x);
1317     }
1318
1319     // The Iter template argument is neccessary for compatibility with a MWCW
1320     // bug workaround
1321     template <class IteratorAdaptor>
1322     void increment(IteratorAdaptor& x) {
1323         ++x.base();
1324         satisfy_predicate(x.base());
1325     }
1326
1327     template <class IteratorAdaptor>
1328     typename IteratorAdaptor::reference dereference(const IteratorAdaptor& x) const
1329         { return *x.base(); }
1330
1331     template <class IteratorAdaptor1, class IteratorAdaptor2>
1332     bool equal(const IteratorAdaptor1& x, const IteratorAdaptor2& y) const
1333         { return x.base() == y.base(); }
1334
1335  private:
1336     void satisfy_predicate(Iterator& iter);
1337     Predicate m_predicate;
1338     Iterator m_end;
1339 };
1340
1341 template <class Predicate, class Iterator>
1342 void filter_iterator_policies<Predicate,Iterator>::satisfy_predicate(
1343     Iterator& iter)
1344 {
1345     while (m_end != iter && !m_predicate(*iter))
1346         ++iter;
1347 }
1348
1349
1350
1351 namespace detail {
1352   // A type generator returning Base if T is derived from Base, and T otherwise.
1353   template <class Base, class T>
1354   struct reduce_to_base_class
1355   {
1356       typedef typename if_true<(
1357             ::boost::is_convertible<T*,Base*>::value
1358           )>::template then<Base,T>::type type;
1359   };
1360
1361   // "Steps down" the category of iterators below bidirectional so the category
1362   // can be used with filter iterators.
1363   template <class Iterator>
1364   struct non_bidirectional_category
1365   {
1366 # if !BOOST_WORKAROUND(__MWERKS__, <= 0x2407)
1367       typedef typename reduce_to_base_class<
1368               std::forward_iterator_tag,
1369                    typename iterator_traits<Iterator>::iterator_category
1370       >::type type;
1371    private:
1372       // For some reason, putting this assertion in filter_iterator_generator fails inexplicably under MSVC
1373       BOOST_STATIC_CONSTANT(
1374           bool, is_bidirectional
1375           = (!boost::is_convertible<type*, std::bidirectional_iterator_tag*>::value));
1376       BOOST_STATIC_ASSERT(is_bidirectional);
1377 # else
1378       // is_convertible doesn't work with MWERKS
1379       typedef typename iterator_traits<Iterator>::iterator_category input_category;
1380   public:
1381       typedef typename if_true<(
1382           boost::is_same<input_category,std::random_access_iterator_tag>::value
1383           || boost::is_same<input_category,std::bidirectional_iterator_tag>::value
1384         )>::template then<
1385           std::forward_iterator_tag,
1386           input_category
1387       >::type type;
1388 # endif
1389   };
1390 }
1391
1392 template <class Predicate, class Iterator,
1393     class Value = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<Iterator>::value_type,
1394     class Reference = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_defaults<Iterator,Value>::reference,
1395     class Pointer = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_defaults<Iterator,Value>::pointer,
1396     class Category = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::non_bidirectional_category<Iterator>::type,
1397     class Distance = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<Iterator>::difference_type
1398          >
1399 class filter_iterator_generator {
1400     BOOST_STATIC_CONSTANT(bool, is_bidirectional
1401         = (boost::is_convertible<Category*, std::bidirectional_iterator_tag*>::value));
1402 #if !BOOST_WORKAROUND(BOOST_MSVC, <= 1300) // I don't have any idea why this occurs, but it doesn't seem to hurt too badly.
1403     BOOST_STATIC_ASSERT(!is_bidirectional);
1404 #endif
1405     typedef filter_iterator_policies<Predicate,Iterator> policies_type;
1406  public:
1407     typedef iterator_adaptor<Iterator,policies_type,
1408         Value,Reference,Pointer,Category,Distance> type;
1409 };
1410
1411 // This keeps MSVC happy; it doesn't like to deduce default template arguments
1412 // for template function return types
1413 namespace detail {
1414   template <class Predicate, class Iterator>
1415   struct filter_generator {
1416     typedef typename boost::filter_iterator_generator<Predicate,Iterator>::type type;
1417   };
1418 }
1419
1420 template <class Predicate, class Iterator>
1421 inline typename detail::filter_generator<Predicate, Iterator>::type
1422 make_filter_iterator(Iterator first, Iterator last, const Predicate& p = Predicate())
1423 {
1424   typedef filter_iterator_generator<Predicate, Iterator> Gen;
1425   typedef filter_iterator_policies<Predicate,Iterator> policies_t;
1426   typedef typename Gen::type result_t;
1427   return result_t(first, policies_t(p, last));
1428 }
1429
1430 } // namespace boost
1431 # undef BOOST_ARG_DEPENDENT_TYPENAME
1432
1433
1434 #endif
1435
1436
1437