|
##
## Datastructures: GAP package providing common datastructures.
##
## Copyright (C) 2015-2017 The datastructures team.
## For list of the team members, please refer to the COPYRIGHT file.
##
## This package is licensed under the GPL 2 or later, please refer
## to the COPYRIGHT.md and LICENSE files for details.
##
##
## Implementation of a hash map for GAP.
##
#! @Chapter Hashmaps
#! @Section API
InstallGlobalFunction(HashMap,
function(arg...)
local hashfunc, eqfunc, capacity, values, v, map;
values := [];
hashfunc := HashBasic;
eqfunc := \=;
capacity := 16;
if Length(arg) > 0 and IsList(arg[1]) then
values := Remove(arg, 1);
capacity := Maximum(capacity, Length(values));
fi;
if Length(arg) > 0 and IsFunction(arg[1]) then
hashfunc := Remove(arg, 1);
fi;
if Length(arg) > 0 and IsInt(arg[Length(arg)]) then
capacity := Remove(arg);
fi;
if Length(arg) = 1 and IsFunction(arg[1]) then
eqfunc := Remove(arg);
fi;
if Length(arg) > 0 then
Error("Invalid arguments");
fi;
map := DS_Hash_Create(hashfunc, eqfunc, capacity, false);
for v in values do
if Length(v) <> 2 then
Error("Invalid initial values");
fi;
map[v[1]] := v[2];
od;
return map;
end);
InstallMethod(PrintString, "for hashmaps",
[ IsHashMapRep ],
function(ht)
local v, first, string;
string := [];
Add(string, "HashMap([\>\>");
first := true;
for v in KeyValueIterator(ht) do
if first then
first := false;
else
Add(string, ",\< \>");
fi;
Add(string, PrintString(v));
od;
Add(string, "\<\<])");
return Concatenation(string);
end);
InstallMethod(String, "for hashmaps",
[ IsHashMapRep ],
function(ht)
local v, first, string;
string := [];
Add(string, "HashMap([");
first := true;
for v in KeyValueIterator(ht) do
if first then
first := false;
else
Add(string, ", ");
fi;
Add(string, String(v));
od;
Add(string, "])");
return Concatenation(string);
end);
#! @Description
#! List-style access for hashmaps.
#! @Arguments hashmap, object
InstallOtherMethod(\[\],
"for a hash map and a key",
[ IsHashMapRep, IsObject ],
DS_Hash_Value); # TODO: raise an error if key is not bound
#! @Description
#! List-style assignment for hashmaps.
#! @Arguments hashmap, object, object
InstallOtherMethod(\[\]\:\=,
"for a hash map, a key and a value",
[ IsHashMapRep, IsObject, IsObject ],
DS_Hash_SetValue);
#! @Description
#! Test whether a key is stored in the hashmap.
#! @Arguments object, hashmap
InstallOtherMethod( \in,
"for a hash map and a key",
[ IsObject, IsHashMapRep ],
{key, ht} -> DS_Hash_Contains(ht, key));
#! @Description
#! Test whether a key is stored in the hashmap.
#! @Arguments object, hashmap
InstallOtherMethod( IsBound\[\],
"for a hash map and a key",
[ IsHashMapRep, IsObject ],
DS_Hash_Contains);
#! @Description
#! Delete a key from a hashmap.
#! @Arguments object, hashmap
InstallOtherMethod( Unbind\[\],
"for a hash map and a key",
[ IsHashMapRep, IsObject ],
DS_Hash_Delete);
#! @Description
#! Determine the number of keys stored in a hashmap.
#! @Arguments hashmap
InstallOtherMethod( Size,
"for a hash map",
[ IsHashMapRep ],
ht -> DS_Hash_Used(ht));
#! @Description
#! Test whether a hashmap is empty.
#! @Arguments object, hashmap
InstallOtherMethod( IsEmpty,
"for a hash map",
[ IsHashMapRep ],
ht -> DS_Hash_Used(ht) = 0);
InstallMethod( Keys,
"for a hash map",
[ IsHashMapRep ],
function(ht)
local keys, k;
keys := [];
for k in ht![5] do
if k <> fail then Add(keys, k); fi;
od;
return keys;
end);
InstallMethod( Values,
"for a hash map",
[ IsHashMapRep ],
ht -> Compacted(ht![6]));
BindGlobal( "NextIterator_HashMap", function(iter)
local idx, next;
if iter!.next > Length(iter!.keys) then
Error("<iter> is exhausted");
fi;
# remember the result index
idx := iter!.next;
# find the next iterator
next := iter!.next + 1;
# skip to the next entry with a bound value
while next <= Length(iter!.keys) and not IsBound(iter!.values[next]) do
Assert(0, not IsBound(iter!.keys[next]) or iter!.keys[next] = fail);
next := next + 1;
od;
iter!.next := next;
# return value depends on the iterator type
if iter!.type = 1 then
return iter!.keys[idx];
elif iter!.type = 2 then
return iter!.values[idx];
else
return [iter!.keys[idx], iter!.values[idx]];
fi;
end);
BindGlobal( "MakeIterator_HashMap", function(ht, type)
local iter;
iter := rec(keys := ht![5],
values := ht![6],
next := PositionBound(~.values),
type := type);
iter.ShallowCopy := iter -> rec(keys := iter!.keys,
values := iter!.values,
next := iter!.next,
type := iter!.type);
iter.IsDoneIterator := iter -> iter!.next > Length(iter!.keys);
iter.NextIterator := NextIterator_HashMap;
return IteratorByFunctions( iter );
end);
InstallMethod( KeyIterator,
"for a hash set",
[ IsHashMapRep ],
ht -> MakeIterator_HashMap(ht, 1));
InstallMethod( ValueIterator,
"for a hash set",
[ IsHashMapRep ],
ht -> MakeIterator_HashMap(ht, 2));
InstallMethod( KeyValueIterator,
"for a hash set",
[ IsHashMapRep ],
ht -> MakeIterator_HashMap(ht, 3));
[ Dauer der Verarbeitung: 0.29 Sekunden
(vorverarbeitet)
]
|
