Skip to content

Instantly share code, notes, and snippets.

@ylegall
Last active December 21, 2015 15:19
Show Gist options
  • Save ylegall/6326083 to your computer and use it in GitHub Desktop.
Save ylegall/6326083 to your computer and use it in GitHub Desktop.
A data structure with: O(1) random access, O(1) insertion, and O(1) deletion.
/**
* data structure with:
* O(1) random access
* O(1) insertion
* O(1) deletion
* O(1) containment
*/
class RandomAccessSet(T)
{
private {
size_t size;
T[] array;
size_t[T] indexMap;
}
this() {
size = 0;
array.length = 1;
}
auto add(T item) {
if (item in indexMap) return false;
indexMap[item] = size;
if (size == array.length) {
array.length *= 2;
}
array[size++] = item;
return true;
}
auto remove(T item) {
if (item !in indexMap) return false;
auto index = indexMap[item];
--size;
swap(index, size);
indexMap[array[index]] = index;
return indexMap.remove(item);
}
private auto swap(size_t a, size_t b) {
auto tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
bool contains(T item) {
return (item in indexMap) != null;
}
T getRandom() {
import std.random;
auto i = uniform(0, size);
return array[i];
}
int opApply(int delegate(ref T) dg) {
int result = 0;
foreach (i; 0 .. size) {
result = dg(array[i]);
if (result) break;
}
return result;
}
override
string toString() {
import std.conv;
return text(array);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment