Squashed 'third_party/boostorg/concept_check/' content from commit ed0a0eb
Change-Id: Ib7230965334f9501601efc300242efde8352a380
git-subtree-dir: third_party/boostorg/concept_check
git-subtree-split: ed0a0ebd72f778cfa4931e0538ea34c28db3a42b
diff --git a/.gitattributes b/.gitattributes
new file mode 100644
index 0000000..3e84d7c
--- /dev/null
+++ b/.gitattributes
@@ -0,0 +1,96 @@
+* text=auto !eol svneol=native#text/plain
+*.gitattributes text svneol=native#text/plain
+
+# Scriptish formats
+*.bat text svneol=native#text/plain
+*.bsh text svneol=native#text/x-beanshell
+*.cgi text svneol=native#text/plain
+*.cmd text svneol=native#text/plain
+*.js text svneol=native#text/javascript
+*.php text svneol=native#text/x-php
+*.pl text svneol=native#text/x-perl
+*.pm text svneol=native#text/x-perl
+*.py text svneol=native#text/x-python
+*.sh eol=lf svneol=LF#text/x-sh
+configure eol=lf svneol=LF#text/x-sh
+
+# Image formats
+*.bmp binary svneol=unset#image/bmp
+*.gif binary svneol=unset#image/gif
+*.ico binary svneol=unset#image/ico
+*.jpeg binary svneol=unset#image/jpeg
+*.jpg binary svneol=unset#image/jpeg
+*.png binary svneol=unset#image/png
+*.tif binary svneol=unset#image/tiff
+*.tiff binary svneol=unset#image/tiff
+*.svg text svneol=native#image/svg%2Bxml
+
+# Data formats
+*.pdf binary svneol=unset#application/pdf
+*.avi binary svneol=unset#video/avi
+*.doc binary svneol=unset#application/msword
+*.dsp text svneol=crlf#text/plain
+*.dsw text svneol=crlf#text/plain
+*.eps binary svneol=unset#application/postscript
+*.gz binary svneol=unset#application/gzip
+*.mov binary svneol=unset#video/quicktime
+*.mp3 binary svneol=unset#audio/mpeg
+*.ppt binary svneol=unset#application/vnd.ms-powerpoint
+*.ps binary svneol=unset#application/postscript
+*.psd binary svneol=unset#application/photoshop
+*.rdf binary svneol=unset#text/rdf
+*.rss text svneol=unset#text/xml
+*.rtf binary svneol=unset#text/rtf
+*.sln text svneol=native#text/plain
+*.swf binary svneol=unset#application/x-shockwave-flash
+*.tgz binary svneol=unset#application/gzip
+*.vcproj text svneol=native#text/xml
+*.vcxproj text svneol=native#text/xml
+*.vsprops text svneol=native#text/xml
+*.wav binary svneol=unset#audio/wav
+*.xls binary svneol=unset#application/vnd.ms-excel
+*.zip binary svneol=unset#application/zip
+
+# Text formats
+.htaccess text svneol=native#text/plain
+*.bbk text svneol=native#text/xml
+*.cmake text svneol=native#text/plain
+*.css text svneol=native#text/css
+*.dtd text svneol=native#text/xml
+*.htm text svneol=native#text/html
+*.html text svneol=native#text/html
+*.ini text svneol=native#text/plain
+*.log text svneol=native#text/plain
+*.mak text svneol=native#text/plain
+*.qbk text svneol=native#text/plain
+*.rst text svneol=native#text/plain
+*.sql text svneol=native#text/x-sql
+*.txt text svneol=native#text/plain
+*.xhtml text svneol=native#text/xhtml%2Bxml
+*.xml text svneol=native#text/xml
+*.xsd text svneol=native#text/xml
+*.xsl text svneol=native#text/xml
+*.xslt text svneol=native#text/xml
+*.xul text svneol=native#text/xul
+*.yml text svneol=native#text/plain
+boost-no-inspect text svneol=native#text/plain
+CHANGES text svneol=native#text/plain
+COPYING text svneol=native#text/plain
+INSTALL text svneol=native#text/plain
+Jamfile text svneol=native#text/plain
+Jamroot text svneol=native#text/plain
+Jamfile.v2 text svneol=native#text/plain
+Jamrules text svneol=native#text/plain
+Makefile* text svneol=native#text/plain
+README text svneol=native#text/plain
+TODO text svneol=native#text/plain
+
+# Code formats
+*.c text svneol=native#text/plain
+*.cpp text svneol=native#text/plain
+*.h text svneol=native#text/plain
+*.hpp text svneol=native#text/plain
+*.ipp text svneol=native#text/plain
+*.tpp text svneol=native#text/plain
+*.jam text svneol=native#text/plain
+*.java text svneol=native#text/plain
diff --git a/Jamfile b/Jamfile
new file mode 100644
index 0000000..cf5eb61
--- /dev/null
+++ b/Jamfile
@@ -0,0 +1,3 @@
+# Empty Jamfile because the super project still expects one to appear here.
+# Can be deleted once 'status/Jamfile.v2' has been updated in the super
+# project.
diff --git a/bad_error_eg.cpp b/bad_error_eg.cpp
new file mode 100644
index 0000000..5f8d892
--- /dev/null
+++ b/bad_error_eg.cpp
@@ -0,0 +1,14 @@
+#include <vector>
+#include <complex>
+#include "algorithm"
+
+int main()
+{
+ std::vector<std::complex<float> > v;
+ std_::stable_sort(v.begin(), v.end());
+}
+
+// (C) Copyright Jeremy Siek 2000.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
diff --git a/bibliography.htm b/bibliography.htm
new file mode 100644
index 0000000..4fcc8fe
--- /dev/null
+++ b/bibliography.htm
@@ -0,0 +1,65 @@
+<HTML>
+<!-- Copyright (c) Jeremy Siek 2000 -->
+<!-- Distributed under the Boost -->
+<!-- Software License, Version 1.0. (See accompanying -->
+<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
+<Head>
+<Title>Boost Concept Checking Library: Bibliography</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+ ALINK="#ff0000">
+<IMG SRC="../../boost.png"
+ ALT="C++ Boost" width="277" height="86">
+
+<BR Clear>
+
+
+<H2>Bibliography</H2>
+
+<DL COMMapCT>
+
+<DD><P></P><DT><a name="alexandrescu99:_better_templ_error_messag">1</a>
+<DD>Andrei Alexandrescu<BR>
+<EM>Better Template Error Messages</EM>.<BR>
+C/C++ Users Journal, March, 1999.
+
+
+<DD><P></P><DT><a name="stroustrup94:_design_evolution">2</a>
+<DD>Bjarne Stroustrup<BR>
+<EM>Design and Evolution of C++</EM>.<BR>
+Addison-Wesley, 1994
+
+<P></P><DT><A NAME="austern99:_gener_progr_stl">3</A>
+<DD>
+M. H. Austern.
+<BR><EM>Generic Programming and the STL</EM>.
+<BR>Professional computing series. Addison-Wesley, 1999.
+
+<P></P><DT><A NAME="IB-H965502">4</A>
+<DD>
+David R. Musser and Atul Saini
+<BR><EM>STL Tutorial and Reference Guide</EM>.
+<BR>Professional computing series. Addison-Wesley, 1996.
+
+<P></P><DT><A NAME="stepa.lee-1994:the.s:TR">5</A>
+<DD>
+A. A. Stepanov and M. Lee
+<BR><EM>The Standard Template Library</EM>.
+<BR>ISO Programming Language C++ Project, May 1994.
+<BR>X3J16/94-0095, WG21/N0482
+
+
+
+</DL>
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright © 2000</TD><TD>
+<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>(<A
+HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
+Andrew Lumsdaine</A>(<A HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
+</TD></TR></TABLE>
+
+</BODY>
+</HTML>
diff --git a/concept_check.htm b/concept_check.htm
new file mode 100644
index 0000000..4a47fa8
--- /dev/null
+++ b/concept_check.htm
@@ -0,0 +1,330 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
+ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
+
+<html xmlns="http://www.w3.org/1999/xhtml">
+<!-- Copyright (c) 2000 Jeremy Siek and Andrew Lumsdaine, 2007 David Abrahams -->
+<!-- Distributed under the Boost -->
+<!-- Software License, Version 1.0. (See accompanying -->
+<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
+
+<head>
+ <meta name="generator" content=
+ "HTML Tidy for Linux/x86 (vers 1 September 2005), see www.w3.org" />
+ <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
+
+ <title>Concept Check Library</title>
+ <link rel="stylesheet" href="../../rst.css" type="text/css" />
+</head>
+
+<body bgcolor="#FFFFFF" link="#0000EE" text="#000000" vlink="#551A8B" alink=
+"#FF0000">
+ <img src="../../boost.png" alt="C++ Boost" width="277" height=
+ "86" /><br clear="none" />
+
+ <h1>The Boost Concept Check Library (BCCL)</h1>
+
+ <blockquote>
+ The Concept Check library allows one to add explicit statement and
+ checking of <a href=
+ "http://www.boost.org/more/generic_programming.html#concept">concepts</a> in the style
+ of the <a href=
+ "http://www.generic-programming.org/languages/conceptcpp/specification/">proposed
+ C++ language extension</a>.
+ </blockquote>
+
+ <h2><a name="sec:concept-checking" id="sec:concept-checking"></a>Synopsis</a></h2>
+
+ <p>Generic programming in C++ is characterized by the use of template
+ parameters to represent abstract data types (or “<a href=
+ "http://www.boost.org/more/generic_programming.html#concept">concepts</a>”). However, the
+ C++ language itself does not provide a mechanism for the writer of a class
+ or function template to explicitly state the concept that the user-supplied
+ template argument should model (or conform to). Template parameters are
+ commonly named after the concept they're required to model as a hint to the
+ user, and to make the concept requirements explicit in code. However, the
+ compiler doesn't treat these special names specially: a parameter named
+ <code>RandomAccessIterator</code> is no different to the compiler than one
+ named <code>T</code>. Furthermore,</p>
+
+ <ul>
+ <li>Compiler error messages resulting from incorrect template arguments
+ can be particularly difficult to decipher. Often times the error does not
+ point to the location of the template call-site, but instead exposes the
+ internals of the template, which the user should never have to see.</li>
+
+ <li>Without checking from the compiler, the documented requirements are
+ oftentimes vague, incorrect, or nonexistent, so a user cannot know
+ exactly what kind of arguments are expected.</li>
+
+ <li>The documented concept requirements may not fully <i>cover</i> the
+ needs of the actual template, meaning the user could get a compiler error
+ even though the supplied template arguments meet the documented
+ requirements.</li>
+
+ <li>The documented concept requirements may be too stringent, requiring
+ more than is really needed by the template.</li>
+
+ <li>Concept names in code may drift out-of-sync with the documented
+ requirements.</li>
+ </ul><p>The Boost Concept Checking Library provides:
+
+ <ul>
+ <li>A mechanism for inserting compile-time checks on template parameters
+ at their point of use.</li>
+
+ <li>A framework for specifying concept requirements through concept
+ checking classes.</li>
+
+ <li>A mechanism for verifying that concept requirements cover the
+ template.</li>
+
+ <li>A suite of concept checking classes and archetype classes that match
+ the concept requirements in the C++ Standard Library.</li>
+
+ <li>An alternative to the use of traits classes for accessing associated
+ types that mirrors the syntax proposed for the next C++ standard.</li>
+ </ul><p>The mechanisms use standard C++ and introduce no run-time overhead.
+ The main cost of using the mechanism is in compile-time.</p>
+
+ <p><strong>Every programmer writing class or function templates ought to
+ make concept checking a normal part of their code writing routine.</strong>
+ A concept check should be inserted for each template parameter in a
+ component's public interface. If the concept is one of the ones from the
+ Standard Library, then simply use the matching concept checking class in
+ the BCCL. If not, then write a new concept checking class - after all, they
+ are typically only a few lines long. For new concepts, a matching archetype
+ class should also be created, which is a minimal skeleton-implementation of
+ the concept</p>
+
+ <p>The documentation is organized into the following sections.</p>
+
+ <ol>
+ <li><a href="#introduction">Introduction</a></li>
+
+ <li><a href="#motivating-example">Motivating Example</a></li>
+
+ <li><a href="#history">History</a></li>
+
+ <li><a href="#publications">Publications</a></li>
+
+ <li><a href="#acknowledgements">Acknowledgements</a></li>
+
+ <li><a href="./using_concept_check.htm">Using Concept Checks</a></li>
+
+ <li><a href="creating_concepts.htm">Creating Concept Checking
+ Classes</a></li>
+
+ <li><a href="./concept_covering.htm">Concept Covering and
+ Archetypes</a></li>
+
+ <li><a href="./prog_with_concepts.htm">Programming With Concepts</a></li>
+
+ <li><a href="./implementation.htm">Implementation</a></li>
+
+ <li><a href="./reference.htm">Reference</a></li>
+ </ol>
+
+ <p><a href="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</a> contributed this
+ library. <a href="http://www.boost.org/people/beman_dawes.html">Beman Dawes</a> managed
+ the formal review. <a href="http://www.boost.org/people/dave_abrahams.htm">Dave
+ Abrahams</a> contributed a rewrite that updated syntax to be more
+ compatible with proposed syntax for concept support the C++ core
+ language.</p>
+
+ <h2><a name="introduction" id="introduction">Introduction</a></h2><p>A
+ <i>concept</i> is a set of requirements (valid expressions, associated
+ types, semantic invariants, complexity guarantees, etc.) that a type must
+ fulfill to be correctly used as arguments in a call to a generic algorithm.
+ In C++, concepts are represented by formal template parameters to function
+ templates (generic algorithms). However, C++ has no explicit mechanism for
+ representing concepts—template parameters are merely placeholders. By
+ convention, these parameters are given names corresponding to the concept
+ that is required, but a C++ compiler does not enforce compliance to the
+ concept when the template parameter is bound to an actual type.
+
+ <p>Naturally, if a generic algorithm is invoked with a type that does not
+ fulfill at least the syntactic requirements of the concept, a compile-time
+ error will occur. However, this error will not <i>per se</i> reflect the
+ fact that the type did not meet all of the requirements of the concept.
+ Rather, the error may occur deep inside the instantiation hierarchy at the
+ point where an expression is not valid for the type, or where a presumed
+ associated type is not available. The resulting error messages are largely
+ uninformative and basically impenetrable.</p>
+
+ <p>What is required is a mechanism for enforcing
+ “concept safety” at (or close to) the point
+ of instantiation. The Boost Concept Checking Library uses some standard C++
+ constructs to enforce early concept compliance and that provides more
+ informative error messages upon non-compliance.</p>
+
+ <p>Note that this technique only addresses the syntactic requirements of
+ concepts (the valid expressions and associated types). We do not address
+ the semantic invariants or complexity guarantees, which are also part of
+ concept requirements..</p>
+
+ <h2><a name="motivating-example" id="motivating-example">Motivating
+ Example</a></h2>
+
+ <p>We present a simple example to illustrate incorrect usage of a template
+ library and the resulting error messages. In the code below, the generic
+ <tt>std::stable_sort()</tt> algorithm from the Standard Template Library
+ (STL)[<a href="bibliography.htm#austern99:_gener_progr_stl">3</a>, <a href=
+ "bibliography.htm#IB-H965502">4</a>,<a href=
+ "bibliography.htm#stepa.lee-1994:the.s:TR">5</a>] is applied to a linked
+ list.</p>
+ <pre>
+ <a href="./bad_error_eg.cpp">bad_error_eg.cpp</a>:
+<font color="gray">1</font> #include <vector>
+<font color="gray">2</font color="gray"> #include <complex>
+<font color="gray">3</font color="gray"> #include <algorithm>
+<font color="gray">4</font color="gray">
+<font color="gray">5</font color="gray"> int main()
+<font color="gray">6</font color="gray"> {
+<font color="gray">7</font color="gray"> std::vector<std::complex<float> > v;
+<font color="gray">8</font color="gray"> std::stable_sort(v.begin(), v.end());
+<font color="gray">9</font color="gray"> }
+</pre>
+
+ <p>Here, the <tt>std::stable_sort()</tt> algorithm is prototyped as
+ follows:</p>
+ <pre>
+ template <class RandomAccessIterator>
+ void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
+</pre>
+
+ <p>Attempting to compile this code with Gnu C++ produces the following
+ compiler error:</p>
+ <pre>
+/usr/include/c++/4.1.2/bits/stl_algo.h: In function ‘void std::
+ __insertion_sort(_RandomAccessIterator, _RandomAccessIterator) [with
+ _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float
+ >*, std::vector<std::complex<float>, std::allocator<std::complex<
+ float> > > >]’:
+/usr/include/c++/4.1.2/bits/stl_algo.h:3066: instantiated from ‘void
+ std::__inplace_stable_sort(_RandomAccessIterator,
+ _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::
+ __normal_iterator<std::complex<float>*, std::vector<std::complex<
+ float>, std::allocator<std::complex<float> > > >]’
+/usr/include/c++/4.1.2/bits/stl_algo.h:3776: instantiated from ‘void
+ std::stable_sort(_RandomAccessIterator, _RandomAccessIterator) [with
+ _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::complex<float
+ >*, std::vector<std::complex<float>, std::allocator<std::complex<
+ float> > > >]’
+bad_error_eg.cpp:8: instantiated from here
+/usr/include/c++/4.1.2/bits/stl_algo.h:2277: error: no match for
+ ‘operator<’ in ‘__val < __first. __gnu_cxx::__normal_iterator<
+ _Iterator, _Container>::operator* [with _Iterator = std::complex<float
+ >*, _Container = std::vector<std::complex<float>, std::allocator<
+ std::complex<float> > >]()’
+</pre>
+
+ <p>In this case, the fundamental error is
+ that <tt>std:complex<float></tt> does not model the <a href=
+ "http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>
+ concept. Unfortunately, there is nothing in the error message to
+ indicate that to the user.</p>
+
+ <p>The error may be obvious to a C++ programmer having enough
+ experience with template libraries, but there are several reasons
+ why this message could be hard for the uninitiated to
+ understand:</p>
+
+ <ol>
+ <li>There is no textual correlation between the error message and the
+ documented requirements for <tt>std::stable_sort()</tt> and for <a href=
+ "http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>.</li>
+
+ <li>The error message is overly long, listing functions internal
+ to the STL (e.g. <code>__insertion_sort</code>) that the user
+ does not (and should not!) know or care about.</li>
+
+ <li>With so many internal library functions listed in the error message,
+ the programmer could easily infer that the problem is in the library,
+ rather than in his or her own code.</li>
+ </ol>
+
+ <p>The following is an example of what we might expect from a more
+ informative message (and is in fact what the Boost Concept Checking Library
+ produces):</p>
+ <pre>
+boost/concept_check.hpp: In destructor ‘boost::LessThanComparable<TT>::~
+ LessThanComparable() [with TT = std::complex<float>]’:
+boost/concept/detail/general.hpp:29: instantiated from ‘static void boost::
+ concepts::requirement<Model>::failed() [with Model = boost::
+ LessThanComparable<std::complex<float> >]’
+boost/concept/requires.hpp:30: instantiated from ‘boost::_requires_<void
+ (*)(boost::LessThanComparable<std::complex<float> >)>’
+bad_error_eg.cpp:8: instantiated from here
+boost/concept_check.hpp:236: error: no match for ‘operator<’ in ‘((boost::
+ LessThanComparable<std::complex<float> >*)this)->boost::
+ LessThanComparable<std::complex<float> >::a < ((boost::
+ LessThanComparable<std::complex<float> >*)this)->boost::
+ LessThanComparable<std::complex<float> >::b’
+</pre>
+
+ <p>This message rectifies several of the shortcomings of the standard error
+ messages.</p>
+
+ <ul>
+ <li>The message refers explicitly to concepts that the user can look up
+ in the STL documentation (<a href=
+ "http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>).</li>
+
+ <li>The error message is now much shorter and does not reveal
+ internal STL functions, nor indeed does it even point
+ to <code>std::stable_sort</code>.</li>
+
+ <li>The presence of <tt>concept_check.hpp</tt> in the error message
+ alerts the user to the fact that the error lies in the user code and not
+ in the library implementation.</li>
+ </ul>
+
+ <h2><a name="history" id="history">History</a></h2>
+
+ <p>The first version of this concept checking system was developed
+ by Jeremy Siek while working at SGI in their C++ compiler and
+ library group. That version is now part of the SGI STL
+ distribution. The system originally introduced as the boost concept
+ checking library differs from concept checking in the SGI STL in
+ that the definition of concept checking classes was greatly
+ simplified, at the price of less helpful verbiage in the error
+ messages. In 2006 the system was rewritten (preserving backward
+ compatibility) by Dave Abrahams to be easier to use, more similar to
+ the proposed concept support the C++ core language, and to give
+ better error messages.
+</p>
+
+ <h2><a name="publications" id="publications">Publications</a></h2>
+
+ <ul>
+ <li><a href="http://www.oonumerics.org/tmpw00/">C++ Template Workshop
+ 2000</a>, Concept Checking</li>
+ </ul>
+
+ <h2><a name="acknowledgements" id=
+ "acknowledgements">Acknowledgements</a></h2><p>The idea to use function
+ pointers to cause instantiation is due to Alexander Stepanov. We are not sure
+ of the origin of the idea to use expressions to do up-front checking of
+ templates, but it did appear in D&E[ <a href=
+ "bibliography.htm#stroustrup94:_design_evolution">2</a>]. Thanks to Matt
+ Austern for his excellent documentation and organization of the STL
+ concepts, upon which these concept checks are based. Thanks to Boost
+ members for helpful comments and reviews.
+
+ <p><a href="./using_concept_check.htm">Next: Using Concept
+ Checks</a><br /></p>
+ <hr />
+
+ <table>
+ <tr valign="top">
+ <td nowrap="nowrap">Copyright © 2000</td>
+
+ <td><a href="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</a>(<a href=
+ "mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</a>) Andrew
+ Lumsdaine(<a href="mailto:lums@osl.iu.edu">lums@osl.iu.edu</a>),
+ 2007 <a href="mailto:dave@boost-consulting.com">David Abrahams</a>.
+</td>
+ </tr>
+ </table>
+</body>
+</html>
diff --git a/concept_covering.htm b/concept_covering.htm
new file mode 100644
index 0000000..d3997e1
--- /dev/null
+++ b/concept_covering.htm
@@ -0,0 +1,125 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
+ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
+
+<html xmlns="http://www.w3.org/1999/xhtml">
+<!-- Copyright (c) Jeremy Siek and Andrew Lumsdaine 2000 -->
+<!-- Distributed under the Boost -->
+<!-- Software License, Version 1.0. (See accompanying -->
+<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
+
+<head>
+ <meta name="generator" content=
+ "HTML Tidy for Linux/x86 (vers 1 September 2005), see www.w3.org" />
+
+ <title>Concept Covering and Archetypes</title>
+ <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
+ <link rel="stylesheet" href="../../rst.css" type="text/css" />
+</head>
+
+<body bgcolor="#FFFFFF" link="#0000EE" text="#000000" vlink="#551A8B" alink=
+"#FF0000">
+ <img src="../../boost.png" alt="C++ Boost" width="277" height=
+ "86" /><br clear="none" />
+
+ <h2><a name="concept-covering" id="concept-covering">Concept Covering and
+ Archetypes</a></h2>
+
+ <p>We have discussed how it is important to select the minimal requirements
+ (concepts) for the inputs to a component, but it is equally important to
+ verify that the chosen concepts <i>cover</i> the algorithm. That is, any
+ possible user error should be caught by the concept checks and not let slip
+ through. Concept coverage can be verified through the use of <i>archetype
+ classes</i>. An archetype class is an exact implementation of the interface
+ associated with a particular concept. The run-time behavior of the
+ archetype class is not important, the functions can be left empty. A simple
+ test program can then be compiled with the archetype classes as the inputs
+ to the component. If the program compiles then one can be sure that the
+ concepts cover the component. The following code shows the archetype class
+ for the <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input
+ Iterator</a> concept. Some care must be taken to ensure that the archetype
+ is an exact match to the concept. For example, the concept states that the
+ return type of <tt>operator*()</tt> must be convertible to the value type.
+ It does not state the more stringent requirement that the return type be
+ <tt>T&</tt> or <tt>const T&</tt>. That means it would be a mistake
+ to use <tt>T&</tt> or <tt>const T&</tt> for the return type of the
+ archetype class. The correct approach is to create an artificial return
+ type that is convertible to <tt>T</tt>, as we have done here with
+ <tt>reference</tt>. The validity of the archetype class test is completely
+ dependent on it being an exact match with the concept, which must be
+ verified by careful (manual) inspection.</p>
+ <pre>
+template <class T>
+class input_iterator_archetype
+{
+private:
+ typedef input_iterator_archetype self;
+public:
+ typedef std::input_iterator_tag iterator_category;
+ typedef T value_type;
+ struct reference {
+ operator const value_type&() const { return static_object<T>::get(); }
+ };
+ typedef const T* pointer;
+ typedef std::ptrdiff_t difference_type;
+ self& operator=(const self&) { return *this; }
+ bool operator==(const self&) const { return true; }
+ bool operator!=(const self&) const { return true; }
+ reference operator*() const { return reference(); }
+ self& operator++() { return *this; }
+ self operator++(int) { return *this; }
+};
+</pre>
+
+ <p>Generic algorithms are often tested by being instantiated with a number
+ of common input types. For example, one might apply
+ <tt>std::stable_sort()</tt> with basic pointer types as the iterators.
+ Though appropriate for testing the run-time behavior of the algorithm, this
+ is not helpful for ensuring concept coverage because C++ types never match
+ particular concepts exactly. Instead, they often provide more than the
+ minimal functionality required by any one concept. Even though the function
+ template has concept checks, and compiles with a given type, the checks may
+ still fall short of covering all the functionality that is actually used.
+ This is why it is important to compile with archetype classes in addition
+ to testing with common input types.</p>
+
+ <p>The following is an excerpt from <a href=
+ "./stl_concept_covering.cpp"><tt>stl_concept_covering.cpp</tt></a> that
+ shows how archetypes can be used to check the requirement documentation for
+ <a href=
+ "http://www.sgi.com/tech/stl/stable_sort.html"><tt>std::stable_sort()</tt></a>.
+ In this case, it looks like the <a href=
+ "../utility/CopyConstructible.html">CopyConstructible</a> and <a href=
+ "../utility/Assignable.html">Assignable</a> requirements were forgotten in
+ the SGI STL documentation (try removing those archetypes). The Boost
+ archetype classes have been designed so that they can be layered. In this
+ example the value type of the iterator is composed out of three archetypes.
+ In the <a href="reference.htm#basic-archetype">archetype class
+ reference</a>, template parameters named <tt>Base</tt> indicate where the
+ layered archetype paradigm can be used.</p>
+ <pre>
+{
+ typedef less_than_comparable_archetype<
+ sgi_assignable_archetype<> > ValueType;
+ random_access_iterator_archetype<ValueType> ri;
+ std::stable_sort(ri, ri);
+}
+</pre>
+
+ <p><a href="./prog_with_concepts.htm">Next: Programming with
+ Concepts</a><br />
+ <a href="./creating_concepts.htm">Prev: Creating Concept Checking
+ Classes</a><br />
+ <hr />
+
+ <table>
+ <tr valign="top">
+ <td nowrap="nowrap">Copyright © 2000</td>
+
+ <td><a href="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</a>(<a href=
+ "mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</a>) Andrew
+ Lumsdaine(<a href="mailto:lums@osl.iu.edu">lums@osl.iu.edu</a>),
+ 2007 <a href="mailto:dave@boost-consulting.com">David Abrahams</a>.
+ </tr>
+ </table>
+</body>
+</html>
diff --git a/creating_concepts.htm b/creating_concepts.htm
new file mode 100644
index 0000000..d579aaf
--- /dev/null
+++ b/creating_concepts.htm
@@ -0,0 +1,157 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
+ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
+
+<html xmlns="http://www.w3.org/1999/xhtml">
+<!-- Copyright (c) Jeremy Siek and Andrew Lumsdaine 2000 -->
+<!-- Distributed under the Boost -->
+<!-- Software License, Version 1.0. (See accompanying -->
+<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
+
+<head>
+ <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
+ <meta name="generator" content=
+ "HTML Tidy for Linux/x86 (vers 1 September 2005), see www.w3.org" />
+
+ <title>Creating Concept Checking Classes</title>
+ <link rel="stylesheet" href="../../rst.css" type="text/css" />
+</head>
+
+<body bgcolor="#FFFFFF" link="#0000EE" text="#000000" vlink="#551A8B" alink=
+"#FF0000">
+ <img src="../../boost.png" alt="C++ Boost" width="277" height=
+ "86" /><br clear="none" />
+
+ <h2><a name="creating-concept-checks" id="creating-concept-checks">Creating
+ Concept Checking Classes</a></h2>
+
+ <p>As an example of how to create a concept checking class template, we
+ look at how to create the corresponding checks for the <a href=
+ "http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a> concept.
+ The complete definition is here:</p>
+ <pre>
+template <class X>
+struct InputIterator
+ : Assignable<X>, EqualityComparable<X>
+{
+ private:
+ typedef std::iterator_traits<X> t;
+ public:
+ typedef typename t::value_type value_type;
+ typedef typename t::difference_type difference_type;
+ typedef typename t::reference reference;
+ typedef typename t::pointer pointer;
+ typedef typename t::iterator_category iterator_category;
+
+ BOOST_CONCEPT_ASSERT((SignedInteger<difference_type>));
+ BOOST_CONCEPT_ASSERT((Convertible<iterator_category, std::input_iterator_tag>));
+
+ BOOST_CONCEPT_USAGE(InputIterator)
+ {
+ X j(i); <font color=
+"green">// require copy construction</font>
+ same_type(*i++,v); <font color=
+"green">// require postincrement-dereference returning value_type</font>
+ X& x = ++j; <font color=
+"green">// require preincrement returning X&</font>
+ }
+
+ private:
+ X i;
+ value_type v;
+
+ <font color=
+"green">// Type deduction will fail unless the arguments have the same type.</font>
+ template <typename T>
+ void same_type(T const&, T const&);
+};
+</pre>
+
+ <h3>Walkthrough</h3>
+
+ <p>First, as a convention we name the concept checking class after the
+ concept. Next, since InputIterator is a refinement of Assignable and
+ EqualityComparable, we derive its concept checking class from the checking
+ classes for those other concepts. The library will automatically check for
+ conformance to Assignable and EqualityComparable whenever it checks the
+ InputIterator concept.</p>
+
+ <p>Next, we declare the concept's <a href=
+ "http://www.boost.org/more/generic_programming.html#associated_type">associated types</a>
+ as member typedefs. The associated difference type is required to be a
+ signed integer, and the iterator category has to be convertible to
+ std::input_iterator_tag, so we assert those relationships. The syntax for
+ accessing associated types through the concept-checking template mirrors
+ the <a href=
+ "http://www.generic-programming.org/languages/conceptcpp/">proposed</a>
+ syntax for associated type access in C++0x Finally, we use the
+ <code>BOOST_CONCEPT_USAGE</code> macro to declare the function that
+ exercises all the concept's valid expressions. Note that at this point you
+ may sometimes need to be a little creative: for example, to check that
+ <code>*i++</code> returns the iterator's value type, we pass both values to
+ the <code>same_type</code> member function template, which requires both
+ arguments to have the same type, modulo references and cv-qualification.
+ It's an imperfect check, but it's better than nothing.</p>
+
+ <h3>Values for Usage Patterns Should Be Data Members</h3>
+
+ <p>You may be wondering why we declared <code>i</code> and <code>v</code>
+ as data members in the example above. Why didn't we simply write the
+ following?</p>
+ <pre>
+BOOST_CONCEPT_USAGE(InputIterator)
+{
+ X i; <font color=
+"green">// create the values we need</font>
+ value_type v;
+
+ X j(i); <font color=
+"green">// require copy construction</font>
+ same_type(*i++,v); <font color=
+"green">// require postincrement-dereference returning value_type</font>
+ X& x = ++j; <font color=
+"green">// require preincrement returning X&</font>
+}
+</pre>
+
+ <p>Unfortunately, that code wouldn't have worked out so well, because it
+ unintentionally imposes the requirement that <code>X</code> and its value
+ type are both default-constructible. On the other hand, since instances of
+ the <code>InputIterator</code> template will never be constructed, the
+ compiler never has to check how its data members will be constructed (C++
+ Standard Section 14.7.1 9). For that reason you should <strong>always
+ declare values needed for usage patterns as data members</strong>.</p>
+
+ <p>These sorts of errors in concept definitions can be detected by the use
+ of <a href="concept_covering.htm">Concept Archetypes</a>, but it's always
+ better to avoid them pre-emptively.</p>
+
+ <h3>Similarity to Proposed C++0x Language Support for Concepts</h3>
+
+ <p>This library's syntaxes for concept refinement and for access of
+ associated types mirrors the corresponding <a href=
+ "http://www.generic-programming.org/languages/conceptcpp/">proposed</a>
+ syntaxes in C++0x. However, C++0x will use
+ “signatures” rather than usage patterns to
+ describe the valid operations on types participating in a concept, so when
+ converting your concept checking classes into language-supported concepts,
+ you'll need to translate your usage function into a series of
+ signatures.</p>
+
+ <p><a href="./concept_covering.htm">Next: Concept Covering and
+ Archetypes</a><br />
+ <a href="./using_concept_check.htm">Prev: Using Concept
+ Checks</a><br /></p>
+ <hr />
+
+ <table>
+ <tr valign="top">
+ <td nowrap="nowrap">Copyright © 2000</td>
+
+ <td><a href="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</a>(<a href=
+ "mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</a>) Andrew
+ Lumsdaine(<a href="mailto:lums@osl.iu.edu">lums@osl.iu.edu</a>),
+ 2007 <a href="mailto:dave@boost-consulting.com">David Abrahams</a>.
+ </tr>
+ </table>
+</body>
+</html>
diff --git a/doc/Jamfile.v2 b/doc/Jamfile.v2
new file mode 100644
index 0000000..d6646f7
--- /dev/null
+++ b/doc/Jamfile.v2
@@ -0,0 +1,14 @@
+project boost/concepts ;
+import boostbook : boostbook ;
+
+boostbook concepts : reference/concepts.xml
+ :
+ <format>pdf:<xsl:param>boost.url.prefix=http://www.boost.org/doc/libs/release/doc/html
+ <xsl:param>boost.root=../../../..
+ ;
+
+###############################################################################
+alias boostdoc ;
+explicit boostdoc ;
+alias boostrelease : concepts ;
+explicit boostrelease ;
diff --git a/doc/reference/Assignable.xml b/doc/reference/Assignable.xml
new file mode 100644
index 0000000..56f4052
--- /dev/null
+++ b/doc/reference/Assignable.xml
@@ -0,0 +1,59 @@
+<?xml version="1.0"?>
+<concept name="Assignable" category="Utility"><!--
+Based on concepts from the SGI Standard Template Library documentation:
+Copyright (c) 1996-1999
+Silicon Graphics Computer Systems, Inc.
+
+Copyright (c) 1994
+Hewlett-Packard Company
+--><!--
+Copyright 2000-2001 University of Notre Dame du Lac.
+Copyright 2001-2002 Indiana University.
+Some concepts based on versions from the MTL draft manual and Boost Graph
+and Property Map documentation:
+Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
+-->
+ <param name="X" role="assignable-type"/>
+
+ <models-sentence>The type <arg num="1"/> must be a model of <self/>.</models-sentence>
+
+ <description>
+ <para>Assignable types must have copy constructors,
+ <code>operator=</code> for assignment, and the <code>swap()</code>
+ function defined.</para>
+ </description>
+
+ <notation variables="x y">
+ <sample-value>
+ <type name="X"/>
+ </sample-value>
+ </notation>
+
+ <refines const="no" concept="CopyConstructible"/>
+
+ <valid-expression name="Assignment">
+ <assign>
+ <sample-value><reference-to><type name="X"/></reference-to></sample-value>
+ <sample-value><const><reference-to><type name="X"/></reference-to></const></sample-value>
+ </assign>
+ <return-type>
+ <require-same-type testable="yes">
+ <reference-to><type name="X"/></reference-to>
+ </require-same-type>
+ </return-type>
+ <semantics>Require <code>operator=</code></semantics>
+ </valid-expression>
+
+ <valid-expression name="Swap">
+ <apply-function name="swap">
+ <sample-value><reference-to><type name="X"/></reference-to></sample-value>
+ <sample-value><reference-to><type name="X"/></reference-to></sample-value>
+ </apply-function>
+ <return-type><require-same-type><type name="void"/></require-same-type></return-type>
+ <semantics>Require <code>swap()</code> function</semantics>
+ </valid-expression>
+
+ <example-model>
+ <type name="int"/>
+ </example-model>
+</concept>
diff --git a/doc/reference/BidirectionalIterator.xml b/doc/reference/BidirectionalIterator.xml
new file mode 100644
index 0000000..9b6b9f6
--- /dev/null
+++ b/doc/reference/BidirectionalIterator.xml
@@ -0,0 +1,136 @@
+<?xml version="1.0"?>
+<concept name="BidirectionalIterator" category="Iterator"><!--
+Based on concepts from the SGI Standard Template Library documentation:
+Copyright (c) 1996-1999
+Silicon Graphics Computer Systems, Inc.
+
+Copyright (c) 1994
+Hewlett-Packard Company
+--><!--
+Copyright 2000-2001 University of Notre Dame du Lac.
+Copyright 2001-2002 Indiana University.
+Some concepts based on versions from the MTL draft manual and Boost Graph
+and Property Map documentation:
+Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
+-->
+ <param name="Iter" role="iterator-type"/>
+
+ <use-header name="iterator"/>
+
+ <models-sentence>The iterator type <arg num="1"/> must be a model of <self/>.</models-sentence>
+
+ <description>
+ <para>A bidirectional iterator is an iterator that can read through a sequence
+ of values. It can move in either direction through the sequence, and can
+ be either mutable (data pointed to by it can be changed) or not mutable.</para>
+
+ <para>An iterator represents a position in a sequence. Therefore, the
+ iterator can point into the sequence (returning a value when dereferenced
+ and being incrementable), or be off-the-end (and not dereferenceable or
+ incrementable).</para>
+ </description>
+
+ <associated-type name="value_type">
+ <get-member-type name="value_type">
+ <apply-template name="std::iterator_traits">
+ <type name="Iter"/>
+ </apply-template>
+ </get-member-type>
+ <description><simpara>The value type of the iterator</simpara></description>
+ </associated-type>
+
+ <refines const="no" concept="ForwardIterator"/>
+
+ <notation variables="i j">
+ <sample-value>
+ <type name="Iter"/>
+ </sample-value>
+ </notation>
+
+ <associated-type name="category">
+ <get-member-type name="iterator_category">
+ <apply-template name="std::iterator_traits">
+ <type name="Iter"/>
+ </apply-template>
+ </get-member-type>
+ <description><simpara>The category of the iterator</simpara></description>
+ </associated-type>
+
+ <notation variables="x">
+ <sample-value>
+ <type name="value_type"/>
+ </sample-value>
+ </notation>
+
+ <valid-type-expression name="Category tag">
+ <description/>
+ <type name="category"/>
+ <return-type>
+ <derived-from testable="yes">
+ <type name="std::bidirectional_iterator_tag"/>
+ </derived-from>
+ </return-type>
+ </valid-type-expression>
+
+ <valid-expression name="Predecrement">
+ <predecrement>
+ <sample-value><reference-to><type name="Iter"/></reference-to></sample-value>
+ </predecrement>
+ <return-type>
+ <require-same-type testable="yes">
+ <reference-to><type name="Iter"/></reference-to>
+ </require-same-type>
+ </return-type>
+ <precondition><code>i</code> is incrementable (not
+ off-the-end) and some dereferenceable iterator <code>j</code> exists
+ such that <code>i == ++j</code></precondition>
+ </valid-expression>
+
+ <valid-expression name="Postdecrement">
+ <postdecrement>
+ <sample-value><reference-to><type name="Iter"/></reference-to></sample-value>
+ </postdecrement>
+ <return-type>
+ <require-same-type testable="yes"><type name="Iter"/></require-same-type>
+ </return-type>
+ <precondition>Same as for predecrement</precondition>
+ <semantics>Equivalent to <code>{Iter j = i; --i; return j;}</code></semantics>
+ <postcondition><code>i</code> is dereferenceable or
+ off-the-end</postcondition>
+ </valid-expression>
+
+ <complexity>
+ All iterator operations must take amortized constant time.
+ </complexity>
+
+ <invariant name="Predecrement must return object">
+ <code>&i = &(--i)</code>
+ </invariant>
+
+ <invariant name="Unique path through sequence">
+ <code>i == j</code> implies <code>--i == --j</code>
+ </invariant>
+
+ <invariant name="Increment and decrement are inverses">
+ <code>++i; --i;</code> and <code>--i; ++i;</code> must end up with the
+ value of <code>i</code> unmodified, if <code>i</code> both of the
+ operations in the pair are valid.
+ </invariant>
+
+ <example-model>
+ <pointer-to>
+ <type name="T"/>
+ </pointer-to>
+ </example-model>
+
+ <example-model>
+ <get-member-type name="iterator">
+ <apply-template name="std::list">
+ <type name="T"/>
+ </apply-template>
+ </get-member-type>
+ </example-model>
+
+ <see-also concept="RandomAccessIterator"/>
+
+</concept>
diff --git a/doc/reference/CopyConstructible.xml b/doc/reference/CopyConstructible.xml
new file mode 100644
index 0000000..9d278f3
--- /dev/null
+++ b/doc/reference/CopyConstructible.xml
@@ -0,0 +1,47 @@
+<?xml version="1.0"?>
+<concept name="CopyConstructible" category="Utility"><!--
+Based on concepts from the SGI Standard Template Library documentation:
+Copyright (c) 1996-1999
+Silicon Graphics Computer Systems, Inc.
+
+Copyright (c) 1994
+Hewlett-Packard Company
+--><!--
+Copyright 2000-2001 University of Notre Dame du Lac.
+Copyright 2001-2002 Indiana University.
+Some concepts based on versions from the MTL draft manual and Boost Graph
+and Property Map documentation:
+Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
+-->
+ <param name="X" role="copy-constructible-type"/>
+
+ <models-sentence>The type <arg num="1"/> must be a model of <self/>.</models-sentence>
+
+ <description>
+ <para>Copy constructible types must be able to be constructed from another
+ member of the type.</para>
+ </description>
+
+ <notation variables="x y">
+ <sample-value>
+ <type name="X"/>
+ </sample-value>
+ </notation>
+
+ <valid-expression name="Copy construction">
+ <construct template-parameters="">
+ <type name="X"/>
+ <sample-value><const><reference-to><type name="X"/></reference-to></const></sample-value>
+ </construct>
+ <return-type>
+ <require-same-type testable="yes">
+ <type name="X"/>
+ </require-same-type>
+ </return-type>
+ <semantics>Require copy constructor.</semantics>
+ </valid-expression>
+
+ <example-model>
+ <type name="int"/>
+ </example-model>
+</concept>
diff --git a/doc/reference/DefaultConstructible.xml b/doc/reference/DefaultConstructible.xml
new file mode 100644
index 0000000..1886ab0
--- /dev/null
+++ b/doc/reference/DefaultConstructible.xml
@@ -0,0 +1,40 @@
+<?xml version="1.0"?>
+<concept name="DefaultConstructible" category="Utility"><!--
+Based on concepts from the SGI Standard Template Library documentation:
+Copyright (c) 1996-1999
+Silicon Graphics Computer Systems, Inc.
+
+Copyright (c) 1994
+Hewlett-Packard Company
+--><!--
+Copyright 2000-2001 University of Notre Dame du Lac.
+Copyright 2001-2002 Indiana University.
+Some concepts based on versions from the MTL draft manual and Boost Graph
+and Property Map documentation:
+Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
+-->
+ <param name="X" role="default-constructible-type"/>
+
+ <models-sentence>The type <arg num="1"/> must be a model of <self/>.</models-sentence>
+
+ <description><para>DefaultConstructible objects only need to have a default
+ constructor.</para></description>
+
+ <valid-expression name="Construction">
+ <construct template-parameters="">
+ <type name="X"/>
+ </construct>
+ <return-type><require-same-type testable="yes"><type name="X"/></require-same-type></return-type>
+ <semantics>Construct an instance of the type with default parameters.</semantics>
+ </valid-expression>
+
+ <example-model>
+ <type name="int"/>
+ </example-model>
+
+ <example-model>
+ <apply-template name="std::vector">
+ <type name="double"/>
+ </apply-template>
+ </example-model>
+</concept>
diff --git a/doc/reference/EqualityComparable.xml b/doc/reference/EqualityComparable.xml
new file mode 100644
index 0000000..5d5479a
--- /dev/null
+++ b/doc/reference/EqualityComparable.xml
@@ -0,0 +1,63 @@
+<?xml version="1.0"?>
+<concept name="EqualityComparable" category="Utility"><!--
+Based on concepts from the SGI Standard Template Library documentation:
+Copyright (c) 1996-1999
+Silicon Graphics Computer Systems, Inc.
+
+Copyright (c) 1994
+Hewlett-Packard Company
+--><!--
+Copyright 2000-2001 University of Notre Dame du Lac.
+Copyright 2001-2002 Indiana University.
+Some concepts based on versions from the MTL draft manual and Boost Graph
+and Property Map documentation:
+Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
+-->
+ <param name="X" role="comparable-type"/>
+
+ <models-sentence>The type <arg num="1"/> must be a model of
+ <self/>.</models-sentence>
+
+ <description><para>Equality Comparable types must have <code>==</code> and
+ <code>!=</code> operators.</para></description>
+
+ <notation variables="x y">
+ <sample-value>
+ <type name="X"/>
+ </sample-value>
+ </notation>
+
+ <valid-expression name="Equality test">
+ <equal-to>
+ <sample-value><type name="X"/></sample-value>
+ <sample-value><type name="X"/></sample-value>
+ </equal-to>
+ <return-type>
+ <convertible-to testable="yes">
+ <type name="bool"/>
+ </convertible-to>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Inequality test">
+ <not-equal-to>
+ <sample-value><type name="X"/></sample-value>
+ <sample-value><type name="X"/></sample-value>
+ </not-equal-to>
+ <return-type>
+ <convertible-to testable="yes">
+ <type name="bool"/>
+ </convertible-to>
+ </return-type>
+ </valid-expression>
+
+ <example-model>
+ <type name="int"/>
+ </example-model>
+
+ <example-model>
+ <apply-template name="std::vector">
+ <type name="int"/>
+ </apply-template>
+ </example-model>
+</concept>
diff --git a/doc/reference/ForwardIterator.xml b/doc/reference/ForwardIterator.xml
new file mode 100644
index 0000000..dffe0ae
--- /dev/null
+++ b/doc/reference/ForwardIterator.xml
@@ -0,0 +1,174 @@
+<?xml version="1.0"?>
+<concept name="ForwardIterator" category="Iterator"><!--
+Based on concepts from the SGI Standard Template Library documentation:
+Copyright (c) 1996-1999
+Silicon Graphics Computer Systems, Inc.
+
+Copyright (c) 1994
+Hewlett-Packard Company
+--><!--
+Copyright 2000-2001 University of Notre Dame du Lac.
+Copyright 2001-2002 Indiana University.
+Some concepts based on versions from the MTL draft manual and Boost Graph
+and Property Map documentation:
+Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
+-->
+ <param name="Iter" role="iterator-type"/>
+
+ <use-header name="iterator"/>
+
+ <models-sentence>The iterator type <arg num="1"/> must be a model of <self/>.</models-sentence>
+
+ <description>
+ <para>A forward iterator is an iterator that can read through a sequence of
+ values. It is multi-pass (old values of the iterator can be
+ re-used), and can be either mutable (data pointed to by it can be
+ changed) or not mutable.</para>
+
+ <para>An iterator represents a position in a sequence. Therefore, the
+ iterator can point into the sequence (returning a value when dereferenced
+ and being incrementable), or be off-the-end (and not dereferenceable or
+ incrementable).</para>
+ </description>
+
+ <associated-type name="value_type">
+ <get-member-type name="value_type">
+ <apply-template name="std::iterator_traits">
+ <type name="Iter"/>
+ </apply-template>
+ </get-member-type>
+ <description><simpara>The value type of the iterator</simpara></description>
+ </associated-type>
+
+ <refines const="no" concept="InputIterator"/>
+ <refines const="no" concept="OutputIterator"/>
+
+<!-- DPG doesn't understand this
+ <models const="no" testable="yes" concept="Input Iterator">
+ <type name="Iter"/>
+ </models>
+-->
+<!--
+ <models-when-mutable concept="Output Iterator">
+ <type name="Iter"/>
+ <type name="value_type"/>
+ </models-when-mutable>
+-->
+
+ <notation variables="i j">
+ <sample-value>
+ <type name="Iter"/>
+ </sample-value>
+ </notation>
+
+ <associated-type name="category">
+ <get-member-type name="iterator_category">
+ <apply-template name="std::iterator_traits">
+ <type name="Iter"/>
+ </apply-template>
+ </get-member-type>
+ <description><simpara>The category of the iterator</simpara></description>
+ </associated-type>
+
+ <notation variables="x">
+ <sample-value>
+ <type name="value_type"/>
+ </sample-value>
+ </notation>
+
+ <valid-type-expression name="Category tag">
+ <description/>
+ <type name="category"/>
+ <return-type>
+ <derived-from testable="yes">
+ <type name="std::forward_iterator_tag"/>
+ </derived-from>
+ </return-type>
+ </valid-type-expression>
+
+ <valid-expression name="Dereference">
+ <dereference>
+ <sample-value><type name="Iter"/></sample-value>
+ </dereference>
+ <return-type>
+ <require-same-type testable="yes">
+ <const-if-not-mutable>
+ <reference-to><type name="value_type"/></reference-to>
+ </const-if-not-mutable>
+ </require-same-type>
+ </return-type>
+ <precondition><code>i</code> is incrementable (not
+ off-the-end)</precondition>
+ </valid-expression>
+
+ <valid-expression name="Member access">
+ <pointer-member>
+ <sample-value><type name="Iter"/></sample-value>
+ </pointer-member>
+ <return-type>
+ <require-same-type testable="yes">
+ <const-if-not-mutable>
+ <pointer-to><type name="value_type"/></pointer-to>
+ </const-if-not-mutable>
+ </require-same-type>
+ </return-type>
+ <precondition><code>i</code> is incrementable (not
+ off-the-end)</precondition>
+ </valid-expression>
+
+ <valid-expression name="Preincrement">
+ <preincrement>
+ <sample-value><reference-to><type name="Iter"/></reference-to></sample-value>
+ </preincrement>
+ <return-type>
+ <require-same-type testable="yes">
+ <reference-to><type name="Iter"/></reference-to>
+ </require-same-type>
+ </return-type>
+ <precondition><code>i</code> is incrementable (not
+ off-the-end)</precondition>
+ </valid-expression>
+
+ <valid-expression name="Postincrement">
+ <postincrement>
+ <sample-value><reference-to><type name="Iter"/></reference-to></sample-value>
+ </postincrement>
+ <return-type>
+ <require-same-type testable="yes"><type name="Iter"/></require-same-type>
+ </return-type>
+ <precondition><code>i</code> is incrementable (not
+ off-the-end)</precondition>
+ <semantics>Equivalent to <code>{Iter j = i; ++i; return j;}</code></semantics>
+ <postcondition><code>i</code> is dereferenceable or
+ off-the-end</postcondition>
+ </valid-expression>
+
+ <complexity>
+ All iterator operations must take amortized constant time.
+ </complexity>
+
+ <invariant name="Predecrement must return object">
+ <code>&i = &(++i)</code>
+ </invariant>
+
+ <invariant name="Unique path through sequence">
+ <code>i == j</code> implies <code>++i == ++j</code>
+ </invariant>
+
+ <example-model>
+ <pointer-to>
+ <type name="T"/>
+ </pointer-to>
+ </example-model>
+
+ <example-model>
+ <get-member-type name="iterator">
+ <apply-template name="std::hash_set">
+ <type name="T"/>
+ </apply-template>
+ </get-member-type>
+ </example-model>
+
+ <see-also concept="BidirectionalIterator"/>
+
+</concept>
diff --git a/doc/reference/InputIterator.xml b/doc/reference/InputIterator.xml
new file mode 100644
index 0000000..794c62c
--- /dev/null
+++ b/doc/reference/InputIterator.xml
@@ -0,0 +1,168 @@
+<?xml version="1.0"?>
+<concept name="InputIterator" category="Iterator"><!--
+Based on concepts from the SGI Standard Template Library documentation:
+Copyright (c) 1996-1999
+Silicon Graphics Computer Systems, Inc.
+
+Copyright (c) 1994
+Hewlett-Packard Company
+--><!--
+Copyright 2000-2001 University of Notre Dame du Lac.
+Copyright 2001-2002 Indiana University.
+Some concepts based on versions from the MTL draft manual and Boost Graph
+and Property Map documentation:
+Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
+-->
+ <param name="Iter" role="iterator-type"/>
+
+ <use-header name="iterator"/>
+
+ <models-sentence>The iterator type <arg num="1"/> must be a model of <self/>.</models-sentence>
+
+ <description>
+ <para>An input iterator is an iterator that can read through a sequence of
+ values. It is single-pass (old values of the iterator cannot be
+ re-used), and read-only.</para>
+
+ <para>An input iterator represents a position in a sequence. Therefore, the
+ iterator can point into the sequence (returning a value when dereferenced
+ and being incrementable), or be off-the-end (and not dereferenceable or
+ incrementable).</para>
+ </description>
+
+ <refines const="no" concept="Assignable"/>
+ <refines const="no" concept="DefaultConstructible"/>
+ <refines const="no" concept="EqualityComparable"/>
+
+ <notation variables="i j">
+ <sample-value>
+ <type name="Iter"/>
+ </sample-value>
+ </notation>
+
+ <associated-type name="value_type">
+ <get-member-type name="value_type">
+ <apply-template name="std::iterator_traits">
+ <type name="Iter"/>
+ </apply-template>
+ </get-member-type>
+ <description><simpara>The value type of the iterator (not necessarily what
+ <code>*i</code> returns)</simpara></description>
+ </associated-type>
+
+ <associated-type name="difference_type">
+ <get-member-type name="difference_type">
+ <apply-template name="std::iterator_traits">
+ <type name="Iter"/>
+ </apply-template>
+ </get-member-type>
+ <description><simpara>The difference type of the iterator</simpara></description>
+ </associated-type>
+
+ <associated-type name="category">
+ <get-member-type name="iterator_category">
+ <apply-template name="std::iterator_traits">
+ <type name="Iter"/>
+ </apply-template>
+ </get-member-type>
+ <description><simpara>The category of the iterator</simpara></description>
+ </associated-type>
+
+ <notation variables="x">
+ <sample-value>
+ <type name="value_type"/>
+ </sample-value>
+ </notation>
+
+ <valid-type-expression name="Category tag">
+ <description/>
+ <type name="category"/>
+ <return-type>
+ <derived-from testable="yes">
+ <type name="std::input_iterator_tag"/>
+ </derived-from>
+ <models-as-first-arg const="no" testable="yes" concept="DefaultConstructible"/>
+ <models-as-first-arg const="no" testable="yes" concept="CopyConstructible"/>
+ </return-type>
+ </valid-type-expression>
+
+ <valid-type-expression name="Value type copy constructibility">
+ <description/>
+ <type name="value_type"/>
+ <return-type>
+ <models-as-first-arg const="no" testable="yes" concept="CopyConstructible"/>
+ </return-type>
+ </valid-type-expression>
+
+ <valid-type-expression name="Difference type properties">
+ <description/>
+ <type name="difference_type"/>
+ <return-type>
+ <models-as-first-arg const="no" testable="yes" concept="SignedInteger"/>
+ </return-type>
+ </valid-type-expression>
+
+ <valid-expression name="Dereference">
+ <dereference>
+ <sample-value><type name="Iter"/></sample-value>
+ </dereference>
+ <return-type>
+ <convertible-to testable="yes"><type name="value_type"/></convertible-to>
+ </return-type>
+ <precondition><code>i</code> is incrementable (not
+ off-the-end)</precondition>
+ </valid-expression>
+
+ <valid-expression name="Preincrement">
+ <preincrement>
+ <sample-value><reference-to><type name="Iter"/></reference-to></sample-value>
+ </preincrement>
+ <return-type>
+ <require-same-type testable="yes">
+ <reference-to><type name="Iter"/></reference-to>
+ </require-same-type>
+ </return-type>
+ <precondition><code>i</code> is incrementable (not
+ off-the-end)</precondition>
+ </valid-expression>
+
+ <valid-expression name="Postincrement">
+ <postincrement>
+ <sample-value><reference-to><type name="Iter"/></reference-to></sample-value>
+ </postincrement>
+ <return-type/>
+ <precondition><code>i</code> is incrementable (not
+ off-the-end)</precondition>
+ <semantics>Equivalent to <code>(void)(++i)</code></semantics>
+ <postcondition><code>i</code> is dereferenceable or
+ off-the-end</postcondition>
+ </valid-expression>
+
+ <valid-expression name="Postincrement and dereference">
+ <dereference>
+ <postincrement>
+ <sample-value><reference-to><type name="Iter"/></reference-to></sample-value>
+ </postincrement>
+ </dereference>
+ <return-type>
+ <convertible-to testable="yes"><type name="value_type"/></convertible-to>
+ </return-type>
+ <precondition><code>i</code> is incrementable (not
+ off-the-end)</precondition>
+ <semantics>Equivalent to <code>{value_type t = *i; ++i; return t;}</code></semantics>
+ <postcondition><code>i</code> is dereferenceable or
+ off-the-end</postcondition>
+ </valid-expression>
+
+ <complexity>
+ All iterator operations must take amortized constant time.
+ </complexity>
+
+ <example-model>
+ <type name="std::istream_iterator"/>
+ </example-model>
+
+ <see-also concept="OutputIterator"/>
+ <see-also concept="ForwardIterator"/>
+
+</concept>
diff --git a/doc/reference/LessThanComparable.xml b/doc/reference/LessThanComparable.xml
new file mode 100644
index 0000000..97f4c46
--- /dev/null
+++ b/doc/reference/LessThanComparable.xml
@@ -0,0 +1,81 @@
+<?xml version="1.0"?>
+<concept name="LessThanComparable" category="Utility"><!--
+Based on concepts from the SGI Standard Template Library documentation:
+Copyright (c) 1996-1999
+Silicon Graphics Computer Systems, Inc.
+
+Copyright (c) 1994
+Hewlett-Packard Company
+--><!--
+Copyright 2000-2001 University of Notre Dame du Lac.
+Copyright 2001-2002 Indiana University.
+Some concepts based on versions from the MTL draft manual and Boost Graph
+and Property Map documentation:
+Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
+-->
+ <param name="X" role="comparable-type"/>
+
+ <models-sentence>The type <arg num="1"/> must be a model of <self/>.</models-sentence>
+
+ <description><para>LessThanComparable types must have <code><</code>,
+ <code>></code>, <code><=</code>, and <code>>=</code>
+ operators.</para></description>
+
+ <notation variables="x y"><sample-value><type name="X"/></sample-value></notation>
+
+ <valid-expression name="Less than">
+ <less-than>
+ <sample-value><type name="X"/></sample-value>
+ <sample-value><type name="X"/></sample-value>
+ </less-than>
+ <return-type>
+ <convertible-to testable="yes">
+ <type name="bool"/>
+ </convertible-to>
+ </return-type>
+ <semantics>Determine if one value is less than another.</semantics>
+ </valid-expression>
+
+ <valid-expression name="Less than or equal">
+ <less-than-or-equal>
+ <sample-value><type name="X"/></sample-value>
+ <sample-value><type name="X"/></sample-value>
+ </less-than-or-equal>
+ <return-type>
+ <convertible-to testable="yes">
+ <type name="bool"/>
+ </convertible-to>
+ </return-type>
+ <semantics>Determine if one value is less than or equal to another.</semantics>
+ </valid-expression>
+
+ <valid-expression name="Greater than">
+ <greater-than>
+ <sample-value><type name="X"/></sample-value>
+ <sample-value><type name="X"/></sample-value>
+ </greater-than>
+ <return-type>
+ <convertible-to testable="yes">
+ <type name="bool"/>
+ </convertible-to>
+ </return-type>
+ <semantics>Determine if one value is greater than another.</semantics>
+ </valid-expression>
+
+ <valid-expression name="Greater than or equal to">
+ <greater-than-or-equal>
+ <sample-value><type name="X"/></sample-value>
+ <sample-value><type name="X"/></sample-value>
+ </greater-than-or-equal>
+ <return-type>
+ <convertible-to testable="yes">
+ <type name="bool"/>
+ </convertible-to>
+ </return-type>
+ <semantics>Determine if one value is greater than or equal to another.</semantics>
+ </valid-expression>
+
+ <example-model>
+ <type name="int"/>
+ </example-model>
+</concept>
diff --git a/doc/reference/OutputIterator.xml b/doc/reference/OutputIterator.xml
new file mode 100644
index 0000000..d3f8062
--- /dev/null
+++ b/doc/reference/OutputIterator.xml
@@ -0,0 +1,203 @@
+<?xml version="1.0"?>
+<concept name="OutputIterator" category="Iterator"><!--
+Based on concepts from the SGI Standard Template Library documentation:
+Copyright (c) 1996-1999
+Silicon Graphics Computer Systems, Inc.
+
+Copyright (c) 1994
+Hewlett-Packard Company
+--><!--
+Copyright 2000-2001 University of Notre Dame du Lac.
+Copyright 2001-2002 Indiana University.
+Some concepts based on versions from the MTL draft manual and Boost Graph
+and Property Map documentation:
+Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
+-->
+ <param name="Iter" role="iterator-type"/>
+ <param name="ValueType" role="value-type"/>
+
+ <use-header name="iterator"/>
+
+ <models-sentence>The iterator type <arg num="1"/> (with value type <arg num="2"/>) must be a model of <self/>.</models-sentence>
+
+ <description>
+ <para>An output iterator is an iterator that can write a sequence of
+ values. It is single-pass (old values of the iterator cannot be
+ re-used), and write-only.</para>
+
+ <para>An output iterator represents a position in a (possibly infinite)
+ sequence. Therefore, the iterator can point into the sequence (returning
+ a value when dereferenced and being incrementable), or be off-the-end
+ (and not dereferenceable or incrementable).</para>
+ </description>
+
+ <models const="no" testable="yes" concept="Assignable">
+ <type name="Iter"/>
+ </models>
+
+ <models const="no" testable="yes" concept="Assignable">
+ <type name="ValueType"/>
+ </models>
+
+ <models const="no" testable="yes" concept="DefaultConstructible">
+ <type name="Iter"/>
+ </models>
+
+ <models const="no" testable="yes" concept="EqualityComparable">
+ <type name="Iter"/>
+ </models>
+
+ <associated-type name="value_type">
+ <get-member-type name="value_type">
+ <apply-template name="std::iterator_traits">
+ <type name="Iter"/>
+ </apply-template>
+ </get-member-type>
+ <description><simpara>The stated value type of the iterator (should be
+ <code>void</code> for an output iterator that does not model some other
+ iterator concept).</simpara></description>
+ </associated-type>
+
+ <associated-type name="difference_type">
+ <get-member-type name="difference_type">
+ <apply-template name="std::iterator_traits">
+ <type name="Iter"/>
+ </apply-template>
+ </get-member-type>
+ <description><simpara>The difference type of the iterator</simpara></description>
+ </associated-type>
+
+ <associated-type name="category">
+ <get-member-type name="iterator_category">
+ <apply-template name="std::iterator_traits">
+ <type name="Iter"/>
+ </apply-template>
+ </get-member-type>
+ <description><simpara>The category of the iterator</simpara></description>
+ </associated-type>
+
+ <notation variables="i j">
+ <sample-value>
+ <type name="Iter"/>
+ </sample-value>
+ </notation>
+
+ <notation variables="x">
+ <sample-value>
+ <type name="ValueType"/>
+ </sample-value>
+ </notation>
+
+ <valid-type-expression name="Category tag">
+ <description/>
+ <type name="category"/>
+ <return-type>
+ <derived-from testable="yes">
+ <type name="std::output_iterator_tag"/>
+ </derived-from>
+ <models-as-first-arg const="no" testable="yes" concept="DefaultConstructible"/>
+ <models-as-first-arg const="no" testable="yes" concept="CopyConstructible"/>
+ </return-type>
+ </valid-type-expression>
+
+ <valid-type-expression name="Difference type properties">
+ <description/>
+ <type name="difference_type"/>
+ <return-type>
+ <models-as-first-arg const="no" testable="yes" concept="SignedInteger"/>
+ </return-type>
+ </valid-type-expression>
+
+ <valid-expression name="Dereference">
+ <dereference>
+ <sample-value><type name="Iter"/></sample-value>
+ </dereference>
+ <return-type/>
+ <precondition><code>i</code> is incrementable (not
+ off-the-end)</precondition>
+ </valid-expression>
+
+ <valid-expression name="Dereference and assign">
+ <assign>
+ <dereference>
+ <sample-value><type name="Iter"/></sample-value>
+ </dereference>
+ <sample-value><const><reference-to><type name="ValueType"/></reference-to></const></sample-value>
+ </assign>
+ <return-type/>
+ <precondition><code>i</code> is incrementable (not
+ off-the-end)</precondition>
+ <postcondition><code>*i</code> may not be written to again until it has
+ been incremented.</postcondition>
+ </valid-expression>
+
+ <valid-expression name="Preincrement">
+ <preincrement>
+ <sample-value><reference-to><type name="Iter"/></reference-to></sample-value>
+ </preincrement>
+ <return-type>
+ <require-same-type testable="yes">
+ <reference-to><type name="Iter"/></reference-to>
+ </require-same-type>
+ </return-type>
+ <precondition><code>i</code> is incrementable (not
+ off-the-end)</precondition>
+ </valid-expression>
+
+ <valid-expression name="Postincrement">
+ <postincrement>
+ <sample-value><reference-to><type name="Iter"/></reference-to></sample-value>
+ </postincrement>
+ <return-type/>
+ <precondition><code>i</code> is incrementable (not
+ off-the-end)</precondition>
+ <semantics>Equivalent to <code>(void)(++i)</code></semantics>
+ <postcondition><code>i</code> is dereferenceable or
+ off-the-end</postcondition>
+ </valid-expression>
+
+ <valid-expression name="Postincrement, dereference, and assign">
+ <assign>
+ <dereference>
+ <postincrement>
+ <sample-value><reference-to><type name="Iter"/></reference-to></sample-value>
+ </postincrement>
+ </dereference>
+ <sample-value><const><reference-to><type name="ValueType"/></reference-to></const></sample-value>
+ </assign>
+ <return-type/>
+ <precondition><code>i</code> is incrementable (not
+ off-the-end)</precondition>
+ <semantics>Equivalent to <code>{*i = t; ++i;}</code></semantics>
+ <postcondition><code>i</code> is dereferenceable or
+ off-the-end</postcondition>
+ </valid-expression>
+
+ <complexity>
+ All iterator operations must take amortized constant time.
+ </complexity>
+
+ <example-model>
+ <type name="std::ostream_iterator"/>
+ <type name="..."/>
+ </example-model>
+
+ <example-model>
+ <type name="std::insert_iterator"/>
+ <type name="..."/>
+ </example-model>
+
+ <example-model>
+ <type name="std::front_insert_iterator"/>
+ <type name="..."/>
+ </example-model>
+
+ <example-model>
+ <type name="std::back_insert_iterator"/>
+ <type name="..."/>
+ </example-model>
+
+ <see-also concept="InputIterator"/>
+ <see-also concept="ForwardIterator"/>
+
+</concept>
diff --git a/doc/reference/RandomAccessIterator.xml b/doc/reference/RandomAccessIterator.xml
new file mode 100644
index 0000000..f77f8fd
--- /dev/null
+++ b/doc/reference/RandomAccessIterator.xml
@@ -0,0 +1,313 @@
+<?xml version="1.0"?>
+<concept name="RandomAccessIterator" category="Iterator"><!--
+Based on concepts from the SGI Standard Template Library documentation:
+Copyright (c) 1996-1999
+Silicon Graphics Computer Systems, Inc.
+
+Copyright (c) 1994
+Hewlett-Packard Company
+--><!--
+Copyright 2000-2001 University of Notre Dame du Lac.
+Copyright 2001-2002 Indiana University.
+Some concepts based on versions from the MTL draft manual and Boost Graph
+and Property Map documentation:
+Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
+-->
+ <param name="Iter" role="iterator-type"/>
+
+ <use-header name="iterator"/>
+
+ <models-sentence>The iterator type <arg num="1"/> must be a model of <self/>.</models-sentence>
+
+ <description>
+ <para>A random access iterator is an iterator that can read through
+ a sequence of values. It can move in either direction through the
+ sequence (by any amount in constant time), and can be either mutable
+ (data pointed to by it can be changed) or not mutable.</para>
+
+ <para>An iterator represents a position in a sequence. Therefore,
+ the iterator can point into the sequence (returning a value when
+ dereferenced and being incrementable), or be off-the-end (and not
+ dereferenceable or incrementable).</para>
+ </description>
+
+ <associated-type name="value_type">
+ <get-member-type name="value_type">
+ <apply-template name="std::iterator_traits">
+ <type name="Iter"/>
+ </apply-template>
+ </get-member-type>
+ <description><simpara>The value type of the iterator</simpara></description>
+ </associated-type>
+
+ <refines const="no" concept="BidirectionalIterator"/>
+ <refines const="no" concept="LessThanComparable"/>
+
+ <notation variables="i j">
+ <sample-value>
+ <type name="Iter"/>
+ </sample-value>
+ </notation>
+
+ <associated-type name="category">
+ <get-member-type name="iterator_category">
+ <apply-template name="std::iterator_traits">
+ <type name="Iter"/>
+ </apply-template>
+ </get-member-type>
+ <description><simpara>The category of the iterator</simpara></description>
+ </associated-type>
+
+ <associated-type name="difference_type">
+ <get-member-type name="difference_type">
+ <apply-template name="std::iterator_traits">
+ <type name="Iter"/>
+ </apply-template>
+ </get-member-type>
+ <description><simpara>The difference type of the iterator (measure of the number
+ of steps between two iterators)</simpara></description>
+ </associated-type>
+
+ <notation variables="x">
+ <sample-value>
+ <type name="value_type"/>
+ </sample-value>
+ </notation>
+
+ <notation variables="n">
+ <sample-value>
+ <type name="difference_type"/>
+ </sample-value>
+ </notation>
+
+ <notation variables="int_off">
+ <sample-value>
+ <type name="int"/>
+ </sample-value>
+ </notation>
+
+ <valid-type-expression name="Category tag">
+ <description/>
+ <type name="category"/>
+ <return-type>
+ <derived-from testable="yes">
+ <type name="std::random_access_iterator_tag"/>
+ </derived-from>
+ </return-type>
+ </valid-type-expression>
+
+ <valid-expression name="Motion">
+ <add-assign>
+ <sample-value><reference-to><type name="Iter"/></reference-to></sample-value>
+ <sample-value><type name="difference_type"/></sample-value>
+ </add-assign>
+ <return-type>
+ <require-same-type testable="yes">
+ <reference-to><type name="Iter"/></reference-to>
+ </require-same-type>
+ </return-type>
+ <semantics>Equivalent to applying <code>i++</code> <code>n</code> times
+ if <code>n</code> is positive, applying <code>i--</code>
+ <code>-n</code> times if <code>n</code> is negative, and to a null
+ operation if <code>n</code> is zero.</semantics>
+ </valid-expression>
+
+ <valid-expression name="Motion (with integer offset)">
+ <add-assign>
+ <sample-value><reference-to><type name="Iter"/></reference-to></sample-value>
+ <sample-value><type name="int"/></sample-value>
+ </add-assign>
+ <return-type>
+ <require-same-type testable="yes">
+ <reference-to><type name="Iter"/></reference-to>
+ </require-same-type>
+ </return-type>
+ <semantics>Equivalent to applying <code>i++</code> <code>n</code> times
+ if <code>n</code> is positive, applying <code>i--</code>
+ <code>-n</code> times if <code>n</code> is negative, and to a null
+ operation if <code>n</code> is zero.</semantics>
+ </valid-expression>
+
+ <valid-expression name="Subtractive motion">
+ <subtract-assign>
+ <sample-value><reference-to><type name="Iter"/></reference-to></sample-value>
+ <sample-value><type name="difference_type"/></sample-value>
+ </subtract-assign>
+ <return-type>
+ <require-same-type testable="yes">
+ <reference-to><type name="Iter"/></reference-to>
+ </require-same-type>
+ </return-type>
+ <semantics>Equivalent to <code>i+=(-n)</code></semantics>
+ </valid-expression>
+
+ <valid-expression name="Subtractive motion (with integer offset)">
+ <subtract-assign>
+ <sample-value><reference-to><type name="Iter"/></reference-to></sample-value>
+ <sample-value><type name="int"/></sample-value>
+ </subtract-assign>
+ <return-type>
+ <require-same-type testable="yes">
+ <reference-to><type name="Iter"/></reference-to>
+ </require-same-type>
+ </return-type>
+ <semantics>Equivalent to <code>i+=(-n)</code></semantics>
+ </valid-expression>
+
+ <valid-expression name="Addition">
+ <add>
+ <sample-value><type name="Iter"/></sample-value>
+ <sample-value><type name="difference_type"/></sample-value>
+ </add>
+ <return-type>
+ <require-same-type testable="yes"><type name="Iter"/></require-same-type>
+ </return-type>
+ <semantics>Equivalent to <code>{Iter j = i; j += n; return j;}</code></semantics>
+ </valid-expression>
+
+ <valid-expression name="Addition with integer">
+ <add>
+ <sample-value><type name="Iter"/></sample-value>
+ <sample-value><type name="int"/></sample-value>
+ </add>
+ <return-type>
+ <require-same-type testable="yes"><type name="Iter"/></require-same-type>
+ </return-type>
+ <semantics>Equivalent to <code>{Iter j = i; j += n; return j;}</code></semantics>
+ </valid-expression>
+
+ <valid-expression name="Addition (count first)">
+ <add>
+ <sample-value><type name="difference_type"/></sample-value>
+ <sample-value><type name="Iter"/></sample-value>
+ </add>
+ <return-type>
+ <require-same-type testable="yes"><type name="Iter"/></require-same-type>
+ </return-type>
+ <semantics>Equivalent to <code>i + n</code></semantics>
+ </valid-expression>
+
+ <valid-expression name="Addition with integer (count first)">
+ <add>
+ <sample-value><type name="int"/></sample-value>
+ <sample-value><type name="Iter"/></sample-value>
+ </add>
+ <return-type>
+ <require-same-type testable="yes"><type name="Iter"/></require-same-type>
+ </return-type>
+ <semantics>Equivalent to <code>i + n</code></semantics>
+ </valid-expression>
+
+ <valid-expression name="Subtraction">
+ <subtract>
+ <sample-value><type name="Iter"/></sample-value>
+ <sample-value><type name="difference_type"/></sample-value>
+ </subtract>
+ <return-type>
+ <require-same-type testable="yes"><type name="Iter"/></require-same-type>
+ </return-type>
+ <semantics>Equivalent to <code>i + (-n)</code></semantics>
+ </valid-expression>
+
+ <valid-expression name="Subtraction with integer">
+ <subtract>
+ <sample-value><type name="Iter"/></sample-value>
+ <sample-value><type name="int"/></sample-value>
+ </subtract>
+ <return-type>
+ <require-same-type testable="yes"><type name="Iter"/></require-same-type>
+ </return-type>
+ <semantics>Equivalent to <code>i + (-n)</code></semantics>
+ </valid-expression>
+
+ <valid-expression name="Distance">
+ <subtract>
+ <sample-value><type name="Iter"/></sample-value>
+ <sample-value><type name="Iter"/></sample-value>
+ </subtract>
+ <return-type>
+ <require-same-type testable="yes"><type name="difference_type"/></require-same-type>
+ </return-type>
+ <semantics>The number of times <code>i</code> must be incremented (or
+ decremented if the result is negative) to reach <code>j</code>. Not
+ defined if <code>j</code> is not reachable from
+ <code>i</code>.</semantics>
+ </valid-expression>
+
+ <valid-expression name="Element access">
+ <subscript>
+ <sample-value><type name="Iter"/></sample-value>
+ <sample-value><type name="difference_type"/></sample-value>
+ </subscript>
+ <return-type>
+ <require-same-type testable="yes">
+ <const-if-not-mutable>
+ <reference-to>
+ <type name="value_type"/>
+ </reference-to>
+ </const-if-not-mutable>
+ </require-same-type>
+ </return-type>
+ <semantics>Equivalent to <code>*(i + n)</code></semantics>
+ </valid-expression>
+
+ <valid-expression name="Element access with integer index">
+ <subscript>
+ <sample-value><type name="Iter"/></sample-value>
+ <sample-value><type name="int"/></sample-value>
+ </subscript>
+ <return-type>
+ <require-same-type testable="yes">
+ <const-if-not-mutable>
+ <reference-to>
+ <type name="value_type"/>
+ </reference-to>
+ </const-if-not-mutable>
+ </require-same-type>
+ </return-type>
+ <semantics>Equivalent to <code>*(i + n)</code></semantics>
+ </valid-expression>
+
+ <complexity>
+ All iterator operations must take amortized constant time.
+ </complexity>
+
+ <example-model>
+ <pointer-to>
+ <type name="T"/>
+ </pointer-to>
+ </example-model>
+
+ <example-model>
+ <get-member-type name="iterator">
+ <apply-template name="std::vector">
+ <type name="T"/>
+ </apply-template>
+ </get-member-type>
+ </example-model>
+
+ <example-model>
+ <get-member-type name="const_iterator">
+ <apply-template name="std::vector">
+ <type name="T"/>
+ </apply-template>
+ </get-member-type>
+ </example-model>
+
+ <example-model>
+ <get-member-type name="iterator">
+ <apply-template name="std::deque">
+ <type name="T"/>
+ </apply-template>
+ </get-member-type>
+ </example-model>
+
+ <example-model>
+ <get-member-type name="const_iterator">
+ <apply-template name="std::deque">
+ <type name="T"/>
+ </apply-template>
+ </get-member-type>
+ </example-model>
+
+</concept>
diff --git a/doc/reference/SignedInteger.xml b/doc/reference/SignedInteger.xml
new file mode 100644
index 0000000..d47693b
--- /dev/null
+++ b/doc/reference/SignedInteger.xml
@@ -0,0 +1,549 @@
+<?xml version="1.0"?>
+<concept name="SignedInteger" category="Utility"><!--
+Based on concepts from the SGI Standard Template Library documentation:
+Copyright (c) 1996-1999
+Silicon Graphics Computer Systems, Inc.
+
+Copyright (c) 1994
+Hewlett-Packard Company
+--><!--
+Copyright 2000-2001 University of Notre Dame du Lac.
+Copyright 2001-2002 Indiana University.
+Some concepts based on versions from the MTL draft manual and Boost Graph
+and Property Map documentation:
+Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
+-->
+ <param name="T" role="integral-type"/>
+
+ <models-sentence>Integer type <arg num="1"/> must be a model of <self/>.</models-sentence>
+
+ <refines const="no" concept="CopyConstructible"/>
+ <refines const="no" concept="Assignable"/>
+ <refines const="no" concept="DefaultConstructible"/>
+ <refines const="no" concept="EqualityComparable"/>
+ <refines const="no" concept="LessThanComparable"/>
+
+ <notation variables="x y z">
+ <sample-value><type name="T"/></sample-value>
+ </notation>
+ <notation variables="a b">
+ <sample-value><type name="int"/></sample-value>
+ </notation>
+
+ <!--
+ <valid-type-expression name="int-ness">
+ <documentation>Should this really be required?</documentation>
+ <type name="T"/>
+ <return-type>
+ <require-same-type>
+ <type name="int"/>
+ </require-same-type>
+ </return-type>
+ </valid-type-expression>
+ -->
+
+ <valid-expression name="Conversion from int">
+ <construct template-parameters="">
+ <type name="T"/>
+ <sample-value><type name="int"/></sample-value>
+ </construct>
+ <return-type><require-same-type testable="yes">
+ <type name="T"/>
+ </require-same-type></return-type>
+ </valid-expression>
+
+ <valid-expression name="Preincrement">
+ <preincrement>
+ <sample-value>
+ <reference-to><type name="T"/></reference-to>
+ </sample-value>
+ </preincrement>
+ <return-type>
+ <require-same-type testable="yes">
+ <reference-to><type name="T"/></reference-to>
+ </require-same-type>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Predecrement">
+ <predecrement>
+ <sample-value>
+ <reference-to><type name="T"/></reference-to>
+ </sample-value>
+ </predecrement>
+ <return-type>
+ <require-same-type testable="yes">
+ <reference-to><type name="T"/></reference-to>
+ </require-same-type>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Postincrement">
+ <postincrement>
+ <sample-value>
+ <reference-to><type name="T"/></reference-to>
+ </sample-value>
+ </postincrement>
+ <return-type>
+ <require-same-type testable="yes">
+ <type name="T"/>
+ </require-same-type>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Postdecrement">
+ <postdecrement>
+ <sample-value>
+ <reference-to><type name="T"/></reference-to>
+ </sample-value>
+ </postdecrement>
+ <return-type>
+ <require-same-type testable="yes">
+ <type name="T"/>
+ </require-same-type>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Sum">
+ <add>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ </add>
+ <return-type>
+ <require-same-type testable="yes">
+ <type name="T"/>
+ </require-same-type>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Sum with int">
+ <add>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="int"/>
+ </sample-value>
+ </add>
+ <return-type>
+ <require-same-type testable="yes">
+ <type name="T"/>
+ </require-same-type>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Sum-assignment">
+ <add-assign>
+ <sample-value>
+ <reference-to><type name="T"/></reference-to>
+ </sample-value>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ </add-assign>
+ <return-type>
+ <require-same-type testable="yes">
+ <reference-to><type name="T"/></reference-to>
+ </require-same-type>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Sum-assignment with int">
+ <add-assign>
+ <sample-value>
+ <reference-to><type name="T"/></reference-to>
+ </sample-value>
+ <sample-value>
+ <type name="int"/>
+ </sample-value>
+ </add-assign>
+ <return-type>
+ <require-same-type testable="yes">
+ <reference-to><type name="T"/></reference-to>
+ </require-same-type>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Difference">
+ <subtract>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ </subtract>
+ <return-type>
+ <require-same-type testable="yes">
+ <type name="T"/>
+ </require-same-type>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Difference with int">
+ <subtract>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="int"/>
+ </sample-value>
+ </subtract>
+ <return-type>
+ <require-same-type testable="yes">
+ <type name="T"/>
+ </require-same-type>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Product">
+ <multiply>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ </multiply>
+ <return-type>
+ <require-same-type testable="yes">
+ <type name="T"/>
+ </require-same-type>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Product with int">
+ <multiply>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="int"/>
+ </sample-value>
+ </multiply>
+ <return-type>
+ <require-same-type testable="yes">
+ <type name="T"/>
+ </require-same-type>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Product-assignment with int">
+ <multiply-assign>
+ <sample-value>
+ <reference-to><type name="T"/></reference-to>
+ </sample-value>
+ <sample-value>
+ <type name="int"/>
+ </sample-value>
+ </multiply-assign>
+ <return-type>
+ <require-same-type testable="yes">
+ <reference-to><type name="T"/></reference-to>
+ </require-same-type>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Product with int on left">
+ <multiply>
+ <sample-value>
+ <type name="int"/>
+ </sample-value>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ </multiply>
+ <return-type>
+ <require-same-type testable="yes">
+ <type name="T"/>
+ </require-same-type>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Quotient">
+ <divide>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ </divide>
+ <return-type>
+ <require-same-type testable="yes">
+ <type name="T"/>
+ </require-same-type>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Quotient with int">
+ <divide>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="int"/>
+ </sample-value>
+ </divide>
+ <return-type>
+ <require-same-type testable="yes">
+ <type name="T"/>
+ </require-same-type>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Right-shift">
+ <shift-right>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ </shift-right>
+ <return-type>
+ <require-same-type testable="yes">
+ <type name="T"/>
+ </require-same-type>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Right-shift with int">
+ <shift-right>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="int"/>
+ </sample-value>
+ </shift-right>
+ <return-type>
+ <require-same-type testable="yes">
+ <type name="T"/>
+ </require-same-type>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Right-shift-assignment with int">
+ <shift-right-assign>
+ <sample-value>
+ <reference-to><type name="T"/></reference-to>
+ </sample-value>
+ <sample-value>
+ <type name="int"/>
+ </sample-value>
+ </shift-right-assign>
+ <return-type>
+ <require-same-type testable="yes">
+ <reference-to><type name="T"/></reference-to>
+ </require-same-type>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Less-than comparison">
+ <less-than>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ </less-than>
+ <return-type>
+ <convertible-to testable="yes">
+ <type name="bool"/>
+ </convertible-to>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Less-than comparison with int">
+ <less-than>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="int"/>
+ </sample-value>
+ </less-than>
+ <return-type>
+ <convertible-to testable="yes">
+ <type name="bool"/>
+ </convertible-to>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Less-than comparison with size_t">
+ <less-than>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="std::size_t"/>
+ </sample-value>
+ </less-than>
+ <return-type>
+ <convertible-to testable="yes">
+ <type name="bool"/>
+ </convertible-to>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Greater-than comparison">
+ <greater-than>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ </greater-than>
+ <return-type>
+ <convertible-to testable="yes">
+ <type name="bool"/>
+ </convertible-to>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Greater-than comparison with int">
+ <greater-than>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="int"/>
+ </sample-value>
+ </greater-than>
+ <return-type>
+ <convertible-to testable="yes">
+ <type name="bool"/>
+ </convertible-to>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Less-than-or-equal comparison">
+ <less-than-or-equal>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ </less-than-or-equal>
+ <return-type>
+ <convertible-to testable="yes">
+ <type name="bool"/>
+ </convertible-to>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Less-than-or-equal comparison with int">
+ <less-than-or-equal>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="int"/>
+ </sample-value>
+ </less-than-or-equal>
+ <return-type>
+ <convertible-to testable="yes">
+ <type name="bool"/>
+ </convertible-to>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Greater-than-or-equal comparison">
+ <greater-than-or-equal>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ </greater-than-or-equal>
+ <return-type>
+ <convertible-to testable="yes">
+ <type name="bool"/>
+ </convertible-to>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Greater-than-or-equal comparison with int">
+ <greater-than-or-equal>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="int"/>
+ </sample-value>
+ </greater-than-or-equal>
+ <return-type>
+ <convertible-to testable="yes">
+ <type name="bool"/>
+ </convertible-to>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Greater-than-or-equal comparison with int on left">
+ <greater-than-or-equal>
+ <sample-value>
+ <type name="int"/>
+ </sample-value>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ </greater-than-or-equal>
+ <return-type>
+ <convertible-to testable="yes">
+ <type name="bool"/>
+ </convertible-to>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Equality comparison">
+ <equal-to>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ </equal-to>
+ <return-type>
+ <convertible-to testable="yes">
+ <type name="bool"/>
+ </convertible-to>
+ </return-type>
+ </valid-expression>
+
+ <valid-expression name="Equality comparison with int">
+ <equal-to>
+ <sample-value>
+ <type name="T"/>
+ </sample-value>
+ <sample-value>
+ <type name="int"/>
+ </sample-value>
+ </equal-to>
+ <return-type>
+ <convertible-to testable="yes">
+ <type name="bool"/>
+ </convertible-to>
+ </return-type>
+ </valid-expression>
+
+ <valid-type-expression name="Conversion to int">
+ <documentation/>
+ <type name="T"/>
+ <return-type>
+ <convertible-to testable="yes">
+ <type name="int"/>
+ </convertible-to>
+ </return-type>
+ </valid-type-expression>
+
+</concept>
diff --git a/doc/reference/concepts.xml b/doc/reference/concepts.xml
new file mode 100644
index 0000000..ffe32c1
--- /dev/null
+++ b/doc/reference/concepts.xml
@@ -0,0 +1,84 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!DOCTYPE library-reference PUBLIC "-//Boost//DTD BoostBook XML V1.0//EN"
+ "http://www.boost.org/tools/boostbook/dtd/boostbook.dtd">
+<library-reference id="concepts.reference"
+ xmlns:xi="http://www.w3.org/2001/XInclude"
+ last-revision="$Date$">
+ <sectioninfo>
+ <copyright>
+ <year>2001</year>
+ <year>2002</year>
+ <holder>Indiana University</holder>
+ </copyright>
+
+ <copyright>
+ <year>2000</year>
+ <year>2001</year>
+ <holder>University of Notre Dame du Lac</holder>
+ </copyright>
+
+ <copyright>
+ <year>2000</year>
+ <holder>Jeremy Siek</holder>
+ <holder>Lie-Quan Lee</holder>
+ <holder>Andrew Lumsdaine</holder>
+ </copyright>
+
+ <copyright>
+ <year>1996</year>
+ <year>1997</year>
+ <year>1998</year>
+ <year>1999</year>
+ <holder>Silicon Graphics Computer Systems, Inc.</holder>
+ </copyright>
+
+ <copyright>
+ <year>1994</year>
+ <holder>Hewlett-Packard Company</holder>
+ </copyright>
+
+ <legalnotice>
+ <para>Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file <filename>LICENSE_1_0.txt</filename> or copy at
+ <ulink
+ url="http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</ulink>)
+ </para>
+
+ <para>This product includes software developed at the University
+ of Notre Dame and the Pervasive Technology Labs at Indiana
+ University. For technical information contact Andrew Lumsdaine
+ at the Pervasive Technology Labs at Indiana University. For
+ administrative and license questions contact the Advanced
+ Research and Technology Institute at 351 West 10th Street.
+ Indianapolis, Indiana 46202, phone 317-278-4100, fax
+ 317-274-5902.</para>
+
+ <para>Some concepts based on versions from the MTL draft manual
+ and Boost Graph and Property Map documentation, the SGI Standard
+ Template Library documentation and the Hewlett-Packard STL,
+ under the following license:
+ <blockquote><simpara>Permission to use, copy, modify, distribute and
+ sell this software and its documentation for any purpose is
+ hereby granted without fee, provided that the above copyright
+ notice appears in all copies and that both that copyright
+ notice and this permission notice appear in supporting
+ documentation. Silicon Graphics makes no representations
+ about the suitability of this software for any purpose. It is
+ provided "as is" without express or implied
+ warranty.</simpara></blockquote></para>
+ </legalnotice>
+ </sectioninfo>
+ <title>Concept reference</title>
+
+ <xi:include href="Assignable.xml"/>
+ <xi:include href="InputIterator.xml"/>
+ <xi:include href="OutputIterator.xml"/>
+ <xi:include href="ForwardIterator.xml"/>
+ <xi:include href="BidirectionalIterator.xml"/>
+ <xi:include href="RandomAccessIterator.xml"/>
+ <xi:include href="DefaultConstructible.xml"/>
+ <xi:include href="CopyConstructible.xml"/>
+ <xi:include href="EqualityComparable.xml"/>
+ <xi:include href="LessThanComparable.xml"/>
+ <xi:include href="SignedInteger.xml"/>
+</library-reference>
diff --git a/implementation.htm b/implementation.htm
new file mode 100644
index 0000000..008fbed
--- /dev/null
+++ b/implementation.htm
@@ -0,0 +1,205 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
+ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
+
+<html xmlns="http://www.w3.org/1999/xhtml">
+<!-- Copyright (c) Jeremy Siek and Andrew Lumsdaine 2000, David Abrahams 2007 -->
+<!-- Distributed under the Boost -->
+<!-- Software License, Version 1.0. (See accompanying -->
+<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
+
+<head>
+ <meta name="generator" content=
+ "HTML Tidy for Linux/x86 (vers 1 September 2005), see www.w3.org" />
+ <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
+ <link rel="stylesheet" href="../../rst.css" type="text/css" />
+
+ <title>Concept Checking Implementation</title>
+</head>
+
+<body bgcolor="#FFFFFF" link="#0000EE" text="#000000" vlink="#551A8B" alink=
+"#FF0000">
+ <img src="../../boost.png" alt="C++ Boost" width="277" height=
+ "86" /><br clear="none" />
+
+ <h2><a name="warning" id="warning"><font color=
+ "red">Warning</font></a></h2>
+
+ <p><font color="red">This documentation is out-of-date; similar but
+ newer implementation techniques are now used. This documentation
+ also refers to components and protocols in the library's old
+ interace such as <code>BOOST_CLASS_REQUIRES</code>
+ and <code>constraints()</code> functions, which are still supported
+ but deprecated.</font></p>
+
+ <h2><a name="implementation" id="implementation">Implementation</a></h2>
+
+ <p>Ideally we would like to catch, and indicate, the concept violation at
+ the point of instantiation. As mentioned in D&E[<a href=
+ "bibliography.htm#stroustrup94:_design_evolution">2</a>], the error can be
+ caught by exercising all of the requirements needed by the function
+ template. Exactly how the requirements (the valid expressions in
+ particular) are exercised is a tricky issue, since we want the code to be
+ compiled—<i>but not executed</i>. Our approach is to exercise the
+ requirements in a separate function that is assigned to a function pointer.
+ In this case, the compiler will instantiate the function but will not
+ actually invoke it. In addition, an optimizing compiler will remove the
+ pointer assignment as ``dead code'' (though the run-time overhead added by
+ the assignment would be trivial in any case). It might be conceivable for a
+ compiler to skip the semantic analysis and compilation of the constraints
+ function in the first place, which would make our function pointer
+ technique ineffective. However, this is unlikely because removal of
+ unnecessary code and functions is typically done in later stages of a
+ compiler. We have successfully used the function pointer technique with GNU
+ C++, Microsoft Visual C++, and several EDG-based compilers (KAI C++, SGI
+ MIPSpro). The following code shows how this technique can be applied to the
+ <tt>std::stable_sort()</tt> function:</p>
+ <pre>
+ template <class RandomAccessIterator>
+ void stable_sort_constraints(RandomAccessIterator i)
+ {
+ typename std::iterator_traits<RandomAccessIterator>
+ ::difference_type n;
+ i += n; // exercise the requirements for RandomAccessIterator
+ ...
+ }
+ template <class RandomAccessIterator>
+ void stable_sort(RandomAccessIterator first, RandomAccessIterator last)
+ {
+ typedef void (*fptr_type)(RandomAccessIterator);
+ fptr_type x = &stable_sort_constraints;
+ ...
+ }
+</pre>
+
+ <p>There is often a large set of requirements that need to be checked, and
+ it would be cumbersome for the library implementor to write constraint
+ functions like <tt>stable_sort_constraints()</tt> for every public
+ function. Instead, we group sets of valid expressions together, according
+ to the definitions of the corresponding concepts. For each concept we
+ define a concept checking class template where the template parameter is
+ for the type to be checked. The class contains a <tt>contraints()</tt>
+ member function which exercises all of the valid expressions of the
+ concept. The objects used in the constraints function, such as <tt>n</tt>
+ and <tt>i</tt>, are declared as data members of the concept checking
+ class.</p>
+ <pre>
+ template <class Iter>
+ struct RandomAccessIteratorConcept
+ {
+ void constraints()
+ {
+ i += n;
+ ...
+ }
+ typename std::iterator_traits<RandomAccessIterator>
+ ::difference_type n;
+ Iter i;
+ ...
+ };
+</pre>
+
+ <p>We can still use the function pointer mechanism to cause instantiation
+ of the constraints function, however now it will be a member function
+ pointer. To make it easy for the library implementor to invoke the concept
+ checks, we wrap the member function pointer mechanism in a function named
+ <tt>function_requires()</tt>. The following code snippet shows how to use
+ <tt>function_requires()</tt> to make sure that the iterator is a <a href=
+ "http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>.</p>
+ <pre>
+ template <class Iter>
+ void stable_sort(Iter first, Iter last)
+ {
+ function_requires< RandomAccessIteratorConcept<Iter> >();
+ ...
+ }
+</pre>
+
+ <p>The definition of the <tt>function_requires()</tt> is as follows. The
+ <tt>Concept</tt> is the concept checking class that has been instantiated
+ with the modeling type. We assign the address of the constraints member
+ function to the function pointer <tt>x</tt>, which causes the instantiation
+ of the constraints function and checking of the concept's valid
+ expressions. We then assign <tt>x</tt> to <tt>x</tt> to avoid unused
+ variable compiler warnings, and wrap everything in a do-while loop to
+ prevent name collisions.</p>
+ <pre>
+ template <class Concept>
+ void function_requires()
+ {
+ void (Concept::*x)() = BOOST_FPTR Concept::constraints;
+ ignore_unused_variable_warning(x);
+ }
+</pre>
+
+ <p>To check the type parameters of class templates, we provide the
+ <tt>BOOST_CLASS_REQUIRE</tt> macro which can be used inside the body of a
+ class definition (whereas <tt>function_requires()</tt> can only be used
+ inside of a function body). This macro declares a nested class template,
+ where the template parameter is a function pointer. We then use the nested
+ class type in a typedef with the function pointer type of the constraint
+ function as the template argument. We use the <tt>type_var</tt> and
+ <tt>concept</tt> names in the nested class and typedef names to help
+ prevent name collisions.</p>
+ <pre>
+#define BOOST_CLASS_REQUIRE(type_var, ns, concept) \
+ typedef void (ns::concept <type_var>::* func##type_var##concept)(); \
+ template <func##type_var##concept _Tp1> \
+ struct concept_checking_##type_var##concept { }; \
+ typedef concept_checking_##type_var##concept< \
+ BOOST_FPTR ns::concept<type_var>::constraints> \
+ concept_checking_typedef_##type_var##concept
+</pre>
+
+ <p>In addition, there are versions of <tt>BOOST_CLASS_REQUIRE</tt> that
+ take more arguments, to handle concepts that include interactions between
+ two or more types. <tt>BOOST_CLASS_REQUIRE</tt> was not used in the
+ implementation of the BCCL concept checks because some compilers do not
+ implement template parameters of function pointer type.
+ <!-- We decided not to go with this version since it is easier to misuse
+
+To check the type parameters of class templates, we provide the
+<tt>class_requires</tt> class which can be used inside the body of a
+class definition (whereas <tt>function_requires()</tt> can only be
+used inside of a function body). <tt>class_requires</tt> declares a
+nested class template, where the template parameter is a function
+pointer. We then use the nested class type in a typedef with the
+function pointer type of the constraint function as the template
+argument.
+
+<pre>
+ template <class Concept>
+ class class_requires
+ {
+ typedef void (Concept::* function_pointer)();
+
+ template <function_pointer Fptr>
+ struct dummy_struct { };
+ public:
+ typedef dummy_struct< BOOST_FPTR Concept::constraints > check;
+ };
+</pre>
+
+<tt>class_requires</tt> was not used in the implementation of the
+Boost Concept Checking Library concept checks because several
+compilers do not implement template parameters of function pointer
+type.
+
+--></p>
+
+ <p><a href="./reference.htm">Next: Reference</a><br />
+ <a href="prog_with_concepts.htm">Prev: Programming With
+ Concepts</a><br /></p>
+ <hr />
+
+ <table>
+ <tr valign="top">
+ <td nowrap="nowrap">Copyright © 2000</td>
+
+ <td><a href="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</a>(<a href=
+ "mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</a>) Andrew
+ Lumsdaine(<a href="mailto:lums@osl.iu.edu">lums@osl.iu.edu</a>),
+ 2007 <a href="mailto:dave@boost-consulting.com">David Abrahams</a>.
+ </tr>
+ </table>
+</body>
+</html>
diff --git a/include/boost/concept/assert.hpp b/include/boost/concept/assert.hpp
new file mode 100644
index 0000000..cf98179
--- /dev/null
+++ b/include/boost/concept/assert.hpp
@@ -0,0 +1,45 @@
+// Copyright David Abrahams 2006. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+#ifndef BOOST_CONCEPT_ASSERT_DWA2006430_HPP
+# define BOOST_CONCEPT_ASSERT_DWA2006430_HPP
+
+# include <boost/config.hpp>
+# include <boost/detail/workaround.hpp>
+
+// The old protocol used a constraints() member function in concept
+// checking classes. If the compiler supports SFINAE, we can detect
+// that function and seamlessly support the old concept checking
+// classes. In this release, backward compatibility with the old
+// concept checking classes is enabled by default, where available.
+// The old protocol is deprecated, though, and backward compatibility
+// will no longer be the default in the next release.
+
+# if !defined(BOOST_NO_OLD_CONCEPT_SUPPORT) \
+ && !defined(BOOST_NO_SFINAE) \
+ \
+ && !(BOOST_WORKAROUND(__GNUC__, == 3) && BOOST_WORKAROUND(__GNUC_MINOR__, < 4))
+
+// Note: gcc-2.96 through 3.3.x have some SFINAE, but no ability to
+// check for the presence of particularmember functions.
+
+# define BOOST_OLD_CONCEPT_SUPPORT
+
+# endif
+
+# ifdef BOOST_MSVC
+# include <boost/concept/detail/msvc.hpp>
+# elif BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
+# include <boost/concept/detail/borland.hpp>
+# else
+# include <boost/concept/detail/general.hpp>
+# endif
+
+ // Usage, in class or function context:
+ //
+ // BOOST_CONCEPT_ASSERT((UnaryFunctionConcept<F,bool,int>));
+ //
+# define BOOST_CONCEPT_ASSERT(ModelInParens) \
+ BOOST_CONCEPT_ASSERT_FN(void(*)ModelInParens)
+
+#endif // BOOST_CONCEPT_ASSERT_DWA2006430_HPP
diff --git a/include/boost/concept/detail/backward_compatibility.hpp b/include/boost/concept/detail/backward_compatibility.hpp
new file mode 100644
index 0000000..66d573e
--- /dev/null
+++ b/include/boost/concept/detail/backward_compatibility.hpp
@@ -0,0 +1,16 @@
+// Copyright David Abrahams 2009. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+#ifndef BOOST_CONCEPT_BACKWARD_COMPATIBILITY_DWA200968_HPP
+# define BOOST_CONCEPT_BACKWARD_COMPATIBILITY_DWA200968_HPP
+
+namespace boost
+{
+ namespace concepts {}
+
+# if defined(BOOST_HAS_CONCEPTS) && !defined(BOOST_CONCEPT_NO_BACKWARD_KEYWORD)
+ namespace concept = concepts;
+# endif
+} // namespace boost::concept
+
+#endif // BOOST_CONCEPT_BACKWARD_COMPATIBILITY_DWA200968_HPP
diff --git a/include/boost/concept/detail/borland.hpp b/include/boost/concept/detail/borland.hpp
new file mode 100644
index 0000000..300d5d4
--- /dev/null
+++ b/include/boost/concept/detail/borland.hpp
@@ -0,0 +1,30 @@
+// Copyright David Abrahams 2006. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+#ifndef BOOST_CONCEPT_DETAIL_BORLAND_DWA2006429_HPP
+# define BOOST_CONCEPT_DETAIL_BORLAND_DWA2006429_HPP
+
+# include <boost/preprocessor/cat.hpp>
+# include <boost/concept/detail/backward_compatibility.hpp>
+
+namespace boost { namespace concepts {
+
+template <class ModelFnPtr>
+struct require;
+
+template <class Model>
+struct require<void(*)(Model)>
+{
+ enum { instantiate = sizeof((((Model*)0)->~Model()), 3) };
+};
+
+# define BOOST_CONCEPT_ASSERT_FN( ModelFnPtr ) \
+ enum \
+ { \
+ BOOST_PP_CAT(boost_concept_check,__LINE__) = \
+ boost::concepts::require<ModelFnPtr>::instantiate \
+ }
+
+}} // namespace boost::concept
+
+#endif // BOOST_CONCEPT_DETAIL_BORLAND_DWA2006429_HPP
diff --git a/include/boost/concept/detail/concept_def.hpp b/include/boost/concept/detail/concept_def.hpp
new file mode 100644
index 0000000..750561e
--- /dev/null
+++ b/include/boost/concept/detail/concept_def.hpp
@@ -0,0 +1,34 @@
+// Copyright David Abrahams 2006. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+#ifndef BOOST_CONCEPT_DETAIL_CONCEPT_DEF_DWA200651_HPP
+# define BOOST_CONCEPT_DETAIL_CONCEPT_DEF_DWA200651_HPP
+# include <boost/preprocessor/seq/for_each_i.hpp>
+# include <boost/preprocessor/seq/enum.hpp>
+# include <boost/preprocessor/comma_if.hpp>
+# include <boost/preprocessor/cat.hpp>
+#endif // BOOST_CONCEPT_DETAIL_CONCEPT_DEF_DWA200651_HPP
+
+// BOOST_concept(SomeName, (p1)(p2)...(pN))
+//
+// Expands to "template <class p1, class p2, ...class pN> struct SomeName"
+//
+// Also defines an equivalent SomeNameConcept for backward compatibility.
+// Maybe in the next release we can kill off the "Concept" suffix for good.
+# define BOOST_concept(name, params) \
+ template < BOOST_PP_SEQ_FOR_EACH_I(BOOST_CONCEPT_typename,~,params) > \
+ struct name; /* forward declaration */ \
+ \
+ template < BOOST_PP_SEQ_FOR_EACH_I(BOOST_CONCEPT_typename,~,params) > \
+ struct BOOST_PP_CAT(name,Concept) \
+ : name< BOOST_PP_SEQ_ENUM(params) > \
+ { \
+ }; \
+ \
+ template < BOOST_PP_SEQ_FOR_EACH_I(BOOST_CONCEPT_typename,~,params) > \
+ struct name
+
+// Helper for BOOST_concept, above.
+# define BOOST_CONCEPT_typename(r, ignored, index, t) \
+ BOOST_PP_COMMA_IF(index) typename t
+
diff --git a/include/boost/concept/detail/concept_undef.hpp b/include/boost/concept/detail/concept_undef.hpp
new file mode 100644
index 0000000..713db89
--- /dev/null
+++ b/include/boost/concept/detail/concept_undef.hpp
@@ -0,0 +1,5 @@
+// Copyright David Abrahams 2006. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+# undef BOOST_concept_typename
+# undef BOOST_concept
diff --git a/include/boost/concept/detail/general.hpp b/include/boost/concept/detail/general.hpp
new file mode 100644
index 0000000..525ea65
--- /dev/null
+++ b/include/boost/concept/detail/general.hpp
@@ -0,0 +1,77 @@
+// Copyright David Abrahams 2006. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+#ifndef BOOST_CONCEPT_DETAIL_GENERAL_DWA2006429_HPP
+# define BOOST_CONCEPT_DETAIL_GENERAL_DWA2006429_HPP
+
+# include <boost/config.hpp>
+# include <boost/preprocessor/cat.hpp>
+# include <boost/concept/detail/backward_compatibility.hpp>
+
+# ifdef BOOST_OLD_CONCEPT_SUPPORT
+# include <boost/concept/detail/has_constraints.hpp>
+# include <boost/mpl/if.hpp>
+# endif
+
+// This implementation works on Comeau and GCC, all the way back to
+// 2.95
+namespace boost { namespace concepts {
+
+template <class ModelFn>
+struct requirement_;
+
+namespace detail
+{
+ template <void(*)()> struct instantiate {};
+}
+
+template <class Model>
+struct requirement
+{
+ static void failed() { ((Model*)0)->~Model(); }
+};
+
+struct failed {};
+
+template <class Model>
+struct requirement<failed ************ Model::************>
+{
+ static void failed() { ((Model*)0)->~Model(); }
+};
+
+# ifdef BOOST_OLD_CONCEPT_SUPPORT
+
+template <class Model>
+struct constraint
+{
+ static void failed() { ((Model*)0)->constraints(); }
+};
+
+template <class Model>
+struct requirement_<void(*)(Model)>
+ : mpl::if_<
+ concepts::not_satisfied<Model>
+ , constraint<Model>
+ , requirement<failed ************ Model::************>
+ >::type
+{};
+
+# else
+
+// For GCC-2.x, these can't have exactly the same name
+template <class Model>
+struct requirement_<void(*)(Model)>
+ : requirement<failed ************ Model::************>
+{};
+
+# endif
+
+# define BOOST_CONCEPT_ASSERT_FN( ModelFnPtr ) \
+ typedef ::boost::concepts::detail::instantiate< \
+ &::boost::concepts::requirement_<ModelFnPtr>::failed> \
+ BOOST_PP_CAT(boost_concept_check,__LINE__) \
+ BOOST_ATTRIBUTE_UNUSED
+
+}}
+
+#endif // BOOST_CONCEPT_DETAIL_GENERAL_DWA2006429_HPP
diff --git a/include/boost/concept/detail/has_constraints.hpp b/include/boost/concept/detail/has_constraints.hpp
new file mode 100644
index 0000000..a309db3
--- /dev/null
+++ b/include/boost/concept/detail/has_constraints.hpp
@@ -0,0 +1,50 @@
+// Copyright David Abrahams 2006. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+#ifndef BOOST_CONCEPT_DETAIL_HAS_CONSTRAINTS_DWA2006429_HPP
+# define BOOST_CONCEPT_DETAIL_HAS_CONSTRAINTS_DWA2006429_HPP
+
+# include <boost/mpl/bool.hpp>
+# include <boost/detail/workaround.hpp>
+# include <boost/concept/detail/backward_compatibility.hpp>
+
+namespace boost { namespace concepts {
+
+namespace detail
+{
+
+// Here we implement the metafunction that detects whether a
+// constraints metafunction exists
+ typedef char yes;
+ typedef char (&no)[2];
+
+ template <class Model, void (Model::*)()>
+ struct wrap_constraints {};
+
+#if BOOST_WORKAROUND(__SUNPRO_CC, <= 0x580) || defined(__CUDACC__)
+ // Work around the following bogus error in Sun Studio 11, by
+ // turning off the has_constraints function entirely:
+ // Error: complex expression not allowed in dependent template
+ // argument expression
+ inline no has_constraints_(...);
+#else
+ template <class Model>
+ inline yes has_constraints_(Model*, wrap_constraints<Model,&Model::constraints>* = 0);
+ inline no has_constraints_(...);
+#endif
+}
+
+// This would be called "detail::has_constraints," but it has a strong
+// tendency to show up in error messages.
+template <class Model>
+struct not_satisfied
+{
+ BOOST_STATIC_CONSTANT(
+ bool
+ , value = sizeof( detail::has_constraints_((Model*)0) ) == sizeof(detail::yes) );
+ typedef mpl::bool_<value> type;
+};
+
+}} // namespace boost::concepts::detail
+
+#endif // BOOST_CONCEPT_DETAIL_HAS_CONSTRAINTS_DWA2006429_HPP
diff --git a/include/boost/concept/detail/msvc.hpp b/include/boost/concept/detail/msvc.hpp
new file mode 100644
index 0000000..078dd22
--- /dev/null
+++ b/include/boost/concept/detail/msvc.hpp
@@ -0,0 +1,123 @@
+// Copyright David Abrahams 2006. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+#ifndef BOOST_CONCEPT_CHECK_MSVC_DWA2006429_HPP
+# define BOOST_CONCEPT_CHECK_MSVC_DWA2006429_HPP
+
+# include <boost/preprocessor/cat.hpp>
+# include <boost/concept/detail/backward_compatibility.hpp>
+# include <boost/config.hpp>
+
+# ifdef BOOST_OLD_CONCEPT_SUPPORT
+# include <boost/concept/detail/has_constraints.hpp>
+# include <boost/mpl/if.hpp>
+# endif
+
+# ifdef BOOST_MSVC
+# pragma warning(push)
+# pragma warning(disable:4100)
+# endif
+
+namespace boost { namespace concepts {
+
+
+template <class Model>
+struct check
+{
+ virtual void failed(Model* x)
+ {
+ x->~Model();
+ }
+};
+
+# ifndef BOOST_NO_PARTIAL_SPECIALIZATION
+struct failed {};
+template <class Model>
+struct check<failed ************ Model::************>
+{
+ virtual void failed(Model* x)
+ {
+ x->~Model();
+ }
+};
+# endif
+
+# ifdef BOOST_OLD_CONCEPT_SUPPORT
+
+namespace detail
+{
+ // No need for a virtual function here, since evaluating
+ // not_satisfied below will have already instantiated the
+ // constraints() member.
+ struct constraint {};
+}
+
+template <class Model>
+struct require
+ : mpl::if_c<
+ not_satisfied<Model>::value
+ , detail::constraint
+# ifndef BOOST_NO_PARTIAL_SPECIALIZATION
+ , check<Model>
+# else
+ , check<failed ************ Model::************>
+# endif
+ >::type
+{};
+
+# else
+
+template <class Model>
+struct require
+# ifndef BOOST_NO_PARTIAL_SPECIALIZATION
+ : check<Model>
+# else
+ : check<failed ************ Model::************>
+# endif
+{};
+
+# endif
+
+# if BOOST_WORKAROUND(BOOST_MSVC, == 1310)
+
+//
+// The iterator library sees some really strange errors unless we
+// do things this way.
+//
+template <class Model>
+struct require<void(*)(Model)>
+{
+ virtual void failed(Model*)
+ {
+ require<Model>();
+ }
+};
+
+# define BOOST_CONCEPT_ASSERT_FN( ModelFnPtr ) \
+enum \
+{ \
+ BOOST_PP_CAT(boost_concept_check,__LINE__) = \
+ sizeof(::boost::concepts::require<ModelFnPtr>) \
+}
+
+# else // Not vc-7.1
+
+template <class Model>
+require<Model>
+require_(void(*)(Model));
+
+# define BOOST_CONCEPT_ASSERT_FN( ModelFnPtr ) \
+enum \
+{ \
+ BOOST_PP_CAT(boost_concept_check,__LINE__) = \
+ sizeof(::boost::concepts::require_((ModelFnPtr)0)) \
+}
+
+# endif
+}}
+
+# ifdef BOOST_MSVC
+# pragma warning(pop)
+# endif
+
+#endif // BOOST_CONCEPT_CHECK_MSVC_DWA2006429_HPP
diff --git a/include/boost/concept/requires.hpp b/include/boost/concept/requires.hpp
new file mode 100644
index 0000000..365ce10
--- /dev/null
+++ b/include/boost/concept/requires.hpp
@@ -0,0 +1,93 @@
+// Copyright David Abrahams 2006. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+#ifndef BOOST_CONCEPT_REQUIRES_DWA2006430_HPP
+# define BOOST_CONCEPT_REQUIRES_DWA2006430_HPP
+
+# include <boost/config.hpp>
+# include <boost/concept/assert.hpp>
+# include <boost/preprocessor/seq/for_each.hpp>
+
+namespace boost {
+
+// unaryfunptr_arg_type from parameter/aux_/parenthesized_type.hpp
+
+namespace ccheck_aux {
+
+// A metafunction that transforms void(*)(T) -> T
+template <class UnaryFunctionPointer>
+struct unaryfunptr_arg_type;
+
+template <class Arg>
+struct unaryfunptr_arg_type<void(*)(Arg)>
+{
+ typedef Arg type;
+};
+
+template <>
+struct unaryfunptr_arg_type<void(*)(void)>
+{
+ typedef void type;
+};
+
+} // namespace ccheck_aux
+
+// Template for use in handwritten assertions
+template <class Model, class More>
+struct requires_ : More
+{
+ BOOST_CONCEPT_ASSERT((Model));
+};
+
+// Template for use by macros, where models must be wrapped in parens.
+// This isn't in namespace detail to keep extra cruft out of resulting
+// error messages.
+template <class ModelFn>
+struct _requires_
+{
+ enum { value = 0 };
+ BOOST_CONCEPT_ASSERT_FN(ModelFn);
+};
+
+template <int check, class Result>
+struct Requires_ : ::boost::ccheck_aux::unaryfunptr_arg_type<Result>
+{
+};
+
+# if BOOST_WORKAROUND(BOOST_INTEL_WIN, BOOST_TESTED_AT(1010))
+# define BOOST_CONCEPT_REQUIRES_(r,data,t) | (::boost::_requires_<void(*)t>::value)
+# else
+# define BOOST_CONCEPT_REQUIRES_(r,data,t) + (::boost::_requires_<void(*)t>::value)
+# endif
+
+#if defined(NDEBUG)
+
+# define BOOST_CONCEPT_REQUIRES(models, result) \
+ typename ::boost::ccheck_aux::unaryfunptr_arg_type<void(*)result>::type
+
+#elif BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
+
+// Same thing as below without the initial typename
+# define BOOST_CONCEPT_REQUIRES(models, result) \
+ ::boost::Requires_< \
+ (0 BOOST_PP_SEQ_FOR_EACH(BOOST_CONCEPT_REQUIRES_, ~, models)), \
+ ::boost::ccheck_aux::unaryfunptr_arg_type<void(*)result> \
+ >::type
+
+#else
+
+// This just ICEs on MSVC6 :(
+# define BOOST_CONCEPT_REQUIRES(models, result) \
+ typename ::boost::Requires_< \
+ (0 BOOST_PP_SEQ_FOR_EACH(BOOST_CONCEPT_REQUIRES_, ~, models)), \
+ void(*)result \
+ >::type
+
+#endif
+
+// C++0x proposed syntax changed. This supports an older usage
+#define BOOST_CONCEPT_WHERE(models,result) BOOST_CONCEPT_REQUIRES(models,result)
+
+} // namespace boost::concept_check
+
+#endif // BOOST_CONCEPT_REQUIRES_DWA2006430_HPP
diff --git a/include/boost/concept/usage.hpp b/include/boost/concept/usage.hpp
new file mode 100644
index 0000000..e73370f
--- /dev/null
+++ b/include/boost/concept/usage.hpp
@@ -0,0 +1,36 @@
+// Copyright David Abrahams 2006. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+#ifndef BOOST_CONCEPT_USAGE_DWA2006919_HPP
+# define BOOST_CONCEPT_USAGE_DWA2006919_HPP
+
+# include <boost/concept/assert.hpp>
+# include <boost/detail/workaround.hpp>
+# include <boost/concept/detail/backward_compatibility.hpp>
+
+namespace boost { namespace concepts {
+
+template <class Model>
+struct usage_requirements
+{
+ ~usage_requirements() { ((Model*)0)->~Model(); }
+};
+
+# if BOOST_WORKAROUND(__GNUC__, <= 3)
+
+# define BOOST_CONCEPT_USAGE(model) \
+ model(); /* at least 2.96 and 3.4.3 both need this :( */ \
+ BOOST_CONCEPT_ASSERT((boost::concepts::usage_requirements<model>)); \
+ ~model()
+
+# else
+
+# define BOOST_CONCEPT_USAGE(model) \
+ BOOST_CONCEPT_ASSERT((boost::concepts::usage_requirements<model>)); \
+ ~model()
+
+# endif
+
+}} // namespace boost::concepts
+
+#endif // BOOST_CONCEPT_USAGE_DWA2006919_HPP
diff --git a/include/boost/concept_archetype.hpp b/include/boost/concept_archetype.hpp
new file mode 100644
index 0000000..f2455fd
--- /dev/null
+++ b/include/boost/concept_archetype.hpp
@@ -0,0 +1,670 @@
+//
+// (C) Copyright Jeremy Siek 2000.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//
+// Revision History:
+//
+// 17 July 2001: Added const to some member functions. (Jeremy Siek)
+// 05 May 2001: Removed static dummy_cons object. (Jeremy Siek)
+
+// See http://www.boost.org/libs/concept_check for documentation.
+
+#ifndef BOOST_CONCEPT_ARCHETYPES_HPP
+#define BOOST_CONCEPT_ARCHETYPES_HPP
+
+#include <boost/config.hpp>
+#include <boost/mpl/identity.hpp>
+#include <functional>
+#include <iterator> // iterator tags
+#include <cstddef> // std::ptrdiff_t
+
+namespace boost {
+
+ //===========================================================================
+ // Basic Archetype Classes
+
+ namespace detail {
+ class dummy_constructor { };
+ }
+
+ // A type that models no concept. The template parameter
+ // is only there so that null_archetype types can be created
+ // that have different type.
+ template <class T = int>
+ class null_archetype {
+ private:
+ null_archetype() { }
+ null_archetype(const null_archetype&) { }
+ null_archetype& operator=(const null_archetype&) { return *this; }
+ public:
+ null_archetype(detail::dummy_constructor) { }
+#ifndef __MWERKS__
+ template <class TT>
+ friend void dummy_friend(); // just to avoid warnings
+#endif
+ };
+
+ // This is a helper class that provides a way to get a reference to
+ // an object. The get() function will never be called at run-time
+ // (nothing in this file will) so this seemingly very bad function
+ // is really quite innocent. The name of this class needs to be
+ // changed.
+ template <class T>
+ class static_object
+ {
+ public:
+ static T& get()
+ {
+#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564))
+ return *reinterpret_cast<T*>(0);
+#else
+ static char d[sizeof(T)];
+ return *reinterpret_cast<T*>(d);
+#endif
+ }
+ };
+
+ template <class Base = null_archetype<> >
+ class default_constructible_archetype : public Base {
+ public:
+ default_constructible_archetype()
+ : Base(static_object<detail::dummy_constructor>::get()) { }
+ default_constructible_archetype(detail::dummy_constructor x) : Base(x) { }
+ };
+
+ template <class Base = null_archetype<> >
+ class assignable_archetype : public Base {
+ assignable_archetype() { }
+ assignable_archetype(const assignable_archetype&) { }
+ public:
+ assignable_archetype& operator=(const assignable_archetype&) {
+ return *this;
+ }
+ assignable_archetype(detail::dummy_constructor x) : Base(x) { }
+ };
+
+ template <class Base = null_archetype<> >
+ class copy_constructible_archetype : public Base {
+ public:
+ copy_constructible_archetype()
+ : Base(static_object<detail::dummy_constructor>::get()) { }
+ copy_constructible_archetype(const copy_constructible_archetype&)
+ : Base(static_object<detail::dummy_constructor>::get()) { }
+ copy_constructible_archetype(detail::dummy_constructor x) : Base(x) { }
+ };
+
+ template <class Base = null_archetype<> >
+ class sgi_assignable_archetype : public Base {
+ public:
+ sgi_assignable_archetype(const sgi_assignable_archetype&)
+ : Base(static_object<detail::dummy_constructor>::get()) { }
+ sgi_assignable_archetype& operator=(const sgi_assignable_archetype&) {
+ return *this;
+ }
+ sgi_assignable_archetype(const detail::dummy_constructor& x) : Base(x) { }
+ };
+
+ struct default_archetype_base {
+ default_archetype_base(detail::dummy_constructor) { }
+ };
+
+ // Careful, don't use same type for T and Base. That results in the
+ // conversion operator being invalid. Since T is often
+ // null_archetype, can't use null_archetype for Base.
+ template <class T, class Base = default_archetype_base>
+ class convertible_to_archetype : public Base {
+ private:
+ convertible_to_archetype() { }
+ convertible_to_archetype(const convertible_to_archetype& ) { }
+ convertible_to_archetype& operator=(const convertible_to_archetype&)
+ { return *this; }
+ public:
+ convertible_to_archetype(detail::dummy_constructor x) : Base(x) { }
+ operator const T&() const { return static_object<T>::get(); }
+ };
+
+ template <class T, class Base = default_archetype_base>
+ class convertible_from_archetype : public Base {
+ private:
+ convertible_from_archetype() { }
+ convertible_from_archetype(const convertible_from_archetype& ) { }
+ convertible_from_archetype& operator=(const convertible_from_archetype&)
+ { return *this; }
+ public:
+ convertible_from_archetype(detail::dummy_constructor x) : Base(x) { }
+ convertible_from_archetype(const T&) { }
+ convertible_from_archetype& operator=(const T&)
+ { return *this; }
+ };
+
+ class boolean_archetype {
+ public:
+ boolean_archetype(const boolean_archetype&) { }
+ operator bool() const { return true; }
+ boolean_archetype(detail::dummy_constructor) { }
+ private:
+ boolean_archetype() { }
+ boolean_archetype& operator=(const boolean_archetype&) { return *this; }
+ };
+
+ template <class Base = null_archetype<> >
+ class equality_comparable_archetype : public Base {
+ public:
+ equality_comparable_archetype(detail::dummy_constructor x) : Base(x) { }
+ };
+ template <class Base>
+ boolean_archetype
+ operator==(const equality_comparable_archetype<Base>&,
+ const equality_comparable_archetype<Base>&)
+ {
+ return boolean_archetype(static_object<detail::dummy_constructor>::get());
+ }
+ template <class Base>
+ boolean_archetype
+ operator!=(const equality_comparable_archetype<Base>&,
+ const equality_comparable_archetype<Base>&)
+ {
+ return boolean_archetype(static_object<detail::dummy_constructor>::get());
+ }
+
+
+ template <class Base = null_archetype<> >
+ class equality_comparable2_first_archetype : public Base {
+ public:
+ equality_comparable2_first_archetype(detail::dummy_constructor x)
+ : Base(x) { }
+ };
+ template <class Base = null_archetype<> >
+ class equality_comparable2_second_archetype : public Base {
+ public:
+ equality_comparable2_second_archetype(detail::dummy_constructor x)
+ : Base(x) { }
+ };
+ template <class Base1, class Base2>
+ boolean_archetype
+ operator==(const equality_comparable2_first_archetype<Base1>&,
+ const equality_comparable2_second_archetype<Base2>&)
+ {
+ return boolean_archetype(static_object<detail::dummy_constructor>::get());
+ }
+ template <class Base1, class Base2>
+ boolean_archetype
+ operator!=(const equality_comparable2_first_archetype<Base1>&,
+ const equality_comparable2_second_archetype<Base2>&)
+ {
+ return boolean_archetype(static_object<detail::dummy_constructor>::get());
+ }
+
+
+ template <class Base = null_archetype<> >
+ class less_than_comparable_archetype : public Base {
+ public:
+ less_than_comparable_archetype(detail::dummy_constructor x) : Base(x) { }
+ };
+ template <class Base>
+ boolean_archetype
+ operator<(const less_than_comparable_archetype<Base>&,
+ const less_than_comparable_archetype<Base>&)
+ {
+ return boolean_archetype(static_object<detail::dummy_constructor>::get());
+ }
+
+
+
+ template <class Base = null_archetype<> >
+ class comparable_archetype : public Base {
+ public:
+ comparable_archetype(detail::dummy_constructor x) : Base(x) { }
+ };
+ template <class Base>
+ boolean_archetype
+ operator<(const comparable_archetype<Base>&,
+ const comparable_archetype<Base>&)
+ {
+ return boolean_archetype(static_object<detail::dummy_constructor>::get());
+ }
+ template <class Base>
+ boolean_archetype
+ operator<=(const comparable_archetype<Base>&,
+ const comparable_archetype<Base>&)
+ {
+ return boolean_archetype(static_object<detail::dummy_constructor>::get());
+ }
+ template <class Base>
+ boolean_archetype
+ operator>(const comparable_archetype<Base>&,
+ const comparable_archetype<Base>&)
+ {
+ return boolean_archetype(static_object<detail::dummy_constructor>::get());
+ }
+ template <class Base>
+ boolean_archetype
+ operator>=(const comparable_archetype<Base>&,
+ const comparable_archetype<Base>&)
+ {
+ return boolean_archetype(static_object<detail::dummy_constructor>::get());
+ }
+
+
+ // The purpose of the optags is so that one can specify
+ // exactly which types the operator< is defined between.
+ // This is useful for allowing the operations:
+ //
+ // A a; B b;
+ // a < b
+ // b < a
+ //
+ // without also allowing the combinations:
+ //
+ // a < a
+ // b < b
+ //
+ struct optag1 { };
+ struct optag2 { };
+ struct optag3 { };
+
+#define BOOST_DEFINE_BINARY_PREDICATE_ARCHETYPE(OP, NAME) \
+ template <class Base = null_archetype<>, class Tag = optag1 > \
+ class NAME##_first_archetype : public Base { \
+ public: \
+ NAME##_first_archetype(detail::dummy_constructor x) : Base(x) { } \
+ }; \
+ \
+ template <class Base = null_archetype<>, class Tag = optag1 > \
+ class NAME##_second_archetype : public Base { \
+ public: \
+ NAME##_second_archetype(detail::dummy_constructor x) : Base(x) { } \
+ }; \
+ \
+ template <class BaseFirst, class BaseSecond, class Tag> \
+ boolean_archetype \
+ operator OP (const NAME##_first_archetype<BaseFirst, Tag>&, \
+ const NAME##_second_archetype<BaseSecond, Tag>&) \
+ { \
+ return boolean_archetype(static_object<detail::dummy_constructor>::get()); \
+ }
+
+ BOOST_DEFINE_BINARY_PREDICATE_ARCHETYPE(==, equal_op)
+ BOOST_DEFINE_BINARY_PREDICATE_ARCHETYPE(!=, not_equal_op)
+ BOOST_DEFINE_BINARY_PREDICATE_ARCHETYPE(<, less_than_op)
+ BOOST_DEFINE_BINARY_PREDICATE_ARCHETYPE(<=, less_equal_op)
+ BOOST_DEFINE_BINARY_PREDICATE_ARCHETYPE(>, greater_than_op)
+ BOOST_DEFINE_BINARY_PREDICATE_ARCHETYPE(>=, greater_equal_op)
+
+#define BOOST_DEFINE_OPERATOR_ARCHETYPE(OP, NAME) \
+ template <class Base = null_archetype<> > \
+ class NAME##_archetype : public Base { \
+ public: \
+ NAME##_archetype(detail::dummy_constructor x) : Base(x) { } \
+ NAME##_archetype(const NAME##_archetype&) \
+ : Base(static_object<detail::dummy_constructor>::get()) { } \
+ NAME##_archetype& operator=(const NAME##_archetype&) { return *this; } \
+ }; \
+ template <class Base> \
+ NAME##_archetype<Base> \
+ operator OP (const NAME##_archetype<Base>&,\
+ const NAME##_archetype<Base>&) \
+ { \
+ return \
+ NAME##_archetype<Base>(static_object<detail::dummy_constructor>::get()); \
+ }
+
+ BOOST_DEFINE_OPERATOR_ARCHETYPE(+, addable)
+ BOOST_DEFINE_OPERATOR_ARCHETYPE(-, subtractable)
+ BOOST_DEFINE_OPERATOR_ARCHETYPE(*, multipliable)
+ BOOST_DEFINE_OPERATOR_ARCHETYPE(/, dividable)
+ BOOST_DEFINE_OPERATOR_ARCHETYPE(%, modable)
+
+ // As is, these are useless because of the return type.
+ // Need to invent a better way...
+#define BOOST_DEFINE_BINARY_OPERATOR_ARCHETYPE(OP, NAME) \
+ template <class Return, class Base = null_archetype<> > \
+ class NAME##_first_archetype : public Base { \
+ public: \
+ NAME##_first_archetype(detail::dummy_constructor x) : Base(x) { } \
+ }; \
+ \
+ template <class Return, class Base = null_archetype<> > \
+ class NAME##_second_archetype : public Base { \
+ public: \
+ NAME##_second_archetype(detail::dummy_constructor x) : Base(x) { } \
+ }; \
+ \
+ template <class Return, class BaseFirst, class BaseSecond> \
+ Return \
+ operator OP (const NAME##_first_archetype<Return, BaseFirst>&, \
+ const NAME##_second_archetype<Return, BaseSecond>&) \
+ { \
+ return Return(static_object<detail::dummy_constructor>::get()); \
+ }
+
+ BOOST_DEFINE_BINARY_OPERATOR_ARCHETYPE(+, plus_op)
+ BOOST_DEFINE_BINARY_OPERATOR_ARCHETYPE(*, time_op)
+ BOOST_DEFINE_BINARY_OPERATOR_ARCHETYPE(/, divide_op)
+ BOOST_DEFINE_BINARY_OPERATOR_ARCHETYPE(-, subtract_op)
+ BOOST_DEFINE_BINARY_OPERATOR_ARCHETYPE(%, mod_op)
+
+ //===========================================================================
+ // Function Object Archetype Classes
+
+ template <class Return>
+ class generator_archetype {
+ public:
+ const Return& operator()() {
+ return static_object<Return>::get();
+ }
+ };
+
+ class void_generator_archetype {
+ public:
+ void operator()() { }
+ };
+
+ template <class Arg, class Return>
+ class unary_function_archetype {
+ private:
+ unary_function_archetype() { }
+ public:
+ unary_function_archetype(detail::dummy_constructor) { }
+ const Return& operator()(const Arg&) const {
+ return static_object<Return>::get();
+ }
+ };
+
+ template <class Arg1, class Arg2, class Return>
+ class binary_function_archetype {
+ private:
+ binary_function_archetype() { }
+ public:
+ binary_function_archetype(detail::dummy_constructor) { }
+ const Return& operator()(const Arg1&, const Arg2&) const {
+ return static_object<Return>::get();
+ }
+ };
+
+ template <class Arg>
+ class unary_predicate_archetype {
+ typedef boolean_archetype Return;
+ unary_predicate_archetype() { }
+ public:
+ unary_predicate_archetype(detail::dummy_constructor) { }
+ const Return& operator()(const Arg&) const {
+ return static_object<Return>::get();
+ }
+ };
+
+ template <class Arg1, class Arg2, class Base = null_archetype<> >
+ class binary_predicate_archetype {
+ typedef boolean_archetype Return;
+ binary_predicate_archetype() { }
+ public:
+ binary_predicate_archetype(detail::dummy_constructor) { }
+ const Return& operator()(const Arg1&, const Arg2&) const {
+ return static_object<Return>::get();
+ }
+ };
+
+ //===========================================================================
+ // Iterator Archetype Classes
+
+ template <class T, int I = 0>
+ class input_iterator_archetype
+ {
+ private:
+ typedef input_iterator_archetype self;
+ public:
+ typedef std::input_iterator_tag iterator_category;
+ typedef T value_type;
+ struct reference {
+ operator const value_type&() const { return static_object<T>::get(); }
+ };
+ typedef const T* pointer;
+ typedef std::ptrdiff_t difference_type;
+ self& operator=(const self&) { return *this; }
+ bool operator==(const self&) const { return true; }
+ bool operator!=(const self&) const { return true; }
+ reference operator*() const { return reference(); }
+ self& operator++() { return *this; }
+ self operator++(int) { return *this; }
+ };
+
+ template <class T>
+ class input_iterator_archetype_no_proxy
+ {
+ private:
+ typedef input_iterator_archetype_no_proxy self;
+ public:
+ typedef std::input_iterator_tag iterator_category;
+ typedef T value_type;
+ typedef const T& reference;
+ typedef const T* pointer;
+ typedef std::ptrdiff_t difference_type;
+ self& operator=(const self&) { return *this; }
+ bool operator==(const self&) const { return true; }
+ bool operator!=(const self&) const { return true; }
+ reference operator*() const { return static_object<T>::get(); }
+ self& operator++() { return *this; }
+ self operator++(int) { return *this; }
+ };
+
+ template <class T>
+ struct output_proxy {
+ output_proxy& operator=(const T&) { return *this; }
+ };
+
+ template <class T>
+ class output_iterator_archetype
+ {
+ public:
+ typedef output_iterator_archetype self;
+ public:
+ typedef std::output_iterator_tag iterator_category;
+ typedef output_proxy<T> value_type;
+ typedef output_proxy<T> reference;
+ typedef void pointer;
+ typedef void difference_type;
+ output_iterator_archetype(detail::dummy_constructor) { }
+ output_iterator_archetype(const self&) { }
+ self& operator=(const self&) { return *this; }
+ bool operator==(const self&) const { return true; }
+ bool operator!=(const self&) const { return true; }
+ reference operator*() const { return output_proxy<T>(); }
+ self& operator++() { return *this; }
+ self operator++(int) { return *this; }
+ private:
+ output_iterator_archetype() { }
+ };
+
+ template <class T>
+ class input_output_iterator_archetype
+ {
+ private:
+ typedef input_output_iterator_archetype self;
+ struct in_out_tag : public std::input_iterator_tag, public std::output_iterator_tag { };
+ public:
+ typedef in_out_tag iterator_category;
+ typedef T value_type;
+ struct reference {
+ reference& operator=(const T&) { return *this; }
+ operator value_type() { return static_object<T>::get(); }
+ };
+ typedef const T* pointer;
+ typedef std::ptrdiff_t difference_type;
+ input_output_iterator_archetype() { }
+ self& operator=(const self&) { return *this; }
+ bool operator==(const self&) const { return true; }
+ bool operator!=(const self&) const { return true; }
+ reference operator*() const { return reference(); }
+ self& operator++() { return *this; }
+ self operator++(int) { return *this; }
+ };
+
+ template <class T>
+ class forward_iterator_archetype
+ {
+ public:
+ typedef forward_iterator_archetype self;
+ public:
+ typedef std::forward_iterator_tag iterator_category;
+ typedef T value_type;
+ typedef const T& reference;
+ typedef T const* pointer;
+ typedef std::ptrdiff_t difference_type;
+ forward_iterator_archetype() { }
+ self& operator=(const self&) { return *this; }
+ bool operator==(const self&) const { return true; }
+ bool operator!=(const self&) const { return true; }
+ reference operator*() const { return static_object<T>::get(); }
+ self& operator++() { return *this; }
+ self operator++(int) { return *this; }
+ };
+
+ template <class T>
+ class mutable_forward_iterator_archetype
+ {
+ public:
+ typedef mutable_forward_iterator_archetype self;
+ public:
+ typedef std::forward_iterator_tag iterator_category;
+ typedef T value_type;
+ typedef T& reference;
+ typedef T* pointer;
+ typedef std::ptrdiff_t difference_type;
+ mutable_forward_iterator_archetype() { }
+ self& operator=(const self&) { return *this; }
+ bool operator==(const self&) const { return true; }
+ bool operator!=(const self&) const { return true; }
+ reference operator*() const { return static_object<T>::get(); }
+ self& operator++() { return *this; }
+ self operator++(int) { return *this; }
+ };
+
+ template <class T>
+ class bidirectional_iterator_archetype
+ {
+ public:
+ typedef bidirectional_iterator_archetype self;
+ public:
+ typedef std::bidirectional_iterator_tag iterator_category;
+ typedef T value_type;
+ typedef const T& reference;
+ typedef T* pointer;
+ typedef std::ptrdiff_t difference_type;
+ bidirectional_iterator_archetype() { }
+ self& operator=(const self&) { return *this; }
+ bool operator==(const self&) const { return true; }
+ bool operator!=(const self&) const { return true; }
+ reference operator*() const { return static_object<T>::get(); }
+ self& operator++() { return *this; }
+ self operator++(int) { return *this; }
+ self& operator--() { return *this; }
+ self operator--(int) { return *this; }
+ };
+
+ template <class T>
+ class mutable_bidirectional_iterator_archetype
+ {
+ public:
+ typedef mutable_bidirectional_iterator_archetype self;
+ public:
+ typedef std::bidirectional_iterator_tag iterator_category;
+ typedef T value_type;
+ typedef T& reference;
+ typedef T* pointer;
+ typedef std::ptrdiff_t difference_type;
+ mutable_bidirectional_iterator_archetype() { }
+ self& operator=(const self&) { return *this; }
+ bool operator==(const self&) const { return true; }
+ bool operator!=(const self&) const { return true; }
+ reference operator*() const { return static_object<T>::get(); }
+ self& operator++() { return *this; }
+ self operator++(int) { return *this; }
+ self& operator--() { return *this; }
+ self operator--(int) { return *this; }
+ };
+
+ template <class T>
+ class random_access_iterator_archetype
+ {
+ public:
+ typedef random_access_iterator_archetype self;
+ public:
+ typedef std::random_access_iterator_tag iterator_category;
+ typedef T value_type;
+ typedef const T& reference;
+ typedef T* pointer;
+ typedef std::ptrdiff_t difference_type;
+ random_access_iterator_archetype() { }
+ self& operator=(const self&) { return *this; }
+ bool operator==(const self&) const { return true; }
+ bool operator!=(const self&) const { return true; }
+ reference operator*() const { return static_object<T>::get(); }
+ self& operator++() { return *this; }
+ self operator++(int) { return *this; }
+ self& operator--() { return *this; }
+ self operator--(int) { return *this; }
+ reference operator[](difference_type) const
+ { return static_object<T>::get(); }
+ self& operator+=(difference_type) { return *this; }
+ self& operator-=(difference_type) { return *this; }
+ difference_type operator-(const self&) const
+ { return difference_type(); }
+ self operator+(difference_type) const { return *this; }
+ self operator-(difference_type) const { return *this; }
+ bool operator<(const self&) const { return true; }
+ bool operator<=(const self&) const { return true; }
+ bool operator>(const self&) const { return true; }
+ bool operator>=(const self&) const { return true; }
+ };
+ template <class T>
+ random_access_iterator_archetype<T>
+ operator+(typename random_access_iterator_archetype<T>::difference_type,
+ const random_access_iterator_archetype<T>& x)
+ { return x; }
+
+
+ template <class T>
+ class mutable_random_access_iterator_archetype
+ {
+ public:
+ typedef mutable_random_access_iterator_archetype self;
+ public:
+ typedef std::random_access_iterator_tag iterator_category;
+ typedef T value_type;
+ typedef T& reference;
+ typedef T* pointer;
+ typedef std::ptrdiff_t difference_type;
+ mutable_random_access_iterator_archetype() { }
+ self& operator=(const self&) { return *this; }
+ bool operator==(const self&) const { return true; }
+ bool operator!=(const self&) const { return true; }
+ reference operator*() const { return static_object<T>::get(); }
+ self& operator++() { return *this; }
+ self operator++(int) { return *this; }
+ self& operator--() { return *this; }
+ self operator--(int) { return *this; }
+ reference operator[](difference_type) const
+ { return static_object<T>::get(); }
+ self& operator+=(difference_type) { return *this; }
+ self& operator-=(difference_type) { return *this; }
+ difference_type operator-(const self&) const
+ { return difference_type(); }
+ self operator+(difference_type) const { return *this; }
+ self operator-(difference_type) const { return *this; }
+ bool operator<(const self&) const { return true; }
+ bool operator<=(const self&) const { return true; }
+ bool operator>(const self&) const { return true; }
+ bool operator>=(const self&) const { return true; }
+ };
+ template <class T>
+ mutable_random_access_iterator_archetype<T>
+ operator+
+ (typename mutable_random_access_iterator_archetype<T>::difference_type,
+ const mutable_random_access_iterator_archetype<T>& x)
+ { return x; }
+
+} // namespace boost
+
+#endif // BOOST_CONCEPT_ARCHETYPES_H
diff --git a/include/boost/concept_check.hpp b/include/boost/concept_check.hpp
new file mode 100644
index 0000000..25f118b
--- /dev/null
+++ b/include/boost/concept_check.hpp
@@ -0,0 +1,1082 @@
+//
+// (C) Copyright Jeremy Siek 2000.
+// Copyright 2002 The Trustees of Indiana University.
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//
+// Revision History:
+// 05 May 2001: Workarounds for HP aCC from Thomas Matelich. (Jeremy Siek)
+// 02 April 2001: Removed limits header altogether. (Jeremy Siek)
+// 01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
+//
+
+// See http://www.boost.org/libs/concept_check for documentation.
+
+#ifndef BOOST_CONCEPT_CHECKS_HPP
+# define BOOST_CONCEPT_CHECKS_HPP
+
+# include <boost/concept/assert.hpp>
+
+# include <iterator>
+# include <boost/type_traits/conversion_traits.hpp>
+# include <utility>
+# include <boost/type_traits/is_same.hpp>
+# include <boost/type_traits/is_void.hpp>
+# include <boost/mpl/assert.hpp>
+# include <boost/mpl/bool.hpp>
+# include <boost/detail/workaround.hpp>
+
+# include <boost/concept/usage.hpp>
+# include <boost/concept/detail/concept_def.hpp>
+
+#if (defined _MSC_VER)
+# pragma warning( push )
+# pragma warning( disable : 4510 ) // default constructor could not be generated
+# pragma warning( disable : 4610 ) // object 'class' can never be instantiated - user-defined constructor required
+#endif
+
+namespace boost
+{
+
+ //
+ // Backward compatibility
+ //
+
+ template <class Model>
+ inline void function_requires(Model* = 0)
+ {
+ BOOST_CONCEPT_ASSERT((Model));
+ }
+ template <class T> inline void ignore_unused_variable_warning(T const&) {}
+
+# define BOOST_CLASS_REQUIRE(type_var, ns, concept) \
+ BOOST_CONCEPT_ASSERT((ns::concept<type_var>))
+
+# define BOOST_CLASS_REQUIRE2(type_var1, type_var2, ns, concept) \
+ BOOST_CONCEPT_ASSERT((ns::concept<type_var1,type_var2>))
+
+# define BOOST_CLASS_REQUIRE3(tv1, tv2, tv3, ns, concept) \
+ BOOST_CONCEPT_ASSERT((ns::concept<tv1,tv2,tv3>))
+
+# define BOOST_CLASS_REQUIRE4(tv1, tv2, tv3, tv4, ns, concept) \
+ BOOST_CONCEPT_ASSERT((ns::concept<tv1,tv2,tv3,tv4>))
+
+
+ //
+ // Begin concept definitions
+ //
+ BOOST_concept(Integer, (T))
+ {
+ BOOST_CONCEPT_USAGE(Integer)
+ {
+ x.error_type_must_be_an_integer_type();
+ }
+ private:
+ T x;
+ };
+
+ template <> struct Integer<char> {};
+ template <> struct Integer<signed char> {};
+ template <> struct Integer<unsigned char> {};
+ template <> struct Integer<short> {};
+ template <> struct Integer<unsigned short> {};
+ template <> struct Integer<int> {};
+ template <> struct Integer<unsigned int> {};
+ template <> struct Integer<long> {};
+ template <> struct Integer<unsigned long> {};
+# if defined(BOOST_HAS_LONG_LONG)
+ template <> struct Integer< ::boost::long_long_type> {};
+ template <> struct Integer< ::boost::ulong_long_type> {};
+# elif defined(BOOST_HAS_MS_INT64)
+ template <> struct Integer<__int64> {};
+ template <> struct Integer<unsigned __int64> {};
+# endif
+
+ BOOST_concept(SignedInteger,(T)) {
+ BOOST_CONCEPT_USAGE(SignedInteger) {
+ x.error_type_must_be_a_signed_integer_type();
+ }
+ private:
+ T x;
+ };
+ template <> struct SignedInteger<signed char> { };
+ template <> struct SignedInteger<short> {};
+ template <> struct SignedInteger<int> {};
+ template <> struct SignedInteger<long> {};
+# if defined(BOOST_HAS_LONG_LONG)
+ template <> struct SignedInteger< ::boost::long_long_type> {};
+# elif defined(BOOST_HAS_MS_INT64)
+ template <> struct SignedInteger<__int64> {};
+# endif
+
+ BOOST_concept(UnsignedInteger,(T)) {
+ BOOST_CONCEPT_USAGE(UnsignedInteger) {
+ x.error_type_must_be_an_unsigned_integer_type();
+ }
+ private:
+ T x;
+ };
+
+ template <> struct UnsignedInteger<unsigned char> {};
+ template <> struct UnsignedInteger<unsigned short> {};
+ template <> struct UnsignedInteger<unsigned int> {};
+ template <> struct UnsignedInteger<unsigned long> {};
+# if defined(BOOST_HAS_LONG_LONG)
+ template <> struct UnsignedInteger< ::boost::ulong_long_type> {};
+# elif defined(BOOST_HAS_MS_INT64)
+ template <> struct UnsignedInteger<unsigned __int64> {};
+# endif
+
+ //===========================================================================
+ // Basic Concepts
+
+ BOOST_concept(DefaultConstructible,(TT))
+ {
+ BOOST_CONCEPT_USAGE(DefaultConstructible) {
+ TT a; // require default constructor
+ ignore_unused_variable_warning(a);
+ }
+ };
+
+ BOOST_concept(Assignable,(TT))
+ {
+ BOOST_CONCEPT_USAGE(Assignable) {
+#if !defined(_ITERATOR_) // back_insert_iterator broken for VC++ STL
+ a = b; // require assignment operator
+#endif
+ const_constraints(b);
+ }
+ private:
+ void const_constraints(const TT& x) {
+#if !defined(_ITERATOR_) // back_insert_iterator broken for VC++ STL
+ a = x; // const required for argument to assignment
+#else
+ ignore_unused_variable_warning(x);
+#endif
+ }
+ private:
+ TT a;
+ TT b;
+ };
+
+
+ BOOST_concept(CopyConstructible,(TT))
+ {
+ BOOST_CONCEPT_USAGE(CopyConstructible) {
+ TT a(b); // require copy constructor
+ TT* ptr = &a; // require address of operator
+ const_constraints(a);
+ ignore_unused_variable_warning(ptr);
+ }
+ private:
+ void const_constraints(const TT& a) {
+ TT c(a); // require const copy constructor
+ const TT* ptr = &a; // require const address of operator
+ ignore_unused_variable_warning(c);
+ ignore_unused_variable_warning(ptr);
+ }
+ TT b;
+ };
+
+ // The SGI STL version of Assignable requires copy constructor and operator=
+ BOOST_concept(SGIAssignable,(TT))
+ {
+ BOOST_CONCEPT_USAGE(SGIAssignable) {
+ TT c(a);
+#if !defined(_ITERATOR_) // back_insert_iterator broken for VC++ STL
+ a = b; // require assignment operator
+#endif
+ const_constraints(b);
+ ignore_unused_variable_warning(c);
+ }
+ private:
+ void const_constraints(const TT& x) {
+ TT c(x);
+#if !defined(_ITERATOR_) // back_insert_iterator broken for VC++ STL
+ a = x; // const required for argument to assignment
+#endif
+ ignore_unused_variable_warning(c);
+ }
+ TT a;
+ TT b;
+ };
+
+ BOOST_concept(Convertible,(X)(Y))
+ {
+ BOOST_CONCEPT_USAGE(Convertible) {
+ Y y = x;
+ ignore_unused_variable_warning(y);
+ }
+ private:
+ X x;
+ };
+
+ // The C++ standard requirements for many concepts talk about return
+ // types that must be "convertible to bool". The problem with this
+ // requirement is that it leaves the door open for evil proxies that
+ // define things like operator|| with strange return types. Two
+ // possible solutions are:
+ // 1) require the return type to be exactly bool
+ // 2) stay with convertible to bool, and also
+ // specify stuff about all the logical operators.
+ // For now we just test for convertible to bool.
+ template <class TT>
+ void require_boolean_expr(const TT& t) {
+ bool x = t;
+ ignore_unused_variable_warning(x);
+ }
+
+ BOOST_concept(EqualityComparable,(TT))
+ {
+ BOOST_CONCEPT_USAGE(EqualityComparable) {
+ require_boolean_expr(a == b);
+ require_boolean_expr(a != b);
+ }
+ private:
+ TT a, b;
+ };
+
+ BOOST_concept(LessThanComparable,(TT))
+ {
+ BOOST_CONCEPT_USAGE(LessThanComparable) {
+ require_boolean_expr(a < b);
+ }
+ private:
+ TT a, b;
+ };
+
+ // This is equivalent to SGI STL's LessThanComparable.
+ BOOST_concept(Comparable,(TT))
+ {
+ BOOST_CONCEPT_USAGE(Comparable) {
+ require_boolean_expr(a < b);
+ require_boolean_expr(a > b);
+ require_boolean_expr(a <= b);
+ require_boolean_expr(a >= b);
+ }
+ private:
+ TT a, b;
+ };
+
+#define BOOST_DEFINE_BINARY_PREDICATE_OP_CONSTRAINT(OP,NAME) \
+ BOOST_concept(NAME, (First)(Second)) \
+ { \
+ BOOST_CONCEPT_USAGE(NAME) { (void)constraints_(); } \
+ private: \
+ bool constraints_() { return a OP b; } \
+ First a; \
+ Second b; \
+ }
+
+#define BOOST_DEFINE_BINARY_OPERATOR_CONSTRAINT(OP,NAME) \
+ BOOST_concept(NAME, (Ret)(First)(Second)) \
+ { \
+ BOOST_CONCEPT_USAGE(NAME) { (void)constraints_(); } \
+ private: \
+ Ret constraints_() { return a OP b; } \
+ First a; \
+ Second b; \
+ }
+
+ BOOST_DEFINE_BINARY_PREDICATE_OP_CONSTRAINT(==, EqualOp);
+ BOOST_DEFINE_BINARY_PREDICATE_OP_CONSTRAINT(!=, NotEqualOp);
+ BOOST_DEFINE_BINARY_PREDICATE_OP_CONSTRAINT(<, LessThanOp);
+ BOOST_DEFINE_BINARY_PREDICATE_OP_CONSTRAINT(<=, LessEqualOp);
+ BOOST_DEFINE_BINARY_PREDICATE_OP_CONSTRAINT(>, GreaterThanOp);
+ BOOST_DEFINE_BINARY_PREDICATE_OP_CONSTRAINT(>=, GreaterEqualOp);
+
+ BOOST_DEFINE_BINARY_OPERATOR_CONSTRAINT(+, PlusOp);
+ BOOST_DEFINE_BINARY_OPERATOR_CONSTRAINT(*, TimesOp);
+ BOOST_DEFINE_BINARY_OPERATOR_CONSTRAINT(/, DivideOp);
+ BOOST_DEFINE_BINARY_OPERATOR_CONSTRAINT(-, SubtractOp);
+ BOOST_DEFINE_BINARY_OPERATOR_CONSTRAINT(%, ModOp);
+
+ //===========================================================================
+ // Function Object Concepts
+
+ BOOST_concept(Generator,(Func)(Return))
+ {
+ BOOST_CONCEPT_USAGE(Generator) { test(is_void<Return>()); }
+
+ private:
+ void test(boost::mpl::false_)
+ {
+ // Do we really want a reference here?
+ const Return& r = f();
+ ignore_unused_variable_warning(r);
+ }
+
+ void test(boost::mpl::true_)
+ {
+ f();
+ }
+
+ Func f;
+ };
+
+ BOOST_concept(UnaryFunction,(Func)(Return)(Arg))
+ {
+ BOOST_CONCEPT_USAGE(UnaryFunction) { test(is_void<Return>()); }
+
+ private:
+ void test(boost::mpl::false_)
+ {
+ f(arg); // "priming the pump" this way keeps msvc6 happy (ICE)
+ Return r = f(arg);
+ ignore_unused_variable_warning(r);
+ }
+
+ void test(boost::mpl::true_)
+ {
+ f(arg);
+ }
+
+#if (BOOST_WORKAROUND(__GNUC__, BOOST_TESTED_AT(4) \
+ && BOOST_WORKAROUND(__GNUC__, > 3)))
+ // Declare a dummy construktor to make gcc happy.
+ // It seems the compiler can not generate a sensible constructor when this is instantiated with a refence type.
+ // (warning: non-static reference "const double& boost::UnaryFunction<YourClassHere>::arg"
+ // in class without a constructor [-Wuninitialized])
+ UnaryFunction();
+#endif
+
+ Func f;
+ Arg arg;
+ };
+
+ BOOST_concept(BinaryFunction,(Func)(Return)(First)(Second))
+ {
+ BOOST_CONCEPT_USAGE(BinaryFunction) { test(is_void<Return>()); }
+ private:
+ void test(boost::mpl::false_)
+ {
+ f(first,second);
+ Return r = f(first, second); // require operator()
+ (void)r;
+ }
+
+ void test(boost::mpl::true_)
+ {
+ f(first,second);
+ }
+
+#if (BOOST_WORKAROUND(__GNUC__, BOOST_TESTED_AT(4) \
+ && BOOST_WORKAROUND(__GNUC__, > 3)))
+ // Declare a dummy constructor to make gcc happy.
+ // It seems the compiler can not generate a sensible constructor when this is instantiated with a refence type.
+ // (warning: non-static reference "const double& boost::BinaryFunction<YourClassHere>::arg"
+ // in class without a constructor [-Wuninitialized])
+ BinaryFunction();
+#endif
+
+ Func f;
+ First first;
+ Second second;
+ };
+
+ BOOST_concept(UnaryPredicate,(Func)(Arg))
+ {
+ BOOST_CONCEPT_USAGE(UnaryPredicate) {
+ require_boolean_expr(f(arg)); // require operator() returning bool
+ }
+ private:
+#if (BOOST_WORKAROUND(__GNUC__, BOOST_TESTED_AT(4) \
+ && BOOST_WORKAROUND(__GNUC__, > 3)))
+ // Declare a dummy constructor to make gcc happy.
+ // It seems the compiler can not generate a sensible constructor when this is instantiated with a refence type.
+ // (warning: non-static reference "const double& boost::UnaryPredicate<YourClassHere>::arg"
+ // in class without a constructor [-Wuninitialized])
+ UnaryPredicate();
+#endif
+
+ Func f;
+ Arg arg;
+ };
+
+ BOOST_concept(BinaryPredicate,(Func)(First)(Second))
+ {
+ BOOST_CONCEPT_USAGE(BinaryPredicate) {
+ require_boolean_expr(f(a, b)); // require operator() returning bool
+ }
+ private:
+#if (BOOST_WORKAROUND(__GNUC__, BOOST_TESTED_AT(4) \
+ && BOOST_WORKAROUND(__GNUC__, > 3)))
+ // Declare a dummy constructor to make gcc happy.
+ // It seems the compiler can not generate a sensible constructor when this is instantiated with a refence type.
+ // (warning: non-static reference "const double& boost::BinaryPredicate<YourClassHere>::arg"
+ // in class without a constructor [-Wuninitialized])
+ BinaryPredicate();
+#endif
+ Func f;
+ First a;
+ Second b;
+ };
+
+ // use this when functor is used inside a container class like std::set
+ BOOST_concept(Const_BinaryPredicate,(Func)(First)(Second))
+ : BinaryPredicate<Func, First, Second>
+ {
+ BOOST_CONCEPT_USAGE(Const_BinaryPredicate) {
+ const_constraints(f);
+ }
+ private:
+ void const_constraints(const Func& fun) {
+ // operator() must be a const member function
+ require_boolean_expr(fun(a, b));
+ }
+#if (BOOST_WORKAROUND(__GNUC__, BOOST_TESTED_AT(4) \
+ && BOOST_WORKAROUND(__GNUC__, > 3)))
+ // Declare a dummy constructor to make gcc happy.
+ // It seems the compiler can not generate a sensible constructor when this is instantiated with a refence type.
+ // (warning: non-static reference "const double& boost::Const_BinaryPredicate<YourClassHere>::arg"
+ // in class without a constructor [-Wuninitialized])
+ Const_BinaryPredicate();
+#endif
+
+ Func f;
+ First a;
+ Second b;
+ };
+
+ BOOST_concept(AdaptableGenerator,(Func)(Return))
+ : Generator<Func, typename Func::result_type>
+ {
+ typedef typename Func::result_type result_type;
+
+ BOOST_CONCEPT_USAGE(AdaptableGenerator)
+ {
+ BOOST_CONCEPT_ASSERT((Convertible<result_type, Return>));
+ }
+ };
+
+ BOOST_concept(AdaptableUnaryFunction,(Func)(Return)(Arg))
+ : UnaryFunction<Func, typename Func::result_type, typename Func::argument_type>
+ {
+ typedef typename Func::argument_type argument_type;
+ typedef typename Func::result_type result_type;
+
+ ~AdaptableUnaryFunction()
+ {
+ BOOST_CONCEPT_ASSERT((Convertible<result_type, Return>));
+ BOOST_CONCEPT_ASSERT((Convertible<Arg, argument_type>));
+ }
+ };
+
+ BOOST_concept(AdaptableBinaryFunction,(Func)(Return)(First)(Second))
+ : BinaryFunction<
+ Func
+ , typename Func::result_type
+ , typename Func::first_argument_type
+ , typename Func::second_argument_type
+ >
+ {
+ typedef typename Func::first_argument_type first_argument_type;
+ typedef typename Func::second_argument_type second_argument_type;
+ typedef typename Func::result_type result_type;
+
+ ~AdaptableBinaryFunction()
+ {
+ BOOST_CONCEPT_ASSERT((Convertible<result_type, Return>));
+ BOOST_CONCEPT_ASSERT((Convertible<First, first_argument_type>));
+ BOOST_CONCEPT_ASSERT((Convertible<Second, second_argument_type>));
+ }
+ };
+
+ BOOST_concept(AdaptablePredicate,(Func)(Arg))
+ : UnaryPredicate<Func, Arg>
+ , AdaptableUnaryFunction<Func, bool, Arg>
+ {
+ };
+
+ BOOST_concept(AdaptableBinaryPredicate,(Func)(First)(Second))
+ : BinaryPredicate<Func, First, Second>
+ , AdaptableBinaryFunction<Func, bool, First, Second>
+ {
+ };
+
+ //===========================================================================
+ // Iterator Concepts
+
+ BOOST_concept(InputIterator,(TT))
+ : Assignable<TT>
+ , EqualityComparable<TT>
+ {
+ typedef typename std::iterator_traits<TT>::value_type value_type;
+ typedef typename std::iterator_traits<TT>::difference_type difference_type;
+ typedef typename std::iterator_traits<TT>::reference reference;
+ typedef typename std::iterator_traits<TT>::pointer pointer;
+ typedef typename std::iterator_traits<TT>::iterator_category iterator_category;
+
+ BOOST_CONCEPT_USAGE(InputIterator)
+ {
+ BOOST_CONCEPT_ASSERT((SignedInteger<difference_type>));
+ BOOST_CONCEPT_ASSERT((Convertible<iterator_category, std::input_iterator_tag>));
+
+ TT j(i);
+ (void)*i; // require dereference operator
+ ++j; // require preincrement operator
+ i++; // require postincrement operator
+ }
+ private:
+ TT i;
+ };
+
+ BOOST_concept(OutputIterator,(TT)(ValueT))
+ : Assignable<TT>
+ {
+ BOOST_CONCEPT_USAGE(OutputIterator) {
+
+ ++i; // require preincrement operator
+ i++; // require postincrement operator
+ *i++ = t; // require postincrement and assignment
+ }
+ private:
+ TT i, j;
+ ValueT t;
+ };
+
+ BOOST_concept(ForwardIterator,(TT))
+ : InputIterator<TT>
+ {
+ BOOST_CONCEPT_USAGE(ForwardIterator)
+ {
+ BOOST_CONCEPT_ASSERT((Convertible<
+ BOOST_DEDUCED_TYPENAME ForwardIterator::iterator_category
+ , std::forward_iterator_tag
+ >));
+
+ typename InputIterator<TT>::reference r = *i;
+ ignore_unused_variable_warning(r);
+ }
+
+ private:
+ TT i;
+ };
+
+ BOOST_concept(Mutable_ForwardIterator,(TT))
+ : ForwardIterator<TT>
+ {
+ BOOST_CONCEPT_USAGE(Mutable_ForwardIterator) {
+ *i++ = *j; // require postincrement and assignment
+ }
+ private:
+ TT i, j;
+ };
+
+ BOOST_concept(BidirectionalIterator,(TT))
+ : ForwardIterator<TT>
+ {
+ BOOST_CONCEPT_USAGE(BidirectionalIterator)
+ {
+ BOOST_CONCEPT_ASSERT((Convertible<
+ BOOST_DEDUCED_TYPENAME BidirectionalIterator::iterator_category
+ , std::bidirectional_iterator_tag
+ >));
+
+ --i; // require predecrement operator
+ i--; // require postdecrement operator
+ }
+ private:
+ TT i;
+ };
+
+ BOOST_concept(Mutable_BidirectionalIterator,(TT))
+ : BidirectionalIterator<TT>
+ , Mutable_ForwardIterator<TT>
+ {
+ BOOST_CONCEPT_USAGE(Mutable_BidirectionalIterator)
+ {
+ *i-- = *j; // require postdecrement and assignment
+ }
+ private:
+ TT i, j;
+ };
+
+ BOOST_concept(RandomAccessIterator,(TT))
+ : BidirectionalIterator<TT>
+ , Comparable<TT>
+ {
+ BOOST_CONCEPT_USAGE(RandomAccessIterator)
+ {
+ BOOST_CONCEPT_ASSERT((Convertible<
+ BOOST_DEDUCED_TYPENAME BidirectionalIterator<TT>::iterator_category
+ , std::random_access_iterator_tag
+ >));
+
+ i += n; // require assignment addition operator
+ i = i + n; i = n + i; // require addition with difference type
+ i -= n; // require assignment subtraction operator
+ i = i - n; // require subtraction with difference type
+ n = i - j; // require difference operator
+ (void)i[n]; // require element access operator
+ }
+
+ private:
+ TT a, b;
+ TT i, j;
+ typename std::iterator_traits<TT>::difference_type n;
+ };
+
+ BOOST_concept(Mutable_RandomAccessIterator,(TT))
+ : RandomAccessIterator<TT>
+ , Mutable_BidirectionalIterator<TT>
+ {
+ BOOST_CONCEPT_USAGE(Mutable_RandomAccessIterator)
+ {
+ i[n] = *i; // require element access and assignment
+ }
+ private:
+ TT i;
+ typename std::iterator_traits<TT>::difference_type n;
+ };
+
+ //===========================================================================
+ // Container s
+
+ BOOST_concept(Container,(C))
+ : Assignable<C>
+ {
+ typedef typename C::value_type value_type;
+ typedef typename C::difference_type difference_type;
+ typedef typename C::size_type size_type;
+ typedef typename C::const_reference const_reference;
+ typedef typename C::const_pointer const_pointer;
+ typedef typename C::const_iterator const_iterator;
+
+ BOOST_CONCEPT_USAGE(Container)
+ {
+ BOOST_CONCEPT_ASSERT((InputIterator<const_iterator>));
+ const_constraints(c);
+ }
+
+ private:
+ void const_constraints(const C& cc) {
+ i = cc.begin();
+ i = cc.end();
+ n = cc.size();
+ n = cc.max_size();
+ b = cc.empty();
+ }
+ C c;
+ bool b;
+ const_iterator i;
+ size_type n;
+ };
+
+ BOOST_concept(Mutable_Container,(C))
+ : Container<C>
+ {
+ typedef typename C::reference reference;
+ typedef typename C::iterator iterator;
+ typedef typename C::pointer pointer;
+
+ BOOST_CONCEPT_USAGE(Mutable_Container)
+ {
+ BOOST_CONCEPT_ASSERT((
+ Assignable<typename Mutable_Container::value_type>));
+
+ BOOST_CONCEPT_ASSERT((InputIterator<iterator>));
+
+ i = c.begin();
+ i = c.end();
+ c.swap(c2);
+ }
+
+ private:
+ iterator i;
+ C c, c2;
+ };
+
+ BOOST_concept(ForwardContainer,(C))
+ : Container<C>
+ {
+ BOOST_CONCEPT_USAGE(ForwardContainer)
+ {
+ BOOST_CONCEPT_ASSERT((
+ ForwardIterator<
+ typename ForwardContainer::const_iterator
+ >));
+ }
+ };
+
+ BOOST_concept(Mutable_ForwardContainer,(C))
+ : ForwardContainer<C>
+ , Mutable_Container<C>
+ {
+ BOOST_CONCEPT_USAGE(Mutable_ForwardContainer)
+ {
+ BOOST_CONCEPT_ASSERT((
+ Mutable_ForwardIterator<
+ typename Mutable_ForwardContainer::iterator
+ >));
+ }
+ };
+
+ BOOST_concept(ReversibleContainer,(C))
+ : ForwardContainer<C>
+ {
+ typedef typename
+ C::const_reverse_iterator
+ const_reverse_iterator;
+
+ BOOST_CONCEPT_USAGE(ReversibleContainer)
+ {
+ BOOST_CONCEPT_ASSERT((
+ BidirectionalIterator<
+ typename ReversibleContainer::const_iterator>));
+
+ BOOST_CONCEPT_ASSERT((BidirectionalIterator<const_reverse_iterator>));
+
+ const_constraints(c);
+ }
+ private:
+ void const_constraints(const C& cc)
+ {
+ const_reverse_iterator i = cc.rbegin();
+ i = cc.rend();
+ }
+ C c;
+ };
+
+ BOOST_concept(Mutable_ReversibleContainer,(C))
+ : Mutable_ForwardContainer<C>
+ , ReversibleContainer<C>
+ {
+ typedef typename C::reverse_iterator reverse_iterator;
+
+ BOOST_CONCEPT_USAGE(Mutable_ReversibleContainer)
+ {
+ typedef typename Mutable_ForwardContainer<C>::iterator iterator;
+ BOOST_CONCEPT_ASSERT((Mutable_BidirectionalIterator<iterator>));
+ BOOST_CONCEPT_ASSERT((Mutable_BidirectionalIterator<reverse_iterator>));
+
+ reverse_iterator i = c.rbegin();
+ i = c.rend();
+ }
+ private:
+ C c;
+ };
+
+ BOOST_concept(RandomAccessContainer,(C))
+ : ReversibleContainer<C>
+ {
+ typedef typename C::size_type size_type;
+ typedef typename C::const_reference const_reference;
+
+ BOOST_CONCEPT_USAGE(RandomAccessContainer)
+ {
+ BOOST_CONCEPT_ASSERT((
+ RandomAccessIterator<
+ typename RandomAccessContainer::const_iterator
+ >));
+
+ const_constraints(c);
+ }
+ private:
+ void const_constraints(const C& cc)
+ {
+ const_reference r = cc[n];
+ ignore_unused_variable_warning(r);
+ }
+
+ C c;
+ size_type n;
+ };
+
+ BOOST_concept(Mutable_RandomAccessContainer,(C))
+ : Mutable_ReversibleContainer<C>
+ , RandomAccessContainer<C>
+ {
+ private:
+ typedef Mutable_RandomAccessContainer self;
+ public:
+ BOOST_CONCEPT_USAGE(Mutable_RandomAccessContainer)
+ {
+ BOOST_CONCEPT_ASSERT((Mutable_RandomAccessIterator<typename self::iterator>));
+ BOOST_CONCEPT_ASSERT((Mutable_RandomAccessIterator<typename self::reverse_iterator>));
+
+ typename self::reference r = c[i];
+ ignore_unused_variable_warning(r);
+ }
+
+ private:
+ typename Mutable_ReversibleContainer<C>::size_type i;
+ C c;
+ };
+
+ // A Sequence is inherently mutable
+ BOOST_concept(Sequence,(S))
+ : Mutable_ForwardContainer<S>
+ // Matt Austern's book puts DefaultConstructible here, the C++
+ // standard places it in Container --JGS
+ // ... so why aren't we following the standard? --DWA
+ , DefaultConstructible<S>
+ {
+ BOOST_CONCEPT_USAGE(Sequence)
+ {
+ S
+ c(n, t),
+ c2(first, last);
+
+ c.insert(p, t);
+ c.insert(p, n, t);
+ c.insert(p, first, last);
+
+ c.erase(p);
+ c.erase(p, q);
+
+ typename Sequence::reference r = c.front();
+
+ ignore_unused_variable_warning(c);
+ ignore_unused_variable_warning(c2);
+ ignore_unused_variable_warning(r);
+ const_constraints(c);
+ }
+ private:
+ void const_constraints(const S& c) {
+ typename Sequence::const_reference r = c.front();
+ ignore_unused_variable_warning(r);
+ }
+
+ typename S::value_type t;
+ typename S::size_type n;
+ typename S::value_type* first, *last;
+ typename S::iterator p, q;
+ };
+
+ BOOST_concept(FrontInsertionSequence,(S))
+ : Sequence<S>
+ {
+ BOOST_CONCEPT_USAGE(FrontInsertionSequence)
+ {
+ c.push_front(t);
+ c.pop_front();
+ }
+ private:
+ S c;
+ typename S::value_type t;
+ };
+
+ BOOST_concept(BackInsertionSequence,(S))
+ : Sequence<S>
+ {
+ BOOST_CONCEPT_USAGE(BackInsertionSequence)
+ {
+ c.push_back(t);
+ c.pop_back();
+ typename BackInsertionSequence::reference r = c.back();
+ ignore_unused_variable_warning(r);
+ const_constraints(c);
+ }
+ private:
+ void const_constraints(const S& cc) {
+ typename BackInsertionSequence::const_reference
+ r = cc.back();
+ ignore_unused_variable_warning(r);
+ }
+ S c;
+ typename S::value_type t;
+ };
+
+ BOOST_concept(AssociativeContainer,(C))
+ : ForwardContainer<C>
+ , DefaultConstructible<C>
+ {
+ typedef typename C::key_type key_type;
+ typedef typename C::key_compare key_compare;
+ typedef typename C::value_compare value_compare;
+ typedef typename C::iterator iterator;
+
+ BOOST_CONCEPT_USAGE(AssociativeContainer)
+ {
+ i = c.find(k);
+ r = c.equal_range(k);
+ c.erase(k);
+ c.erase(i);
+ c.erase(r.first, r.second);
+ const_constraints(c);
+ BOOST_CONCEPT_ASSERT((BinaryPredicate<key_compare,key_type,key_type>));
+
+ typedef typename AssociativeContainer::value_type value_type_;
+ BOOST_CONCEPT_ASSERT((BinaryPredicate<value_compare,value_type_,value_type_>));
+ }
+
+ // Redundant with the base concept, but it helps below.
+ typedef typename C::const_iterator const_iterator;
+ private:
+ void const_constraints(const C& cc)
+ {
+ ci = cc.find(k);
+ n = cc.count(k);
+ cr = cc.equal_range(k);
+ }
+
+ C c;
+ iterator i;
+ std::pair<iterator,iterator> r;
+ const_iterator ci;
+ std::pair<const_iterator,const_iterator> cr;
+ typename C::key_type k;
+ typename C::size_type n;
+ };
+
+ BOOST_concept(UniqueAssociativeContainer,(C))
+ : AssociativeContainer<C>
+ {
+ BOOST_CONCEPT_USAGE(UniqueAssociativeContainer)
+ {
+ C c(first, last);
+
+ pos_flag = c.insert(t);
+ c.insert(first, last);
+
+ ignore_unused_variable_warning(c);
+ }
+ private:
+ std::pair<typename C::iterator, bool> pos_flag;
+ typename C::value_type t;
+ typename C::value_type* first, *last;
+ };
+
+ BOOST_concept(MultipleAssociativeContainer,(C))
+ : AssociativeContainer<C>
+ {
+ BOOST_CONCEPT_USAGE(MultipleAssociativeContainer)
+ {
+ C c(first, last);
+
+ pos = c.insert(t);
+ c.insert(first, last);
+
+ ignore_unused_variable_warning(c);
+ ignore_unused_variable_warning(pos);
+ }
+ private:
+ typename C::iterator pos;
+ typename C::value_type t;
+ typename C::value_type* first, *last;
+ };
+
+ BOOST_concept(SimpleAssociativeContainer,(C))
+ : AssociativeContainer<C>
+ {
+ BOOST_CONCEPT_USAGE(SimpleAssociativeContainer)
+ {
+ typedef typename C::key_type key_type;
+ typedef typename C::value_type value_type;
+ BOOST_MPL_ASSERT((boost::is_same<key_type,value_type>));
+ }
+ };
+
+ BOOST_concept(PairAssociativeContainer,(C))
+ : AssociativeContainer<C>
+ {
+ BOOST_CONCEPT_USAGE(PairAssociativeContainer)
+ {
+ typedef typename C::key_type key_type;
+ typedef typename C::value_type value_type;
+ typedef typename C::mapped_type mapped_type;
+ typedef std::pair<const key_type, mapped_type> required_value_type;
+ BOOST_MPL_ASSERT((boost::is_same<value_type,required_value_type>));
+ }
+ };
+
+ BOOST_concept(SortedAssociativeContainer,(C))
+ : AssociativeContainer<C>
+ , ReversibleContainer<C>
+ {
+ BOOST_CONCEPT_USAGE(SortedAssociativeContainer)
+ {
+ C
+ c(kc),
+ c2(first, last),
+ c3(first, last, kc);
+
+ p = c.upper_bound(k);
+ p = c.lower_bound(k);
+ r = c.equal_range(k);
+
+ c.insert(p, t);
+
+ ignore_unused_variable_warning(c);
+ ignore_unused_variable_warning(c2);
+ ignore_unused_variable_warning(c3);
+ const_constraints(c);
+ }
+
+ void const_constraints(const C& c)
+ {
+ kc = c.key_comp();
+ vc = c.value_comp();
+
+ cp = c.upper_bound(k);
+ cp = c.lower_bound(k);
+ cr = c.equal_range(k);
+ }
+
+ private:
+ typename C::key_compare kc;
+ typename C::value_compare vc;
+ typename C::value_type t;
+ typename C::key_type k;
+ typedef typename C::iterator iterator;
+ typedef typename C::const_iterator const_iterator;
+
+ typedef SortedAssociativeContainer self;
+ iterator p;
+ const_iterator cp;
+ std::pair<typename self::iterator,typename self::iterator> r;
+ std::pair<typename self::const_iterator,typename self::const_iterator> cr;
+ typename C::value_type* first, *last;
+ };
+
+ // HashedAssociativeContainer
+
+ BOOST_concept(Collection,(C))
+ {
+ BOOST_CONCEPT_USAGE(Collection)
+ {
+ boost::function_requires<boost::InputIteratorConcept<iterator> >();
+ boost::function_requires<boost::InputIteratorConcept<const_iterator> >();
+ boost::function_requires<boost::CopyConstructibleConcept<value_type> >();
+ const_constraints(c);
+ i = c.begin();
+ i = c.end();
+ c.swap(c);
+ }
+
+ void const_constraints(const C& cc) {
+ ci = cc.begin();
+ ci = cc.end();
+ n = cc.size();
+ b = cc.empty();
+ }
+
+ private:
+ typedef typename C::value_type value_type;
+ typedef typename C::iterator iterator;
+ typedef typename C::const_iterator const_iterator;
+ typedef typename C::reference reference;
+ typedef typename C::const_reference const_reference;
+ // typedef typename C::pointer pointer;
+ typedef typename C::difference_type difference_type;
+ typedef typename C::size_type size_type;
+
+ C c;
+ bool b;
+ iterator i;
+ const_iterator ci;
+ size_type n;
+ };
+} // namespace boost
+
+#if (defined _MSC_VER)
+# pragma warning( pop )
+#endif
+
+# include <boost/concept/detail/concept_undef.hpp>
+
+#endif // BOOST_CONCEPT_CHECKS_HPP
+
diff --git a/include/boost/concept_check/borland.hpp b/include/boost/concept_check/borland.hpp
new file mode 100644
index 0000000..107926b
--- /dev/null
+++ b/include/boost/concept_check/borland.hpp
@@ -0,0 +1,25 @@
+// Copyright David Abrahams 2006. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+#ifndef BOOST_CONCEPT_CHECK_BORLAND_DWA2006429_HPP
+# define BOOST_CONCEPT_CHECK_BORLAND_DWA2006429_HPP
+
+namespace boost {
+
+template <class ModelFn>
+struct concept_check;
+
+template <class Model>
+struct concept_check<void(*)(Model)>
+{
+ enum { instantiate = sizeof((((Model*)0)->~Model()), 3) };
+};
+
+# define BOOST_CONCEPT_ASSERT( ModelInParens ) \
+ enum { BOOST_PP_CAT(boost_concept_check,__LINE__) = \
+ boost::concept_check<void(*)ModelInParens>::instantiate \
+ }
+
+} // namespace boost::concept_checking
+
+#endif // BOOST_CONCEPT_CHECK_BORLAND_DWA2006429_HPP
diff --git a/include/boost/concept_check/general.hpp b/include/boost/concept_check/general.hpp
new file mode 100644
index 0000000..cd09fb0
--- /dev/null
+++ b/include/boost/concept_check/general.hpp
@@ -0,0 +1,82 @@
+// Copyright David Abrahams 2006. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+#ifndef BOOST_CONCEPT_CHECK_MSVC_DWA2006429_HPP
+# define BOOST_CONCEPT_CHECK_MSVC_DWA2006429_HPP
+
+# ifdef BOOST_OLD_CONCEPT_SUPPORT
+# include <boost/concept_check/has_constraints.hpp>
+# include <boost/mpl/if.hpp>
+# endif
+
+
+// This implementation works on GCC and Comeau, but has actually been
+// fairly carefully tuned to work on GCC versions starting with
+// gcc-2.95.x. If you're trying to get an additional compiler to pass
+// the tests you might consider breaking out a separate gcc.hpp and
+// starting over on the general case.
+namespace boost
+{
+ namespace concept_checking
+ {
+ template <void(*)()> struct instantiate {};
+ }
+
+ template <class ModelFn> struct concept_check_;
+
+ template <class Model>
+ void concept_check_failed()
+ {
+ ((Model*)0)->~Model();
+ }
+
+ template <class Model>
+ struct concept_check
+ {
+ concept_checking::instantiate<concept_check_failed<Model> > x;
+ enum { instantiate = 1 };
+ };
+
+# ifdef BOOST_OLD_CONCEPT_SUPPORT
+
+ template <class Model>
+ void constraint_check_failed()
+ {
+ ((Model*)0)->constraints();
+ }
+
+ template <class Model>
+ struct constraint_check
+ {
+ concept_checking::instantiate<constraint_check_failed<Model> > x;
+ enum { instantiate = 1 };
+ };
+
+ template <class Model>
+ struct concept_check_<void(*)(Model)>
+ : mpl::if_c<
+ concept_checking::has_constraints<Model>::value
+ , constraint_check<Model>
+ , concept_check<Model>
+ >::type
+ {};
+
+# else
+
+ template <class Model>
+ struct concept_check_<void(*)(Model)>
+ : concept_check<Model>
+ {};
+
+# endif
+
+ // Usage, in class or function context:
+ //
+ // BOOST_CONCEPT_ASSERT((UnaryFunctionConcept<F,bool,int>));
+# define BOOST_CONCEPT_ASSERT( ModelInParens ) \
+ enum { BOOST_PP_CAT(boost_concept_check,__LINE__) = \
+ ::boost::concept_check_<void(*) ModelInParens>::instantiate \
+ }
+}
+
+#endif // BOOST_CONCEPT_CHECK_MSVC_DWA2006429_HPP
diff --git a/include/boost/concept_check/has_constraints.hpp b/include/boost/concept_check/has_constraints.hpp
new file mode 100644
index 0000000..e19f664
--- /dev/null
+++ b/include/boost/concept_check/has_constraints.hpp
@@ -0,0 +1,31 @@
+// Copyright David Abrahams 2006. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+#ifndef BOOST_CONCEPT_CHECK_HAS_CONSTRAINTS_DWA2006429_HPP
+# define BOOST_CONCEPT_CHECK_HAS_CONSTRAINTS_DWA2006429_HPP
+
+namespace boost { namespace concept_checking {
+
+// Here we implement the "metafunction" that detects whether a
+// constraints metafunction exists
+typedef char yes;
+typedef char (&no)[2];
+
+template <class Model, void (Model::*)()>
+struct wrap_constraints {};
+
+template <class Model>
+inline yes has_constraints_(Model*, wrap_constraints<Model,&Model::constraints>* = 0);
+inline no has_constraints_(...);
+
+template <class Model>
+struct has_constraints
+{
+ BOOST_STATIC_CONSTANT(
+ bool
+ , value = sizeof( concept_checking::has_constraints_((Model*)0) ) == 1 );
+};
+
+}} // namespace boost::concept_checking
+
+#endif // BOOST_CONCEPT_CHECK_HAS_CONSTRAINTS_DWA2006429_HPP
diff --git a/include/boost/concept_check/msvc.hpp b/include/boost/concept_check/msvc.hpp
new file mode 100644
index 0000000..3968469
--- /dev/null
+++ b/include/boost/concept_check/msvc.hpp
@@ -0,0 +1,90 @@
+// Copyright David Abrahams 2006. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+#ifndef BOOST_CONCEPT_CHECK_MSVC_DWA2006429_HPP
+# define BOOST_CONCEPT_CHECK_MSVC_DWA2006429_HPP
+
+# ifdef BOOST_OLD_CONCEPT_SUPPORT
+# include <boost/concept_check/has_constraints.hpp>
+# include <boost/mpl/if.hpp>
+# endif
+
+
+namespace boost
+{
+ namespace concept_checking
+ {
+ template <class Model>
+ struct concept_check_
+ {
+ virtual void failed(Model* x)
+ {
+ x->~Model();
+ }
+ };
+ }
+
+# ifdef BOOST_OLD_CONCEPT_SUPPORT
+
+ namespace concept_checking
+ {
+ template <class Model>
+ struct constraint_check
+ {
+ virtual void failed(Model* x)
+ {
+ x->constraints();
+ }
+ };
+ }
+
+ template <class Model>
+ struct concept_check
+ : mpl::if_c<
+ concept_checking::has_constraints<Model>::value
+ , concept_checking::constraint_check<Model>
+ , concept_checking::concept_check_<Model>
+ >::type
+ {};
+
+# else
+
+ template <class Model>
+ struct concept_check
+ : concept_checking::concept_check_<Model>
+ {};
+
+# endif
+
+# if BOOST_WORKAROUND(BOOST_MSVC, == 1310)
+
+ //
+ // The iterator library sees some really strange errors unless we
+ // use partial specialization to extract the model type with
+ // msvc-7.1
+ //
+ template <class Model>
+ struct concept_check<void(*)(Model)>
+ : concept_check<Model>
+ { };
+
+# define BOOST_CONCEPT_ASSERT( ModelInParens ) \
+ enum { BOOST_PP_CAT(boost_concept_check,__LINE__) = \
+ sizeof(::boost::concept_check<void(*) ModelInParens>) \
+ }
+
+# else
+
+ template <class Model>
+ concept_check<Model>
+ concept_check_(void(*)(Model));
+
+# define BOOST_CONCEPT_ASSERT( ModelInParens ) \
+ enum { BOOST_PP_CAT(boost_concept_check,__LINE__) = \
+ sizeof(::boost::concept_check_((void(*) ModelInParens)0)) \
+ }
+
+# endif
+}
+
+#endif // BOOST_CONCEPT_CHECK_MSVC_DWA2006429_HPP
diff --git a/index.html b/index.html
new file mode 100644
index 0000000..36fea49
--- /dev/null
+++ b/index.html
@@ -0,0 +1,13 @@
+<html>
+<head>
+<meta http-equiv="refresh" content="0; URL=concept_check.htm">
+</head>
+<body>
+Automatic redirection failed, please go to
+<a href="concept_check.htm">concept_check.htm</a>. <hr>
+<p>© Copyright Beman Dawes, 2001</p>
+<p>Distributed under the Boost Software License, Version 1.0. (See accompanying
+file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or copy
+at <a href="http://www.boost.org/LICENSE_1_0.txt">www.boost.org/LICENSE_1_0.txt</a>)</p>
+</body>
+</html>
\ No newline at end of file
diff --git a/meta/libraries.json b/meta/libraries.json
new file mode 100644
index 0000000..480b9c8
--- /dev/null
+++ b/meta/libraries.json
@@ -0,0 +1,15 @@
+{
+ "key": "concept_check",
+ "name": "Concept Check",
+ "authors": [
+ "Jeremy Siek"
+ ],
+ "description": "Tools for generic programming.",
+ "category": [
+ "Correctness",
+ "Generic"
+ ],
+ "maintainers": [
+ "Jeremy Siek <jeremy.siek -at- gmail.com>"
+ ]
+}
diff --git a/prog_with_concepts.htm b/prog_with_concepts.htm
new file mode 100644
index 0000000..fb04aed
--- /dev/null
+++ b/prog_with_concepts.htm
@@ -0,0 +1,144 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
+ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
+
+<html xmlns="http://www.w3.org/1999/xhtml">
+<!-- Copyright (c) Jeremy Siek and Andrew Lumsdaine 2000 -->
+<!-- Distributed under the Boost -->
+<!-- Software License, Version 1.0. (See accompanying -->
+<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
+
+<head>
+ <meta name="generator" content=
+ "HTML Tidy for Linux/x86 (vers 1 September 2005), see www.w3.org" />
+
+ <title>Programming With Concepts</title>
+ <meta http-equiv="Content-Type" content="text/html; charset=us-ascii" />
+ <link rel="stylesheet" href="../../rst.css" type="text/css" />
+</head>
+
+<body bgcolor="#FFFFFF" link="#0000EE" text="#000000" vlink="#551A8B" alink=
+"#FF0000">
+ <img src="../../boost.png" alt="C++ Boost" width="277" height=
+ "86" /><br clear="none" />
+
+ <h2><a name="programming-with-concepts" id=
+ "programming-with-concepts">Programming with Concepts</a></h2>
+
+ <p>The process of deciding how to group requirements into concepts and
+ deciding which concepts to use in each algorithm is perhaps the most
+ difficult (yet most important) part of building a generic library. A
+ guiding principle to use during this process is one we call the
+ <i>requirement minimization principle</i>.</p>
+
+ <p><b>Requirement Minimization Principle:</b> Minimize the requirements on
+ the input parameters of a component to increase its reusability.</p>
+
+ <p>There is natural tension in this statement. By definition, the input
+ parameters must be used by the component in order for the component to
+ accomplish its task (by ``component'' we mean a function or class
+ template). The challenge then is to implement the component in such a way
+ that makes the fewest assumptions (the minimum requirements) about the
+ inputs while still accomplishing the task.</p>
+
+ <p>The traditional notions of <i>abstraction</i> tie in directly to the
+ idea of minimal requirements. The more abstract the input, the fewer the
+ requirements. Thus, concepts are simply the embodiment of generic abstract
+ data types in C++ template programming.</p>
+
+ <p>When designing the concepts for some problem domain it is important to
+ keep in mind their purpose, namely to express the requirements for the
+ input to the components. With respect to the requirement minimization
+ principle, this means we want to minimize concepts.
+ <!-- the following discussion does not match the Standard definition
+ of LessThanComparable and needs to be changed -Jeremy
+
+<p>
+It is important to note, however, that
+minimizing concepts does not mean simply
+reducing the number of valid expressions
+in the concept.
+For example, the
+<tt>std::stable_sort()</tt> function requires that the value type of
+the iterator be <a
+href="http://www.sgi.com/tech/stl/LessThanComparable.html">
+LessThanComparable</a>, which not only
+includes <tt>operator<()</tt>, but also <tt>operator>()</tt>,
+<tt>operator<=()</tt>, and <tt>operator>=()</tt>.
+It turns out that <tt>std::stable_sort()</tt> only uses
+<tt>operator<()</tt>. The question then arises: should
+<tt>std::stable_sort()</tt> be specified in terms of the concept
+<a
+href="http://www.sgi.com/tech/stl/LessThanComparable.html">
+LessThanComparable</a> or in terms of a concept that only
+requires <tt>operator<()</tt>?
+
+<p>
+We remark first that the use of <a
+href="http://www.sgi.com/tech/stl/LessThanComparable.html">
+LessThanComparable</a> does not really violate the requirement
+minimization principle because all of the other operators can be
+trivially implemented in terms of <tt>operator<()</tt>. By
+``trivial'' we mean one line of code and a constant run-time cost.
+More fundamentally, however, the use of <a
+href="http://www.sgi.com/tech/stl/LessThanComparable.html">
+LessThanComparable</a> does not violate the requirement minimization
+principle because all of the comparison operators (<tt><</tt>,
+<tt>></tt>, <tt><=</tt>, <tt>>=</tt>) are conceptually equivalent (in
+a mathematical sense). Adding conceptually equivalent valid
+expressions is not a violation of the requirement minimization
+principle because no new semantics are being added === only new
+syntax. The added syntax increases re-usability.
+
+<p>
+For example,
+the
+maintainer of the <tt>std::stable_sort()</tt> may some day change the
+implementation in places to use <tt>operator>()</tt> instead of
+<tt>operator<()</tt>, since, after all, they are equivalent. Since the
+requirements are part of the public interface, such a change could
+potentially break client code. If instead
+<a
+href="http://www.sgi.com/tech/stl/LessThanComparable.html">
+LessThanComparable</a> is given as the requirement for
+<tt>std::stable_sort()</tt>, then the maintainer is given a reasonable
+amount of flexibility within which to work.
+
+--></p>
+
+ <p>Minimality in concepts is a property associated with the underlying
+ semantics of the problem domain being represented. In the problem domain of
+ basic containers, requiring traversal in a single direction is a smaller
+ requirement than requiring traversal in both directions (hence the
+ distinction between <a href=
+ "http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a> and
+ <a href=
+ "http://www.sgi.com/tech/stl/BidirectionalIterator.html">BidirectionalIterator</a>).
+ The semantic difference can be easily seen in the difference between the
+ set of concrete data structures that have forward iterators versus the set
+ that has bidirectional iterators. For example, singly-linked lists would
+ fall in the set of data structures having forward iterators, but not
+ bidirectional iterators. In addition, the set of algorithms that one can
+ implement using only forward iterators is quite different than the set that
+ can be implemented with bidirectional iterators. Because of this, it is
+ important to factor families of requirements into rather fine-grained
+ concepts. For example, the requirements for iterators are factored into the
+ six STL iterator concepts (trivial, output, input, forward, bidirectional,
+ and random access).</p>
+
+ <p><a href="./implementation.htm">Next: Implementation</a><br />
+ <a href="./concept_covering.htm">Prev: Concept Covering and
+ Archetypes</a><br /></p>
+ <hr />
+
+ <table>
+ <tr valign="top">
+ <td nowrap="nowrap">Copyright © 2000</td>
+
+ <td><a href="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</a>(<a href=
+ "mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</a>) Andrew
+ Lumsdaine(<a href="mailto:lums@osl.iu.edu">lums@osl.iu.edu</a>),
+ 2007 <a href="mailto:dave@boost-consulting.com">David Abrahams</a>.
+ </tr>
+ </table>
+</body>
+</html>
diff --git a/reference.htm b/reference.htm
new file mode 100644
index 0000000..ae8d502
--- /dev/null
+++ b/reference.htm
@@ -0,0 +1,418 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
+ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
+
+<html xmlns="http://www.w3.org/1999/xhtml">
+<!-- Copyright (c) Jeremy Siek and Andrew Lumsdaine 2000 -->
+<!-- Distributed under the Boost -->
+<!-- Software License, Version 1.0. (See accompanying -->
+<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
+
+<head>
+ <meta name="generator" content=
+ "HTML Tidy for Linux/x86 (vers 1 September 2005), see www.w3.org" />
+ <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
+ <link rel="stylesheet" href="../../rst.css" type="text/css" />
+
+ <title>Boost Concept Checking Reference</title>
+</head>
+
+<body bgcolor="#FFFFFF" link="#0000EE" text="#000000" vlink="#551A8B" alink=
+"#FF0000">
+ <img src="../../boost.png" alt="C++ Boost" width="277" height=
+ "86" /><br clear="none" />
+
+ <h2><a name="reference" id="reference">Reference</a></h2>
+
+ <ol>
+ <li><a href="#macros">Macros</a></li>
+
+ <li><a href="#basic-concepts">Basic Concept Checking Classes</a></li>
+
+ <li><a href="#iterator-concepts">Iterator Concept Checking
+ Classes</a></li>
+
+ <li><a href="#function-object-concepts">Function Object Concept Checking
+ Classes</a></li>
+
+ <li><a href="#container-concepts">Container Concept Checking
+ Classes</a></li>
+
+ <li><a href="#basic-archetype">Basic Archetype Classes</a></li>
+
+ <li><a href="#iterator-archetype">Iterator Archetype Classes</a></li>
+
+ <li><a href="#function-object-archetype">Function Object Archetype
+ Classes</a></li>
+
+ <li><a href="#container-archetype">Container Archetype Classes</a></li>
+
+ <li><a href="#deprecated-functions">Deprecated Functions</a></li>
+
+ <li><a href="#deprecated-macros">Deprecated Macros</a></li>
+
+ <li><a href="#deprecated-concept-checking-classes">Deprecated Concept
+ Checking Classes</a></li>
+ </ol>
+
+ <h3><a name="macros" id="macros">Macros</a></h3>
+ <pre>
+#include "boost/concept/assert.hpp"
+
+BOOST_CONCEPT_ASSERT((<em>concept checking class template specialization</em>));
+</pre>
+
+ <p><strong>Effects:</strong> causes a compilation failure if the concept is
+ not satisfied.<br />
+ <strong>Note:</strong> this macro can be used at global, class, or function
+ scope.</p>
+
+ <pre>
+#include "boost/concept/requires.hpp"
+
+<font color="gray">template <…<em>template parameters</em>…></font>
+BOOST_CONCEPT_REQUIRES(
+ ((<em>concept checking class template specialization<sub>1</sub></em>))
+ ((<em>concept checking class template specialization<sub>2</sub></em>))…
+ ((<em>concept checking class template specialization<sub>n</sub></em>))<strong>,</strong>
+ (<em>function return type</em>)
+) <font color="gray"><em>function_template_name</em>(…<em>function parameters</em>…)</font>
+</pre>
+
+ <p><strong>Effects:</strong> causes a compilation failure if the
+ given concepts are not satisfied.<br />
+ <strong>Note:</strong> this macro is intended to be used in place of
+ a function template's return type.</p>
+
+ <h3><a name="basic-concepts" id="basic-concepts">Basic Concept Checking
+ Classes</a></h3>
+ <pre>
+#include "boost/concept_check.hpp"
+
+template <class T>
+struct Integer; // Is T a built-in integer type?
+
+template <class T>
+struct SignedInteger; // Is T a built-in signed integer type?
+
+template <class T>
+struct UnsignedInteger; // Is T a built-in unsigned integer type?
+
+template <class X, class Y>
+struct Convertible; // Is X convertible to Y?
+
+template <class T>
+struct <a href=
+"../utility/Assignable.html">Assignable</a>; // Standard ref 23.1
+
+template <class T>
+struct SGI<a href=
+"http://www.sgi.com/tech/stl/Assignable.html">Assignable</a>;
+
+template <class T>
+struct <a href=
+"http://www.sgi.com/tech/stl/DefaultConstructible.html">DefaultConstructible</a>;
+
+template <class T>
+struct <a href=
+"../utility/CopyConstructible.html">CopyConstructible</a>; // Standard ref 20.1.3
+
+template <class T>
+struct <a href=
+"http://www.sgi.com/tech/stl/EqualityComparable.html">EqualityComparable</a>; // Standard ref 20.1.1
+
+template <class T>
+struct <a href=
+"../utility/LessThanComparable.html">LessThanComparable</a>; // Standard ref 20.1.2
+
+template <class T>
+struct Comparable; // The SGI STL <a href=
+"http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a> concept
+</pre>
+
+ <h3><a name="iterator-concepts" id="iterator-concepts">Iterator Concept
+ Checking Classes</a></h3>
+ <pre>
+template <class Iter>
+struct <a href=
+"http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>; // Standard ref 24.1.1 Table 72
+
+template <class Iter, class T>
+struct <a href=
+"http://www.sgi.com/tech/stl/OutputIterator.html">OutputIterator</a>; // Standard ref 24.1.2 Table 73
+
+template <class Iter>
+struct <a href=
+"http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a>; // Standard ref 24.1.3 Table 74
+
+template <class Iter>
+struct Mutable_ForwardIterator;
+
+template <class Iter>
+struct <a href=
+"http://www.sgi.com/tech/stl/BidirectionalIterator.html">BidirectionalIterator</a>; // Standard ref 24.1.4 Table 75
+
+template <class Iter>
+struct Mutable_BidirectionalIterator;
+
+template <class Iter>
+struct <a href=
+"http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>; // Standard ref 24.1.5 Table 76
+
+template <class Iter>
+struct Mutable_RandomAccessIterator;
+</pre>
+
+ <h3><a name="function-object-concepts" id=
+ "function-object-concepts">Function Object Concept Checking
+ Classes</a></h3>
+ <pre>
+#include "boost/concept_check.hpp"
+
+template <class Func, class Return>
+struct <a href="http://www.sgi.com/tech/stl/Generator.html">Generator</a>;
+
+template <class Func, class Return, class Arg>
+struct <a href=
+"http://www.sgi.com/tech/stl/UnaryFunction.html">UnaryFunction</a>;
+
+template <class Func, class Return, class First, class Second>
+struct <a href=
+"http://www.sgi.com/tech/stl/BinaryFunction.html">BinaryFunction</a>;
+
+template <class Func, class Arg>
+struct Unary<a href=
+"http://www.sgi.com/tech/stl/Predicate.html">Predicate</a>;
+
+template <class Func, class First, class Second>
+struct <a href=
+"http://www.sgi.com/tech/stl/BinaryPredicate.html">BinaryPredicate</a>;
+
+template <class Func, class First, class Second>
+struct Const_BinaryPredicate;
+
+template <class Func, class Return>
+struct <a href=
+"http://www.sgi.com/tech/stl/AdaptableGenerator.html">AdaptableGenerator</a>;
+
+template <class Func, class Return, class Arg>
+struct <a href=
+"http://www.sgi.com/tech/stl/AdaptableUnaryFunction.html">AdaptableUnaryFunction</a>;
+
+template <class Func, class First, class Second>
+struct <a href=
+"http://www.sgi.com/tech/stl/AdaptableBinaryFunction.html">AdaptableBinaryFunction</a>;
+
+template <class Func, class Arg>
+struct <a href=
+"http://www.sgi.com/tech/stl/AdaptablePredicate.html">AdaptablePredicate</a>;
+
+template <class Func, class First, class Second>
+struct <a href=
+"http://www.sgi.com/tech/stl/AdaptableBinaryPredicate.html">AdaptableBinaryPredicate</a>;
+</pre>
+
+ <h3><a name="container-concepts" id="container-concepts">Container Concept
+ Checking Classes</a></h3>
+ <pre>
+#include "boost/concept_check.hpp"
+
+template <class C>
+struct <a href=
+"http://www.sgi.com/tech/stl/Container.html">Container</a>; // Standard ref 23.1 Table 65
+
+template <class C>
+struct Mutable_Container;
+
+template <class C>
+struct <a href=
+"http://www.sgi.com/tech/stl/ForwardContainer.html">ForwardContainer</a>;
+
+template <class C>
+struct Mutable_ForwardContainer;
+
+template <class C>
+struct <a href=
+"http://www.sgi.com/tech/stl/ReversibleContainer.html">ReversibleContainer</a>; // Standard ref 23.1 Table 66
+
+template <class C>
+struct Mutable_ReversibleContainer;
+
+template <class C>
+struct <a href=
+"http://www.sgi.com/tech/stl/RandomAccessContainer.html">RandomAccessContainer</a>;
+
+template <class C>
+struct Mutable_RandomAccessContainer;
+
+template <class C>
+struct <a href=
+"http://www.sgi.com/tech/stl/Sequence.html">Sequence</a>; // Standard ref 23.1.1
+
+template <class C>
+struct <a href=
+"http://www.sgi.com/tech/stl/FrontInsertionSequence.html">FrontInsertionSequence</a>;
+
+template <class C>
+struct <a href=
+"http://www.sgi.com/tech/stl/BackInsertionSequence.html">BackInsertionSequence</a>;
+
+template <class C>
+struct <a href=
+"http://www.sgi.com/tech/stl/AssociativeContainer.html">AssociativeContainer</a>; // Standard ref 23.1.2 Table 69
+
+template <class C>
+struct <a href=
+"http://www.sgi.com/tech/stl/UniqueAssociativeContainer.html">UniqueAssociativeContainer</a>;
+
+template <class C>
+struct <a href=
+"http://www.sgi.com/tech/stl/MultipleAssociativeContainer.html">MultipleAssociativeContainer</a>;
+
+template <class C>
+struct <a href=
+"http://www.sgi.com/tech/stl/SimpleAssociativeContainer.html">SimpleAssociativeContainer</a>;
+
+template <class C>
+struct <a href=
+"http://www.sgi.com/tech/stl/PairAssociativeContainer.html">PairAssociativeContainer</a>;
+
+template <class C>
+struct <a href=
+"http://www.sgi.com/tech/stl/SortedAssociativeContainer.html">SortedAssociativeContainer</a>;
+
+template <class C>
+struct <a href=
+"../utility/Collection.html">Collection</a>;
+</pre>
+
+ <h3><a name="basic-archetype" id="basic-archetype">Basic Archetype
+ Classes</a></h3>
+ <pre>
+#include "boost/concept_archetype.hpp"
+
+template <class T = int>
+class null_archetype; // A type that models no concepts.
+
+template <class Base = null_archetype>
+class default_constructible_archetype;
+
+template <class Base = null_archetype>
+class assignable_archetype;
+
+template <class Base = null_archetype>
+class copy_constructible_archetype;
+
+template <class Base = null_archetype>
+class equality_comparable_archetype;
+
+template <class T, class Base = null_archetype>
+class convertible_to_archetype;
+</pre>
+
+ <h3><a name="iterator-archetype" id="iterator-archetype">Iterator Archetype
+ Classes</a></h3>
+ <pre>
+#include "boost/concept_archetype.hpp"
+
+template <class ValueType>
+class trivial_iterator_archetype;
+
+template <class ValueType>
+class mutable_trivial_iterator_archetype;
+
+template <class ValueType>
+class input_iterator_archetype;
+
+template <class ValueType>
+class forward_iterator_archetype;
+
+template <class ValueType>
+class bidirectional_iterator_archetype;
+
+template <class ValueType>
+class random_access_iterator_archetype;
+</pre>
+
+ <h3><a name="function-object-archetype" id=
+ "function-object-archetype">Function Object Archetype Classes</a></h3>
+ <pre>
+#include "boost/concept_archetype.hpp"
+
+template <class Arg, class Return>
+class unary_function_archetype;
+
+template <class Arg1, class Arg2, class Return>
+class binary_function_archetype;
+
+template <class Arg>
+class predicate_archetype;
+
+template <class Arg1, class Arg2>
+class binary_predicate_archetype;
+</pre>
+
+ <h3><a name="container-archetype" id="container-archetype">Container
+ Archetype Classes</a></h3>
+ <pre>
+UNDER CONSTRUCTION
+</pre>
+
+ <h3><a name="deprecated-functions" id="deprecated-functions">Deprecated
+ Functions</a></h3>
+ <pre>
+#include "boost/concept_check.hpp"
+
+template <class Concept>
+void function_requires();
+</pre>
+
+ <p><code>function_requires()</code> has been deprecated in favor of <code>BOOST_CONCEPT_ASSERT</code>.
+ This means that <del><code>function_requires< Concept<Type> >();</code></del>
+ becomes <code>BOOST_CONCEPT_ASSERT((Concept<Type>));</code>
+ (don't forget to <code>#include "boost/concept/assert.hpp"</code>).
+
+
+ <h3><a name="deprecated-macros" id="deprecated-macros">Deprecated
+ Macros</a></h3>
+ <pre>
+#include "boost/concept_check.hpp"
+
+// Apply concept checks in class definitions.
+BOOST_CLASS_REQUIRE(<i>type</i>, <i>namespace-of-concept</i>, <i>concept</i>);
+BOOST_CLASS_REQUIRE2(<i>type1</i>, <i>type2</i>, <i>namespace-of-concept</i>, <i>concept</i>);
+BOOST_CLASS_REQUIRE3(<i>type1</i>, <i>type2</i>, <i>type3</i>, <i>namespace-of-concept</i>, <i>concept</i>);
+BOOST_CLASS_REQUIRE4(<i>type1</i>, <i>type2</i>, <i>type3</i>, <i>type4</i>, <i>namespace-of-concept</i>, <i>concept</i>);
+
+// Apply concept checks in class definitions.
+BOOST_CLASS_REQUIRES(<i>type</i>, <i>concept</i>);
+BOOST_CLASS_REQUIRES2(<i>type1</i>, <i>type2</i>, <i>concept</i>);
+BOOST_CLASS_REQUIRES3(<i>type1</i>, <i>type2</i>, <i>type3</i>, <i>concept</i>);
+BOOST_CLASS_REQUIRES4(<i>type1</i>, <i>type2</i>, <i>type3</i>, <i>type4</i>, <i>concept</i>);
+</pre>
+
+ <h3><a name="deprecated-concept-checking-classes" id=
+ "deprecated-concept-checking-classes">Deprecated Concept Checking
+ Classes</a></h3>
+
+ <p>For each of the concepts documented here, the library includes an
+ identical concept checking class whose name ends in
+ “<code>Concept</code>” For example, in
+ addition to <code>RandomAccessIterator</code>, the library defines a
+ <code>RandomAccessIteratorConcept</code> class template.</p>
+
+ <p><a href="./concept_check.htm">Back to Introduction</a><br />
+ <a href="./implementation.htm">Prev: Implementation</a><br /></p>
+ <hr />
+
+ <table>
+ <tr valign="top">
+ <td nowrap="nowrap">Copyright © 2000</td>
+
+ <td><a href="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</a>(<a href=
+ "mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</a>) Andrew
+ Lumsdaine(<a href="mailto:lums@osl.iu.edu">lums@osl.iu.edu</a>), 2007
+ <a href="mailto:dave@boost-consulting.com">David Abrahams</a>.</td>
+ </tr>
+ </table>
+</body>
+</html>
diff --git a/test/Jamfile.v2 b/test/Jamfile.v2
new file mode 100644
index 0000000..7b7c833
--- /dev/null
+++ b/test/Jamfile.v2
@@ -0,0 +1,25 @@
+# Copyright David Abrahams, Jeremy Siek, Vladimir Prus
+# 2006. Distributed under the Boost Software License, Version
+# 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+# http://www.boost.org/LICENSE_1_0.txt)
+import testing ;
+
+test-suite concept_check
+ : [ run stl_concept_covering.cpp ]
+ [ run stl_concept_check.cpp ]
+ [ run concept_check_test.cpp ]
+ [ run class_concept_check_test.cpp ]
+ [ compile-fail concept_check_fail_expected.cpp ]
+ [ compile-fail class_concept_fail_expected.cpp ]
+
+ [ run where.cpp ]
+ [ compile-fail where_fail.cpp ]
+ [ compile-fail usage_fail.cpp ]
+
+ # Backward compatibility tests
+ [ run old_concept_pass.cpp ]
+ [ compile-fail function_requires_fail.cpp ]
+ [ compile-fail old_concept_function_fail.cpp ]
+ [ compile-fail old_concept_class_fail.cpp ]
+ ;
+
diff --git a/test/class_concept_check_test.cpp b/test/class_concept_check_test.cpp
new file mode 100644
index 0000000..d5512c6
--- /dev/null
+++ b/test/class_concept_check_test.cpp
@@ -0,0 +1,34 @@
+// (C) Copyright Jeremy Siek 2000.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/concept_check.hpp>
+
+/*
+
+ This file verifies that the BOOST_CLASS_REQUIRE macro of the Boost
+ Concept Checking Library does not cause errors when it is not suppose
+ to.
+
+*/
+
+struct foo { bool operator()(int) { return true; } };
+struct bar { bool operator()(int, char) { return true; } };
+
+class class_requires_test
+{
+ BOOST_CONCEPT_ASSERT((boost::EqualityComparable<int>));
+ typedef int* int_ptr; typedef const int* const_int_ptr;
+ BOOST_CONCEPT_ASSERT((boost::EqualOp<int_ptr,const_int_ptr>));
+ BOOST_CONCEPT_ASSERT((boost::UnaryFunction<foo,bool,int>));
+ BOOST_CONCEPT_ASSERT((boost::BinaryFunction<bar,bool,int,char>));
+};
+
+int
+main()
+{
+ class_requires_test x;
+ boost::ignore_unused_variable_warning(x);
+ return 0;
+}
diff --git a/test/class_concept_fail_expected.cpp b/test/class_concept_fail_expected.cpp
new file mode 100644
index 0000000..74268e3
--- /dev/null
+++ b/test/class_concept_fail_expected.cpp
@@ -0,0 +1,32 @@
+// (C) Copyright Jeremy Siek, David Abrahams 2000-2006.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//
+// Change Log:
+// 20 Jan 2001 - Added warning suppression (David Abrahams)
+
+#include <boost/concept_check.hpp>
+
+/*
+
+ This file verifies that class_requires of the Boost Concept Checking
+ Library catches errors when it is supposed to.
+
+*/
+
+struct foo { };
+
+template <class T>
+class class_requires_test
+{
+ BOOST_CONCEPT_ASSERT((boost::EqualityComparable<foo>));
+};
+
+int
+main()
+{
+ class_requires_test<int> x;
+ (void)x; // suppress unused variable warning
+ return 0;
+}
diff --git a/test/concept_check_fail_expected.cpp b/test/concept_check_fail_expected.cpp
new file mode 100644
index 0000000..15bfe7a8
--- /dev/null
+++ b/test/concept_check_fail_expected.cpp
@@ -0,0 +1,26 @@
+// (C) Copyright Jeremy Siek, David Abrahams 2000-2006.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifdef NDEBUG
+# undef NDEBUG
+#endif
+
+#include <boost/concept_check.hpp>
+
+/*
+
+ This file verifies that BOOST_CONCEPT_ASSERT catches errors in
+ function context.
+
+*/
+
+struct foo { };
+
+int
+main()
+{
+ BOOST_CONCEPT_ASSERT((boost::EqualityComparable<foo>));
+ return 0;
+}
diff --git a/test/concept_check_test.cpp b/test/concept_check_test.cpp
new file mode 100644
index 0000000..f39ced7
--- /dev/null
+++ b/test/concept_check_test.cpp
@@ -0,0 +1,177 @@
+// (C) Copyright Jeremy Siek 2000.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/concept_check.hpp>
+#include <boost/concept_archetype.hpp>
+
+/*
+
+ This file verifies that function_requires() of the Boost Concept
+ Checking Library does not cause errors when it is not suppose to
+ and verifies that the concept archetypes meet the requirements of
+ their matching concepts.
+
+*/
+
+
+int
+main()
+{
+ using namespace boost;
+
+ //===========================================================================
+ // Basic Concepts
+ {
+ typedef default_constructible_archetype<> foo;
+ function_requires< DefaultConstructible<foo> >();
+ }
+ {
+ typedef assignable_archetype<> foo;
+ function_requires< Assignable<foo> >();
+ }
+ {
+ typedef copy_constructible_archetype<> foo;
+ function_requires< CopyConstructible<foo> >();
+ }
+ {
+ typedef sgi_assignable_archetype<> foo;
+ function_requires< SGIAssignable<foo> >();
+ }
+ {
+ typedef copy_constructible_archetype<> foo;
+ typedef convertible_to_archetype<foo> convertible_to_foo;
+ function_requires< Convertible<convertible_to_foo, foo> >();
+ }
+ {
+ function_requires< Convertible<boolean_archetype, bool> >();
+ }
+ {
+ typedef equality_comparable_archetype<> foo;
+ function_requires< EqualityComparable<foo> >();
+ }
+ {
+ typedef less_than_comparable_archetype<> foo;
+ function_requires< LessThanComparable<foo> >();
+ }
+ {
+ typedef comparable_archetype<> foo;
+ function_requires< Comparable<foo> >();
+ }
+ {
+ typedef equal_op_first_archetype<> First;
+ typedef equal_op_second_archetype<> Second;
+ function_requires< EqualOp<First, Second> >();
+ }
+ {
+ typedef not_equal_op_first_archetype<> First;
+ typedef not_equal_op_second_archetype<> Second;
+ function_requires< NotEqualOp<First, Second> >();
+ }
+ {
+ typedef less_than_op_first_archetype<> First;
+ typedef less_than_op_second_archetype<> Second;
+ function_requires< LessThanOp<First, Second> >();
+ }
+ {
+ typedef less_equal_op_first_archetype<> First;
+ typedef less_equal_op_second_archetype<> Second;
+ function_requires< LessEqualOp<First, Second> >();
+ }
+ {
+ typedef greater_than_op_first_archetype<> First;
+ typedef greater_than_op_second_archetype<> Second;
+ function_requires< GreaterThanOp<First, Second> >();
+ }
+ {
+ typedef greater_equal_op_first_archetype<> First;
+ typedef greater_equal_op_second_archetype<> Second;
+ function_requires< GreaterEqualOp<First, Second> >();
+ }
+
+ {
+ typedef copy_constructible_archetype<> Return;
+ typedef plus_op_first_archetype<Return> First;
+ typedef plus_op_second_archetype<Return> Second;
+ function_requires< PlusOp<Return, First, Second> >();
+ }
+
+ //===========================================================================
+ // Function Object Concepts
+
+ {
+ typedef generator_archetype<null_archetype<> > foo;
+ function_requires< Generator<foo, null_archetype<> > >();
+ }
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ {
+ function_requires< Generator< void_generator_archetype, void > >();
+ }
+#endif
+ {
+ typedef unary_function_archetype<int, int> F;
+ function_requires< UnaryFunction<F, int, int> >();
+ }
+ {
+ typedef binary_function_archetype<int, int, int> F;
+ function_requires< BinaryFunction<F, int, int, int> >();
+ }
+ {
+ typedef unary_predicate_archetype<int> F;
+ function_requires< UnaryPredicate<F, int> >();
+ }
+ {
+ typedef binary_predicate_archetype<int, int> F;
+ function_requires< BinaryPredicate<F, int, int> >();
+ }
+
+ //===========================================================================
+ // Iterator Concepts
+ {
+ typedef input_iterator_archetype<null_archetype<> > Iter;
+ function_requires< InputIterator<Iter> >();
+ }
+ {
+ typedef output_iterator_archetype<int> Iter;
+ function_requires< OutputIterator<Iter, int> >();
+ }
+ {
+ typedef input_output_iterator_archetype<int> Iter;
+ function_requires< InputIterator<Iter> >();
+ function_requires< OutputIterator<Iter, int> >();
+ }
+ {
+ typedef forward_iterator_archetype<null_archetype<> > Iter;
+ function_requires< ForwardIterator<Iter> >();
+ }
+ {
+ typedef mutable_forward_iterator_archetype<assignable_archetype<> > Iter;
+ function_requires< Mutable_ForwardIterator<Iter> >();
+ }
+ {
+ typedef bidirectional_iterator_archetype<null_archetype<> > Iter;
+ function_requires< BidirectionalIterator<Iter> >();
+ }
+ {
+ typedef mutable_bidirectional_iterator_archetype<assignable_archetype<> >
+ Iter;
+ function_requires< Mutable_BidirectionalIterator<Iter> >();
+ }
+ {
+ typedef random_access_iterator_archetype<null_archetype<> > Iter;
+ function_requires< RandomAccessIterator<Iter> >();
+ }
+ {
+ typedef mutable_random_access_iterator_archetype<assignable_archetype<> >
+ Iter;
+ function_requires< Mutable_RandomAccessIterator<Iter> >();
+ }
+
+ //===========================================================================
+ // Container Concepts
+
+ // UNDER CONSTRUCTION
+
+ return 0;
+}
diff --git a/test/fake_sort.hpp b/test/fake_sort.hpp
new file mode 100644
index 0000000..99c7546
--- /dev/null
+++ b/test/fake_sort.hpp
@@ -0,0 +1,27 @@
+// Copyright David Abrahams 2006. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+#ifndef BOOST_LIBS_CONCEPT_CHECK_FAKE_SORT_DWA2006430_HPP
+# define BOOST_LIBS_CONCEPT_CHECK_FAKE_SORT_DWA2006430_HPP
+
+# include <boost/detail/iterator.hpp>
+# include <boost/concept/requires.hpp>
+# include <boost/concept_check.hpp>
+
+namespace fake
+{
+ using namespace boost;
+
+ template<typename RanIter>
+ BOOST_CONCEPT_REQUIRES(
+ ((Mutable_RandomAccessIterator<RanIter>))
+ ((LessThanComparable<typename Mutable_RandomAccessIterator<RanIter>::value_type>))
+
+ , (void))
+ sort(RanIter,RanIter)
+ {
+
+ }
+}
+
+#endif // BOOST_LIBS_CONCEPT_CHECK_FAKE_SORT_DWA2006430_HPP
diff --git a/test/function_requires_fail.cpp b/test/function_requires_fail.cpp
new file mode 100644
index 0000000..03beaec
--- /dev/null
+++ b/test/function_requires_fail.cpp
@@ -0,0 +1,26 @@
+// (C) Copyright Jeremy Siek 2000.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifdef NDEBUG
+# undef NDEBUG
+#endif
+
+#include <boost/concept_check.hpp>
+
+/*
+
+ This file verifies that function_requires() of the Boost Concept
+ Checking Library catches errors when it is suppose to.
+
+*/
+
+struct foo { };
+
+int
+main()
+{
+ boost::function_requires< boost::EqualityComparable<foo> >();
+ return 0;
+}
diff --git a/test/old_concept_class_fail.cpp b/test/old_concept_class_fail.cpp
new file mode 100644
index 0000000..be41037
--- /dev/null
+++ b/test/old_concept_class_fail.cpp
@@ -0,0 +1,28 @@
+// (C) Copyright Jeremy Siek, David Abrahams 2000-2006.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//
+// Change Log:
+// 20 Jan 2001 - Added warning suppression (David Abrahams)
+
+#include "old_concepts.hpp"
+
+// This file verifies that concepts written the old way still catch
+// errors in class context. This is not expected to work on compilers
+// without SFINAE support.
+
+struct foo { };
+
+class class_requires_test
+{
+ BOOST_CLASS_REQUIRE(foo, old, EqualityComparableConcept);
+};
+
+int
+main()
+{
+ class_requires_test x;
+ (void)x; // suppress unused variable warning
+ return 0;
+}
diff --git a/test/old_concept_function_fail.cpp b/test/old_concept_function_fail.cpp
new file mode 100644
index 0000000..6b7bf30
--- /dev/null
+++ b/test/old_concept_function_fail.cpp
@@ -0,0 +1,23 @@
+// (C) Copyright Jeremy Siek 2000.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifdef NDEBUG
+# undef NDEBUG
+#endif
+
+#include "old_concepts.hpp"
+
+// This file verifies that concepts written the old way still catch
+// errors in function context. This is not expected to work on
+// compilers without SFINAE support.
+
+struct foo { };
+
+int
+main()
+{
+ boost::function_requires< old::EqualityComparableConcept<foo> >();
+ return 0;
+}
diff --git a/test/old_concept_pass.cpp b/test/old_concept_pass.cpp
new file mode 100644
index 0000000..e9601fc
--- /dev/null
+++ b/test/old_concept_pass.cpp
@@ -0,0 +1,34 @@
+// (C) Copyright Jeremy Siek, David Abrahams 2000-2006.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/concept_check.hpp>
+#include "old_concepts.hpp"
+
+// This test verifies that use of the old-style concept checking
+// classes still compiles (but not that it detects constraint
+// violations). We check them with the old-style macros just for
+// completeness, since those macros stranslate into
+// BOOST_CONCEPT_ASSERTs.
+
+struct foo { bool operator()(int) { return true; } };
+struct bar { bool operator()(int, char) { return true; } };
+
+
+class class_requires_test
+{
+ BOOST_CLASS_REQUIRE(int, old, EqualityComparableConcept);
+ typedef int* int_ptr; typedef const int* const_int_ptr;
+ BOOST_CLASS_REQUIRE2(int_ptr, const_int_ptr, old, EqualOpConcept);
+ BOOST_CLASS_REQUIRE3(foo, bool, int, old, UnaryFunctionConcept);
+ BOOST_CLASS_REQUIRE4(bar, bool, int, char, old, BinaryFunctionConcept);
+};
+
+int
+main()
+{
+ class_requires_test x;
+ boost::ignore_unused_variable_warning(x);
+ return 0;
+}
diff --git a/test/old_concepts.hpp b/test/old_concepts.hpp
new file mode 100644
index 0000000..76fad3c
--- /dev/null
+++ b/test/old_concepts.hpp
@@ -0,0 +1,67 @@
+// Copyright Jeremy Siek, David Abrahams 2000-2006. Distributed under
+// the Boost Software License, Version 1.0. (See accompanying file
+// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+#ifndef BOOST_LIBS_CONCEPT_CHECK_OLD_CONCEPTS_DWA2006428_HPP
+# define BOOST_LIBS_CONCEPT_CHECK_OLD_CONCEPTS_DWA2006428_HPP
+
+#include <boost/concept_check.hpp>
+
+namespace old
+{
+ template <class TT>
+ void require_boolean_expr(const TT& t) {
+ bool x = t;
+ boost::ignore_unused_variable_warning(x);
+ }
+
+ template <class TT>
+ struct EqualityComparableConcept
+ {
+ void constraints() {
+ boost::require_boolean_expr(a == b);
+ boost::require_boolean_expr(a != b);
+ }
+ TT a, b;
+ };
+
+ template <class Func, class Return, class Arg>
+ struct UnaryFunctionConcept
+ {
+ // required in case any of our template args are const-qualified:
+ UnaryFunctionConcept();
+
+ void constraints() {
+ r = f(arg); // require operator()
+ }
+ Func f;
+ Arg arg;
+ Return r;
+ };
+
+ template <class Func, class Return, class First, class Second>
+ struct BinaryFunctionConcept
+ {
+ void constraints() {
+ r = f(first, second); // require operator()
+ }
+ Func f;
+ First first;
+ Second second;
+ Return r;
+ };
+
+#define DEFINE_BINARY_PREDICATE_OP_CONSTRAINT(OP,NAME) \
+ template <class First, class Second> \
+ struct NAME { \
+ void constraints() { (void)constraints_(); } \
+ bool constraints_() { \
+ return a OP b; \
+ } \
+ First a; \
+ Second b; \
+ }
+
+ DEFINE_BINARY_PREDICATE_OP_CONSTRAINT(==, EqualOpConcept);
+}
+
+#endif // BOOST_LIBS_CONCEPT_CHECK_OLD_CONCEPTS_DWA2006428_HPP
diff --git a/test/stl_concept_check.cpp b/test/stl_concept_check.cpp
new file mode 100644
index 0000000..d336de1
--- /dev/null
+++ b/test/stl_concept_check.cpp
@@ -0,0 +1,93 @@
+// (C) Copyright Jeremy Siek 2000.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+//
+// This file checks to see if various standard container
+// implementations live up to requirements specified in the C++
+// standard. As many implementations do not live to the requirements,
+// it is not uncommon for this file to fail to compile. The
+// BOOST_HIDE_EXPECTED_ERRORS macro is provided here if you want to
+// see as much of this file compile as possible.
+//
+
+#include <boost/concept_check.hpp>
+
+#include <iterator>
+#include <set>
+#include <map>
+#include <vector>
+#include <list>
+#include <deque>
+#if 0
+#include <slist>
+#endif
+
+// Define this macro if you want to hide the expected error, that is,
+// error in the various C++ standard library implementations.
+//
+//#define BOOST_HIDE_EXPECTED_ERRORS
+
+int
+main()
+{
+ using namespace boost;
+
+#if defined(_ITERATOR_) && defined(BOOST_HIDE_EXPECTED_ERRORS)
+ // VC++ STL implementation is not standard conformant and
+ // fails to pass these concept checks
+#else
+ typedef std::vector<int> Vector;
+ typedef std::deque<int> Deque;
+ typedef std::list<int> List;
+
+ // VC++ missing pointer and const_pointer typedefs
+ function_requires< Mutable_RandomAccessContainer<Vector> >();
+ function_requires< BackInsertionSequence<Vector> >();
+
+#if !(defined(__GNUC__) && defined(BOOST_HIDE_EXPECTED_ERRORS))
+#if !((defined(__sgi) || (defined(__DECCXX) && defined(_RWSTD_VER) && _RWSTD_VER <= 0x0203)) \
+ && defined(BOOST_HIDE_EXPECTED_ERRORS))
+ // old deque iterator missing n + iter operation
+ function_requires< Mutable_RandomAccessContainer<Deque> >();
+#endif
+ // warnings about signed and unsigned in old deque version
+ function_requires< FrontInsertionSequence<Deque> >();
+ function_requires< BackInsertionSequence<Deque> >();
+#endif
+
+ // VC++ missing pointer and const_pointer typedefs
+ function_requires< Mutable_ReversibleContainer<List> >();
+ function_requires< FrontInsertionSequence<List> >();
+ function_requires< BackInsertionSequence<List> >();
+
+#if 0
+ typedef BOOST_STD_EXTENSION_NAMESPACE::slist<int> SList;
+ function_requires< FrontInsertionSequence<SList> >();
+#endif
+
+ typedef std::set<int> Set;
+ typedef std::multiset<int> MultiSet;
+ typedef std::map<int,int> Map;
+ typedef std::multimap<int,int> MultiMap;
+
+ function_requires< SortedAssociativeContainer<Set> >();
+ function_requires< SimpleAssociativeContainer<Set> >();
+ function_requires< UniqueAssociativeContainer<Set> >();
+
+ function_requires< SortedAssociativeContainer<MultiSet> >();
+ function_requires< SimpleAssociativeContainer<MultiSet> >();
+ function_requires< MultipleAssociativeContainer<MultiSet> >();
+
+ function_requires< SortedAssociativeContainer<Map> >();
+ function_requires< UniqueAssociativeContainer<Map> >();
+ function_requires< PairAssociativeContainer<Map> >();
+
+ function_requires< SortedAssociativeContainer<MultiMap> >();
+ function_requires< MultipleAssociativeContainer<MultiMap> >();
+ function_requires< PairAssociativeContainer<MultiMap> >();
+#endif
+
+ return 0;
+}
diff --git a/test/stl_concept_covering.cpp b/test/stl_concept_covering.cpp
new file mode 100644
index 0000000..6d3144d
--- /dev/null
+++ b/test/stl_concept_covering.cpp
@@ -0,0 +1,916 @@
+// (C) Copyright Jeremy Siek 2000-2002.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// This file doesn't work on other compilers.
+#if defined(__GNUC__) || defined(__KCC)
+
+#include <algorithm>
+#include <numeric>
+#include <boost/config.hpp>
+#include <boost/concept_check.hpp>
+#include <boost/concept_archetype.hpp>
+
+/*
+
+ This file uses the archetype classes to find out which concepts
+ actually *cover* the STL algorithms true requirements. The
+ archetypes/concepts chosen do not necessarily match the C++ standard
+ or the SGI STL documentation, but instead were chosen based on the
+ minimal concepts that current STL implementations require, which in
+ many cases is less stringent than the standard. In some places there
+ was significant differences in the implementations' requirements and
+ in those places macros were used to select different requirements,
+ the purpose being to document what the requirements of various
+ implementations are. It is an open issue as to whether the C++
+ standard should be changed to reflect these weaker requirements.
+
+*/
+
+boost::detail::dummy_constructor dummy_cons;
+
+// This is a special concept needed for std::swap_ranges.
+// It is mutually convertible, and also SGIAssignable
+template <class T>
+class mutually_convertible_archetype
+{
+private:
+ mutually_convertible_archetype() { }
+public:
+ mutually_convertible_archetype(const mutually_convertible_archetype&) { }
+ mutually_convertible_archetype&
+ operator=(const mutually_convertible_archetype&)
+ { return *this; }
+ mutually_convertible_archetype(boost::detail::dummy_constructor) { }
+
+ template <class U>
+ mutually_convertible_archetype&
+ operator=(const mutually_convertible_archetype<U>&)
+ { return *this; }
+
+};
+
+
+// for std::accumulate
+namespace accum
+{
+ typedef boost::sgi_assignable_archetype<> Ret;
+ struct T {
+ T(const Ret&) { }
+ T(boost::detail::dummy_constructor x) { }
+ };
+ typedef boost::null_archetype<> Tin;
+ Ret operator+(const T&, const Tin&) {
+ return Ret(dummy_cons);
+ }
+}
+
+// for std::inner_product
+namespace inner_prod
+{
+ typedef boost::sgi_assignable_archetype<> RetAdd;
+ typedef boost::sgi_assignable_archetype<> RetMult;
+ struct T {
+ T(const RetAdd&) { }
+ T(boost::detail::dummy_constructor x) { }
+ };
+ typedef boost::null_archetype<int> Tin1;
+ typedef boost::null_archetype<char> Tin2;
+}
+
+namespace boost { // so Koenig lookup will find
+
+ inner_prod::RetMult
+ operator*(const inner_prod::Tin1&, const inner_prod::Tin2&) {
+ return inner_prod::RetMult(dummy_cons);
+ }
+ inner_prod::RetAdd
+ operator+(const inner_prod::T&,
+ const inner_prod::RetMult&) {
+ return inner_prod::RetAdd(dummy_cons);
+ }
+}
+
+
+// for std::partial_sum and adj_diff
+namespace part_sum
+{
+ class T {
+ public:
+ typedef boost::sgi_assignable_archetype<> Ret;
+ T(const Ret&) { }
+ T(boost::detail::dummy_constructor x) { }
+ private:
+ T() { }
+ };
+ T::Ret operator+(const T&, const T&) {
+ return T::Ret(dummy_cons);
+ }
+ T::Ret operator-(const T&, const T&) {
+ return T::Ret(dummy_cons);
+ }
+}
+
+// for std::power
+
+namespace power_stuff {
+ struct monoid_archetype {
+ monoid_archetype(boost::detail::dummy_constructor x) { }
+ };
+
+ boost::multipliable_archetype<monoid_archetype>
+ identity_element
+ (std::multiplies< boost::multipliable_archetype<monoid_archetype> >)
+ {
+ return boost::multipliable_archetype<monoid_archetype>(dummy_cons);
+ }
+}
+
+struct tag1 { };
+struct tag2 { };
+
+
+int
+main()
+{
+ using namespace boost;
+
+ //===========================================================================
+ // Non-mutating Algorithms
+ {
+ input_iterator_archetype< null_archetype<> > in;
+ unary_function_archetype< null_archetype<> , null_archetype<> >
+ f(dummy_cons);
+ std::for_each(in, in, f);
+ }
+ // gcc bug
+ {
+ typedef equality_comparable2_first_archetype<> Left;
+ input_iterator_archetype< Left > in;
+ equality_comparable2_second_archetype<> value(dummy_cons);
+ in = std::find(in, in, value);
+ }
+ {
+ typedef null_archetype<> T;
+ input_iterator_archetype<T> in;
+ unary_predicate_archetype<T> pred(dummy_cons);
+ in = std::find_if(in, in, pred);
+ }
+ {
+ forward_iterator_archetype< equality_comparable_archetype<> > fo;
+ fo = std::adjacent_find(fo, fo);
+ }
+ {
+ forward_iterator_archetype<
+ convertible_to_archetype< null_archetype<> > > fo;
+ binary_predicate_archetype<null_archetype<> , null_archetype<> >
+ pred(dummy_cons);
+ fo = std::adjacent_find(fo, fo, pred);
+ }
+ // gcc bug
+ {
+ typedef equal_op_first_archetype<> Left;
+ input_iterator_archetype<Left> in;
+ typedef equal_op_second_archetype<> Right;
+ forward_iterator_archetype<Right> fo;
+ in = std::find_first_of(in, in, fo, fo);
+ }
+ {
+ typedef equal_op_first_archetype<> Left;
+ typedef input_iterator_archetype<Left> InIter;
+ InIter in;
+ function_requires< InputIterator<InIter> >();
+ equal_op_second_archetype<> value(dummy_cons);
+ std::iterator_traits<InIter>::difference_type
+ n = std::count(in, in, value);
+ ignore_unused_variable_warning(n);
+ }
+ {
+ typedef input_iterator_archetype< null_archetype<> > InIter;
+ InIter in;
+ unary_predicate_archetype<null_archetype<> > pred(dummy_cons);
+ std::iterator_traits<InIter>::difference_type
+ n = std::count_if(in, in, pred);
+ ignore_unused_variable_warning(n);
+ }
+ // gcc bug
+ {
+ typedef equal_op_first_archetype<> Left;
+ typedef input_iterator_archetype<Left> InIter1;
+ InIter1 in1;
+ typedef equal_op_second_archetype<> Right;
+ typedef input_iterator_archetype<Right> InIter2;
+ InIter2 in2;
+ std::pair<InIter1, InIter2> p = std::mismatch(in1, in1, in2);
+ ignore_unused_variable_warning(p);
+ }
+ {
+ typedef input_iterator_archetype<null_archetype<> > InIter;
+ InIter in1, in2;
+ binary_predicate_archetype<null_archetype<> , null_archetype<> >
+ pred(dummy_cons);
+ std::pair<InIter, InIter> p = std::mismatch(in1, in1, in2, pred);
+ ignore_unused_variable_warning(p);
+ }
+ // gcc bug
+ {
+ typedef equality_comparable2_first_archetype<> Left;
+ input_iterator_archetype<Left> in1;
+ typedef equality_comparable2_second_archetype<> Right;
+ input_iterator_archetype<Right> in2;
+ bool b = std::equal(in1, in1, in2);
+ ignore_unused_variable_warning(b);
+ }
+ {
+ input_iterator_archetype< null_archetype<> >
+ in1, in2;
+ binary_predicate_archetype<null_archetype<> , null_archetype<> >
+ pred(dummy_cons);
+ bool b = std::equal(in1, in1, in2, pred);
+ ignore_unused_variable_warning(b);
+ }
+ {
+ typedef equality_comparable2_first_archetype<> Left;
+ forward_iterator_archetype<Left> fo1;
+ typedef equality_comparable2_second_archetype<> Right;
+ forward_iterator_archetype<Right> fo2;
+ fo1 = std::search(fo1, fo1, fo2, fo2);
+ }
+ {
+ typedef equality_comparable2_first_archetype<
+ convertible_to_archetype<null_archetype<> > > Left;
+ forward_iterator_archetype<Left> fo1;
+ typedef equality_comparable2_second_archetype<
+ convertible_to_archetype<null_archetype<> > > Right;
+ forward_iterator_archetype<Right> fo2;
+ binary_predicate_archetype<null_archetype<> , null_archetype<> >
+ pred(dummy_cons);
+ fo1 = std::search(fo1, fo1, fo2, fo2, pred);
+ }
+ {
+ typedef equality_comparable2_first_archetype<> Left;
+ forward_iterator_archetype<Left> fo;
+ equality_comparable2_second_archetype<> value(dummy_cons);
+ int n = 1;
+ fo = std::search_n(fo, fo, n, value);
+ }
+ {
+ forward_iterator_archetype<
+ convertible_to_archetype<null_archetype<> > > fo;
+ convertible_to_archetype<null_archetype<> > value(dummy_cons);
+ binary_predicate_archetype<null_archetype<> , null_archetype<> >
+ pred(dummy_cons);
+ int n = 1;
+ fo = std::search_n(fo, fo, n, value, pred);
+ }
+ {
+ typedef equality_comparable2_first_archetype<> Left;
+ forward_iterator_archetype<Left> fo1;
+ typedef equality_comparable2_second_archetype<null_archetype<> > Right;
+ forward_iterator_archetype<Right> fo2;
+ fo1 = std::find_end(fo1, fo1, fo2, fo2);
+ }
+ {
+ // equality comparable required because find_end() calls search
+ typedef equality_comparable2_first_archetype<
+ convertible_to_archetype<null_archetype<> > > Left;
+ forward_iterator_archetype<Left> fo1;
+ typedef equality_comparable2_second_archetype<
+ convertible_to_archetype<null_archetype<> > > Right;
+ forward_iterator_archetype<Right> fo2;
+ binary_predicate_archetype<null_archetype<> , null_archetype<> >
+ pred(dummy_cons);
+ fo1 = std::find_end(fo1, fo1, fo2, fo2, pred);
+ }
+
+ //===========================================================================
+ // Mutating Algorithms
+
+ {
+ typedef null_archetype<> T;
+ input_iterator_archetype<T> in;
+ output_iterator_archetype<T> out(dummy_cons);
+ out = std::copy(in, in, out);
+ }
+ {
+ typedef assignable_archetype<> OutT;
+ typedef convertible_to_archetype<OutT> InT;
+ bidirectional_iterator_archetype<InT> bid_in;
+ mutable_bidirectional_iterator_archetype<OutT> bid_out;
+ bid_out = std::copy_backward(bid_in, bid_in, bid_out);
+ }
+ {
+ sgi_assignable_archetype<> a(dummy_cons), b(dummy_cons);
+ std::swap(a, b);
+ }
+ {
+ typedef sgi_assignable_archetype<> T;
+ mutable_forward_iterator_archetype<T> a, b;
+ std::iter_swap(a, b);
+ }
+ {
+ typedef mutually_convertible_archetype<int> Tin;
+ typedef mutually_convertible_archetype<char> Tout;
+ mutable_forward_iterator_archetype<Tin> fi1;
+ mutable_forward_iterator_archetype<Tout> fi2;
+ fi2 = std::swap_ranges(fi1, fi1, fi2);
+ }
+ {
+ typedef null_archetype<int> Tin;
+ typedef null_archetype<char> Tout;
+ input_iterator_archetype<Tin> in;
+ output_iterator_archetype<Tout> out(dummy_cons);
+ unary_function_archetype<null_archetype<> ,
+ convertible_to_archetype<Tout> > op(dummy_cons);
+ out = std::transform(in, in, out, op);
+ }
+ {
+ typedef null_archetype<int> Tin1;
+ typedef null_archetype<char> Tin2;
+ typedef null_archetype<double> Tout;
+ input_iterator_archetype<Tin1> in1;
+ input_iterator_archetype<Tin2> in2;
+ output_iterator_archetype<Tout> out(dummy_cons);
+ binary_function_archetype<Tin1, Tin2,
+ convertible_to_archetype<Tout> > op(dummy_cons);
+ out = std::transform(in1, in1, in2, out, op);
+ }
+ {
+ typedef equality_comparable2_first_archetype<
+ assignable_archetype<> > FT;
+ mutable_forward_iterator_archetype<FT> fi;
+ equality_comparable2_second_archetype<
+ convertible_to_archetype<FT> > value(dummy_cons);
+ std::replace(fi, fi, value, value);
+ }
+ {
+ typedef null_archetype<> PredArg;
+ typedef assignable_archetype<
+ convertible_to_archetype<PredArg> > FT;
+ mutable_forward_iterator_archetype<FT> fi;
+ unary_predicate_archetype<PredArg> pred(dummy_cons);
+ convertible_to_archetype<FT> value(dummy_cons);
+ std::replace_if(fi, fi, pred, value);
+ }
+ // gcc bug
+ {
+ // Issue, the use of ?: inside replace_copy() complicates things
+ typedef equal_op_first_archetype<> Tin;
+ typedef null_archetype<> Tout;
+ typedef equal_op_second_archetype< convertible_to_archetype<Tout> > T;
+ input_iterator_archetype<Tin> in;
+ output_iterator_archetype<Tout> out(dummy_cons);
+ T value(dummy_cons);
+ out = std::replace_copy(in, in, out, value, value);
+ }
+ {
+ // The issue of ?: also affects this function
+ typedef null_archetype<> Tout;
+ typedef assignable_archetype< convertible_to_archetype<Tout> > Tin;
+ input_iterator_archetype<Tin> in;
+ output_iterator_archetype<Tout> out(dummy_cons);
+ unary_predicate_archetype<Tin> pred(dummy_cons);
+ Tin value(dummy_cons);
+ out = std::replace_copy_if(in, in, out, pred, value);
+ }
+ {
+ typedef assignable_archetype<> FT;
+ mutable_forward_iterator_archetype<FT> fi;
+ typedef convertible_to_archetype<FT> T;
+ T value(dummy_cons);
+ std::fill(fi, fi, value);
+ }
+ {
+ typedef null_archetype<> Tout;
+ typedef convertible_to_archetype<Tout> T;
+ output_iterator_archetype<Tout> out(dummy_cons);
+ T value(dummy_cons);
+ int n = 1;
+ out = std::fill_n(out, n, value);
+ }
+ {
+ typedef assignable_archetype<> FT;
+ typedef convertible_to_archetype<FT> Ret;
+ mutable_forward_iterator_archetype<FT> fi;
+ generator_archetype<Ret> gen;
+ std::generate(fi, fi, gen);
+ }
+ {
+ typedef assignable_archetype<> FT;
+ typedef convertible_to_archetype<FT> Ret;
+ mutable_forward_iterator_archetype<FT> fi;
+ generator_archetype<Ret> gen;
+ int n = 1;
+ std::generate_n(fi, n, gen);
+ }
+ {
+ typedef assignable_archetype< equality_comparable2_first_archetype<> > FT;
+ typedef equality_comparable2_second_archetype<> T;
+ mutable_forward_iterator_archetype<FT> fi;
+ T value(dummy_cons);
+ fi = std::remove(fi, fi, value);
+ }
+ {
+ typedef assignable_archetype<> FT;
+ mutable_forward_iterator_archetype<FT> fi;
+ typedef null_archetype<> PredArg;
+ unary_predicate_archetype<PredArg> pred(dummy_cons);
+ fi = std::remove_if(fi, fi, pred);
+ }
+ // gcc bug
+ {
+ typedef null_archetype<> Tout;
+ typedef equality_comparable2_first_archetype<
+ convertible_to_archetype<Tout> > Tin;
+ typedef equality_comparable2_second_archetype<> T;
+ input_iterator_archetype<Tin> in;
+ output_iterator_archetype<Tout> out(dummy_cons);
+ T value(dummy_cons);
+ out = std::remove_copy(in, in, out, value);
+ }
+ {
+ typedef null_archetype<> T;
+ input_iterator_archetype<T> in;
+ output_iterator_archetype<T> out(dummy_cons);
+ unary_predicate_archetype<T> pred(dummy_cons);
+ out = std::remove_copy_if(in, in, out, pred);
+ }
+ {
+ typedef sgi_assignable_archetype< equality_comparable_archetype<> > T;
+ mutable_forward_iterator_archetype<T> fi;
+ fi = std::unique(fi, fi);
+ }
+ {
+ typedef null_archetype<int> Arg1;
+ typedef null_archetype<char> Arg2;
+ typedef sgi_assignable_archetype<
+ convertible_to_archetype<Arg1,
+ convertible_to_archetype<Arg2> > > FT;
+ mutable_forward_iterator_archetype<FT> fi;
+ binary_predicate_archetype<Arg1, Arg2> pred(dummy_cons);
+ fi = std::unique(fi, fi, pred);
+ }
+ // gcc bug
+ {
+ typedef equality_comparable_archetype< sgi_assignable_archetype<> > T;
+ input_iterator_archetype<T> in;
+ output_iterator_archetype<T> out(dummy_cons);
+ out = std::unique_copy(in, in, out);
+ }
+ {
+ typedef sgi_assignable_archetype<> T;
+ input_iterator_archetype<T> in;
+ output_iterator_archetype<T> out(dummy_cons);
+ binary_predicate_archetype<T, T> pred(dummy_cons);
+ out = std::unique_copy(in, in, out, pred);
+ }
+ {
+ typedef sgi_assignable_archetype<> T;
+ mutable_bidirectional_iterator_archetype<T> bi;
+ std::reverse(bi, bi);
+ }
+ {
+ typedef null_archetype<> Tout;
+ typedef convertible_to_archetype<Tout> Tin;
+ bidirectional_iterator_archetype<Tin> bi;
+ output_iterator_archetype<Tout> out(dummy_cons);
+ out = std::reverse_copy(bi, bi, out);
+ }
+ {
+ typedef sgi_assignable_archetype<> T;
+ mutable_forward_iterator_archetype<T> fi;
+ // Issue, SGI STL is not have void return type, C++ standard does
+ std::rotate(fi, fi, fi);
+ }
+ {
+ typedef null_archetype<> Tout;
+ typedef convertible_to_archetype<Tout> FT;
+ forward_iterator_archetype<FT> fi;
+ output_iterator_archetype<Tout> out(dummy_cons);
+ out = std::rotate_copy(fi, fi, fi, out);
+ }
+ {
+ typedef sgi_assignable_archetype<> T;
+ mutable_random_access_iterator_archetype<T> ri;
+ std::random_shuffle(ri, ri);
+ }
+ {
+ typedef sgi_assignable_archetype<> T;
+ mutable_random_access_iterator_archetype<T> ri;
+ unary_function_archetype<std::ptrdiff_t, std::ptrdiff_t> ran(dummy_cons);
+ std::random_shuffle(ri, ri, ran);
+ }
+ {
+ typedef null_archetype<> PredArg;
+ typedef sgi_assignable_archetype<convertible_to_archetype<PredArg> > FT;
+ mutable_bidirectional_iterator_archetype<FT> bi;
+ unary_predicate_archetype<PredArg> pred(dummy_cons);
+ bi = std::partition(bi, bi, pred);
+ }
+ {
+ typedef null_archetype<> PredArg;
+ typedef sgi_assignable_archetype<convertible_to_archetype<PredArg> > FT;
+ mutable_forward_iterator_archetype<FT> fi;
+ unary_predicate_archetype<PredArg> pred(dummy_cons);
+ fi = std::stable_partition(fi, fi, pred);
+ }
+
+ //===========================================================================
+ // Sorting Algorithms
+ {
+ typedef sgi_assignable_archetype<
+ less_than_comparable_archetype<> > T;
+ mutable_random_access_iterator_archetype<T> ri;
+ std::sort(ri, ri);
+ }
+ {
+ typedef null_archetype<> Arg;
+ typedef sgi_assignable_archetype<
+ convertible_to_archetype<Arg> > T;
+ mutable_random_access_iterator_archetype<T> ri;
+ binary_predicate_archetype<Arg, Arg> comp(dummy_cons);
+ std::sort(ri, ri, comp);
+ }
+ {
+ typedef less_than_comparable_archetype<
+ sgi_assignable_archetype<> > ValueType;
+ mutable_random_access_iterator_archetype<ValueType> ri;
+ std::stable_sort(ri, ri);
+ }
+ {
+ typedef null_archetype<> Arg;
+ typedef sgi_assignable_archetype<
+ convertible_to_archetype<Arg> > ValueType;
+ mutable_random_access_iterator_archetype<ValueType> ri;
+ binary_predicate_archetype<Arg, Arg> comp(dummy_cons);
+ std::stable_sort(ri, ri, comp);
+ }
+ {
+ typedef sgi_assignable_archetype<
+ less_than_comparable_archetype<> > T;
+ mutable_random_access_iterator_archetype<T> ri;
+ std::partial_sort(ri, ri, ri);
+ }
+
+ {
+ typedef null_archetype<> Arg;
+ typedef sgi_assignable_archetype<
+ convertible_to_archetype<Arg> > T;
+ mutable_random_access_iterator_archetype<T> ri;
+ binary_predicate_archetype<Arg, Arg> comp(dummy_cons);
+ std::partial_sort(ri, ri, ri, comp);
+ }
+ // gcc bug
+ {
+ // This could be formulated so that the two iterators are not
+ // required to have the same value type, but it is messy.
+ typedef sgi_assignable_archetype<
+ less_than_comparable_archetype<> > T;
+ input_iterator_archetype<T> in;
+ mutable_random_access_iterator_archetype<T> ri_out;
+ ri_out = std::partial_sort_copy(in, in , ri_out, ri_out);
+ }
+ {
+ typedef sgi_assignable_archetype<> T;
+ input_iterator_archetype<T> in;
+ mutable_random_access_iterator_archetype<T> ri_out;
+ binary_predicate_archetype<T, T> comp(dummy_cons);
+ ri_out = std::partial_sort_copy(in, in , ri_out, ri_out, comp);
+ }
+ {
+ typedef sgi_assignable_archetype< less_than_comparable_archetype<> > T;
+ mutable_random_access_iterator_archetype<T> ri;
+ std::nth_element(ri, ri, ri);
+ }
+ {
+ typedef null_archetype<int> Arg1;
+ typedef null_archetype<char> Arg2;
+ typedef sgi_assignable_archetype<
+ convertible_to_archetype<Arg1,
+ convertible_to_archetype<Arg2> > > T;
+ mutable_random_access_iterator_archetype<T> ri;
+ binary_predicate_archetype<Arg1, Arg2> comp(dummy_cons);
+ std::nth_element(ri, ri, ri, comp);
+ }
+ {
+#if defined(__GNUC__)
+ typedef less_than_op_first_archetype<> FT;
+ typedef less_than_op_second_archetype<> T;
+#elif defined(__KCC)
+ // The KAI version of this uses a one-argument less-than function
+ // object.
+ typedef less_than_comparable_archetype<> T;
+ typedef convertible_to_archetype<T> FT;
+#endif
+ forward_iterator_archetype<FT> fi;
+ T value(dummy_cons);
+ fi = std::lower_bound(fi, fi, value);
+ }
+ {
+ typedef null_archetype<int> Arg1;
+ typedef null_archetype<char> Arg2;
+ typedef convertible_to_archetype<Arg1> FT;
+ typedef convertible_to_archetype<Arg2> T;
+ forward_iterator_archetype<FT> fi;
+ T value(dummy_cons);
+ binary_predicate_archetype<Arg1, Arg2> comp(dummy_cons);
+ fi = std::lower_bound(fi, fi, value, comp);
+ }
+ {
+#if defined(__GNUC__)
+ // Note, order of T,FT is flipped from lower_bound
+ typedef less_than_op_second_archetype<> FT;
+ typedef less_than_op_first_archetype<> T;
+#elif defined(__KCC)
+ typedef less_than_comparable_archetype<> T;
+ typedef convertible_to_archetype<T> FT;
+#endif
+ forward_iterator_archetype<FT> fi;
+ T value(dummy_cons);
+ fi = std::upper_bound(fi, fi, value);
+ }
+ {
+ typedef null_archetype<int> Arg1;
+ typedef null_archetype<char> Arg2;
+ // Note, order of T,FT is flipped from lower_bound
+ typedef convertible_to_archetype<Arg1> T;
+ typedef convertible_to_archetype<Arg2> FT;
+ forward_iterator_archetype<FT> fi;
+ T value(dummy_cons);
+ binary_predicate_archetype<Arg1, Arg2> comp(dummy_cons);
+ fi = std::upper_bound(fi, fi, value, comp);
+ }
+ {
+#if defined(__GNUC__)
+ typedef less_than_op_first_archetype<
+ less_than_op_second_archetype< null_archetype<>, optag2>, optag1> FT;
+ typedef less_than_op_second_archetype<
+ less_than_op_first_archetype< null_archetype<>, optag2>, optag1> T;
+#elif defined(__KCC)
+ typedef less_than_comparable_archetype<> T;
+ typedef convertible_to_archetype<T> FT;
+#endif
+ typedef forward_iterator_archetype<FT> FIter;
+ FIter fi;
+ T value(dummy_cons);
+ std::pair<FIter,FIter> p = std::equal_range(fi, fi, value);
+ ignore_unused_variable_warning(p);
+ }
+ {
+ typedef null_archetype<int> Arg1;
+ typedef null_archetype<char> Arg2;
+ typedef convertible_to_archetype<Arg1,
+ convertible_to_archetype<Arg2> > FT;
+ typedef convertible_to_archetype<Arg2,
+ convertible_to_archetype<Arg1> > T;
+ typedef forward_iterator_archetype<FT> FIter;
+ FIter fi;
+ T value(dummy_cons);
+ binary_predicate_archetype<Arg1, Arg2> comp(dummy_cons);
+ std::pair<FIter,FIter> p = std::equal_range(fi, fi, value, comp);
+ ignore_unused_variable_warning(p);
+ }
+ {
+#if defined(__GNUC__)
+ typedef less_than_op_first_archetype<
+ less_than_op_second_archetype<null_archetype<>, optag2>, optag1> FT;
+ typedef less_than_op_second_archetype<
+ less_than_op_first_archetype<null_archetype<>, optag2>, optag1> T;
+#elif defined(__KCC)
+ typedef less_than_op_first_archetype< less_than_comparable_archetype<> > T;
+ typedef less_than_op_second_archetype< convertible_to_archetype<T> > FT;
+#endif
+ forward_iterator_archetype<FT> fi;
+ T value(dummy_cons);
+ bool b = std::binary_search(fi, fi, value);
+ ignore_unused_variable_warning(b);
+ }
+ {
+ typedef null_archetype<int> Arg1;
+ typedef null_archetype<char> Arg2;
+#if defined(__GNUC__) || defined(__KCC)
+ typedef convertible_to_archetype<Arg1,
+ convertible_to_archetype<Arg2> > FT;
+ typedef convertible_to_archetype<Arg2,
+ convertible_to_archetype<Arg1> > T;
+#endif
+ typedef forward_iterator_archetype<FT> FIter;
+ FIter fi;
+ T value(dummy_cons);
+ binary_predicate_archetype<Arg1, Arg2> comp(dummy_cons);
+ bool b = std::binary_search(fi, fi, value, comp);
+ ignore_unused_variable_warning(b);
+ }
+ {
+ typedef null_archetype<> Tout;
+#if defined(__GNUC__) || defined(__KCC)
+ typedef less_than_op_first_archetype<
+ less_than_op_second_archetype<
+ convertible_to_archetype<Tout>, optag2>, optag1 > Tin1;
+ typedef less_than_op_second_archetype<
+ less_than_op_first_archetype<
+ convertible_to_archetype<Tout>, optag2> ,optag1> Tin2;
+#endif
+ // gcc bug
+ input_iterator_archetype<Tin1> in1;
+ input_iterator_archetype<Tin2> in2;
+ output_iterator_archetype<Tout> out(dummy_cons);
+ out = std::merge(in1, in1, in2, in2, out);
+ out = std::set_union(in1, in1, in2, in2, out);
+ out = std::set_intersection(in1, in1, in2, in2, out);
+ out = std::set_difference(in1, in1, in2, in2, out);
+ out = std::set_symmetric_difference(in1, in1, in2, in2, out);
+ }
+ {
+ typedef null_archetype<> T;
+ input_iterator_archetype<T> in1;
+ input_iterator_archetype<T,2> in2;
+ typedef convertible_from_archetype<T> Tout;
+ output_iterator_archetype<T> out(dummy_cons);
+ binary_predicate_archetype<T, T> comp(dummy_cons);
+ out = std::merge(in1, in1, in2, in2, out, comp);
+ out = std::set_union(in1, in1, in2, in2, out, comp);
+ out = std::set_intersection(in1, in1, in2, in2, out, comp);
+ out = std::set_difference(in1, in1, in2, in2, out, comp);
+ out = std::set_symmetric_difference(in1, in1, in2, in2, out, comp);
+ }
+ {
+ typedef sgi_assignable_archetype<
+ less_than_comparable_archetype<> > T;
+ mutable_bidirectional_iterator_archetype<T> bi;
+ std::inplace_merge(bi, bi, bi);
+ }
+ {
+ typedef null_archetype<> Arg;
+ typedef sgi_assignable_archetype<
+ convertible_to_archetype<Arg> > T;
+ mutable_bidirectional_iterator_archetype<T> bi;
+ binary_predicate_archetype<Arg, Arg> comp(dummy_cons);
+ std::inplace_merge(bi, bi, bi, comp);
+ }
+ // gcc bug
+ {
+ typedef less_than_op_first_archetype<
+ less_than_op_second_archetype<null_archetype<>, optag1>, optag2> Tin1;
+ typedef less_than_op_second_archetype<
+ less_than_op_first_archetype<null_archetype<>, optag1>, optag2> Tin2;
+ input_iterator_archetype<Tin1> in1;
+ input_iterator_archetype<Tin2> in2;
+ bool b = std::includes(in1, in1, in2, in2);
+ b = std::lexicographical_compare(in1, in1, in2, in2);
+ ignore_unused_variable_warning(b);
+ }
+ {
+ typedef null_archetype<int> Tin;
+ input_iterator_archetype<Tin> in1;
+ input_iterator_archetype<Tin,1> in2;
+ binary_predicate_archetype<Tin, Tin> comp(dummy_cons);
+ bool b = std::includes(in1, in1, in2, in2, comp);
+ b = std::lexicographical_compare(in1, in1, in2, in2, comp);
+ ignore_unused_variable_warning(b);
+ }
+ {
+ typedef sgi_assignable_archetype<
+ less_than_comparable_archetype<> > T;
+ mutable_random_access_iterator_archetype<T> ri;
+ std::push_heap(ri, ri);
+ std::pop_heap(ri, ri);
+ std::make_heap(ri, ri);
+ std::sort_heap(ri, ri);
+ }
+ {
+ typedef null_archetype<> Arg;
+ typedef sgi_assignable_archetype<
+ convertible_to_archetype<Arg> > T;
+ mutable_random_access_iterator_archetype<T> ri;
+ binary_predicate_archetype<Arg, Arg> comp(dummy_cons);
+ std::push_heap(ri, ri, comp);
+ std::pop_heap(ri, ri, comp);
+ std::make_heap(ri, ri, comp);
+ std::sort_heap(ri, ri, comp);
+ }
+ {
+ typedef less_than_comparable_archetype<> T;
+ T a(dummy_cons), b(dummy_cons);
+ BOOST_USING_STD_MIN();
+ BOOST_USING_STD_MAX();
+ const T& c = min BOOST_PREVENT_MACRO_SUBSTITUTION(a, b);
+ const T& d = max BOOST_PREVENT_MACRO_SUBSTITUTION(a, b);
+ ignore_unused_variable_warning(c);
+ ignore_unused_variable_warning(d);
+ }
+ {
+ typedef null_archetype<> Arg;
+ binary_predicate_archetype<Arg, Arg> comp(dummy_cons);
+ typedef convertible_to_archetype<Arg> T;
+ T a(dummy_cons), b(dummy_cons);
+ BOOST_USING_STD_MIN();
+ BOOST_USING_STD_MAX();
+ const T& c = min BOOST_PREVENT_MACRO_SUBSTITUTION(a, b, comp);
+ const T& d = max BOOST_PREVENT_MACRO_SUBSTITUTION(a, b, comp);
+ ignore_unused_variable_warning(c);
+ ignore_unused_variable_warning(d);
+ }
+ {
+ typedef less_than_comparable_archetype<> T;
+ forward_iterator_archetype<T> fi;
+ fi = std::min_element(fi, fi);
+ fi = std::max_element(fi, fi);
+ }
+ {
+ typedef null_archetype<> Arg;
+ binary_predicate_archetype<Arg, Arg> comp(dummy_cons);
+ typedef convertible_to_archetype<Arg> T;
+ forward_iterator_archetype<T> fi;
+ fi = std::min_element(fi, fi, comp);
+ fi = std::max_element(fi, fi, comp);
+ }
+ {
+ typedef sgi_assignable_archetype<
+ less_than_comparable_archetype<> > T;
+ mutable_bidirectional_iterator_archetype<T> bi;
+ bool b = std::next_permutation(bi, bi);
+ b = std::prev_permutation(bi, bi);
+ ignore_unused_variable_warning(b);
+ }
+ {
+ typedef null_archetype<> Arg;
+ binary_predicate_archetype<Arg, Arg> comp(dummy_cons);
+ typedef sgi_assignable_archetype<
+ convertible_to_archetype<Arg> > T;
+ mutable_bidirectional_iterator_archetype<T> bi;
+ bool b = std::next_permutation(bi, bi, comp);
+ b = std::prev_permutation(bi, bi, comp);
+ ignore_unused_variable_warning(b);
+ }
+ //===========================================================================
+ // Generalized Numeric Algorithms
+
+ {
+ // Bummer, couldn't use plus_op because of a problem with
+ // mutually recursive types.
+ input_iterator_archetype<accum::Tin> in;
+ accum::T init(dummy_cons);
+ init = std::accumulate(in, in, init);
+ }
+ {
+ typedef null_archetype<int> Arg1;
+ typedef null_archetype<char> Arg2;
+ typedef sgi_assignable_archetype<
+ convertible_to_archetype<Arg1> > T;
+ typedef convertible_to_archetype<T> Ret;
+ input_iterator_archetype<Arg2> in;
+ T init(dummy_cons);
+ binary_function_archetype<Arg1, Arg2, Ret> op(dummy_cons);
+ init = std::accumulate(in, in, init, op);
+ }
+ {
+ input_iterator_archetype<inner_prod::Tin1> in1;
+ input_iterator_archetype<inner_prod::Tin2> in2;
+ inner_prod::T init(dummy_cons);
+ init = std::inner_product(in1, in1, in2, init);
+ }
+ {
+ typedef null_archetype<int> MultArg1;
+ typedef null_archetype<char> MultArg2;
+ typedef null_archetype<short> AddArg1;
+ typedef null_archetype<long> AddArg2;
+ typedef sgi_assignable_archetype<
+ convertible_to_archetype<AddArg1> > T;
+ typedef convertible_to_archetype<AddArg2> RetMult;
+ typedef convertible_to_archetype<T> RetAdd;
+ input_iterator_archetype<MultArg1> in1;
+ input_iterator_archetype<MultArg2> in2;
+ T init(dummy_cons);
+ binary_function_archetype<MultArg1, MultArg2, RetMult> mult_op(dummy_cons);
+ binary_function_archetype<AddArg1, AddArg2, RetAdd> add_op(dummy_cons);
+ init = std::inner_product(in1, in1, in2, init, add_op, mult_op);
+ }
+ {
+ input_iterator_archetype<part_sum::T> in;
+ output_iterator_archetype<part_sum::T> out(dummy_cons);
+ out = std::partial_sum(in, in, out);
+ }
+ {
+ typedef sgi_assignable_archetype<> T;
+ input_iterator_archetype<T> in;
+ output_iterator_archetype<T> out(dummy_cons);
+ binary_function_archetype<T, T, T> add_op(dummy_cons);
+ out = std::partial_sum(in, in, out, add_op);
+ binary_function_archetype<T, T, T> subtract_op(dummy_cons);
+ out = std::adjacent_difference(in, in, out, subtract_op);
+ }
+ {
+ input_iterator_archetype<part_sum::T> in;
+ output_iterator_archetype<part_sum::T> out(dummy_cons);
+ out = std::adjacent_difference(in, in, out);
+ }
+ return 0;
+}
+
+#else
+
+int main() {}
+
+#endif
diff --git a/test/usage_fail.cpp b/test/usage_fail.cpp
new file mode 100644
index 0000000..29796b9
--- /dev/null
+++ b/test/usage_fail.cpp
@@ -0,0 +1,22 @@
+// Copyright David Abrahams 2006. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/concept/usage.hpp>
+
+template <class T>
+struct StringInitializable
+{
+ typedef int associated;
+ BOOST_CONCEPT_USAGE(StringInitializable)
+ {
+ T x = "foo";
+ }
+};
+
+// Test that accessing an associated type will actually exercise usage
+// requirements
+typedef StringInitializable<int>::associated tee;
+
+
+
diff --git a/test/where.cpp b/test/where.cpp
new file mode 100644
index 0000000..dfbfd02
--- /dev/null
+++ b/test/where.cpp
@@ -0,0 +1,13 @@
+// Copyright David Abrahams 2006. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+#include <vector>
+#undef NDEBUG
+#include "fake_sort.hpp"
+
+int main()
+{
+ std::vector<int> v;
+ fake::sort(v.begin(), v.end());
+ return 0;
+}
diff --git a/test/where_fail.cpp b/test/where_fail.cpp
new file mode 100644
index 0000000..e56b40f
--- /dev/null
+++ b/test/where_fail.cpp
@@ -0,0 +1,13 @@
+// Copyright David Abrahams 2006. Distributed under the Boost
+// Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+#include <list>
+#undef NDEBUG
+#include "fake_sort.hpp"
+
+int main()
+{
+ std::list<int> v;
+ fake::sort(v.begin(), v.end());
+ return 0;
+}
diff --git a/using_concept_check.htm b/using_concept_check.htm
new file mode 100644
index 0000000..80c95cb
--- /dev/null
+++ b/using_concept_check.htm
@@ -0,0 +1,186 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
+ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
+
+<html xmlns="http://www.w3.org/1999/xhtml">
+<!-- Copyright (c) Jeremy Siek and Andrew Lumsdaine 2000 -->
+<!-- Distributed under the Boost -->
+<!-- Software License, Version 1.0. (See accompanying -->
+<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
+
+<head>
+ <meta name="generator" content=
+ "HTML Tidy for Linux/x86 (vers 1 September 2005), see www.w3.org" />
+ <meta http-equiv="Content-Type" content="text/html; charset=us-ascii" />
+
+ <title>Using Concept Checks</title>
+ <link rel="stylesheet" href="../../rst.css" type="text/css" />
+</head>
+
+<body bgcolor="#FFFFFF" link="#0000EE" text="#000000" vlink="#551A8B" alink=
+"#FF0000">
+ <img src="../../boost.png" alt="C++ Boost" width="277" height=
+ "86" /><br clear="none" />
+
+ <h2><a name="using-concept-checks" id="using-concept-checks">Using Concept
+ Checks</a></h2>
+
+ <p>For each concept there is a concept checking class template that can be
+ used to make sure that a given type (or set of types) models the concept.
+ The Boost Concept Checking Library (BCCL) includes concept checking class
+ templates for all of the concepts used in the C++ standard library and a
+ few more. See the <a href="./reference.htm">Reference</a> section for a
+ complete list. In addition, other boost libraries come with concept
+ checking classes for the concepts that are particular to those libraries.
+ For example, there are <a href="../graph/doc/graph_concepts.html">graph
+ concepts</a> and <a href="../property_map/doc/property_map.html">property map
+ concepts</a>. Also, whenever <b>anyone</b> writing function templates needs
+ to express requirements that are not yet stated by an existing concept, a
+ new concept checking class should be created. How to do this is explained
+ in <a href="./creating_concepts.htm">Creating Concept Checking
+ Classes</a>.</p>
+
+ <p>An example of a concept checking class from the BCCL is the
+ <tt>EqualityComparableConcept</tt> class. The class corresponds to the
+ EqualityComparable requirements described in 20.1.1 of the C++ Standard,
+ and to the <a href=
+ "http://www.sgi.com/tech/stl/EqualityComparable.html">EqualityComparable</a>
+ concept documented in the SGI STL.</p>
+ <pre>
+template <class T>
+struct EqualityComparable;
+</pre>
+
+ <p>The template argument is the type to be checked. That is, the purpose of
+ <tt>EqualityComparable<<em>T</em>></tt> is to make sure that
+ <tt><em>T</em></tt> models the EqualityComparable concept.</p>
+
+ <h4><tt>BOOST_CONCEPT_ASSERT()</tt></h4>
+
+ <p>The most versatile way of checking concept requirements is to use the
+ <code>BOOST_CONCEPT_ASSERT()</code> macro. You can use this macro at any
+ scope, by passing a concept checking template specialization enclosed in
+ parentheses. <strong>Note:</strong> that means invocations of
+ <code>BOOST_CONCEPT_ASSERT</code> will appear to use <strong>double
+ parentheses</strong>.</p>
+ <pre>
+<font color="green">// In my library:</font>
+template <class T>
+void generic_library_function(T x)
+{
+ BOOST_CONCEPT_ASSERT<strong>((</strong>EqualityComparable<T><strong>))</strong>;
+ <font color="green">// ...</font>
+};
+
+template <class It>
+class generic_library_class
+{
+ BOOST_CONCEPT_ASSERT<strong>((</strong>RandomAccessIterator<It><strong>))</strong>;
+ <font color="green">// ...</font>
+};
+
+<font color="green">// In the user's code:</font>
+class foo {
+ <font color="green">//... </font>
+};
+
+int main() {
+ foo x;
+ generic_library_function(x);
+ generic_library_class<std::vector<char>::iterator> y;
+ <font color="green">//...</font>
+}
+</pre>
+
+ <h4><tt>BOOST_CONCEPT_REQUIRES</tt></h4>
+
+ <p>One of the nice things about the proposed C++0x <a href=
+ "http://www.generic-programming.org/languages/conceptcpp/tutorial">syntax
+ for declaring concept constrained function templates</a> is the way that
+ constraints are part of the function <em>declaration</em>, so clients will
+ see them. <code>BOOST_CONCEPT_ASSERT</code> can only express constraints
+ within the function template definition, which hides the constraint in the
+ function body. Aside from the loss of a self-documenting interface,
+ asserting conformance only in the function body can undesirably delay
+ checking if the function is explicitly instantiated in a different
+ translation unit from the one in which it is called, or if the compiler
+ does link-time instantiation.</p>
+
+ <p>The <tt>BOOST_CONCEPT_REQUIRES</tt> macro can be used in a function
+ template declaration to check whether some type models a concept. It
+ accepts two arguments, a <strong>list of constraints</strong>, and the
+ function template's return type. The list of constraints takes the form of
+ a sequence of adjacent concept checking template specializations,
+ <strong>in double parentheses</strong>, and the function's return type must
+ also be parenthesized. For example, the standard <code>stable_sort</code>
+ algorithm might be declared as follows: </p>
+ <pre>
+template <class RanIter>
+BOOST_CONCEPT_REQUIRES(
+ ((Mutable_RandomAccessIterator<RanIter>))
+ ((LessThanComparable<typename Mutable_RandomAccessIterator<RanIter>::value_type>)),
+ (void)) <font color="green">// return type</font>
+ stable_sort(RanIter,RanIter);
+</pre>
+
+ <p>Note that the algorithm requires that the value type of the iterator be
+ LessThanComparable, and it accesses that value type through the
+ <code>Mutable_RandomAccessIterator</code> concept checking template. In
+ general, the Boost concept checking classes expose associated types as
+ nested member typedefs so that you can use this syntax, which mimics the
+ approach used in the concept support proposed for the next version of
+ C++.</p>
+
+ <h4>Multi-Type Concepts</h4>
+
+ <p>Some concepts deal with more than one type. In this case the
+ corresponding concept checking class will have multiple template
+ parameters. The following example shows how <tt>BOOST_CONCEPT_REQUIRES</tt>
+ is used with the <a href=
+ "../property_map/doc/ReadWritePropertyMap.html">ReadWritePropertyMap</a>
+ concept, which takes two type parameters: a property map and the key type
+ for the map.</p>
+ <pre>
+template <class G, class Buffer, class BFSVisitor,
+ class ColorMap>
+BOOST_CONCEPT_REQUIRES(
+ ((ReadWritePropertyMap<ColorMap, typename IncidenceGraph<G>::vertex_descriptor>)),
+ (void)) <font color="green">// return type</font>
+breadth_first_search(G& g,
+ typename graph_traits<IncidenceGraph>::vertex_descriptor s,
+ Buffer& Q, BFSVisitor vis, ColorMap color)
+{
+ typedef typename IncidenceGraph<G>::vertex_descriptor Vertex;
+ ...
+}
+</pre>
+
+ <p>Although concept checks are designed for use by generic library
+ implementors, they can also be useful to end users. Sometimes one may not
+ be sure whether some type models a particular concept. The syntactic
+ requirements, at least, can easily be checked by creating a small program
+ and using <tt>BOOST_CONCEPT_ASSERT</tt> with the type and concept in
+ question. For example:</p>
+ <pre>
+<font color=
+"green">// Make sure list<int> has bidirectional iterators.</font>
+BOOST_CONCEPT_ASSERT((BidirectionalIterator<std::list<int>::iterator>));
+</pre>
+
+ <p><a href="./concept_check.htm">Prev: Concept Checking
+ Introduction</a><br />
+ <a href="./creating_concepts.htm">Next: Creating Concept Checking
+ Classes</a><br /></p>
+ <hr />
+
+ <table>
+ <tr valign="top">
+ <td nowrap="nowrap">Copyright © 2000</td>
+
+ <td><a href="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</a>(<a href=
+ "mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</a>) Andrew
+ Lumsdaine(<a href="mailto:lums@osl.iu.edu">lums@osl.iu.edu</a>), 2007
+ <a href="mailto:dave@boost-consulting.com">David Abrahams</a>.</td>
+ </tr>
+ </table>
+</body>
+</html>