Quelle  kary-heap.gi   Sprache: Shell

######################### BEGIN COPYRIGHT MESSAGE #########################
# GBNP - computing Gröbner bases of noncommutative polynomials
# Copyright 2001-2010 by Arjeh M. Cohen, Dié A.H. Gijsbers, Jan Willem
# Knopper, Chris Krook. Address: Discrete Algebra and Geometry (DAM) group
# at the Department of Mathematics and Computer Science of Eindhoven
# University of Technology.
#
# For acknowledgements see the manual. The manual can be found in several
# formats in the doc subdirectory of the GBNP distribution. The
# acknowledgements formatted as text can be found in the file chap0.txt.
#
# GBNP is free software; you can redistribute it and/or modify it under
# the terms of the Lesser GNU General Public License as published by the
# Free Software Foundation (FSF); either version 2.1 of the License, or
# (at your option) any later version. For details, see the file 'LGPL' in
# the doc subdirectory of the GBNP distribution or see the FSF's own site:
# https://www.gnu.org/licenses/lgpl.html
########################## END COPYRIGHT MESSAGE ##########################

# Add, Remove, ELM_LIST, Minimum,
# todo List, Set

InstallGlobalFunction(
THeapOT,function(todo, OT)
local   H,
        temp,temp2,sorted,i;

        temp:=LMonsNP(todo);
        sorted:=true;
        i:=1;
        while (i<Length(temp)) and (sorted) do
                sorted:=LtNP(temp[i],temp[i+1]);
                i:=i+1;
        od;
        if sorted=false then
                temp2:=StructuralCopy(temp);
                SortParallel(temp,todo,LtNP);
                GBNP.SortParallelOT(temp2,OT,LtNP);
        fi;

        H:=Objectify(THeapOTType, rec(list:=todo, OT:=OT));
        return H;
end);

InstallMethod(Add,
        "for 3-ary heaps with Tries",
        [ IsTHeapOT, IsObject ],
        function( heap, obj )
                #Print("add\n");
                #GBNP.THeapOTCheck(heap);
                Add(heap!.list, obj);
                GBNP.AddMonToTreePTSLR(obj[1][1],-1, heap!.OT, true);
                GBNP.THeapOTBalanceUp(heap, Length(heap!.list));
                #GBNP.THeapOTCheck(heap);
        end
);

InstallMethod(ELM_LIST,
        "for 3-ary heaps with Tries",
        [ IsTHeapOT, IsInt ],
        function( heap, pos )
                #Print("elm_list\n");
                #GBNP.THeapOTCheck(heap);
                return heap!.list[pos];
        end
);

InstallMethod(Length,
        "for 3-ary heaps with Tries",
        [ IsTHeapOT ],
        function( heap )
                return Length(heap!.list);
        end
);

InstallMethod(Remove,
        "for 3-ary heaps with Tries",
        [ IsTHeapOT, IsInt ],
        function( heap, pos)
        local   parent;
                #Print("remove\n");
                #GBNP.THeapOTCheck(heap);
                GBNP.THeapOTSwap(heap, pos, Length(heap!.list));
                GBNP.RemoveMonFromTreePTSLR(heap!.list[Length(heap!.list)][1][1],Length(heap!.list),heap!.OT,true);
                Remove(heap!.list); # remove last element
                parent:=GBNP.THeapOTGetParentIndex(pos);
                if (pos<=Length(heap)) then
                        if (pos>1) and (LtNP(heap!.list[pos][1][1],heap!.list[parent][1][1]))
                        then
                                GBNP.THeapOTBalanceUp(heap, pos);
                        else
                                GBNP.THeapOTBalanceDown(heap, pos);
                        fi;
                fi;
                #GBNP.THeapOTCheck(heap);
        end
);

InstallMethod(Replace,
        "for 3-ary heaps with Tries",
        [ IsTHeapOT, IsInt, IsObject ],
        function( heap, pos, obj)
        local   parent;
                #Print("replace\n");
                #GBNP.THeapOTCheck(heap);
                GBNP.RemoveMonFromTreePTSLR(heap!.list[pos][1][1],pos,heap!.OT,true);
                GBNP.AddMonToTreePTSLR(obj[1][1],pos,heap!.OT,true);
                heap!.list[pos]:=obj;

                parent:=GBNP.THeapOTGetParentIndex(pos);
                if (pos>1) and
                        LtNP(heap!.list[pos][1][1],heap!.list[parent][1][1])
                then
                        GBNP.THeapOTBalanceUp(heap, pos);
                else
                        GBNP.THeapOTBalanceDown(heap, pos);
                fi;
                #GBNP.THeapOTCheck(heap);
        end
);

