Protocol Deque is written for a struct, but DequeDoubleLinkedList is written as a class. The protocol appears as a struct in the 4th edition of the online book and the github repo.
protocol Deque {
associatedtype Element
var isEmpty: Bool { get }
func peek(from direction: Direction) -> Element?
mutating func enqueue(_ element: Element,
to direction: Direction) -> Bool
mutating func dequeue(from direction: Direction) -> Element?
}
Two methods are list as mutating.
mutating func enqueue(_ element: Element, to direction: Direction) → Bool
mutating func dequeue(from direction: Direction) → Element?
I image there was an intention to transition from class to struct. Or not.
I changed DequeDoubleLinkedList to a struct. I made minor changes to get value semantics working for the struct. Changes to DoubleLinkedList.swift:
lines 42 and 57 become
mutating func prepend(_ value: T) {
mutating func append(_ value: T) {
I modified remove(node: ) and adapted copyNodesIfNeeded() from copyNodes() in the book to work with DoubleLinkedList.
mutating func remove(_ node: Node<T>) -> T {
copyNodesIfNeeded()
let headOrTail = node.next == nil ? self.last : self.first
let prev = headOrTail?.previous
let next = headOrTail?.next
if let prev = prev {
prev.next = nil
tail = prev
} else {
head = next
}
node.previous = nil
node.next = nil
return node.value
}
private mutating func copyNodesIfNeeded() {
guard !isKnownUniquelyReferenced(&head) else { return }
guard var oldNode = head else { return }
head = Node(value: oldNode.value)
var newNode = head
newNode?.previous = nil
while let nextOldNode = oldNode.next {
let newNodeCopy = Node(value: nextOldNode.value)
newNode!.next = newNodeCopy
newNodeCopy.previous = newNode
newNode = newNodeCopy
oldNode = nextOldNode
}
tail = newNode
}
Change to file Contents.swift, from the repo. Make DequeDoubleLinkedList a struct and make to methods mutating.
line 39
struct DequeDoubleLinkedList<Element>: Deque {
line 57
mutating func enqueue(_ element: Element, to direction: Direction) -> Bool {
line 67
mutating func dequeue(from direction: Direction) -> Element? {
Small test run. Create a new DequeDoubleLinkedList from an existing one.
var deque = DequeDoubleLinkedList()
deque.enqueue(1, to: .back)
deque.enqueue(2, to: .back)
deque.enqueue(3, to: .back)
deque.enqueue(4, to: .back)
var deque2 = deque
print(“\nCreate deque2 from deque”)
print(deque)
print(deque2)
print(“\nEnqueue to front”)
deque.enqueue(5, to: .front)
print(deque)
print(deque2)
print(“\nDequeue from back”)
deque.dequeue(from: .back)
print(deque)
print(deque2)
print(“\nDequeue duque2 from back”)
deque2.dequeue(from: .back)
print(deque)
print(deque2)