Skip to content

Instantly share code, notes, and snippets.

@flyinghyrax
Created August 13, 2015 15:48
Show Gist options
  • Save flyinghyrax/414b5bfb2a5eb69ad0c5 to your computer and use it in GitHub Desktop.
Save flyinghyrax/414b5bfb2a5eb69ad0c5 to your computer and use it in GitHub Desktop.
Started indexing code and never finished
import Foundation
// helper protocols for adding things to the index
protocol Identifiable {
var id: Int { get }
}
protocol Tagged {
var tags: Set<Tag> { get }
}
protocol Indexable: Identifiable, Tagged {}
// This should map IDs to tags, and tags to IDs. That's it!
class SimpleIndex {
// This is only really used for removing tags... by keeping track of
// which tags an Id is associated with (in that direction), we can remove
// from the index without traversing the entire InvertedIndex
typealias ForwardIndex = Dictionary<Int, Set<Tag>>
// The important one: given some tag, provides the ID's matching that tag
typealias InvertedIndex = Dictionary<Tag, Set<Int>>
private var theDex: InvertedIndex = InvertedIndex()
private var forwardDex: ForwardIndex = ForwardIndex()
/// adds to the index
func add(id id: Int, tags: Set<Tag>) {
// first, record the ID => Tags mapping
addToForward(id: id, tags: tags)
// then, record the Tag => ID mapping
addToInverse(id: id, tags: tags)
}
private func addToForward(id id: Int, tags: Set<Tag>) {
if !forwardDex.keys.contains(id) {
// we've not added tags for this ID to the index before
forwardDex[id] = Set<Tag>()
}
// we might be adding tags to an existing set of tags
forwardDex[id]!.unionInPlace(tags)
}
private func addToInverse(id id: Int, tags: Set<Tag>) {
for tag in tags {
if !theDex.keys.contains(tag) {
theDex[tag] = Set<Int>()
}
theDex[tag]?.insert(id)
}
}
/**
Adds a sequence of Indexable things to the index. Note that the index does not preserve
any information about the thing that was added, it only uses its ID and tags.
- parameter things: `SequenceType` of `Indexable`s
*/
func add<T: Indexable, S: SequenceType where S.Generator.Element == T>(things: S) {
for thing in things {
add(id: thing.id, tags: thing.tags)
}
}
/**
Removes an ID from the index.
I wish this were simpler.
- parameter id: ID to remove from index
*/
func remove(id id: Int) {
// check that we have this ID in the index
if forwardDex.keys.contains(id) {
// go through each of the tags associated with that ID
for tag in forwardDex[id]! {
// if the inverted index contains a set of IDs for that tag...
if theDex.keys.contains(tag) {
// remove the ID fromt that set
theDex[tag]!.remove(id)
// if that was the only ID in the set, then the set is now empty
if theDex[tag]!.isEmpty {
// and we can remove the entire entry from the inverted index
theDex.removeValueForKey(tag)
}
}
}
// now remove the ID and tags from the forward index
forwardDex.removeValueForKey(id)
}
}
// never finished search methods
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment