Skip to content

Instantly share code, notes, and snippets.

@bendmorris
Last active August 29, 2015 14:19
Show Gist options
  • Save bendmorris/0bc49c7a35773817ccd3 to your computer and use it in GitHub Desktop.
Save bendmorris/0bc49c7a35773817ccd3 to your computer and use it in GitHub Desktop.
MapArray - array with linked hashmap for fast existence/position lookups
class MapArray<T>
{
public static function main()
{
var x = new MapArray<Int>(new Map<Int, Int>());
for (i in 1 ... 100001)
x.push(i);
x.remove(5002);
trace(x.toString());
}
var _map:Map<T, Int>;
var _array:Array<T>;
public var length(get, never):Int;
function get_length():Int return _array.length;
@:arrayAccess public inline function get(i:Int) return _array[i];
@to public inline function toMap():Map<T, Int> return _map;
@to public inline function toArray():Array<T> return _array;
public function new(map:Map<T, Int>)
{
_map = map;
_array = new Array();
}
public function recalculate()
{
for (k in _map.keys()) _map.remove(k);
for (i in 0 ... _array.length)
{
_map[_array[i]] = i;
}
}
public function push(x:T):Int
{
_map[x] = _array.length;
return _array.push(x);
}
public function pop():Null<T>
{
var result = _array.pop();
if (result != null) recalculate();
return result;
}
public function indexOf(x:T):Null<Int>
{
var i:Null<Int> = _map[x];
if (i == null || _array[_map[x]] != x)
{
recalculate();
i = _map[x];
}
return i;
}
public inline function exists(x:T):Bool return _map.exists(x);
public function remove(x:T):Bool
{
if (_map.exists(x))
{
var i:Null<Int> = _map[x];
if (i != null && _array[i] != x)
{
i = _array.indexOf(x);
if (i == null) recalculate();
}
if (i != null)
{
_array.splice(i, 1);
recalculate();
return true;
}
}
return false;
}
public inline function toString() return _array.toString();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment