Last active
August 23, 2019 04:41
-
-
Save bmitchelmore/154bfa8af44de79aca7bf0681af5075e to your computer and use it in GitHub Desktop.
Constant time OrderedSet
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
struct OrderedSet<T: Hashable> { | |
private class Link { | |
var previous: Link? | |
var next: Link? | |
var value: T | |
init(value: T) { | |
self.value = value | |
} | |
} | |
private var pos : [T:Link] = [:] | |
private var head : Link? | |
private var tail : Link? | |
func contains(value: T) -> Bool { | |
return pos[value] != nil | |
} | |
mutating func add(value: T) { | |
if pos[value] == nil { | |
let link = Link(value: value) | |
if let head = self.head { | |
link.next = head | |
head.previous = link | |
self.head = link | |
} else { | |
self.head = link; | |
} | |
if self.tail == nil { | |
self.tail = link | |
} | |
pos[value] = link | |
} | |
} | |
mutating func remove(value: T) { | |
if let link = pos[value] { | |
if link === self.head && link === self.tail { | |
self.head = nil | |
self.tail = nil | |
} else if link === self.head { | |
link.next?.previous = nil | |
self.head = link.next | |
} else if link === self.tail { | |
link.previous?.next = nil | |
self.tail = link.previous | |
} else { | |
link.previous?.next = link.next | |
link.next?.previous = link.previous | |
} | |
} | |
pos[value] = nil | |
} | |
var count : Int { | |
get { | |
return pos.count | |
} | |
} | |
var array : [T] { | |
get { | |
var array : [T] = []; | |
var link = tail | |
while link != nil { | |
guard let current = link else { break } | |
array.append(current.value) | |
link = current.previous | |
} | |
return array | |
} | |
} | |
init(values: [T] = []) { | |
for value in values { | |
add(value: value) | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Using a bidirectional linked list to keep track of order and a dictionary to provide a uniqueness test along with constant time access to arbitrary locations in the linked list, we can have constant time insertion and deletion in an ordered set.