Skip to content

Instantly share code, notes, and snippets.

@loromits
Last active September 11, 2017 10:06
Show Gist options
  • Save loromits/78bce21f1d605c255d29c8e7572ed42f to your computer and use it in GitHub Desktop.
Save loromits/78bce21f1d605c255d29c8e7572ed42f to your computer and use it in GitHub Desktop.
Simple Stack data structure implementation in Swift
struct Stack<Element> {
fileprivate class Node {
let value: Element
var previousNode: Node?
init(_ value: Element, previousNode: Node?) {
self.value = value
self.previousNode = previousNode
}
}
fileprivate var topNode: Node?
init() {}
init<S: Sequence>(_ s: S) where S.Iterator.Element == Element {
for entry in s {
push(entry)
}
}
mutating func rotateLeft(_ count: Int) {
guard count > 0 else { return }
var cnt = count
var insertionCursor = topNode
while cnt != 0 && insertionCursor?.previousNode != nil {
cnt -= 1
insertionCursor = insertionCursor?.previousNode
}
let tailNode = insertionCursor?.previousNode
insertionCursor?.previousNode = topNode
topNode = topNode?.previousNode
insertionCursor?.previousNode?.previousNode = tailNode
}
mutating func swap() {
rotateLeft(1)
}
mutating func rotateRight(_ count: Int) {
guard count > 0 else { return }
var cnt = count - 1
var extractionParentCursor = topNode
while cnt != 0 && extractionParentCursor?.previousNode?.previousNode != nil {
cnt -= 1
extractionParentCursor = extractionParentCursor?.previousNode
}
let extractedNode = extractionParentCursor?.previousNode
let tailNode = extractedNode?.previousNode
extractedNode?.previousNode = topNode?.previousNode
extractionParentCursor?.previousNode = tailNode
topNode = extractedNode
}
mutating func duplicate() {
if let topValue = topNode?.value {
topNode = Node(topValue, previousNode: topNode)
}
}
mutating func push(_ value: Element) {
topNode = Node(value, previousNode: topNode)
}
mutating func pop() -> Element? {
let oldNode = topNode
topNode = oldNode?.previousNode
return oldNode?.value
}
func peek() -> Element? {
return topNode?.value
}
}
extension Stack where Element: Equatable {
static func ==(lhs: Stack, rhs: Stack) -> Bool {
var (lhsCursor, rhsCursor) = (lhs.topNode, rhs.topNode)
while let lhsValue = lhsCursor?.value,
let rhsValue = rhsCursor?.value,
lhsValue == rhsValue {
(lhsCursor, rhsCursor) = (lhsCursor?.previousNode, rhsCursor?.previousNode)
}
return lhsCursor == nil && rhsCursor == nil
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment