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