 //
 // 2. We can't specify constraints on associated types.  This forces many
 //    trivial algorithms to specify useless constraints.
-
-infix operator  ...* { associativity none precedence 135 }
-infix operator  ..<* { associativity none precedence 135 }
+//
+// 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


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

import StdlibUnittest

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

  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()

