Circular dependencies between typical types (CollectionType and its index / generator, for example)

Question

Given the general structbased on struct...

struct MyCollection<Element>: CollectionType, MyProtocol {
    typealias Index = MyIndex<MyCollection>

    subscript(i: Index) -> Element { … }

    func generate() -> IndexingGenerator<MyCollection> {
        return IndexingGenerator(self)
    }
}

... how to define Indexfor him ...

struct MyIndex<Collection: MyProtocol>: BidirectionalIndexType {

    func predecessor() -> MyIndex { … }
    func successor() -> MyIndex { … }
}

... without introducing a death dependency cycle?

A general character is MyIndexnecessary because:

• It should work with any type MyProtocol.
• MyProtocollinks Selfand therefore can only be used as a type restriction.

If forward declarations (à la Objective-C) appeared, I would just ^[sic!] Add one for MyIndex<MyCollection>mine MyCollection<…>. Alas, this does not happen.

---

A possible specific use case is binary trees, such as:

indirect enum BinaryTree<Element>: CollectionType, BinaryTreeType {
    typealias Index = BinaryTreeIndex<BinaryTree>

    case Nil
    case Node(BinaryTree, Element, BinaryTree)

    subscript(i: Index) -> Element { … }
}

This will require Indexa stack based:

struct BinaryTreeIndex<BinaryTree: BinaryTreeType>: BidirectionalIndexType {
    let stack: [BinaryTree]

    func predecessor() -> BinaryTreeIndex { … }
    func successor() -> BinaryTreeIndex { … }
}

---

(?) struct struct Swift.
BinaryTreeIndex<…> BinaryTree<…>.

BinaryTreeIndex,
BinaryTreeType.

Answer 1

, CollectionType, Index ( ( )), , Index BinaryTree, Element.

, MyCollection MyCollectionStorage, CollectionType , MyCollection CollectionType.

"", :

• MyCollection<E> SortedSet<E>
• MyCollectionStorage<E> BinaryTree<E>
• MyIndex<T> BinaryTreeIndex<T>

, :

struct SortedSet<Element>: CollectionType {
    typealias Tree = BinaryTree<Element>
    typealias Index = BinaryTreeIndex<Tree>

    subscript(i: Index) -> Element { … }

    func generate() -> IndexingGenerator<SortedSet> {
        return IndexingGenerator(self)
    }
}

struct BinaryTree<Element>: BinaryTreeType {

}

struct BinaryTreeIndex<BinaryTree: BinaryTreeType>: BidirectionalIndexType {
    func predecessor() -> BinaryTreeIndex { … }
    func successor() -> BinaryTreeIndex { … }
}

.

Answer 2

, . arent , . , , ?

Objective-C, . indirect enums - .

, . , indirect , :

// turns any type T into a reference type
final class Box<T> {
    let unbox: T
    init(_ x: T) { unbox = x }
}

, , :

struct ListNode<T> {
    var box: Box<(element: T, next: ListNode<T>)>?

    func cons(x: T) -> ListNode<T> {
        return ListNode(node: Box(element: x, next: self))
    }

    init() { box = nil }
    init(node: Box<(element: T, next: ListNode<T>)>?)
    { box = node }
}

let nodes = ListNode().cons(1).cons(2).cons(3)
nodes.box?.unbox.element // first element
nodes.box?.unbox.next.box?.unbox.element // second element

node , ForwardIndexType, CollectionType, .

, ==:

• , . , Equatable.

• , , . , Equatable i.e.:

  func == <T where T: Equatable>(lhs: List<T>, rhs: List<T>) -> Bool {
      // once the List conforms to at least SequenceType:
      return lhs.elementsEqual(rhs)
  }
  

. "" - , :

struct ListIndex<T>: ForwardIndexType {
    let node: ListNode<T>

    func successor() -> ListIndex<T> {
        guard let next = node.box?.unbox.next
            else { fatalError("attempt to advance past end") }
        return ListIndex(node: next)
    }
}

func == <T>(lhs: ListIndex<T>, rhs: ListIndex<T>) -> Bool {
    switch (lhs.node.box, rhs.node.box) {
    case (nil,nil): return true
    case (_?,nil),(nil,_?): return false
    case let (x,y): return x === y
    }
}

struct List<T>: CollectionType {
    typealias Index = ListIndex<T>
    var startIndex: Index
    var endIndex: Index { return ListIndex(node: ListNode()) }
    subscript(idx: Index) -> T {
        guard let element = idx.node.box?.unbox.element
            else { fatalError("index out of bounds") }
        return element
    }
}

( generate() - "" 2.0 CollectionType)

:

// in practice you would add methods to List such as
// conforming to ArrayLiteralConvertible or init from 
// another sequence
let list = List(startIndex: ListIndex(node: nodes))

list.first  // 3
for x in list { print(x) }  // prints 3 2 1

.

, , indirect , . - .

, . . - thats what Optional. nil (.. Optional.None) End . , .

.