CTMacUser/LinkedList.swift Secret

## LinkedList.swift
//
//  LinkedList.swift
//  Trie
//
//  Created by Daryle Walker on 5/30/19.
//


// MARK: - Singly-Linked List

/// A seqeunce stored as a singly linked list.
enum LinkedList<Element> {

    /// An empty sequence, also used for the cap of a non-empty one.
    case empty

    /// A non-empty sequence, with a leading head element and a tail of the
    /// trailing elements.
    indirect case nonempty(head: Element, tail: LinkedList)

}

// MARK: Debugging

extension LinkedList: CustomDebugStringConvertible {

    var debugDescription: String {
        switch self {
        case .empty:
            return "∅"
        case let .nonempty(h, t):
            return String(reflecting: h) + " → " + String(reflecting: t)
        }
    }

}

// MARK: Comparisons

extension LinkedList: Equatable where Element: Equatable {}
extension LinkedList: Hashable where Element: Hashable {}

extension LinkedList: Comparable where Element: Comparable {

    // Comparison is in lexicographical order.

    static func < (lhs: LinkedList, rhs: LinkedList) -> Bool {
        switch (lhs, rhs) {
        case let (.nonempty(lh, _), .nonempty(rh, _)) where lh < rh:
            fallthrough
        case (.empty, .nonempty):
            return true
        case let (.nonempty(lh, _), .nonempty(rh, _)) where lh > rh:
            fallthrough
        case (_, .empty):
            return false
        case let (.nonempty(lh, lt), .nonempty(rh, rt)):
            assert(lh == rh)
            return lt < rt
        }
    }

}

// MARK: Sequencing

extension LinkedList: IteratorProtocol, Sequence {

    // Since a separate iterator type would need to carry a copy of the list,
    // might as well group iteration within the list type.

    mutating func next() -> Element? {
        switch self {
        case .empty:
            return nil
        case let .nonempty(head, tail):
            defer { self = tail }
            return head
        }
    }

    var underestimatedCount: Int {
        switch self {
        case .empty:
            return 0
        case .nonempty:
            return 1
        }
    }

}

extension LinkedList {

    /// Creates a copy of the given iterator's underlying sequence.
    private init<I: IteratorProtocol>(_ i: inout I) where I.Element == Element {
        switch i.next() {
        case nil:
            self = .empty
        case let h?:
            self = .nonempty(head: h, tail: .init(&i))
        }
    }

    /// Creates a copy of the given sequence's underlying sequence.
    ///
    /// - Parameter s: The sequence to copy elements from.
    ///
    /// - Postcondition: `self` and `s` vend the same underlying sequence.
    ///
    /// - Complexity: O(*n*), where *n* is the length of `s`.
    init<S: Sequence>(_ s: S) where S.Element == Element {
        var iterator = s.makeIterator()
        self.init(&iterator)
    }

}

// MARK: Accessors

extension LinkedList {

    /// Indicates whether the list contains no elements.
    ///
    /// - Complexity: O(1)
    var isEmpty: Bool {
        switch self {
        case .empty:
            return true
        case .nonempty:
            return false
        }
    }

    /// The first element of the list.
    ///
    /// If the list is empty, expresses `nil`.
    var first: Element? {
        switch self {
        case .empty:
            return nil
        case .nonempty(let h, _):
            return h
        }
    }

    /// The list without its first element
    ///
    /// If the list is empty, expresses `nil`.
    var rest: LinkedList? {
        switch self {
        case .empty:
            return nil
        case .nonempty(_, let t):
            return t
        }
    }

}

## LinkedListTests.swift
//
//  LinkedListTests.swift
//  TrieTests
//
//  Created by Daryle Walker on 5/30/19.
//

import XCTest
@testable import Trie


class LinkedListTests: XCTestCase {

    enum Constants {

        static let emptyList = LinkedList<Int>.empty
        static let singleList = LinkedList.nonempty(head: 1, tail: .empty)
        static let doubleList = LinkedList.nonempty(head: 2, tail: .nonempty(head: 3, tail: .empty))
        static let tripleList = LinkedList.nonempty(head: 4, tail: .nonempty(head: 5, tail: .nonempty(head: 6, tail: .empty)))

    }

    override func setUp() {
        // Put setup code here. This method is called before the invocation of each test method in the class.
    }

    override func tearDown() {
        // Put teardown code here. This method is called after the invocation of each test method in the class.
    }

    // Test debug-string conversion
    func testSerialization() {
        // Check empty-list case
        XCTAssertEqual(String(reflecting: Constants.emptyList), "∅")

        // Check non-empty list
        XCTAssertEqual(String(reflecting: Constants.singleList), "1 → ∅")

        // Check more recursive cases
        XCTAssertEqual(String(reflecting: Constants.doubleList), "2 → 3 → ∅")
        XCTAssertEqual(String(reflecting: Constants.tripleList), "4 → 5 → 6 → ∅")
    }

    // Test lexiographic comparison
    func testCompare() {
        XCTAssertLessThan(Constants.emptyList, Constants.singleList)

        XCTAssertGreaterThanOrEqual(Constants.emptyList, Constants.emptyList)
        XCTAssertGreaterThanOrEqual(Constants.singleList, Constants.emptyList)

        let singleTwo = LinkedList.nonempty(head: 2, tail: .empty)
        XCTAssertLessThan(Constants.singleList, singleTwo)
        XCTAssertGreaterThanOrEqual(singleTwo, Constants.singleList)

        XCTAssertEqual(singleTwo, singleTwo)
        XCTAssertGreaterThanOrEqual(singleTwo, singleTwo)
        XCTAssertLessThan(singleTwo, Constants.doubleList)
        XCTAssertGreaterThanOrEqual(Constants.doubleList, singleTwo)

        let fourSeven = LinkedList.nonempty(head: 4, tail: .nonempty(head: 7, tail: .empty))
        let fourFiveEight = LinkedList.nonempty(head: 4, tail: .nonempty(head: 5, tail: .nonempty(head: 8, tail: .empty)))
        XCTAssertLessThan(Constants.doubleList, fourSeven)
        XCTAssertGreaterThanOrEqual(fourSeven, Constants.doubleList)
        XCTAssertLessThan(Constants.doubleList, fourFiveEight)
        XCTAssertGreaterThanOrEqual(fourFiveEight, Constants.doubleList)
        XCTAssertLessThan(Constants.tripleList, fourFiveEight)
        XCTAssertGreaterThanOrEqual(fourFiveEight, Constants.tripleList)
    }

    // Test sequence conformance
    func testSequenceUse() {
        XCTAssertEqual(Constants.emptyList.underestimatedCount, 0)
        XCTAssertEqual(Constants.singleList.underestimatedCount, 1)
        XCTAssertEqual(Constants.doubleList.underestimatedCount, 1)
        XCTAssertEqual(Constants.tripleList.underestimatedCount, 1)

        XCTAssertEqual(Array(Constants.emptyList), [Int]())
        XCTAssertEqual(Array(Constants.singleList), [1])
        XCTAssertEqual(Array(Constants.doubleList), [2, 3])
        XCTAssertEqual(Array(Constants.tripleList), [4, 5, 6])
    }

    // Test initialization from sequences
    func testSequenceInit() {
        XCTAssertEqual(LinkedList([Int]()), Constants.emptyList)
        XCTAssertEqual(LinkedList([1]), Constants.singleList)
        XCTAssertEqual(LinkedList([2, 3]), Constants.doubleList)
        XCTAssertEqual(LinkedList([4, 5, 6]), Constants.tripleList)
    }

    // Test element accessors and status
    func testAccess() {
        XCTAssertTrue(Constants.emptyList.isEmpty)
        XCTAssertFalse(Constants.singleList.isEmpty)
        XCTAssertFalse(Constants.doubleList.isEmpty)
        XCTAssertFalse(Constants.tripleList.isEmpty)

        XCTAssertNil(Constants.emptyList.first)
        XCTAssertEqual(Constants.singleList.first, 1)
        XCTAssertEqual(Constants.doubleList.first, 2)
        XCTAssertEqual(Constants.tripleList.first, 4)

        XCTAssertNil(Constants.emptyList.rest)
        XCTAssertEqual(Constants.singleList.rest, Constants.emptyList)
        XCTAssertEqual(Constants.doubleList.rest, LinkedList([3]))
        XCTAssertEqual(Constants.tripleList.rest, LinkedList([5, 6]))
    }

    static var allTests = [
        ("testSerialization", testSerialization),
        ("testCompare", testCompare),
        ("testSequenceUse", testSequenceUse),
        ("testSequenceInit", testSequenceInit),
        ("testAccess", testAccess),
    ]

}

## NeverEmptyTrie.swift
//
//  NeverEmptyTrie.swift
//  Trie
//
//  Created by Daryle Walker on 5/30/19.
//


// MARK: - Trie without allowing empty sets

/// A never-empty set of type-erased sequences sharing the same element type.
///
/// The sequences are exploded into separate element nodes connected into a
/// doubly chained tree.
///
/// Mandating the element type to `Comparable` conformance enables uniqueness of
/// sequences stored in the trie.  It also allows visitation of those sequences
/// as a sequence with a consistent order.
///
/// Since the outline of this enumeration type cannot enforce the invariants,
/// this type must be hidden as an implementation type.
enum NeverEmptyTrie<SubElement: Comparable> {

    /// Marks the end of a chain of sequence elements.
    case cap

    /// Marks the initial element of the last branch of stored sequences, along
    /// with all possible suffix branches and a possible link to sibling
    /// branches.
    indirect case branch(previousSibling: NeverEmptyTrie?, head: SubElement, tail: NeverEmptyTrie)

}

// MARK: Debugging

extension NeverEmptyTrie {

    /// Whether the invariants of the type have been kept.
    ///
    /// The invariant is: where there are sibling branches, earlier siblings
    /// must have `head` values less than the current `head` value.
    var invariantKept: Bool {
        switch self {
        case .cap:
            // No stored elements.
            return true
        case .branch(.none, _, let t), .branch(.some(.cap), _, let t):
            // Only one stored element
            return t.invariantKept
        case let .branch(.some(.branch(ps1, h1, t1)), h0, t0):
            // Multiple store elements at the same level, plus the other levels.
            return t0.invariantKept && h0 > h1 && t1.invariantKept && ps1?.invariantKept ?? true
        }
    }

}

extension NeverEmptyTrie: CustomDebugStringConvertible {

    /// A debug-worthy text representation of this direct branch of this trie,
    /// without regard for its siblings (if any).
    private var soloDebugDescription: String {
        switch self {
        case .cap:
            return "∅"
        case let .branch(_, head, tail):
            switch tail {
            case .cap, .branch(nil, _, _):
                return String(reflecting: head) + " → " + tail.soloDebugDescription
            case .branch(let earlierTailSibling?, _, _):
                return String(reflecting: head) + " → " + earlierTailSibling.siblingDebugDescription + tail.soloDebugDescription + ")"
            }
        }
    }

    /// A debug-worthy text representation of this direct branch of this trie,
    /// along with any siblings.
    private var siblingDebugDescription: String {
        switch self {
        case .cap:
            return "(∅ | "
        case .branch(let previousSibling, _, _):
            let suffix = soloDebugDescription + " | "
            if let previous = previousSibling {
                return previous.siblingDebugDescription + suffix
            } else {
                return "(" + suffix
            }
        }
    }

    var debugDescription: String {
        switch self {
        case .cap, .branch(nil, _, _):
            return soloDebugDescription
        case .branch(let previousSibling?, _, _):
            // There will be no ")" after the last term, so remove the "(" that
            // starts the first term.
            return previousSibling.siblingDebugDescription.dropFirst() + soloDebugDescription
        }
    }

}

// MARK: Comparisons

extension NeverEmptyTrie: Equatable {}

