1. Basic Concepts
=================

1.1. Trivial Container
----------------------

Trivial Container is a refactoring of the existing Container concept: it has
iterator types:

  X::iterator
  X::const_iterator

which are models of Trivial Iterator. This provides weaker guarantees than
Container, which has iterator types modeling Input Iterator. The member
functions:

  a.begin()
  a.end()

are NOT present in a Trivial Container. These aside, Trivial Container is
identical to Container. Container can be viewed as a refinement of Trivial
Container, analogous to Input Iterator's relationship to Trivial Iterator.

1.2. Multiply Traversable Container
-----------------------------------

Multiply Traversable Container is a refinement of Trivial Container, similar
to the existing Container concept except that no single ordering of the
elements in the container may be considered canonical. It therefore
parametrizes iteration on traversal policy:

  X::iterator<InputTraversal>
  X::const_iterator<InputTraversal>

which when instantiated are models of Input Iterator. (See section 1.5 below
for detail on traversals). The expressions:

  a.begin<InputTraversal>()
  a.end<InputTraversal>()

are introduced to mirror Container's analogous methods, and return iterators
with the specified traversal policy to the beginning and end of the container
respectively.

1.3. Forward Multiply Traversable Container
-------------------------------------------

Forward Multiply Traversable Container refines Multiply Traversable Container
and Equality Comparable, providing the additional guarantee that iterators
into the container are Forward Iterators (and consequently that traversals
are Forward Traversals), making multi-pass algorithms possible.

Unlike Forward Container, it does not refine Less Than Comparable, because
no single ordering of the elements in the container may be considered
definitive. See 3.1 (class single_traversal) below for a way to treat instances
of these container concepts as their analogous pre-existing Containers.

[NOTE: For those iterators that are Assignable -- that is, Output Iterator and
its refinements -- it's important to be able to convert between traversal
policies. They wouldn't be much good if they weren't interchangeable. So for
iterators i and j of types Iterator<T> and Iterator<U>, the expressions:

  Iterator<T>(j)
  Iterator<T> i(j)
  Iterator<T> i = j
  i = j
  swap(i, j)

must be legal. That implies a copy constructor and assignment operator like:

  template <typename T> struct Iter {
    template <typename U> Iter (const Iter<U>&);
    template <typename U> Iter& operator = (const Iter<U>&);
  };

for all iterators in Forward Multiply Traversable Containers.]

1.4. Reversible Multiply Traversable Container
----------------------------------------------

Reversible Multiply Traversable Container is a refinement of Forward Multiply
Traversable Container, whose iterators are Bidirectional Iterators. Additional
iterator templates are provided:

  X::reverse_iterator<BidirectionalTraversal>
  X::const_reverse_iterator<BidirectionalTraversal>

as well as member function templates:

  a.rbegin<BidirectionalTraversal>()
  a.rend<BidirectionalTraversal>()

This is analogous to Reversible Container, except the guarantees that, for
a given traversal policy t:

  a.begin<t>() == a.rend<t>()
  a.end<t>() == a.rbegin<t>()

no longer necessarily hold.

[NOTE: This is a roundabout way of admitting, without mentioning trees
specifically, that the reverse of a preorder traversal of a tree is not the
same as a preorder traversal of the reverse of a tree. This seems kind of
appropriate, given that this concept doesn't limit itself to trees only.

On the other hand, we could force these guarantees, which would still have a
possibly acceptable result for trees: Whereas the range

  [ a.begin<pre_order_traversal>(), a.end<pre_order_traversal>() )

yields a pre-order traversal of a tree forwards, the range

  [ a.rbegin<pre_order_traversal>(), a.rend<pre_order_traversal>() )

would actually yield a post-order traversal of the reverse of the tree. For
in-order traversals of binary trees, of course, there is no ambiguity.

A third option is not to present this concept at all, as the reversal could
be represented by the traversal policy class. I don't prefer this option,
though, since it diverges from parity with the standard library.]

[NOTE: These three concepts for multiply traversable containers could represent
more than just trees. I'm totally unfamiliar with the Boost Graph Library, but
it strikes me that they should be equally applicable to graphs.]

[NOTE: A hypothetical "Random Access Multiply Traversable Container" doesn't
really make much sense: the only additional legal expression would be array
access, which is an operator overload. As such, you can't call it with a
template parameter the same way you can invoke a.begin<t>(). Also, it's not
really necessary for our trees.]

1.5. Traversal
--------------

Traversal is a new concept necessary for the multiply traversable containers.
It is essentially a refactoring of Iterator, encapsulating the logic of
iteration separately from the iterator's dereferencing semantics. Models of
the Traversal concept are specific to the container they traverse.

[NOTE: Strictly speaking there are five separate Traversal concepts: Input,
Output, Forward, Bidirectional and Random Access, mirroring the Iterators they
are intended to support, but for now I'll lump them together.]

Valid expressions (t, u are models of Traversal, n is a model of Distance):

  ++t                   (Input, Output, Forward, Bidirectional, Random Access)
  --t                   (Bidirectional, Random Access)
  t += n                (Random Access)
  t + n or n + t        (Random Access)
  t -= n                (Random Access)
  t - n                 (Random Access)
  t - u                 (Random Access)
  t < u                 (Random Access)
  t.begin(), t.end()    (Forward, Bidirectional, Random Access)
  t.rbegin(), t.rend()  (Bidirectional, Random Access)

[NOTE: Postincrement and postdecrement seemed unnecessary to include.
Addition assignment and subtraction assignment probably are too.]

[TODO: These really shouldn't be modeled on the existing iterator categories
in the standard, but instead on the new iterators proposed by
http://www.boost.org/libs/iterator/doc/new-iter-concepts.html.]

2. Tree Concepts
================

2.1. Tree
---------

A Tree is a Reversible Multiply Traversable Container representing a tree
structure. [NOTE: I was very tempted to split Tree up into multiple concepts
representing the distinctions between trees whose nodes don't contain back-
links to their parents vs. those who do, and trees whose child sequences are
Forward vs. Reversible. I can imagine the distinction might be useful, but for
this draft I'm just going to lump them together.]

The following seven Bidirectional Traversal policies are defined:

  X::pre_order_traversal
  X::post_order_traversal
  X::depth_first_traversal
  X::breadth_first_traversal

  X::sibling_traversal
  X::first_descendant_traversal
  X::last_descendant_traversal

The first four traverse the whole tree, whereas the second three may traverse
only a subset of the tree. Typedefs are provided for iterators instantiated
with each traversal policy, for convenience:

  X::pre_order_iterator
  X::const_pre_order_iterator
  X::reverse_pre_order_iterator
  X::const_reverse_pre_order_iterator
  ...

New Members:

  X ();
  pre_order_iterator root ();

[TODO: need more member functions.]

2.2. Binary Tree
----------------

A Binary Tree is a Tree where each node may have a maximum of two children.
A new traversal and set of iterator typedefs are provided:

  X::in_order_traversal

  X::in_order_iterator
  X::const_in_order_iterator
  X::reverse_in_order_iterator
  X::const_reverse_in_order_iterator

[TODO: need member functions.]

2.3. K-Ary Tree
---------------

A K-Ary Tree is a Tree where each node may have a maximum of k children, where
k is an integer.

[TODO: need member functions.]

2.3. Sequence Tree
------------------

A Sequence Tree is a general-purpose tree in which each node may contain an
arbitrary number of children stored in a sequence.

New Members:

  template <typename Traversal> Sequence children (iterator<Traversal>);
  template <typename Traversal> insert ();
  template <typename Traversal> erase ();

[NOTE: The member function templates insert(), erase(), etc. must respect the
traversal order on which they are parametrized. That means that calling
insert() with a pre-order traversal iterator will yield different results from
calling insert() with a post-order traversal iterator. This seems strange at
first sight, but I actually think it's both acceptable and desirable
behavior. Acceptable, because in the cases where the structure of the tree
needs to be carefully controlled, the "fundamental" traversals --
sibling_traversal, first_descendant_traversal and last_descendant_traversal --
which let you go up, down, left and right, will be used instead of the whole-
tree traversals. And desirable, because it's important that standard
algorithms such as std::remove_if(), etc. can operate on trees as easily
as other sequences, with predictable results.]

[TODO: need more member functions.]

[TODO: Rename "Sequence Tree" to something better. It sounds stupid.]

[TODO: Refactor these three concepts as needed. More member functions will
help illustrate whatever overlap there might be.]

3. Utility Classes
==================

3.1. single_traversal
---------------------

The single_traversal class proxies a Multiply Traversable Container to yield
a regular Container. The Multiply Traversable Container has the disadvantage
of not being Less Than Comparable, which for existing Containers makes the
comparison operators and a single canonical iterator sensible. This adaptor
provides that missing functionality.

[NOTE: This should model Container, Forward Container or Reversible Container
depending on the adapted type. First of all, is it possible to do this all
in one class (using iterator tags, or some such)? And second of all, how to
document the variability in which concept this models?]

[TODO: Flesh out the interface for this class.]

4. Tree Classes
===============

[NOTE: So here's where I got stuck. I wanted to provide three class templates:
binary_tree<>, k_ary_tree<>, and tree<>, modeling Binary Tree, K-Ary Tree and
Sequence Tree, respectively. I think the first two are pretty straightforward,
so I didn't bother spending time on them. But the third, tree<>, is eluding
me.

I wanted to offer the ability to parametrize tree<> not just on value and
allocator type, but also on the type of sequence used to contain the children
of a node. But I hit three problems with this:

1. If a node contains a sequence of nodes, but tree's children() member wants
to return a sequence of values, how can I reconcile the type mismatch without
returning a copy?

2. The tree's iterators have to contain iterators for the child sequences. But
if I have an iterator to a node, for example, a pre-order traversal iterator,
and incrementing the iterator should yield the node's parent, how do I get the
underlying sequence iterator? That seems to imply that a node contains not a
pointer to its parent, but rather an iterator. First of all, that makes the
node fatter. Second of all, the tree's iterators are also fatter as a result
of wrapping the child sequence iterators. And lastly, the root node doesn't
even have a sequence iterator that can reasonably point to it, because it is
not in the child sequence of any other node.

3. I couldn't think of any reason why a client of tree<> would actually want
anything other than a simple linked-list implementation.]