Skip to content

Instantly share code, notes, and snippets.

@CTMacUser CTMacUser/LinkedList.swift Secret
Last active Jun 3, 2019

Embed
What would you like to do?
//
// 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),
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.