extension NeverEmptyTrie: Hashable where SubElement: Hashable {}

// MARK: Conversions

extension NeverEmptyTrie {

    /// Creates a trie with the given sequence as its sole member.
    init(list: LinkedList<SubElement>) {
        switch list {
        case .empty:
            self = .cap
        case .nonempty(let h, let t):
            self = .branch(previousSibling: nil, head: h, tail: .init(list: t))
        }
    }

}

// MARK: Membership

extension NeverEmptyTrie {

    /// Returns whether the given sequence is a member of this set.
    func contains(_ list: LinkedList<SubElement>) -> Bool {
        switch (self, list) {
        case (.cap, .empty):
            // Elementary.
            return true
        case let (.branch(_, bh, _), .nonempty(lh, _)) where bh < lh:
            // No match, and siblings have even smaller head values, so...
            fallthrough
        case (.cap, .nonempty):
            // No match and no more siblings to check.
            return false
        case let (.branch(_, bh, bt), .nonempty(lh, lt)) where bh == lh:
            // First match, now recursively continue.
            return bt.contains(lt)
        case (.branch(let bs, _, _), _):
            // (Either list.isEmpty or self.head > list.head)
            // There is still a chance that a sibling branch may match.
            return bs?.contains(list) ?? false
        }
    }

    /// Returns a copy of this set with the given list added as a member, and a
    /// flag indicating if the list wasn't already a member.
    func doInsert(_ list: LinkedList<SubElement>) -> (trie: NeverEmptyTrie, didInsert: Bool) {
        switch (self, list) {
        case (.cap, .empty):
            // Elementary.
            return (trie: self, didInsert: false)
        case let (.branch(_, bh, _), .nonempty(lh, lt)) where bh < lh:
            // List has the largest head value among its would-be siblings...
            fallthrough
        case let (.cap, .nonempty(lh, lt)):
            // Insert list's branch ahead of existing ones.
            return (trie: .branch(previousSibling: self, head: lh, tail: .init(list: lt)), didInsert: true)
        case let (.branch(ps, bh, bt), .nonempty(lh, lt)) where bh == lh:
            // Recursively continue insertion for the sub-trie and suffix.
            let newTailInsertion = bt.doInsert(lt)
            return (trie: .branch(previousSibling: ps, head: bh, tail: newTailInsertion.trie), didInsert: newTailInsertion.didInsert)
        case let (.branch(nil, bh, bt), _):
            // (Either list == .empty or self.head > list.head)
            // Insert list's branch behind the existing ones.
            return (trie: .branch(previousSibling: .init(list: list), head: bh, tail: bt), didInsert: true)
        case let (.branch(ps?, bh, bt), _):
            // (Either list == .empty or self.head > list.head)
            // Insert list's branch past a sibling branch.
            let newSiblingInsertion = ps.doInsert(list)
            return (trie: .branch(previousSibling: newSiblingInsertion.trie, head: bh, tail: bt), didInsert: newSiblingInsertion.didInsert)
        }
    }

    /// Returns a copy of this set without the given list as a member, possibly
    /// nil if that list was the sole member, and a flag indicating if the list
    /// was initially a member.
    func doRemove(_ list: LinkedList<SubElement>) -> (trie: NeverEmptyTrie?, didRemove: Bool) {
        switch (self, list) {
        case (.cap, .empty):
            // Elementary.
            return (trie: nil, didRemove: true)
        case let (.branch(_, bh, _), .nonempty(lh, _)) where bh < lh:
            // List has the largest head value among its would-be siblings...
            fallthrough
        case (.cap, .nonempty):
            // No more branches that could be searched for a match.
            return (trie: self, didRemove: false)
        case let (.branch(ps, bh, bt), .nonempty(lh, lt)) where bh == lh:
            // Recursively check & remove the sub-trie and suffix.
            let newTailRemoval = bt.doRemove(lt)
            if let newTail = newTailRemoval.trie {
                return (trie: .branch(previousSibling: ps, head: bh, tail: newTail), didRemove: newTailRemoval.didRemove)
            } else {
                assert(newTailRemoval.didRemove)
                return (trie: ps, didRemove: true)
            }
        case (.branch(nil, _, _), _):
            // (Either list == .empty or self.head > list.head)
            // No matches found, and no more to search.
            return (trie: self, didRemove: false)
        case let (.branch(ps?, bh, bt), _):
            // (Either list == .empty or self.head > list.head)
            // Check sibling branches for the target.
            let newSiblingRemoval = ps.doRemove(list)
            return (trie: .branch(previousSibling: newSiblingRemoval.trie, head: bh, tail: bt), didRemove: newSiblingRemoval.didRemove)
        }
    }

}

extension NeverEmptyTrie {

    /// Returns whether there is only one member in the set.
    ///
    /// Such sets will return `nil` for `popFirst().trie` and `popLast().trie`.
    var countIsOne: Bool {
        switch self {
        case .cap:
            return true
        case .branch(nil, _, let t):
            return t.countIsOne
        case .branch(_?, _, _):
            return false
        }
    }

    /// Returns the lexiographically first sequence stored in the set.
    var first: LinkedList<SubElement> {
        switch self {
        case .cap:
            return .empty
        case let .branch(nil, h, t):
            return .nonempty(head: h, tail: t.first)
        case .branch(let ps?, _, _):
            return ps.first
        }
    }

    /// Returns the lexiographically last sequence stored in the set.
    var last: LinkedList<SubElement> {
        switch self {
        case .cap:
            return .empty
        case let .branch(_, h, t):
            return .nonempty(head: h, tail: t.last)
        }
    }

    /// Removes the lexiographically first sequence stored in the set,
    /// returning that ex-member and the post-removal set.
    func popFirst() -> (member: LinkedList<SubElement>, trie: NeverEmptyTrie?) {
        switch self {
        case .cap:
            return (member: .empty, trie: nil)
        case let .branch(nil, h, t):
            let strippedTail = t.popFirst()
            let member = LinkedList.nonempty(head: h, tail: strippedTail.member)
            let trie = strippedTail.trie.map { NeverEmptyTrie.branch(previousSibling: nil, head: h, tail: $0) }
            return (member: member, trie: trie)
        case let .branch(ps?, h, t):
            let psPopped = ps.popFirst()
            return (member: psPopped.member, trie: .branch(previousSibling: psPopped.trie, head: h, tail: t))
        }
    }

    /// Removes the lexiographically last sequence stored in the set,
    /// returning that ex-member and the post-removal set.
    func popLast() -> (member: LinkedList<SubElement>, trie: NeverEmptyTrie?) {
        switch self {
        case .cap:
            return (member: .empty, trie: nil)
        case let .branch(ps, h, t):
            let strippedTail = t.popLast()
            let member = LinkedList.nonempty(head: h, tail: strippedTail.member)
            let trie = strippedTail.trie.map { NeverEmptyTrie.branch(previousSibling: ps, head: h, tail: $0) } ?? ps
            return (member: member, trie: trie)
        }
    }

}

// MARK: Set Operations

extension NeverEmptyTrie {

    /// Creates a set that is the union of the given sets.
    init?(unify f: NeverEmptyTrie?, with s: NeverEmptyTrie?) {
        switch (f, s) {
        case (.none, .none):
            // Nothing to combine.
            return nil
        case (.some(let t), .none), (.none, .some(let t)):
            // Copy the sole proper argument.
            self = t
        case (.some(.cap), .some(.cap)):
            // Identical.
            self = .cap
        case let (.some(.cap), .some(.branch(ps, h, t))), let (.some(.branch(ps, h, t)), .some(.cap)):
            // Chain them together.
            self = .branch(previousSibling: NeverEmptyTrie(unify: .cap, with: ps), head: h, tail: t)
        case let (.some(.branch(lessPs, lessH, lessT)), .some(.branch(greatPs, greatH, tail: greatT))) where lessH < greatH, let (.some(.branch(greatPs, greatH, greatT)), .some(.branch(lessPs, lessH, lessT))) where greatH > lessH:
            // The set with the smaller head becomes a sibling branch from the other set.
            self = .branch(previousSibling: NeverEmptyTrie(unify: .branch(previousSibling: lessPs, head: lessH, tail: lessT), with: greatPs), head: greatH, tail: greatT)
        case let (.some(.branch(fps, fh, ft)), .some(.branch(sps, sh, st))):
            // Recursively blend the suffixes and chain the sibling branches.
            assert(fh == sh)
            self = .branch(previousSibling: NeverEmptyTrie(unify: fps, with: sps), head: fh, tail: NeverEmptyTrie(unify: ft, with: st)!)
        }
    }

    /// Creates a set that is the intersection of the given sets.
    init?(intersect f: NeverEmptyTrie?, with s: NeverEmptyTrie?) {
        // The intersection of nothing with anything is nothing.
        guard let ff = f, let ss = s else { return nil }

        switch (ff, ss) {
        case (.cap, .cap):
            // Identical.
            self = .cap
        case (.cap, .branch(let ps, _, _)), (.branch(let ps, _, _), .cap):
            // Whatever's in common doesn't include the last branch.
            self.init(intersect: .cap, with: ps)
        case let (.branch(lessPs, lessH, lessT), .branch(greatPs, greatH, _)) where lessH < greatH, let (.branch(greatPs, greatH, _), .branch(lessPs, lessH, lessT)) where greatH > lessH:
            // Whatever's in common doesn't include the would-be last branch.
            self.init(intersect: .branch(previousSibling: lessPs, head: lessH, tail: lessT), with: greatPs)
        case let (.branch(fps, fh, ft), .branch(sps, sh, st)):
            // Recursively blend the suffixes and chain the sibling branches.
            assert(fh == sh)
            if let tailIntersection = NeverEmptyTrie(intersect: ft, with: st) {
                self = .branch(previousSibling: NeverEmptyTrie(intersect: fps, with: sps), head: fh, tail: tailIntersection)
            } else {
                self.init(intersect: fps, with: sps)
            }
        }
    }

    /// Creates a set that is the symmetric difference of the given sets.
    init?(antiIntersect f: NeverEmptyTrie?, with s: NeverEmptyTrie?) {
        switch (f, s) {
        case (.none, .none):
            // Nothing to combine.
            return nil
        case (.some(let t), .none), (.none, .some(let t)):
            // The sole proper argument is outside the intersection.
            self = t
        case (.some(.cap), .some(.cap)):
            // Identical.
            return nil
        case let (.some(.cap), .some(.branch(ps, h, t))), let (.some(.branch(ps, h, t)), .some(.cap)):
            // The last branch doesn't overlap, but a sibling might.
            self = .branch(previousSibling: NeverEmptyTrie(antiIntersect: .cap, with: ps), head: h, tail: t)
        case let (.some(.branch(lessPs, lessH, lessT)), .some(.branch(greatPs, greatH, greatT))) where lessH < greatH, let (.some(.branch(greatPs, greatH, greatT)), .some(.branch(lessPs, lessH, lessT))) where greatH > lessH:
            // The would-be last branch is included, but its siblings might not be.
            self = .branch(previousSibling: NeverEmptyTrie(antiIntersect: .branch(previousSibling: lessPs, head: lessH, tail: lessT), with: greatPs), head: greatH, tail: greatT)
        case let (.some(.branch(fps, fh, ft)), .some(.branch(sps, sh, st))):
            // Recursively blend the suffixes and chain the sibling branches
            assert(fh == sh)
            if let tailSymDiff = NeverEmptyTrie(antiIntersect: ft, with: st) {
                self = .branch(previousSibling: NeverEmptyTrie(antiIntersect: fps, with: sps), head: fh, tail: tailSymDiff)
            } else {
                self.init(antiIntersect: fps, with: sps)
            }
        }
    }

}

## NeverEmptyTrieTests.swift
//
//  NeverEmptyTrieTests.swift
//  TrieTests
//
//  Created by Daryle Walker on 5/30/19.
//

