   for _ in OldSequence(0..<*10) {}
 }
 
+NewCollection.test("MyBinaryTree.init()") {
+  _ = MyBinaryTree<Int>()
+}
+
+NewCollection.test("MyBinaryTree.insert(_:)") {
+  var t = MyBinaryTree<Int>()
+  t.insert(20)
+  t.insert(10)
+  t.insert(30)
+  dump(t)
+
+  do {
+    var i = t.startIndex
+    expectEqual(10, t[i])
+
+    i = t.next(i)
+    expectEqual(20, t[i])
+
+    i = t.next(i)
+    expectEqual(30, t[i])
+
+    i = t.next(i)
+    expectEqual(t.endIndex, i)
+  }
+  do {
+    var i = t.endIndex
+    i = t.previous(i)
+    dump(i, name: "30")
+    expectEqual(30, t[i])
+
+    i = t.previous(i)
+    dump(i, name: "20")
+    expectEqual(20, t[i])
+
+    i = t.previous(i)
+    dump(i, name: "10")
+    expectEqual(10, t[i])
+    expectEqual(t.startIndex, i)
+  }
+}
+
 runAllTests()
 


// FIXME: how does AnyCollection look like in the new scheme?

import StdlibUnittest

// Also import modules which are used by StdlibUnittest internally. This

//
// 2. We can't specify constraints on associated types.  This forces many
//    trivial algorithms to specify useless constraints.
//
// Trees
// =====
//
// Trees are very interesting data structures with many unique
// requirements.  We are interested in allowing efficient and
// memory-safe implementations of collections based on a search trees
// (e.g., RB trees or B-trees).  The specific list of requirements is
// as follows.
//
// - The collection and indices should be memory-safe.  They should
//   provide good QoI in the form of precondition traps.  Ensuring
//   memory-safety shouldn't cause unreasonable performance or memory
//   overhead.
//
// - Collection instances should be able to share nodes on mutation
//   (persistent data structures).
//
// - Subscript on an index should be at worst amortized O(1).
//
// - Advancing an index to the next or previous position should cost
//   at worst amortized O(1).
//
// - Indices should not contain reference countable stored properties.
//
// - Mutating or deleting an element in the collection should not
//   invalidate indices pointing at other elements.
//
//   This design constraint needs some extra motivation, because it
//   might not be obvious.  Preserving index validity across mutation
//   is important for algorithms that iterate over the tree and mutate
//   it in place, for exmaple, removing a subrange of elements between
//   two indices, or removing elements that don't satisfy a predicate.
//   When implementing such an algorithm, you would typically have an
//   index that points to the current element.  You can copy the
//   index, advance it, and then remove the previous element using its
//   index.  If the mutation of the tree invalidates all indices,
//   it is not possible to continue the iteration.  Thus, it is
//   desired to invalidate just one index for the element that was
//   deleted.
//
// It is not possible to satisfy all of these requirements at the same
// time.  Designs that cover some of the requiremens are possible.
//
// 1. Persistent trees with O(log n) subscripting and advancing, and
//    strict index invalidation.
//
//    If we choose to make a persistent data structure with node
//    reuse, then the tree nodes can't have parent pointers (a node
//    can have multiple different parents in different trees).  This
//    means that it is not possible to advance an index in O(1).  If
//    we need to go up the tree while advancing the index, we would
//    need to traverse the tree starting from the root in O(log n).
//    Thus, index has to essentially store a path through the tree
//    from the root to the node (it is usually possible to encode this
//    path in a 64-bit number).  Since the index stores the path,
//    subscripting on such an index would also cost O(log n).
//
//    We should note that even though the operations mentioned cost
//    O(log n), the base of the logarithm would be typically large
//    (e.g., 32), and the size of the machine memory is limited.
//    Thus, we could treat the complexity as effectively constant for
//    all practical purposes.
//
// 2. Trees with O(1) subscripting and advancing.
//
//    If we want subscripting to be O(1), then the index has to store
//    a pointer to a tree node.  Since we want avoid reference
//    countable properties in indices, the node pointer should either
//    be `unsafe(unowned)` or an `UnsafePointer`.  These pointers
//    can't be dereferenced safely without knowing in advance that it
//    is safe to do so.  We need some way to quickly check if it is
//    safe to dereference the pointer stored in the node.
//
//    A pointer to a tree node can become invalid when the node was
//    deallocated.  A tree node can be deallocated if the
//    corresponding element is removed from the tree.
//
//    (a) Trees with O(1) subscripting and advancing, and strict index
//        invalidation.
//
//        One simple way to perform the safety check when
//        dereferencing the unsafe pointer stored within the index
//        would be to detect any tree mutation between the index
//        creation and index use.  It is simple to do with version
//        numbers: we add an ID number to every tree.  This ID would
//        be unique among all trees created within the process, and it
//        would be re-generated on every mutation.  The tree ID is
//        copied into every index.  When the index is used with the
//        collection, we check that the ID of the tree matches the
//        tree ID stored in the index.  This fast check ensures memory
//        safety.
//
//    (b) Trees with O(1) subscripting and advancing, permissive index
//        invalidation, and extra storage to ensure memory safety.
//
//        Another way to perform the safety check would be to directly
//        check if the unsafe pointer stored in the index is actually
//        linked into the tree.  To do that with acceptable time
//        complexity, we would need to have an extra data structure
//        for every tree, for example, a hash table-based set of all
//        node pointers.  With this design, all index operations get
//        an O(1) hit for the hash table lookup for the safety check,
//        but we get an O(log n) memory overhead for the extra data
//        structure.  On the other hand, a tree already has O(log n)
//        memory overhead for allocating nodes themselves, thus the
//        extra data structure would only increase the constant factor
//        on memory overhead.
//
// Each of the designs discussed above has its uses, but the intuition
// is that (2)(a) is the one most commonly needed in practice.  (2)(a)
// does not have the desired index invalidation properties.  There is
// a small number of commonly used algorithms that require that
// property, and they can be provided as methods on the collection,
// for example removeAll(in: Range<Index>) and
// removeAll(_: (Element)->Bool).

infix operator ...* { associativity none precedence 135 }
infix operator ..<* { associativity none precedence 135 }

public protocol MyGeneratorType {
  associatedtype Element
