/usr/share/gap/lib/dicthf.gi

#############################################################################
##
#W  dicthf.gi                   GAP Library                   Gene Cooperman
#W                                                              Scott Murray
#W                                                          Alexander Hulpke
##
##
#Y  Copyright (C)  1999,  Lehrstuhl D für Mathematik,  RWTH Aachen,  Germany
#Y  (C) 1999 School Math and Comp. Sci., University of St Andrews, Scotland
#Y  Copyright (C) 2002 The GAP Group
##
##  This file contains some hashfunctions for objects in the GAP library.
##  This code was factored out from dict.gi to prevent cross dependencies
##  between dict.gi and the rest of the library.
##
#T  * This is all apparently completely undocumented.
#

InstallMethod(DenseIntKey,"default fail",true,[IsObject,IsObject],
        0,ReturnFail);

InstallMethod(SparseIntKey,"defaults to DenseIntKey",true,[IsObject,IsObject],
        0,DenseIntKey);

#############################################################################
##
#F  HashKeyBag(<obj>,<seed>,<skip>,<maxread>)
##
##  returns a hash key which is given by the bytes in the bag storing <obj>.
##  The result is reduced modulo $2^{28}$ (on 32 bit systems) resp. modulo
##  $2^{60}$ (on 64 bit systems) to obtain a small integer.
##  As some objects carry excess data in their bag, the first <skip> bytes
##  will be skipped and <maxread> bytes (a value of -1 represents infinity)
##  will be read at most. (The proper values for these numbers might depend on
##  the internal representation used as well as on the word length of the
##  machine on which {\GAP} is running and care has to be taken when using
##  `HashKeyBag' to ensure identical key values for equal objects.)
##
##  The values returned by `HashKeyBag' are not guaranteed to be portable
##  between different runs of {\GAP} and no reference to their absolute
##  values ought to be made.
##
BindGlobal("HashKeyBag",HASHKEY_BAG);

#############################################################################
##
#M  DenseIntKey(<objcol>)
##
InstallMethod(SparseIntKey,"for finite Gaussian row spaces",true,
    [ IsFFECollColl and IsGaussianRowSpace,IsObject ], 0,
function(m,v)
local f,n,bytelen,data,qq,i;
  f:=LeftActingDomain(m);
  n:=Size(f);
  if n=2 then
    bytelen:=QuoInt(Length(v),8);
    if bytelen<=8 then
      # short GF2
      return x->NumberFFVector(x,2);
    else
      # long GF2
      data:=[2*GAPInfo.BytesPerVariable,bytelen];
      return function(x)
             if not IsGF2VectorRep(x) then
                 Info(InfoWarning,1,"uncompressed vector");
                 x:=ShallowCopy(x);
                 ConvertToGF2VectorRep(x);
               fi;
               return HashKeyBag(x,101,data[1],data[2]);
             end;
    fi;
  elif n < 256 then
    qq:=n; # log
    i:=0;
    while qq<=256 do
        qq:=qq*n;
        i:=i+1;
    od;
    # i is now the number of field elements per byte
    bytelen := QuoInt(Length(v),i);
    if bytelen<=8 then
      # short 8-bit
      return x->NumberFFVector(x,n);
    else
      # long 8 bit
      data:=[3*GAPInfo.BytesPerVariable,bytelen];
      # must check type
      #return x->HashKeyBag(x,101,data[1],data[2]); 
      return function(x)
             if not Is8BitVectorRep(x) or
	       Q_VEC8BIT(x)<>n then
                 Info(InfoWarning,1,"un- or miscompressed vector");
                 x:=ShallowCopy(x);
                 ConvertToVectorRep(x,n);
               fi;
               return HashKeyBag(x,101,data[1],data[2]);
             end;

    fi;
  else
    # large field -- vector represented as plist.
    f:=AsSSortedList(f);
    return function(v)
           local x,sy,p;
              sy := 0;
              for x in v do
                p := Position(f, x);
# want to be quick: Assume no failures
#               if p = fail then
#                   Error("NumberFFVector: Vector not over specified field");
#               fi;
                sy := n*sy + (p-1);
              od;
            return sy;
           end;
  fi;
end);

SparseIntKeyVecListAndMatrix:=function(d,m)
local f,n,pow,fct;
  if IsList(d) and Length(d)>0 and IsMatrix(d[1]) then
    f:=DefaultScalarDomainOfMatrixList(d);
  else
    f:=DefaultScalarDomainOfMatrixList([m]);
  fi;

  fct:=SparseIntKey(f^Length(m[1]),m[1]);

  n:=Minimum(Size(f),11)^Minimum(12,QuoInt(Length(m[1]),2));
  #pow:=n^Length(m[1]);
  pow:=NextPrimeInt(n); # otherwise we produce huge numbers which take time
  return function(x)
          local i,gsy;
            gsy:=0;
            for i in x do
              gsy:=pow*gsy+fct(i);
            od;
            return gsy;
          end;
end;

InstallMethod(SparseIntKey,"for lists of vectors",true,
    [ IsFFECollColl,IsObject ], 0,
function(m,v)
local f,n;
if not (IsList(m) and IS_PLIST_REP(m) and ForAll(m,i->IsRowVector(i))) then
    TryNextMethod();
  fi;
  f:=DefaultFieldOfMatrix(m);
  return SparseIntKey(f^Length(v),v);
end);

InstallMethod(SparseIntKey,
  "for matrices over finite field vector spaces",true,
  [IsObject,IsFFECollColl and IsMatrix],0,
SparseIntKeyVecListAndMatrix);

InstallMethod(SparseIntKey,
  "for vector listsover finite field vector spaces",true,
  [IsObject,IsFFECollColl and IsList],0,
SparseIntKeyVecListAndMatrix);

#############################################################################
##
#M  SparseIntKey( <dom>, <key> ) for row spaces over finite fields
##
InstallMethod( SparseIntKey, "for row spaces over finite fields", true,
    [ IsObject,IsVectorSpace and IsRowSpace], 0,
function( key, dom )
  return function(key)
    local sz, n, ret, k,d;

    d:=LeftActingDomain( key );
    sz := Size(d);
    key := BasisVectors( CanonicalBasis( key ) );
    n := sz ^ Length( key[1] );
    ret := 1;
    for k in key do
        ret := ret * n + NumberFFVector( k, sz );
    od;
    return ret;
  end;
end );


InstallMethod(DenseIntKey,"integers",true,
  [IsObject,IsPosInt],0,
function(d,i)
  #T this function might cause problems if there are nonpositive integers
  #T used densly.
  return IdFunc;
end);

InstallMethod(SparseIntKey,"permutations, arbitrary domain",true,
  [IsObject,IsInternalRep and IsPerm],0,
function(d,pe)
  return function(p)
         local l;
           l:=LARGEST_MOVED_POINT_PERM(p);
           if IsPerm4Rep(p) then
             # is it a proper 4byte perm?
             if l>65536 then
               return HashKeyBag(p,255,0,4*l);
             else
               # the permutation does not require 4 bytes. Trim in two
               # byte representation (we need to do this to get consistent
               # hash keys, regardless of representation.)
               TRIM_PERM(p,l);
             fi;
            fi;
            # now we have a Perm2Rep:
            return HashKeyBag(p,255,0,2*l);
          end;
end);

#T Still to do: Permutation values based on base images: Method if the
#T domain given is a permgroup.

InstallMethod(SparseIntKey,"kernel pc group elements",true,
  [IsObject,
    IsElementFinitePolycyclicGroup and IsDataObjectRep and IsNBitsPcWordRep],0,
function(d,e)
local l,p;
  # we want to use an small shift to avoid cancellation due to similar bit
  # patterns in many bytes (the exponent values in most cases are very
  # small). The pcgs length is a reasonable small value-- otherwise we get
  # already overlap for the generators alone.
  p:=FamilyObj(e)!.DefiningPcgs;
  l:=NextPrimeInt(Length(p)+1);
  p:=Product(RelativeOrders(p));
  while Gcd(l,p)>1 do
    l:=NextPrimeInt(l);
  od;
  return e->HashKeyBag(e,l,DOUBLE_OBJLEN,-1);
end);

InstallMethod(SparseIntKey,"pcgs element lists: i.e. pcgs",true,
  [IsObject,IsElementFinitePolycyclicGroupCollection and IsList],0,
function(d,p)
local o,e;

  if IsPcgs(p) then
    o:=OneOfPcgs(p);
  else
    o:=One(p[1]);
  fi;

  e:=SparseIntKey(false,o); # element hash fun
  o:=DefiningPcgs(FamilyObj(o));
  o:=Product(RelativeOrders(o)); # order of group
  return function(x)
         local i,h;
           h:=0;
           for i in x do
             h:=h*o+e(i);
           od;
           return h;
         end;
end);

InstallMethod(SparseIntKey, "for an object and transformation", 
[IsObject, IsTransformation],
function(d, t)
  return x-> NumberTransformation(t, DegreeOfTransformation(t)); 
end);
gap-libs 4r8p6-2 / usr / share / gap / lib / dicthf.gi