import XCTest
@testable import Trie


class NeverEmptyTrieTests: XCTestCase {

    override func setUp() {
        // Put setup code here. This method is called before the invocation of each test method in the class.
    }

    override func tearDown() {
        // Put teardown code here. This method is called after the invocation of each test method in the class.
    }

    // MARK: Debugging

    // Test the invariant checker
    func testInvariantCheck() {
        XCTAssertTrue(NeverEmptyTrie<Int>.cap.invariantKept)
        XCTAssertTrue(NeverEmptyTrie.branch(previousSibling: nil, head: 0, tail: .cap).invariantKept)
        XCTAssertTrue(NeverEmptyTrie.branch(previousSibling: .cap, head: 1, tail: .cap).invariantKept)

        XCTAssertTrue(NeverEmptyTrie.branch(previousSibling: .branch(previousSibling: nil, head: 2, tail: .cap), head: 3, tail: .cap).invariantKept)

        let failingHeads = NeverEmptyTrie.branch(previousSibling: .branch(previousSibling: nil, head: 5, tail: .cap), head: 4, tail: .cap)
        XCTAssertFalse(failingHeads.invariantKept)

        let failingOuterTail = NeverEmptyTrie.branch(previousSibling: .branch(previousSibling: nil, head: 6, tail: .cap), head: 7, tail: failingHeads)
        XCTAssertFalse(failingOuterTail.invariantKept)

        let failingInnerTail = NeverEmptyTrie.branch(previousSibling: .branch(previousSibling: nil, head: 8, tail: failingHeads), head: 9, tail: .cap)
        XCTAssertFalse(failingInnerTail.invariantKept)

        let failingSibling = NeverEmptyTrie.branch(previousSibling: .branch(previousSibling: failingHeads, head: 10, tail: .cap), head: 11, tail: .cap)
        XCTAssertFalse(failingSibling.invariantKept)

        let failingEqualHeads = NeverEmptyTrie.branch(previousSibling: .branch(previousSibling: nil, head: 12, tail: .cap), head: 12, tail: .cap)
        XCTAssertFalse(failingEqualHeads.invariantKept)
    }

    // Test debug-string conversion
    func testSerialization() {
        XCTAssertEqual(String(reflecting: NeverEmptyTrie<Int>.cap), "∅")

        let singleNode = NeverEmptyTrie.branch(previousSibling: nil, head: 1, tail: .cap)
        XCTAssertEqual(String(reflecting: singleNode), "1 → ∅")

        let doubleNodeLine = NeverEmptyTrie.branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap))
        XCTAssertEqual(String(reflecting: doubleNodeLine), "2 → 3 → ∅")

        let branchedNodes = NeverEmptyTrie.branch(previousSibling: nil, head: 4, tail: .branch(previousSibling: .branch(previousSibling: nil, head: 5, tail: .cap), head: 6, tail: .cap))
        XCTAssertEqual(String(reflecting: branchedNodes), "4 → (5 → ∅ | 6 → ∅)")

        let tripleNodes = NeverEmptyTrie.branch(previousSibling: nil, head: 7, tail: .branch(previousSibling: .branch(previousSibling: .cap, head: 8, tail: .cap), head: 9, tail: .cap))
        XCTAssertEqual(String(reflecting: tripleNodes), "7 → (∅ | 8 → ∅ | 9 → ∅)")

        let topBranches = NeverEmptyTrie.branch(previousSibling: .branch(previousSibling: .cap, head: 10, tail: .branch(previousSibling: nil, head: 11, tail: .cap)), head: 12, tail: .branch(previousSibling: .branch(previousSibling: nil, head: 13, tail: .cap), head: 14, tail: .cap))
        XCTAssertEqual(String(reflecting: topBranches), "∅ | 10 → 11 → ∅ | 12 → (13 → ∅ | 14 → ∅)")

        let topNonemptyBranches = NeverEmptyTrie.branch(previousSibling: .branch(previousSibling: .branch(previousSibling: nil, head: 15, tail: .cap), head: 16, tail: .branch(previousSibling: .branch(previousSibling: nil, head: 17, tail: .cap), head: 18, tail: .cap)), head: 19, tail: .branch(previousSibling: nil, head: 20, tail: .branch(previousSibling: nil, head: 21, tail: .cap)))
        XCTAssertEqual(String(reflecting: topNonemptyBranches), "15 → ∅ | 16 → (17 → ∅ | 18 → ∅) | 19 → 20 → 21 → ∅")
    }

    // MARK: Element Manipulation

    // Test list conversion
    func testListConversion() {
        XCTAssertEqual(NeverEmptyTrie(list: LinkedList<Int>.empty), NeverEmptyTrie.cap)

        XCTAssertEqual(NeverEmptyTrie(list: LinkedList([1])), NeverEmptyTrie.branch(previousSibling: nil, head: 1, tail: .cap))
        XCTAssertEqual(NeverEmptyTrie(list: LinkedList([2, 3])), NeverEmptyTrie.branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap)))
        XCTAssertEqual(NeverEmptyTrie(list: LinkedList([4, 5, 6])), NeverEmptyTrie.branch(previousSibling: nil, head: 4, tail: .branch(previousSibling: nil, head: 5, tail: .branch(previousSibling: nil, head: 6, tail: .cap))))
    }

    // Test containment check
    func testContains() {
        let emptyList = LinkedList<Int>.empty
        let singleList = LinkedList([1])
        XCTAssertTrue(NeverEmptyTrie.cap.contains(emptyList))
        XCTAssertFalse(NeverEmptyTrie.cap.contains(singleList))

        let singleNode = NeverEmptyTrie.branch(previousSibling: nil, head: 1, tail: .cap)
        let doubleList = LinkedList([2, 3])
        XCTAssertFalse(singleNode.contains(doubleList))
        XCTAssertTrue(singleNode.contains(singleList))
        XCTAssertFalse(singleNode.contains(emptyList))

        let zeroOrOneNode = NeverEmptyTrie.branch(previousSibling: .cap, head: 1, tail: .cap)
        XCTAssertTrue(zeroOrOneNode.contains(emptyList))
        XCTAssertTrue(zeroOrOneNode.contains(singleList))
        XCTAssertFalse(zeroOrOneNode.contains(doubleList))

        let zeroToTwoNodes = NeverEmptyTrie.branch(previousSibling: zeroOrOneNode, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap))
        XCTAssertTrue(zeroToTwoNodes.contains(emptyList))
        XCTAssertTrue(zeroToTwoNodes.contains(singleList))
        XCTAssertTrue(zeroToTwoNodes.contains(doubleList))

        let longNodes = NeverEmptyTrie.branch(previousSibling: nil, head: 4, tail: .branch(previousSibling: nil, head: 5, tail: .branch(previousSibling: .branch(previousSibling: nil, head: 6, tail: .cap), head: 7, tail: .branch(previousSibling: .cap, head: 8, tail: .cap))))
        XCTAssertTrue(longNodes.contains(LinkedList([4, 5, 6])))
        XCTAssertTrue(longNodes.contains(LinkedList([4, 5, 7])))
        XCTAssertFalse(longNodes.contains(LinkedList([4, 5, 8])))
        XCTAssertTrue(longNodes.contains(LinkedList([4, 5, 7, 8])))
    }

    // Test inserting a member
    func testInsertion() {
        let emptyList = LinkedList<Int>.empty
        var result = NeverEmptyTrie.cap.doInsert(emptyList)
        XCTAssertEqual(result.trie, .cap)
        XCTAssertFalse(result.didInsert)

        let singleList = LinkedList([1])
        result = NeverEmptyTrie.cap.doInsert(singleList)
        XCTAssertEqual(result.trie, .branch(previousSibling: .cap, head: 1, tail: .cap))
        XCTAssertTrue(result.didInsert)

        let zeroValueNode = NeverEmptyTrie.branch(previousSibling: nil, head: 0, tail: .cap)
        result = zeroValueNode.doInsert(singleList)
        XCTAssertEqual(result.trie, .branch(previousSibling: .branch(previousSibling: nil, head: 0, tail: .cap), head: 1, tail: .cap))
        XCTAssertTrue(result.didInsert)

        let twoTwoNode = NeverEmptyTrie.branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: nil, head: 2, tail: .cap))
        let doubleList = LinkedList([2, 3])
        result = twoTwoNode.doInsert(doubleList)
        XCTAssertEqual(result.trie, .branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: .branch(previousSibling: nil, head: 2, tail: .cap), head: 3, tail: .cap)))
        XCTAssertTrue(result.didInsert)

        result = result.trie.doInsert(doubleList)
        XCTAssertEqual(result.trie, .branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: .branch(previousSibling: nil, head: 2, tail: .cap), head: 3, tail: .cap)))
        XCTAssertFalse(result.didInsert)

        result = twoTwoNode.doInsert(singleList)
        XCTAssertEqual(result.trie, .branch(previousSibling: .branch(previousSibling: nil, head: 1, tail: .cap), head: 2, tail: .branch(previousSibling: nil, head: 2, tail: .cap)))
        XCTAssertTrue(result.didInsert)

        result = result.trie.doInsert(emptyList)
        XCTAssertEqual(result.trie, .branch(previousSibling: .branch(previousSibling: .cap, head: 1, tail: .cap), head: 2, tail: .branch(previousSibling: nil, head: 2, tail: .cap)))
        XCTAssertTrue(result.didInsert)

        result = result.trie.doInsert(emptyList)
        XCTAssertEqual(result.trie, .branch(previousSibling: .branch(previousSibling: .cap, head: 1, tail: .cap), head: 2, tail: .branch(previousSibling: nil, head: 2, tail: .cap)))
        XCTAssertFalse(result.didInsert)
    }

    // Test removing a member
    func testRemoval() {
        let onlyEmptySequence = NeverEmptyTrie<Int>.cap
        let emptyList = LinkedList<Int>.empty
        var result = onlyEmptySequence.doRemove(emptyList)
        XCTAssertNil(result.trie)
        XCTAssertTrue(result.didRemove)

        let singleList = LinkedList([1])
        result = onlyEmptySequence.doRemove(singleList)
        XCTAssertEqual(result.trie, onlyEmptySequence)
        XCTAssertFalse(result.didRemove)

        let zeroValueNode = NeverEmptyTrie.branch(previousSibling: nil, head: 0, tail: .cap)
        result = zeroValueNode.doRemove(singleList)
        XCTAssertEqual(result.trie, zeroValueNode)
        XCTAssertFalse(result.didRemove)

        result = zeroValueNode.doRemove(emptyList)
        XCTAssertEqual(result.trie, zeroValueNode)
        XCTAssertFalse(result.didRemove)

        let doubleList = LinkedList([2, 3])
        let twoNode = NeverEmptyTrie(list: doubleList)
        result = twoNode.doRemove(singleList)
        XCTAssertEqual(result.trie, twoNode)
        XCTAssertFalse(result.didRemove)

        let oneValueNode = NeverEmptyTrie.branch(previousSibling: nil, head: 1, tail: .cap)
        result = oneValueNode.doRemove(singleList)
        XCTAssertNil(result.trie)
        XCTAssertTrue(result.didRemove)

        let twoTwoList = LinkedList([2, 2])
        result = twoNode.doRemove(twoTwoList)
        XCTAssertEqual(result.trie, twoNode)
        XCTAssertFalse(result.didRemove)

        result = twoNode.doRemove(doubleList)
        XCTAssertNil(result.trie)
        XCTAssertTrue(result.didRemove)

        let twoThreeNode = twoNode.doInsert(twoTwoList).trie
        result = twoThreeNode.doRemove(doubleList)
        XCTAssertEqual(result.trie, NeverEmptyTrie(list: twoTwoList))
        XCTAssertTrue(result.didRemove)

        let twoThreeEmptyNode = twoThreeNode.doInsert(emptyList).trie
        result = twoThreeEmptyNode.doRemove(emptyList)
        XCTAssertEqual(result.trie, twoThreeNode)
        XCTAssertTrue(result.didRemove)

        result = twoThreeEmptyNode.doRemove(singleList)
        XCTAssertEqual(result.trie, twoThreeEmptyNode)
        XCTAssertFalse(result.didRemove)

        result = twoThreeNode.doRemove(twoTwoList)
        XCTAssertEqual(result.trie, NeverEmptyTrie(list: doubleList))
        XCTAssertTrue(result.didRemove)
    }

    // Test check & extracting the end members
    func testFirstLast() {
        let onlyEmptySequence = NeverEmptyTrie<Int>.cap
        let emptyList = LinkedList<Int>.empty
        XCTAssertTrue(onlyEmptySequence.countIsOne)
        XCTAssertEqual(onlyEmptySequence.first, emptyList)
        XCTAssertEqual(onlyEmptySequence.last, emptyList)

        var result = onlyEmptySequence.popFirst()
        XCTAssertEqual(result.member, emptyList)
        XCTAssertNil(result.trie)
        result = onlyEmptySequence.popLast()
        XCTAssertEqual(result.member, emptyList)
        XCTAssertNil(result.trie)

        let singleList = LinkedList([1])
        let oneValueNode = NeverEmptyTrie(list: singleList)
        XCTAssertTrue(oneValueNode.countIsOne)
        XCTAssertEqual(oneValueNode.first, singleList)
        XCTAssertEqual(oneValueNode.last, singleList)
        result = oneValueNode.popFirst()
        XCTAssertEqual(result.member, singleList)
        XCTAssertNil(result.trie)
        result = oneValueNode.popLast()
        XCTAssertEqual(result.member, singleList)
        XCTAssertNil(result.trie)

        let doubleList = LinkedList([2, 3])
        let twoValueNode = NeverEmptyTrie(list: doubleList)
        let twoWayNode = twoValueNode.doInsert(singleList).trie
        XCTAssertFalse(twoWayNode.countIsOne)
        XCTAssertEqual(twoWayNode.first, singleList)
        XCTAssertEqual(twoWayNode.last, doubleList)
        result = twoWayNode.popFirst()
        XCTAssertEqual(result.member, singleList)
        XCTAssertEqual(result.trie, twoValueNode)
        result = twoWayNode.popLast()
        XCTAssertEqual(result.member, doubleList)
        XCTAssertEqual(result.trie, oneValueNode)

        let twoTwoList = LinkedList([2, 2])
        let twoDoubleNode = twoValueNode.doInsert(twoTwoList).trie
        XCTAssertFalse(twoDoubleNode.countIsOne)
        XCTAssertEqual(twoDoubleNode.first, twoTwoList)
        XCTAssertEqual(twoDoubleNode.last, doubleList)
        result = twoDoubleNode.popFirst()
        XCTAssertEqual(result.member, twoTwoList)
        XCTAssertEqual(result.trie, twoValueNode)
        result = twoDoubleNode.popLast()
        XCTAssertEqual(result.member, doubleList)
        XCTAssertEqual(result.trie, NeverEmptyTrie(list: twoTwoList))
    }

    // MARK: Set Manipulation

    // Test set union
    func testUnion() {
        let onlyEmptySequence = NeverEmptyTrie<Int>.cap
        XCTAssertNil(NeverEmptyTrie<Int>(unify: nil, with: nil))
        XCTAssertEqual(NeverEmptyTrie(unify: nil, with: onlyEmptySequence), onlyEmptySequence)
        XCTAssertEqual(NeverEmptyTrie(unify: onlyEmptySequence, with: nil), onlyEmptySequence)

        XCTAssertEqual(NeverEmptyTrie(unify: onlyEmptySequence, with: onlyEmptySequence), onlyEmptySequence)

        let oneValueNode = NeverEmptyTrie.branch(previousSibling: nil, head: 1, tail: .cap)
        XCTAssertEqual(NeverEmptyTrie(unify: nil, with: oneValueNode), oneValueNode)
        XCTAssertEqual(NeverEmptyTrie(unify: oneValueNode, with: nil), oneValueNode)

        let oneOrEmptyNode = NeverEmptyTrie.branch(previousSibling: .cap, head: 1, tail: .cap)
        XCTAssertEqual(NeverEmptyTrie(unify: onlyEmptySequence, with: oneValueNode), oneOrEmptyNode)
        XCTAssertEqual(NeverEmptyTrie(unify: oneValueNode, with: onlyEmptySequence), oneOrEmptyNode)

        XCTAssertEqual(NeverEmptyTrie(unify: oneValueNode, with: oneValueNode), oneValueNode)

        let twoThreeNode = NeverEmptyTrie.branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap))
        let oneTwoThreeNode = NeverEmptyTrie.branch(previousSibling: oneValueNode, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap))
        XCTAssertEqual(NeverEmptyTrie(unify: twoThreeNode, with: oneValueNode), oneTwoThreeNode)
        XCTAssertEqual(NeverEmptyTrie(unify: oneValueNode, with: twoThreeNode), oneTwoThreeNode)

        let twoTwoNode = NeverEmptyTrie.branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: nil, head: 2, tail: .cap))
        let twoTwoThreeNode = NeverEmptyTrie.branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: .branch(previousSibling: nil, head: 2, tail: .cap), head: 3, tail: .cap))
        XCTAssertEqual(NeverEmptyTrie(unify: twoThreeNode, with: twoTwoNode), twoTwoThreeNode)
        XCTAssertEqual(NeverEmptyTrie(unify: twoTwoNode, with: twoThreeNode), twoTwoThreeNode)
    }

    // Test set intersection
    func testIntersection() {
        let onlyEmptySequence = NeverEmptyTrie<Int>.cap
        XCTAssertNil(NeverEmptyTrie<Int>(intersect: nil, with: nil))
        XCTAssertNil(NeverEmptyTrie(intersect: nil, with: onlyEmptySequence))
        XCTAssertNil(NeverEmptyTrie(intersect: onlyEmptySequence, with: nil))

        XCTAssertEqual(NeverEmptyTrie(intersect: onlyEmptySequence, with: onlyEmptySequence), onlyEmptySequence)

        let oneValueNode = NeverEmptyTrie.branch(previousSibling: nil, head: 1, tail: .cap)
        XCTAssertNil(NeverEmptyTrie(intersect: onlyEmptySequence, with: oneValueNode))
        XCTAssertNil(NeverEmptyTrie(intersect: oneValueNode, with: onlyEmptySequence))

        XCTAssertEqual(NeverEmptyTrie(intersect: oneValueNode, with: oneValueNode), oneValueNode)

        let oneOrEmptyNode = NeverEmptyTrie.branch(previousSibling: .cap, head: 1, tail: .cap)
        XCTAssertEqual(NeverEmptyTrie(intersect: onlyEmptySequence, with: oneOrEmptyNode), onlyEmptySequence)
        XCTAssertEqual(NeverEmptyTrie(intersect: oneOrEmptyNode, with: onlyEmptySequence), onlyEmptySequence)
        XCTAssertEqual(NeverEmptyTrie(intersect: oneValueNode, with: oneOrEmptyNode), oneValueNode)
        XCTAssertEqual(NeverEmptyTrie(intersect: oneOrEmptyNode, with: oneValueNode), oneValueNode)

        let oneTwoThreeNode = NeverEmptyTrie.branch(previousSibling: oneValueNode, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap))
        XCTAssertEqual(NeverEmptyTrie(intersect: oneTwoThreeNode, with: oneOrEmptyNode), oneValueNode)
        XCTAssertEqual(NeverEmptyTrie(intersect: oneOrEmptyNode, with: oneTwoThreeNode), oneValueNode)

        let twoThreeNode = NeverEmptyTrie.branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap))
        let twoTwoNode = NeverEmptyTrie.branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: nil, head: 2, tail: .cap))
        XCTAssertNil(NeverEmptyTrie(intersect: twoTwoNode, with: twoThreeNode))
    }

    // Test set symmetric-difference
    func testSymmetricDifference() {
        let onlyEmptySequence = NeverEmptyTrie<Int>.cap
        XCTAssertNil(NeverEmptyTrie<Int>(antiIntersect: nil, with: nil))
        XCTAssertEqual(NeverEmptyTrie(antiIntersect: nil, with: onlyEmptySequence), onlyEmptySequence)
        XCTAssertEqual(NeverEmptyTrie(antiIntersect: onlyEmptySequence, with: nil), onlyEmptySequence)

        XCTAssertNil(NeverEmptyTrie(antiIntersect: onlyEmptySequence, with: onlyEmptySequence))

        let oneValueNode = NeverEmptyTrie.branch(previousSibling: nil, head: 1, tail: .cap)
        let oneOrEmptyNode = NeverEmptyTrie.branch(previousSibling: .cap, head: 1, tail: .cap)
        XCTAssertEqual(NeverEmptyTrie(antiIntersect: onlyEmptySequence, with: oneValueNode), oneOrEmptyNode)
        XCTAssertEqual(NeverEmptyTrie(antiIntersect: oneValueNode, with: onlyEmptySequence), oneOrEmptyNode)

        let twoThreeNode = NeverEmptyTrie.branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap))
        let oneTwoThreeNode = NeverEmptyTrie.branch(previousSibling: oneValueNode, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap))
        let oneTwoThreeEmptyNode = NeverEmptyTrie.branch(previousSibling: oneOrEmptyNode, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap))
        XCTAssertEqual(NeverEmptyTrie(antiIntersect: onlyEmptySequence, with: oneTwoThreeNode), oneTwoThreeEmptyNode)
        XCTAssertEqual(NeverEmptyTrie(antiIntersect: oneTwoThreeNode, with: onlyEmptySequence), oneTwoThreeEmptyNode)

        XCTAssertEqual(NeverEmptyTrie(antiIntersect: oneValueNode, with: oneTwoThreeNode), twoThreeNode)
        XCTAssertEqual(NeverEmptyTrie(antiIntersect: oneTwoThreeNode, with: oneValueNode), twoThreeNode)

        let oneTwoTwoThreeFourNode = NeverEmptyTrie.branch(previousSibling: oneValueNode, head: 2, tail: .branch(previousSibling: .branch(previousSibling: .branch(previousSibling: .cap, head: 2, tail: .cap), head: 3, tail: .cap), head: 4, tail: .cap))
        let emptyTwoThreeNode = NeverEmptyTrie.branch(previousSibling: .cap, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap))
        let emptyOneTwoTwoFourNode = NeverEmptyTrie.branch(previousSibling: .branch(previousSibling: .cap, head: 1, tail: .cap), head: 2, tail: .branch(previousSibling: .branch(previousSibling: .cap, head: 2, tail: .cap), head: 4, tail: .cap))
        XCTAssertEqual(NeverEmptyTrie(antiIntersect: oneTwoTwoThreeFourNode, with: emptyTwoThreeNode), emptyOneTwoTwoFourNode)
        XCTAssertEqual(NeverEmptyTrie(antiIntersect: emptyTwoThreeNode, with: oneTwoTwoThreeFourNode), emptyOneTwoTwoFourNode)
    }

    static var allTests = [
        ("testInvariantCheck", testInvariantCheck),
        ("testSerialization", testSerialization),

        ("testListConversion", testListConversion),
        ("testContains", testContains),
        ("testInsertion", testInsertion),
        ("testRemoval", testRemoval),
        ("testFirstLast", testFirstLast),

        ("testUnion", testUnion),
        ("testIntersection", testIntersection),
        ("testSymmetricDifference", testSymmetricDifference),
    ]

}
	//
	// LinkedList.swift
	// Trie
	//
	// Created by Daryle Walker on 5/30/19.
	//


	// MARK: - Singly-Linked List

	/// A seqeunce stored as a singly linked list.
	enum LinkedList<Element> {

	/// An empty sequence, also used for the cap of a non-empty one.
	case empty

	/// A non-empty sequence, with a leading head element and a tail of the
	/// trailing elements.
	indirect case nonempty(head: Element, tail: LinkedList)

	}

	// MARK: Debugging

	extension LinkedList: CustomDebugStringConvertible {

	var debugDescription: String {
	switch self {
	case .empty:
	return "∅"
	case let .nonempty(h, t):
	return String(reflecting: h) + " → " + String(reflecting: t)
	}
	}

	}

	// MARK: Comparisons

	extension LinkedList: Equatable where Element: Equatable {}
	extension LinkedList: Hashable where Element: Hashable {}

	extension LinkedList: Comparable where Element: Comparable {

	// Comparison is in lexicographical order.

	static func < (lhs: LinkedList, rhs: LinkedList) -> Bool {
	switch (lhs, rhs) {
	case let (.nonempty(lh, _), .nonempty(rh, _)) where lh < rh:
	fallthrough
	case (.empty, .nonempty):
	return true
	case let (.nonempty(lh, _), .nonempty(rh, _)) where lh > rh:
	fallthrough
	case (_, .empty):
	return false
	case let (.nonempty(lh, lt), .nonempty(rh, rt)):
	assert(lh == rh)
	return lt < rt
	}
	}

	}

	// MARK: Sequencing

	extension LinkedList: IteratorProtocol, Sequence {

	// Since a separate iterator type would need to carry a copy of the list,
	// might as well group iteration within the list type.

	mutating func next() -> Element? {
	switch self {
	case .empty:
	return nil
	case let .nonempty(head, tail):
	defer { self = tail }
	return head
	}
	}

	var underestimatedCount: Int {
	switch self {
	case .empty:
	return 0
	case .nonempty:
	return 1
	}
	}

	}

	extension LinkedList {

	/// Creates a copy of the given iterator's underlying sequence.
	private init<I: IteratorProtocol>(_ i: inout I) where I.Element == Element {
	switch i.next() {
	case nil:
	self = .empty
	case let h?:
	self = .nonempty(head: h, tail: .init(&i))
	}
	}

	/// Creates a copy of the given sequence's underlying sequence.
	///
	/// - Parameter s: The sequence to copy elements from.
	///
	/// - Postcondition: `self` and `s` vend the same underlying sequence.
	///
	/// - Complexity: O(n), where n is the length of `s`.
	init<S: Sequence>(_ s: S) where S.Element == Element {
	var iterator = s.makeIterator()
	self.init(&iterator)
	}

	}

	// MARK: Accessors

	extension LinkedList {

	/// Indicates whether the list contains no elements.
	///
	/// - Complexity: O(1)
	var isEmpty: Bool {
	switch self {
	case .empty:
	return true
	case .nonempty:
	return false
	}
	}

	/// The first element of the list.
	///
	/// If the list is empty, expresses `nil`.
	var first: Element? {
	switch self {
	case .empty:
	return nil
	case .nonempty(let h, _):
	return h
	}
	}

	/// The list without its first element
	///
	/// If the list is empty, expresses `nil`.
	var rest: LinkedList? {
	switch self {
	case .empty:
	return nil
	case .nonempty(_, let t):
	return t
	}
	}

	}
	//
	// LinkedListTests.swift
	// TrieTests
	//
	// Created by Daryle Walker on 5/30/19.
	//

	import XCTest
	@testable import Trie


	class LinkedListTests: XCTestCase {

	enum Constants {

	static let emptyList = LinkedList<Int>.empty
	static let singleList = LinkedList.nonempty(head: 1, tail: .empty)
	static let doubleList = LinkedList.nonempty(head: 2, tail: .nonempty(head: 3, tail: .empty))
	static let tripleList = LinkedList.nonempty(head: 4, tail: .nonempty(head: 5, tail: .nonempty(head: 6, tail: .empty)))

	}

	override func setUp() {
	// Put setup code here. This method is called before the invocation of each test method in the class.
	}

	override func tearDown() {
	// Put teardown code here. This method is called after the invocation of each test method in the class.
	}

	// Test debug-string conversion
	func testSerialization() {
	// Check empty-list case
	XCTAssertEqual(String(reflecting: Constants.emptyList), "∅")

	// Check non-empty list
	XCTAssertEqual(String(reflecting: Constants.singleList), "1 → ∅")

	// Check more recursive cases
	XCTAssertEqual(String(reflecting: Constants.doubleList), "2 → 3 → ∅")
	XCTAssertEqual(String(reflecting: Constants.tripleList), "4 → 5 → 6 → ∅")
	}

	// Test lexiographic comparison
	func testCompare() {
	XCTAssertLessThan(Constants.emptyList, Constants.singleList)

	XCTAssertGreaterThanOrEqual(Constants.emptyList, Constants.emptyList)
	XCTAssertGreaterThanOrEqual(Constants.singleList, Constants.emptyList)

	let singleTwo = LinkedList.nonempty(head: 2, tail: .empty)
	XCTAssertLessThan(Constants.singleList, singleTwo)
	XCTAssertGreaterThanOrEqual(singleTwo, Constants.singleList)

	XCTAssertEqual(singleTwo, singleTwo)
	XCTAssertGreaterThanOrEqual(singleTwo, singleTwo)
	XCTAssertLessThan(singleTwo, Constants.doubleList)
	XCTAssertGreaterThanOrEqual(Constants.doubleList, singleTwo)

	let fourSeven = LinkedList.nonempty(head: 4, tail: .nonempty(head: 7, tail: .empty))
	let fourFiveEight = LinkedList.nonempty(head: 4, tail: .nonempty(head: 5, tail: .nonempty(head: 8, tail: .empty)))
	XCTAssertLessThan(Constants.doubleList, fourSeven)
	XCTAssertGreaterThanOrEqual(fourSeven, Constants.doubleList)
	XCTAssertLessThan(Constants.doubleList, fourFiveEight)
	XCTAssertGreaterThanOrEqual(fourFiveEight, Constants.doubleList)
	XCTAssertLessThan(Constants.tripleList, fourFiveEight)
	XCTAssertGreaterThanOrEqual(fourFiveEight, Constants.tripleList)
	}

	// Test sequence conformance
	func testSequenceUse() {
	XCTAssertEqual(Constants.emptyList.underestimatedCount, 0)
	XCTAssertEqual(Constants.singleList.underestimatedCount, 1)
	XCTAssertEqual(Constants.doubleList.underestimatedCount, 1)
	XCTAssertEqual(Constants.tripleList.underestimatedCount, 1)

	XCTAssertEqual(Array(Constants.emptyList), [Int]())
	XCTAssertEqual(Array(Constants.singleList), [1])
	XCTAssertEqual(Array(Constants.doubleList), [2, 3])
	XCTAssertEqual(Array(Constants.tripleList), [4, 5, 6])
	}

	// Test initialization from sequences
	func testSequenceInit() {
	XCTAssertEqual(LinkedList([Int]()), Constants.emptyList)
	XCTAssertEqual(LinkedList([1]), Constants.singleList)
	XCTAssertEqual(LinkedList([2, 3]), Constants.doubleList)
	XCTAssertEqual(LinkedList([4, 5, 6]), Constants.tripleList)
	}

	// Test element accessors and status
	func testAccess() {
	XCTAssertTrue(Constants.emptyList.isEmpty)
	XCTAssertFalse(Constants.singleList.isEmpty)
	XCTAssertFalse(Constants.doubleList.isEmpty)
	XCTAssertFalse(Constants.tripleList.isEmpty)

	XCTAssertNil(Constants.emptyList.first)
	XCTAssertEqual(Constants.singleList.first, 1)
	XCTAssertEqual(Constants.doubleList.first, 2)
	XCTAssertEqual(Constants.tripleList.first, 4)

	XCTAssertNil(Constants.emptyList.rest)
	XCTAssertEqual(Constants.singleList.rest, Constants.emptyList)
	XCTAssertEqual(Constants.doubleList.rest, LinkedList([3]))
	XCTAssertEqual(Constants.tripleList.rest, LinkedList([5, 6]))
	}

	static var allTests = [
	("testSerialization", testSerialization),
	("testCompare", testCompare),
	("testSequenceUse", testSequenceUse),
	("testSequenceInit", testSequenceInit),
	("testAccess", testAccess),
	]

	}
	//
	// NeverEmptyTrie.swift
	// Trie
	//
	// Created by Daryle Walker on 5/30/19.
	//


	// MARK: - Trie without allowing empty sets

	/// A never-empty set of type-erased sequences sharing the same element type.
	///
	/// The sequences are exploded into separate element nodes connected into a
	/// doubly chained tree.
	///
	/// Mandating the element type to `Comparable` conformance enables uniqueness of
	/// sequences stored in the trie. It also allows visitation of those sequences
	/// as a sequence with a consistent order.
	///
	/// Since the outline of this enumeration type cannot enforce the invariants,
	/// this type must be hidden as an implementation type.
	enum NeverEmptyTrie<SubElement: Comparable> {

	/// Marks the end of a chain of sequence elements.
	case cap

	/// Marks the initial element of the last branch of stored sequences, along
	/// with all possible suffix branches and a possible link to sibling
	/// branches.
	indirect case branch(previousSibling: NeverEmptyTrie?, head: SubElement, tail: NeverEmptyTrie)

	}

	// MARK: Debugging

	extension NeverEmptyTrie {

	/// Whether the invariants of the type have been kept.
	///
	/// The invariant is: where there are sibling branches, earlier siblings
	/// must have `head` values less than the current `head` value.
	var invariantKept: Bool {
	switch self {
	case .cap:
	// No stored elements.
	return true
	case .branch(.none, _, let t), .branch(.some(.cap), _, let t):
	// Only one stored element
	return t.invariantKept
	case let .branch(.some(.branch(ps1, h1, t1)), h0, t0):
	// Multiple store elements at the same level, plus the other levels.
	return t0.invariantKept && h0 > h1 && t1.invariantKept && ps1?.invariantKept ?? true
	}
	}

	}

	extension NeverEmptyTrie: CustomDebugStringConvertible {

	/// A debug-worthy text representation of this direct branch of this trie,
	/// without regard for its siblings (if any).
	private var soloDebugDescription: String {
	switch self {
	case .cap:
	return "∅"
	case let .branch(_, head, tail):
	switch tail {
	case .cap, .branch(nil, _, _):
	return String(reflecting: head) + " → " + tail.soloDebugDescription
	case .branch(let earlierTailSibling?, _, _):
	return String(reflecting: head) + " → " + earlierTailSibling.siblingDebugDescription + tail.soloDebugDescription + ")"
	}
	}
	}

	/// A debug-worthy text representation of this direct branch of this trie,
	/// along with any siblings.
	private var siblingDebugDescription: String {
	switch self {
	case .cap:
	return "(∅ \| "
	case .branch(let previousSibling, _, _):
	let suffix = soloDebugDescription + " \| "
	if let previous = previousSibling {
	return previous.siblingDebugDescription + suffix
	} else {
	return "(" + suffix
	}
	}
	}

	var debugDescription: String {
	switch self {
	case .cap, .branch(nil, _, _):
	return soloDebugDescription
	case .branch(let previousSibling?, _, _):
	// There will be no ")" after the last term, so remove the "(" that
	// starts the first term.
	return previousSibling.siblingDebugDescription.dropFirst() + soloDebugDescription
	}
	}

	}

	// MARK: Comparisons

	extension NeverEmptyTrie: Equatable {}

	extension NeverEmptyTrie: Hashable where SubElement: Hashable {}

	// MARK: Conversions

	extension NeverEmptyTrie {

	/// Creates a trie with the given sequence as its sole member.
	init(list: LinkedList<SubElement>) {
	switch list {
	case .empty:
	self = .cap
	case .nonempty(let h, let t):
	self = .branch(previousSibling: nil, head: h, tail: .init(list: t))
	}
	}

	}

	// MARK: Membership

	extension NeverEmptyTrie {

	/// Returns whether the given sequence is a member of this set.
	func contains(_ list: LinkedList<SubElement>) -> Bool {
	switch (self, list) {
	case (.cap, .empty):
	// Elementary.
	return true
	case let (.branch(_, bh, _), .nonempty(lh, _)) where bh < lh:
	// No match, and siblings have even smaller head values, so...
	fallthrough
	case (.cap, .nonempty):
	// No match and no more siblings to check.
	return false
	case let (.branch(_, bh, bt), .nonempty(lh, lt)) where bh == lh:
	// First match, now recursively continue.
	return bt.contains(lt)
	case (.branch(let bs, _, _), _):
	// (Either list.isEmpty or self.head > list.head)
	// There is still a chance that a sibling branch may match.
	return bs?.contains(list) ?? false
	}
	}

	/// Returns a copy of this set with the given list added as a member, and a
	/// flag indicating if the list wasn't already a member.
	func doInsert(_ list: LinkedList<SubElement>) -> (trie: NeverEmptyTrie, didInsert: Bool) {
	switch (self, list) {
	case (.cap, .empty):
	// Elementary.
	return (trie: self, didInsert: false)
	case let (.branch(_, bh, _), .nonempty(lh, lt)) where bh < lh:
	// List has the largest head value among its would-be siblings...
	fallthrough
	case let (.cap, .nonempty(lh, lt)):
	// Insert list's branch ahead of existing ones.
	return (trie: .branch(previousSibling: self, head: lh, tail: .init(list: lt)), didInsert: true)
	case let (.branch(ps, bh, bt), .nonempty(lh, lt)) where bh == lh:
	// Recursively continue insertion for the sub-trie and suffix.
	let newTailInsertion = bt.doInsert(lt)
	return (trie: .branch(previousSibling: ps, head: bh, tail: newTailInsertion.trie), didInsert: newTailInsertion.didInsert)
	case let (.branch(nil, bh, bt), _):
	// (Either list == .empty or self.head > list.head)
	// Insert list's branch behind the existing ones.
	return (trie: .branch(previousSibling: .init(list: list), head: bh, tail: bt), didInsert: true)
	case let (.branch(ps?, bh, bt), _):
	// (Either list == .empty or self.head > list.head)
	// Insert list's branch past a sibling branch.
	let newSiblingInsertion = ps.doInsert(list)
	return (trie: .branch(previousSibling: newSiblingInsertion.trie, head: bh, tail: bt), didInsert: newSiblingInsertion.didInsert)
	}
	}

	/// Returns a copy of this set without the given list as a member, possibly
	/// nil if that list was the sole member, and a flag indicating if the list
	/// was initially a member.
	func doRemove(_ list: LinkedList<SubElement>) -> (trie: NeverEmptyTrie?, didRemove: Bool) {
	switch (self, list) {
	case (.cap, .empty):
	// Elementary.
	return (trie: nil, didRemove: true)
	case let (.branch(_, bh, _), .nonempty(lh, _)) where bh < lh:
	// List has the largest head value among its would-be siblings...
	fallthrough
	case (.cap, .nonempty):
	// No more branches that could be searched for a match.
	return (trie: self, didRemove: false)
	case let (.branch(ps, bh, bt), .nonempty(lh, lt)) where bh == lh:
	// Recursively check & remove the sub-trie and suffix.
	let newTailRemoval = bt.doRemove(lt)
	if let newTail = newTailRemoval.trie {
	return (trie: .branch(previousSibling: ps, head: bh, tail: newTail), didRemove: newTailRemoval.didRemove)
	} else {
	assert(newTailRemoval.didRemove)
	return (trie: ps, didRemove: true)
	}
	case (.branch(nil, _, _), _):
	// (Either list == .empty or self.head > list.head)
	// No matches found, and no more to search.
	return (trie: self, didRemove: false)
	case let (.branch(ps?, bh, bt), _):
	// (Either list == .empty or self.head > list.head)
	// Check sibling branches for the target.
	let newSiblingRemoval = ps.doRemove(list)
	return (trie: .branch(previousSibling: newSiblingRemoval.trie, head: bh, tail: bt), didRemove: newSiblingRemoval.didRemove)
	}
	}

	}

	extension NeverEmptyTrie {

	/// Returns whether there is only one member in the set.
	///
	/// Such sets will return `nil` for `popFirst().trie` and `popLast().trie`.
	var countIsOne: Bool {
	switch self {
	case .cap:
	return true
	case .branch(nil, _, let t):
	return t.countIsOne
	case .branch(_?, _, _):
	return false
	}
	}

	/// Returns the lexiographically first sequence stored in the set.
	var first: LinkedList<SubElement> {
	switch self {
	case .cap:
	return .empty
	case let .branch(nil, h, t):
	return .nonempty(head: h, tail: t.first)
	case .branch(let ps?, _, _):
	return ps.first
	}
	}

	/// Returns the lexiographically last sequence stored in the set.
	var last: LinkedList<SubElement> {
	switch self {
	case .cap:
	return .empty
	case let .branch(_, h, t):
	return .nonempty(head: h, tail: t.last)
	}
	}

	/// Removes the lexiographically first sequence stored in the set,
	/// returning that ex-member and the post-removal set.
	func popFirst() -> (member: LinkedList<SubElement>, trie: NeverEmptyTrie?) {
	switch self {
	case .cap:
	return (member: .empty, trie: nil)
	case let .branch(nil, h, t):
	let strippedTail = t.popFirst()
	let member = LinkedList.nonempty(head: h, tail: strippedTail.member)
	let trie = strippedTail.trie.map { NeverEmptyTrie.branch(previousSibling: nil, head: h, tail: $0) }
	return (member: member, trie: trie)
	case let .branch(ps?, h, t):
	let psPopped = ps.popFirst()
	return (member: psPopped.member, trie: .branch(previousSibling: psPopped.trie, head: h, tail: t))
	}
	}

	/// Removes the lexiographically last sequence stored in the set,
	/// returning that ex-member and the post-removal set.
	func popLast() -> (member: LinkedList<SubElement>, trie: NeverEmptyTrie?) {
	switch self {
	case .cap:
	return (member: .empty, trie: nil)
	case let .branch(ps, h, t):
	let strippedTail = t.popLast()
	let member = LinkedList.nonempty(head: h, tail: strippedTail.member)
	let trie = strippedTail.trie.map { NeverEmptyTrie.branch(previousSibling: ps, head: h, tail: $0) } ?? ps
	return (member: member, trie: trie)
	}
	}

	}

	// MARK: Set Operations

	extension NeverEmptyTrie {

	/// Creates a set that is the union of the given sets.
	init?(unify f: NeverEmptyTrie?, with s: NeverEmptyTrie?) {
	switch (f, s) {
	case (.none, .none):
	// Nothing to combine.
	return nil
	case (.some(let t), .none), (.none, .some(let t)):
	// Copy the sole proper argument.
	self = t
	case (.some(.cap), .some(.cap)):
	// Identical.
	self = .cap
	case let (.some(.cap), .some(.branch(ps, h, t))), let (.some(.branch(ps, h, t)), .some(.cap)):
	// Chain them together.
	self = .branch(previousSibling: NeverEmptyTrie(unify: .cap, with: ps), head: h, tail: t)
	case let (.some(.branch(lessPs, lessH, lessT)), .some(.branch(greatPs, greatH, tail: greatT))) where lessH < greatH, let (.some(.branch(greatPs, greatH, greatT)), .some(.branch(lessPs, lessH, lessT))) where greatH > lessH:
	// The set with the smaller head becomes a sibling branch from the other set.
	self = .branch(previousSibling: NeverEmptyTrie(unify: .branch(previousSibling: lessPs, head: lessH, tail: lessT), with: greatPs), head: greatH, tail: greatT)
	case let (.some(.branch(fps, fh, ft)), .some(.branch(sps, sh, st))):
	// Recursively blend the suffixes and chain the sibling branches.
	assert(fh == sh)
	self = .branch(previousSibling: NeverEmptyTrie(unify: fps, with: sps), head: fh, tail: NeverEmptyTrie(unify: ft, with: st)!)
	}
	}

	/// Creates a set that is the intersection of the given sets.
	init?(intersect f: NeverEmptyTrie?, with s: NeverEmptyTrie?) {
	// The intersection of nothing with anything is nothing.
	guard let ff = f, let ss = s else { return nil }

	switch (ff, ss) {
	case (.cap, .cap):
	// Identical.
	self = .cap
	case (.cap, .branch(let ps, _, _)), (.branch(let ps, _, _), .cap):
	// Whatever's in common doesn't include the last branch.
	self.init(intersect: .cap, with: ps)
	case let (.branch(lessPs, lessH, lessT), .branch(greatPs, greatH, _)) where lessH < greatH, let (.branch(greatPs, greatH, _), .branch(lessPs, lessH, lessT)) where greatH > lessH:
	// Whatever's in common doesn't include the would-be last branch.
	self.init(intersect: .branch(previousSibling: lessPs, head: lessH, tail: lessT), with: greatPs)
	case let (.branch(fps, fh, ft), .branch(sps, sh, st)):
	// Recursively blend the suffixes and chain the sibling branches.
	assert(fh == sh)
	if let tailIntersection = NeverEmptyTrie(intersect: ft, with: st) {
	self = .branch(previousSibling: NeverEmptyTrie(intersect: fps, with: sps), head: fh, tail: tailIntersection)
	} else {
	self.init(intersect: fps, with: sps)
	}
	}
	}

	/// Creates a set that is the symmetric difference of the given sets.
	init?(antiIntersect f: NeverEmptyTrie?, with s: NeverEmptyTrie?) {
	switch (f, s) {
	case (.none, .none):
	// Nothing to combine.
	return nil
	case (.some(let t), .none), (.none, .some(let t)):
	// The sole proper argument is outside the intersection.
	self = t
	case (.some(.cap), .some(.cap)):
	// Identical.
	return nil
	case let (.some(.cap), .some(.branch(ps, h, t))), let (.some(.branch(ps, h, t)), .some(.cap)):
	// The last branch doesn't overlap, but a sibling might.
	self = .branch(previousSibling: NeverEmptyTrie(antiIntersect: .cap, with: ps), head: h, tail: t)
	case let (.some(.branch(lessPs, lessH, lessT)), .some(.branch(greatPs, greatH, greatT))) where lessH < greatH, let (.some(.branch(greatPs, greatH, greatT)), .some(.branch(lessPs, lessH, lessT))) where greatH > lessH:
	// The would-be last branch is included, but its siblings might not be.
	self = .branch(previousSibling: NeverEmptyTrie(antiIntersect: .branch(previousSibling: lessPs, head: lessH, tail: lessT), with: greatPs), head: greatH, tail: greatT)
	case let (.some(.branch(fps, fh, ft)), .some(.branch(sps, sh, st))):
	// Recursively blend the suffixes and chain the sibling branches
	assert(fh == sh)
	if let tailSymDiff = NeverEmptyTrie(antiIntersect: ft, with: st) {
	self = .branch(previousSibling: NeverEmptyTrie(antiIntersect: fps, with: sps), head: fh, tail: tailSymDiff)
	} else {
	self.init(antiIntersect: fps, with: sps)
	}
	}
	}

	}
	//
	// NeverEmptyTrieTests.swift
	// TrieTests
	//
	// Created by Daryle Walker on 5/30/19.
	//

	import XCTest
	@testable import Trie


	class NeverEmptyTrieTests: XCTestCase {

	override func setUp() {
	// Put setup code here. This method is called before the invocation of each test method in the class.
	}

	override func tearDown() {
	// Put teardown code here. This method is called after the invocation of each test method in the class.
	}

	// MARK: Debugging

	// Test the invariant checker
	func testInvariantCheck() {
	XCTAssertTrue(NeverEmptyTrie<Int>.cap.invariantKept)
	XCTAssertTrue(NeverEmptyTrie.branch(previousSibling: nil, head: 0, tail: .cap).invariantKept)
	XCTAssertTrue(NeverEmptyTrie.branch(previousSibling: .cap, head: 1, tail: .cap).invariantKept)

	XCTAssertTrue(NeverEmptyTrie.branch(previousSibling: .branch(previousSibling: nil, head: 2, tail: .cap), head: 3, tail: .cap).invariantKept)

	let failingHeads = NeverEmptyTrie.branch(previousSibling: .branch(previousSibling: nil, head: 5, tail: .cap), head: 4, tail: .cap)
	XCTAssertFalse(failingHeads.invariantKept)

	let failingOuterTail = NeverEmptyTrie.branch(previousSibling: .branch(previousSibling: nil, head: 6, tail: .cap), head: 7, tail: failingHeads)
	XCTAssertFalse(failingOuterTail.invariantKept)

	let failingInnerTail = NeverEmptyTrie.branch(previousSibling: .branch(previousSibling: nil, head: 8, tail: failingHeads), head: 9, tail: .cap)
	XCTAssertFalse(failingInnerTail.invariantKept)

	let failingSibling = NeverEmptyTrie.branch(previousSibling: .branch(previousSibling: failingHeads, head: 10, tail: .cap), head: 11, tail: .cap)
	XCTAssertFalse(failingSibling.invariantKept)

	let failingEqualHeads = NeverEmptyTrie.branch(previousSibling: .branch(previousSibling: nil, head: 12, tail: .cap), head: 12, tail: .cap)
	XCTAssertFalse(failingEqualHeads.invariantKept)
	}

	// Test debug-string conversion
	func testSerialization() {
	XCTAssertEqual(String(reflecting: NeverEmptyTrie<Int>.cap), "∅")

	let singleNode = NeverEmptyTrie.branch(previousSibling: nil, head: 1, tail: .cap)
	XCTAssertEqual(String(reflecting: singleNode), "1 → ∅")

	let doubleNodeLine = NeverEmptyTrie.branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap))
	XCTAssertEqual(String(reflecting: doubleNodeLine), "2 → 3 → ∅")

	let branchedNodes = NeverEmptyTrie.branch(previousSibling: nil, head: 4, tail: .branch(previousSibling: .branch(previousSibling: nil, head: 5, tail: .cap), head: 6, tail: .cap))
	XCTAssertEqual(String(reflecting: branchedNodes), "4 → (5 → ∅ \| 6 → ∅)")

	let tripleNodes = NeverEmptyTrie.branch(previousSibling: nil, head: 7, tail: .branch(previousSibling: .branch(previousSibling: .cap, head: 8, tail: .cap), head: 9, tail: .cap))
	XCTAssertEqual(String(reflecting: tripleNodes), "7 → (∅ \| 8 → ∅ \| 9 → ∅)")

	let topBranches = NeverEmptyTrie.branch(previousSibling: .branch(previousSibling: .cap, head: 10, tail: .branch(previousSibling: nil, head: 11, tail: .cap)), head: 12, tail: .branch(previousSibling: .branch(previousSibling: nil, head: 13, tail: .cap), head: 14, tail: .cap))
	XCTAssertEqual(String(reflecting: topBranches), "∅ \| 10 → 11 → ∅ \| 12 → (13 → ∅ \| 14 → ∅)")

	let topNonemptyBranches = NeverEmptyTrie.branch(previousSibling: .branch(previousSibling: .branch(previousSibling: nil, head: 15, tail: .cap), head: 16, tail: .branch(previousSibling: .branch(previousSibling: nil, head: 17, tail: .cap), head: 18, tail: .cap)), head: 19, tail: .branch(previousSibling: nil, head: 20, tail: .branch(previousSibling: nil, head: 21, tail: .cap)))
	XCTAssertEqual(String(reflecting: topNonemptyBranches), "15 → ∅ \| 16 → (17 → ∅ \| 18 → ∅) \| 19 → 20 → 21 → ∅")
	}

	// MARK: Element Manipulation

	// Test list conversion
	func testListConversion() {
	XCTAssertEqual(NeverEmptyTrie(list: LinkedList<Int>.empty), NeverEmptyTrie.cap)

	XCTAssertEqual(NeverEmptyTrie(list: LinkedList([1])), NeverEmptyTrie.branch(previousSibling: nil, head: 1, tail: .cap))
	XCTAssertEqual(NeverEmptyTrie(list: LinkedList([2, 3])), NeverEmptyTrie.branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap)))
	XCTAssertEqual(NeverEmptyTrie(list: LinkedList([4, 5, 6])), NeverEmptyTrie.branch(previousSibling: nil, head: 4, tail: .branch(previousSibling: nil, head: 5, tail: .branch(previousSibling: nil, head: 6, tail: .cap))))
	}

	// Test containment check
	func testContains() {
	let emptyList = LinkedList<Int>.empty
	let singleList = LinkedList([1])
	XCTAssertTrue(NeverEmptyTrie.cap.contains(emptyList))
	XCTAssertFalse(NeverEmptyTrie.cap.contains(singleList))

	let singleNode = NeverEmptyTrie.branch(previousSibling: nil, head: 1, tail: .cap)
	let doubleList = LinkedList([2, 3])
	XCTAssertFalse(singleNode.contains(doubleList))
	XCTAssertTrue(singleNode.contains(singleList))
	XCTAssertFalse(singleNode.contains(emptyList))

	let zeroOrOneNode = NeverEmptyTrie.branch(previousSibling: .cap, head: 1, tail: .cap)
	XCTAssertTrue(zeroOrOneNode.contains(emptyList))
	XCTAssertTrue(zeroOrOneNode.contains(singleList))
	XCTAssertFalse(zeroOrOneNode.contains(doubleList))

	let zeroToTwoNodes = NeverEmptyTrie.branch(previousSibling: zeroOrOneNode, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap))
	XCTAssertTrue(zeroToTwoNodes.contains(emptyList))
	XCTAssertTrue(zeroToTwoNodes.contains(singleList))
	XCTAssertTrue(zeroToTwoNodes.contains(doubleList))

	let longNodes = NeverEmptyTrie.branch(previousSibling: nil, head: 4, tail: .branch(previousSibling: nil, head: 5, tail: .branch(previousSibling: .branch(previousSibling: nil, head: 6, tail: .cap), head: 7, tail: .branch(previousSibling: .cap, head: 8, tail: .cap))))
	XCTAssertTrue(longNodes.contains(LinkedList([4, 5, 6])))
	XCTAssertTrue(longNodes.contains(LinkedList([4, 5, 7])))
	XCTAssertFalse(longNodes.contains(LinkedList([4, 5, 8])))
	XCTAssertTrue(longNodes.contains(LinkedList([4, 5, 7, 8])))
	}

	// Test inserting a member
	func testInsertion() {
	let emptyList = LinkedList<Int>.empty
	var result = NeverEmptyTrie.cap.doInsert(emptyList)
	XCTAssertEqual(result.trie, .cap)
	XCTAssertFalse(result.didInsert)

	let singleList = LinkedList([1])
	result = NeverEmptyTrie.cap.doInsert(singleList)
	XCTAssertEqual(result.trie, .branch(previousSibling: .cap, head: 1, tail: .cap))
	XCTAssertTrue(result.didInsert)

	let zeroValueNode = NeverEmptyTrie.branch(previousSibling: nil, head: 0, tail: .cap)
	result = zeroValueNode.doInsert(singleList)
	XCTAssertEqual(result.trie, .branch(previousSibling: .branch(previousSibling: nil, head: 0, tail: .cap), head: 1, tail: .cap))
	XCTAssertTrue(result.didInsert)

	let twoTwoNode = NeverEmptyTrie.branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: nil, head: 2, tail: .cap))
	let doubleList = LinkedList([2, 3])
	result = twoTwoNode.doInsert(doubleList)
	XCTAssertEqual(result.trie, .branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: .branch(previousSibling: nil, head: 2, tail: .cap), head: 3, tail: .cap)))
	XCTAssertTrue(result.didInsert)

	result = result.trie.doInsert(doubleList)
	XCTAssertEqual(result.trie, .branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: .branch(previousSibling: nil, head: 2, tail: .cap), head: 3, tail: .cap)))
	XCTAssertFalse(result.didInsert)

	result = twoTwoNode.doInsert(singleList)
	XCTAssertEqual(result.trie, .branch(previousSibling: .branch(previousSibling: nil, head: 1, tail: .cap), head: 2, tail: .branch(previousSibling: nil, head: 2, tail: .cap)))
	XCTAssertTrue(result.didInsert)

	result = result.trie.doInsert(emptyList)
	XCTAssertEqual(result.trie, .branch(previousSibling: .branch(previousSibling: .cap, head: 1, tail: .cap), head: 2, tail: .branch(previousSibling: nil, head: 2, tail: .cap)))
	XCTAssertTrue(result.didInsert)

	result = result.trie.doInsert(emptyList)
	XCTAssertEqual(result.trie, .branch(previousSibling: .branch(previousSibling: .cap, head: 1, tail: .cap), head: 2, tail: .branch(previousSibling: nil, head: 2, tail: .cap)))
	XCTAssertFalse(result.didInsert)
	}

	// Test removing a member
	func testRemoval() {
	let onlyEmptySequence = NeverEmptyTrie<Int>.cap
	let emptyList = LinkedList<Int>.empty
	var result = onlyEmptySequence.doRemove(emptyList)
	XCTAssertNil(result.trie)
	XCTAssertTrue(result.didRemove)

	let singleList = LinkedList([1])
	result = onlyEmptySequence.doRemove(singleList)
	XCTAssertEqual(result.trie, onlyEmptySequence)
	XCTAssertFalse(result.didRemove)

	let zeroValueNode = NeverEmptyTrie.branch(previousSibling: nil, head: 0, tail: .cap)
	result = zeroValueNode.doRemove(singleList)
	XCTAssertEqual(result.trie, zeroValueNode)
	XCTAssertFalse(result.didRemove)

	result = zeroValueNode.doRemove(emptyList)
	XCTAssertEqual(result.trie, zeroValueNode)
	XCTAssertFalse(result.didRemove)

	let doubleList = LinkedList([2, 3])
	let twoNode = NeverEmptyTrie(list: doubleList)
	result = twoNode.doRemove(singleList)
	XCTAssertEqual(result.trie, twoNode)
	XCTAssertFalse(result.didRemove)

	let oneValueNode = NeverEmptyTrie.branch(previousSibling: nil, head: 1, tail: .cap)
	result = oneValueNode.doRemove(singleList)
	XCTAssertNil(result.trie)
	XCTAssertTrue(result.didRemove)

	let twoTwoList = LinkedList([2, 2])
	result = twoNode.doRemove(twoTwoList)
	XCTAssertEqual(result.trie, twoNode)
	XCTAssertFalse(result.didRemove)

	result = twoNode.doRemove(doubleList)
	XCTAssertNil(result.trie)
	XCTAssertTrue(result.didRemove)

	let twoThreeNode = twoNode.doInsert(twoTwoList).trie
	result = twoThreeNode.doRemove(doubleList)
	XCTAssertEqual(result.trie, NeverEmptyTrie(list: twoTwoList))
	XCTAssertTrue(result.didRemove)

	let twoThreeEmptyNode = twoThreeNode.doInsert(emptyList).trie
	result = twoThreeEmptyNode.doRemove(emptyList)
	XCTAssertEqual(result.trie, twoThreeNode)
	XCTAssertTrue(result.didRemove)

	result = twoThreeEmptyNode.doRemove(singleList)
	XCTAssertEqual(result.trie, twoThreeEmptyNode)
	XCTAssertFalse(result.didRemove)

	result = twoThreeNode.doRemove(twoTwoList)
	XCTAssertEqual(result.trie, NeverEmptyTrie(list: doubleList))
	XCTAssertTrue(result.didRemove)
	}

	// Test check & extracting the end members
	func testFirstLast() {
	let onlyEmptySequence = NeverEmptyTrie<Int>.cap
	let emptyList = LinkedList<Int>.empty
	XCTAssertTrue(onlyEmptySequence.countIsOne)
	XCTAssertEqual(onlyEmptySequence.first, emptyList)
	XCTAssertEqual(onlyEmptySequence.last, emptyList)

	var result = onlyEmptySequence.popFirst()
	XCTAssertEqual(result.member, emptyList)
	XCTAssertNil(result.trie)
	result = onlyEmptySequence.popLast()
	XCTAssertEqual(result.member, emptyList)
	XCTAssertNil(result.trie)

	let singleList = LinkedList([1])
	let oneValueNode = NeverEmptyTrie(list: singleList)
	XCTAssertTrue(oneValueNode.countIsOne)
	XCTAssertEqual(oneValueNode.first, singleList)
	XCTAssertEqual(oneValueNode.last, singleList)
	result = oneValueNode.popFirst()
	XCTAssertEqual(result.member, singleList)
	XCTAssertNil(result.trie)
	result = oneValueNode.popLast()
	XCTAssertEqual(result.member, singleList)
	XCTAssertNil(result.trie)

	let doubleList = LinkedList([2, 3])
	let twoValueNode = NeverEmptyTrie(list: doubleList)
	let twoWayNode = twoValueNode.doInsert(singleList).trie
	XCTAssertFalse(twoWayNode.countIsOne)
	XCTAssertEqual(twoWayNode.first, singleList)
	XCTAssertEqual(twoWayNode.last, doubleList)
	result = twoWayNode.popFirst()
	XCTAssertEqual(result.member, singleList)
	XCTAssertEqual(result.trie, twoValueNode)
	result = twoWayNode.popLast()
	XCTAssertEqual(result.member, doubleList)
	XCTAssertEqual(result.trie, oneValueNode)

	let twoTwoList = LinkedList([2, 2])
	let twoDoubleNode = twoValueNode.doInsert(twoTwoList).trie
	XCTAssertFalse(twoDoubleNode.countIsOne)
	XCTAssertEqual(twoDoubleNode.first, twoTwoList)
	XCTAssertEqual(twoDoubleNode.last, doubleList)
	result = twoDoubleNode.popFirst()
	XCTAssertEqual(result.member, twoTwoList)
	XCTAssertEqual(result.trie, twoValueNode)
	result = twoDoubleNode.popLast()
	XCTAssertEqual(result.member, doubleList)
	XCTAssertEqual(result.trie, NeverEmptyTrie(list: twoTwoList))
	}

	// MARK: Set Manipulation

	// Test set union
	func testUnion() {
	let onlyEmptySequence = NeverEmptyTrie<Int>.cap
	XCTAssertNil(NeverEmptyTrie<Int>(unify: nil, with: nil))
	XCTAssertEqual(NeverEmptyTrie(unify: nil, with: onlyEmptySequence), onlyEmptySequence)
	XCTAssertEqual(NeverEmptyTrie(unify: onlyEmptySequence, with: nil), onlyEmptySequence)

	XCTAssertEqual(NeverEmptyTrie(unify: onlyEmptySequence, with: onlyEmptySequence), onlyEmptySequence)

	let oneValueNode = NeverEmptyTrie.branch(previousSibling: nil, head: 1, tail: .cap)
	XCTAssertEqual(NeverEmptyTrie(unify: nil, with: oneValueNode), oneValueNode)
	XCTAssertEqual(NeverEmptyTrie(unify: oneValueNode, with: nil), oneValueNode)

	let oneOrEmptyNode = NeverEmptyTrie.branch(previousSibling: .cap, head: 1, tail: .cap)
	XCTAssertEqual(NeverEmptyTrie(unify: onlyEmptySequence, with: oneValueNode), oneOrEmptyNode)
	XCTAssertEqual(NeverEmptyTrie(unify: oneValueNode, with: onlyEmptySequence), oneOrEmptyNode)

	XCTAssertEqual(NeverEmptyTrie(unify: oneValueNode, with: oneValueNode), oneValueNode)

	let twoThreeNode = NeverEmptyTrie.branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap))
	let oneTwoThreeNode = NeverEmptyTrie.branch(previousSibling: oneValueNode, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap))
	XCTAssertEqual(NeverEmptyTrie(unify: twoThreeNode, with: oneValueNode), oneTwoThreeNode)
	XCTAssertEqual(NeverEmptyTrie(unify: oneValueNode, with: twoThreeNode), oneTwoThreeNode)

	let twoTwoNode = NeverEmptyTrie.branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: nil, head: 2, tail: .cap))
	let twoTwoThreeNode = NeverEmptyTrie.branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: .branch(previousSibling: nil, head: 2, tail: .cap), head: 3, tail: .cap))
	XCTAssertEqual(NeverEmptyTrie(unify: twoThreeNode, with: twoTwoNode), twoTwoThreeNode)
	XCTAssertEqual(NeverEmptyTrie(unify: twoTwoNode, with: twoThreeNode), twoTwoThreeNode)
	}

	// Test set intersection
	func testIntersection() {
	let onlyEmptySequence = NeverEmptyTrie<Int>.cap
	XCTAssertNil(NeverEmptyTrie<Int>(intersect: nil, with: nil))
	XCTAssertNil(NeverEmptyTrie(intersect: nil, with: onlyEmptySequence))
	XCTAssertNil(NeverEmptyTrie(intersect: onlyEmptySequence, with: nil))

	XCTAssertEqual(NeverEmptyTrie(intersect: onlyEmptySequence, with: onlyEmptySequence), onlyEmptySequence)

	let oneValueNode = NeverEmptyTrie.branch(previousSibling: nil, head: 1, tail: .cap)
	XCTAssertNil(NeverEmptyTrie(intersect: onlyEmptySequence, with: oneValueNode))
	XCTAssertNil(NeverEmptyTrie(intersect: oneValueNode, with: onlyEmptySequence))

	XCTAssertEqual(NeverEmptyTrie(intersect: oneValueNode, with: oneValueNode), oneValueNode)

	let oneOrEmptyNode = NeverEmptyTrie.branch(previousSibling: .cap, head: 1, tail: .cap)
	XCTAssertEqual(NeverEmptyTrie(intersect: onlyEmptySequence, with: oneOrEmptyNode), onlyEmptySequence)
	XCTAssertEqual(NeverEmptyTrie(intersect: oneOrEmptyNode, with: onlyEmptySequence), onlyEmptySequence)
	XCTAssertEqual(NeverEmptyTrie(intersect: oneValueNode, with: oneOrEmptyNode), oneValueNode)
	XCTAssertEqual(NeverEmptyTrie(intersect: oneOrEmptyNode, with: oneValueNode), oneValueNode)

	let oneTwoThreeNode = NeverEmptyTrie.branch(previousSibling: oneValueNode, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap))
	XCTAssertEqual(NeverEmptyTrie(intersect: oneTwoThreeNode, with: oneOrEmptyNode), oneValueNode)
	XCTAssertEqual(NeverEmptyTrie(intersect: oneOrEmptyNode, with: oneTwoThreeNode), oneValueNode)

	let twoThreeNode = NeverEmptyTrie.branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap))
	let twoTwoNode = NeverEmptyTrie.branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: nil, head: 2, tail: .cap))
	XCTAssertNil(NeverEmptyTrie(intersect: twoTwoNode, with: twoThreeNode))
	}

	// Test set symmetric-difference
	func testSymmetricDifference() {
	let onlyEmptySequence = NeverEmptyTrie<Int>.cap
	XCTAssertNil(NeverEmptyTrie<Int>(antiIntersect: nil, with: nil))
	XCTAssertEqual(NeverEmptyTrie(antiIntersect: nil, with: onlyEmptySequence), onlyEmptySequence)
	XCTAssertEqual(NeverEmptyTrie(antiIntersect: onlyEmptySequence, with: nil), onlyEmptySequence)

	XCTAssertNil(NeverEmptyTrie(antiIntersect: onlyEmptySequence, with: onlyEmptySequence))

	let oneValueNode = NeverEmptyTrie.branch(previousSibling: nil, head: 1, tail: .cap)
	let oneOrEmptyNode = NeverEmptyTrie.branch(previousSibling: .cap, head: 1, tail: .cap)
	XCTAssertEqual(NeverEmptyTrie(antiIntersect: onlyEmptySequence, with: oneValueNode), oneOrEmptyNode)
	XCTAssertEqual(NeverEmptyTrie(antiIntersect: oneValueNode, with: onlyEmptySequence), oneOrEmptyNode)

	let twoThreeNode = NeverEmptyTrie.branch(previousSibling: nil, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap))
	let oneTwoThreeNode = NeverEmptyTrie.branch(previousSibling: oneValueNode, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap))
	let oneTwoThreeEmptyNode = NeverEmptyTrie.branch(previousSibling: oneOrEmptyNode, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap))
	XCTAssertEqual(NeverEmptyTrie(antiIntersect: onlyEmptySequence, with: oneTwoThreeNode), oneTwoThreeEmptyNode)
	XCTAssertEqual(NeverEmptyTrie(antiIntersect: oneTwoThreeNode, with: onlyEmptySequence), oneTwoThreeEmptyNode)

	XCTAssertEqual(NeverEmptyTrie(antiIntersect: oneValueNode, with: oneTwoThreeNode), twoThreeNode)
	XCTAssertEqual(NeverEmptyTrie(antiIntersect: oneTwoThreeNode, with: oneValueNode), twoThreeNode)

	let oneTwoTwoThreeFourNode = NeverEmptyTrie.branch(previousSibling: oneValueNode, head: 2, tail: .branch(previousSibling: .branch(previousSibling: .branch(previousSibling: .cap, head: 2, tail: .cap), head: 3, tail: .cap), head: 4, tail: .cap))
	let emptyTwoThreeNode = NeverEmptyTrie.branch(previousSibling: .cap, head: 2, tail: .branch(previousSibling: nil, head: 3, tail: .cap))
	let emptyOneTwoTwoFourNode = NeverEmptyTrie.branch(previousSibling: .branch(previousSibling: .cap, head: 1, tail: .cap), head: 2, tail: .branch(previousSibling: .branch(previousSibling: .cap, head: 2, tail: .cap), head: 4, tail: .cap))
	XCTAssertEqual(NeverEmptyTrie(antiIntersect: oneTwoTwoThreeFourNode, with: emptyTwoThreeNode), emptyOneTwoTwoFourNode)
	XCTAssertEqual(NeverEmptyTrie(antiIntersect: emptyTwoThreeNode, with: oneTwoTwoThreeFourNode), emptyOneTwoTwoFourNode)
	}

	static var allTests = [
	("testInvariantCheck", testInvariantCheck),
	("testSerialization", testSerialization),

	("testListConversion", testListConversion),
	("testContains", testContains),
	("testInsertion", testInsertion),
	("testRemoval", testRemoval),
	("testFirstLast", testFirstLast),

	("testUnion", testUnion),
	("testIntersection", testIntersection),
	("testSymmetricDifference", testSymmetricDifference),
	]

	}