Created
July 8, 2019 20:49
-
-
Save davbeck/c469d7c74a9377146dd8db95281e112d to your computer and use it in GitHub Desktop.
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
/// The result of a binary search. | |
struct BinarySearchResult<Index> { | |
/// The index for the searched key. | |
/// | |
/// Use this to either insert new values while maintaining the sort order of the collection, or to lookup the value if `isPresent` is true. | |
var index: Index | |
/// Whether the key was found in the collection. | |
/// | |
/// When performing a binary search, even if the value is not found in the collection, an index is returned which can be used to insert a new item at the correct location. | |
var isPresent: Bool | |
} | |
extension Collection where Index: BinaryInteger { | |
/// Search for an index for a given key. | |
/// | |
/// Searches through a sorted collection to find the index where the item should be inserted, or already exists. | |
/// | |
/// This method assumes that the collection is already sorted by the given key. | |
func binarySearch<Key: Comparable>(for key: Key, using: (Element) -> Key) -> BinarySearchResult<Index> { | |
if self.endIndex == self.startIndex { | |
return BinarySearchResult(index: startIndex, isPresent: false) | |
} | |
let midIndex = startIndex + (endIndex - startIndex) / Index(exactly: 2)! | |
let midKey = using(self[midIndex]) | |
// Is the search key in the left half? | |
if midKey > key { | |
return self[startIndex..<midIndex].binarySearch(for: key, using: using) | |
// Is the search key in the right half? | |
} else if midKey < key { | |
return self[(midIndex + 1)..<endIndex].binarySearch(for: key, using: using) | |
// If we get here, then we've found the search key! | |
} else { | |
return BinarySearchResult(index: midIndex, isPresent: true) | |
} | |
} | |
} | |
extension Collection where Index: BinaryInteger, Element: Comparable { | |
/// Search for an index for a given element. | |
/// | |
/// Searches through a sorted collection to find the index where the item should be inserted, or already exists. | |
/// | |
/// This method assumes that the collection is already sorted. | |
func binarySearch(for key: Element) -> BinarySearchResult<Index> { | |
return self.binarySearch(for: key, using: { $0 }) | |
} | |
} | |
/// A cache that removes elements once they are no longer used (retained). | |
class ReferenceCache<Key: Hashable, Value: AnyObject> { | |
private struct Content { | |
var hash: Int | |
struct Entry { | |
var key: Key | |
var value: Value | |
} | |
var entries: [Entry] | |
} | |
private var content: [Content] = [] | |
subscript(key: Key) -> Value? { | |
get { | |
let result = content.binarySearch(for: key.hashValue, using: { $0.hash }) | |
guard result.isPresent else { return nil } | |
return content[result.index].entries.first(where: { $0.key == key })?.value | |
} | |
set(newValue) { | |
let result = content.binarySearch(for: key.hashValue, using: { $0.hash }) | |
let index = result.index | |
if result.isPresent { | |
if let newValue = newValue { | |
if let entryIndex = content[index].entries.firstIndex(where: { $0.key == key }) { | |
content[index].entries[entryIndex].value = newValue | |
} else { | |
content[index].entries.append(Content.Entry(key: key, value: newValue)) | |
} | |
} else { | |
content[index].entries.removeAll(where: { $0.key == key }) | |
if content[index].entries.isEmpty { | |
content.remove(at: index) | |
} | |
} | |
} else { | |
guard let newValue = newValue else { return } | |
content.insert(Content(hash: key.hashValue, entries: [Content.Entry(key: key, value: newValue)]), at: index) | |
} | |
} | |
} | |
func clean() { | |
for index in content.indices.reversed() { | |
for entryIndex in content[index].entries.indices.reversed() { | |
if isKnownUniquelyReferenced(&self.content[index].entries[entryIndex].value) { | |
self.content[index].entries.remove(at: entryIndex) | |
if self.content[index].entries.isEmpty { | |
self.content[index].entries.remove(at: entryIndex) | |
} | |
} | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment