[swift-evolution] [RFC] New collections model: collections advance indices

[Howard Lovatt]

I have used the node of a linked list as the list's index! The node wasn't
Hashable, Equatable, or Comparable; hash and equate would be easy to add
but Comparable would be expensive. It is probably not a big deal since
linked lists aren't that great a data structure anyway. Code below:

class Node<Element> {

    var value: Element

    private(set) var next: Node<Element>? = nil

    init(_ value: Element) { self.value = value }

    init(value: Element, successor: Node<Element>) {

        self.value = value

        self.next = successor

    }

}


class LinkedListGenerator<Element>: GeneratorType {

    private var index: Node<Element>?

    init(_ startIndex: Node<Element>) { index = startIndex }

    func next() -> Element? {

        guard let i = index else { return nil }

        let element = i.value

        index = i.next

        return element

    }

}


class LinkedList<Element>: SequenceType { // Has same interface as
Indexable, but without the ForwardIndexType constraint

    private(set) var startIndex: Node<Element>

    private(set) var endIndex: Node<Element>

    convenience init<S: SequenceType where S.Generator.Element ==
Element>(elements:
S) {

        var gen = elements.generate()

        var element = gen.next()

        guard let first = element else { fatalError("Empty list") }

        self.init(first)

        element = gen.next()

        while element != nil {

            append(element!)

            element = gen.next()

        }

    }

    init(_ element: Element) {

        startIndex = Node(element)

        endIndex = startIndex

    }

    subscript(index: Node<Element>) -> Element {

        get { return index.value }

        set { index.value = newValue }

    }

    func generate() -> LinkedListGenerator<Element> { return
LinkedListGenerator(startIndex) }

    func prepend(element: Element) { startIndex = Node(value: element,
successor: startIndex) }

    func prepend(elements elements: LinkedList<Element>) {

        let old = startIndex

        startIndex = elements.startIndex

        elements.endIndex.next = old

    }

    func append(element: Element) {

        endIndex.next = Node(element)

        endIndex = endIndex.next!

    }

    func append(elements elements: LinkedList<Element>) {

        endIndex.next = elements.startIndex

        endIndex = elements.endIndex

    }

}


  -- Howard.

On 8 March 2016 at 12:25, Dmitri Gribenko via swift-evolution <
swift-evolution at swift.org> wrote:

> Hi,
>
> What does everyone think about requiring indices to conform to
> Hashable, in addition to the existing requirements for Equatable and
> Comparable?
>
> I don't think this should limit any viable collection designs, and yet
> might be useful, for example, to store indices in a set.
>
> Dmitri
>
> --
> main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
> (j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr at gmail.com>*/
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160309/6153818f/attachment.html>