InstallMethod(HeapMin,
        "for 3-ary heaps with Tries",
        [IsTHeapOT],
        function( heap )
                #Print("heapmin\n");
                #GBNP.THeapOTCheck(heap);
                return heap!.list[1];
        end
);

InstallMethod(IsTHeapOTEmpty,
        "for 3-ary heaps with Tries",
        [IsTHeapOT],
        function( heap )
                #Print("isempty\n");
                #GBNP.THeapOTCheck(heap);
                return Length(heap)=0;
        end
);

GBNP.THeapOTBalanceDown:=function(heap, index)
local   ready,
        child, children, minchild, minval;

        #Print("balance down\n");
        ready:=false;
        while not ready do
                ready:=true;
                children:=GBNP.THeapOTGetChildrenIndex(index);
                minchild:=0; minval:=heap!.list[index][1][1];
                for child in children do
                        if IsBound(heap!.list[child]) and LtNP(heap!.list[child][1][1],minval)
                        then
                                minval:=heap!.list[child][1][1];
                                minchild:=child;
                        fi;
                od;
                if minchild<>0 then
                        ready:=false;
                        GBNP.THeapOTSwap(heap, index, minchild);
                        index:=minchild;
                fi;
        od;
        #GBNP.THeapOTCheck(heap);
end;

GBNP.THeapOTBalanceUp:=function(heap, index)
local   ready,
        parent;

        #Print("balance up\n");
        ready:=false;
        while (index>1) and not ready do
                parent:=GBNP.THeapOTGetParentIndex(index);
                if LtNP(heap!.list[index][1][1],heap!.list[parent][1][1]) then
                        GBNP.THeapOTSwap(heap, index, parent);
                        index:=parent;
                else
                        ready:=true;
                fi;
        od;
        #GBNP.THeapOTCheck(heap);
end;

# 2 3 4 <- 1, 5 6 7 <- 2, 8 9 10 <-3
GBNP.THeapOTGetChildrenIndex:=function(index)
        return [3*index-1, 3*index, 3*index+1];
end;

# 2 3 4 -> 1, 5 6 7 -> 2, 8 9 10 ->3
GBNP.THeapOTGetParentIndex:=function(index)
        return (index+1 - ((index+1)mod 3))/3;
end;

GBNP.THeapOTSwap:=function(heap, index1, index2)
local   swap;
        if index1=index2 then
                return;
        fi;

        swap:=heap!.list[index1];
        heap!.list[index1]:=heap!.list[index2];
        heap!.list[index2]:=swap;
        swap:=heap!.OT.arr2tree[index1];
        heap!.OT.arr2tree[index1]:=heap!.OT.arr2tree[index2];
        heap!.OT.arr2tree[index2]:=swap;
        heap!.OT.tree2arr[heap!.OT.arr2tree[index1]]:=index1;
        heap!.OT.tree2arr[heap!.OT.arr2tree[index2]]:=index2;
end;

GBNP.THeapOTCheck:=function(heap)
local   ok,
        i,
        j;

        ok:=true;
        if Length(heap!.list)<>Length(heap!.OT.arr2tree) then
                Print("heap lengths not equal: ", Length(heap!.list), " vs ", Length(heap!.OT.arr2tree), "\n");
                ok:=false;
        fi;
        for i in [1..Length(heap!.OT.arr2tree)] do
                if heap!.OT.tree2arr[heap!.OT.arr2tree[i]]<>i then
                        if ok then
                                Print("arr2tree vs tree2arr link wrong at ",i, "\n");
                                ok:=false;
                        fi;
                fi;
        od;
        for i in [1..Length(heap!.list)] do
                j:=GBNP.OccurInLstT(heap!.list[i][1][1], heap!.OT)[1];
                if j=0 then
                        if ok then
                                Print("OT tree does not contain todo[", i,"]\n");
                                ok:=false;
                        fi;
                else
                        if (i<>j) and (heap!.list[i][1][1]<>heap!.list[j][1][1]) then
                                if ok then
                                        Print("OT tree gives wrong answer for [", i,"]\n");
                                        ok:=false;
                                fi;
                        fi;
                fi;
        od;

        for i in [1..Length(heap!.list)] do
                if LtNP(heap!.list[i][1][1],heap!.list[1][1][1]) then
                        if ok then
                                Print("Warning minimum not correct at position ", i, "\n",1/0);
                                ok:=false;
                        fi;
                fi;
        od;
        return ok;
end;