Created
August 13, 2015 15:48
-
-
Save flyinghyrax/414b5bfb2a5eb69ad0c5 to your computer and use it in GitHub Desktop.
Started indexing code and never finished
This file contains hidden or 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
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