1############################################################################# 2## 3## orb package 4## avltree.gd 5## Juergen Mueller 6## Max Neunhoeffer 7## Felix Noeske 8## 9## Copyright 2009-2009 by the authors. 10## This file is free software, see license information at the end. 11## 12## Declaration stuff for AVL trees in GAP. 13## 14## adding, removing and finding in O(log n), n is number of nodes 15## 16## see Knuth: "The Art of Computer Programming" for algorithms 17## 18############################################################################# 19 20BindGlobal( "AVLTreeFamily", NewFamily("AVLTreeFamily") ); 21DeclareCategory( "IsAVLTree", IsPositionalObjectRep ); 22DeclareRepresentation( "IsAVLTreeFlatRep", IsAVLTree, [] ); 23BindGlobal( "AVLTreeType", NewType(AVLTreeFamily,IsAVLTreeFlatRep) ); 24BindGlobal( "AVLTreeTypeMutable", NewType(AVLTreeFamily, 25 IsAVLTreeFlatRep and IsMutable) ); 26 27# All of the following functions exist on the GAP level and some of 28# them on the C level for speedup. The GAP versions have "_GAP" appended 29# to their name, the C versions have "_C" appended. The version with 30# nothing appended is the one to be used, it is assigned to the C 31# version if it is there and otherwise to the GAP version. 32 33DeclareGlobalFunction( "AVLCmp" ); 34DeclareGlobalFunction( "AVLTree" ); 35DeclareGlobalFunction( "AVLNewNode" ); 36DeclareGlobalFunction( "AVLFreeNode" ); 37DeclareGlobalFunction( "AVLData" ); 38DeclareGlobalFunction( "AVLSetData" ); 39DeclareGlobalFunction( "AVLLeft" ); 40DeclareGlobalFunction( "AVLSetLeft" ); 41DeclareGlobalFunction( "AVLRight" ); 42DeclareGlobalFunction( "AVLSetRight" ); 43DeclareGlobalFunction( "AVLRank" ); 44DeclareGlobalFunction( "AVLSetRank" ); 45DeclareGlobalFunction( "AVLBalFactor" ); 46DeclareGlobalFunction( "AVLSetBalFactor" ); 47DeclareGlobalFunction( "AVLValue" ); 48DeclareGlobalFunction( "AVLSetValue" ); 49DeclareGlobalFunction( "AVLFind" ); 50DeclareGlobalFunction( "AVLFindIndex" ); 51DeclareGlobalFunction( "AVLLookup" ); 52DeclareGlobalFunction( "AVLIndex" ); 53DeclareGlobalFunction( "AVLIndexFind" ); 54DeclareGlobalFunction( "AVLRebalance" ); 55DeclareGlobalFunction( "AVLIndexLookup" ); 56DeclareGlobalFunction( "AVLAdd" ); 57DeclareGlobalFunction( "AVLIndexAdd" ); 58DeclareGlobalFunction( "AVLDelete" ); 59DeclareGlobalFunction( "AVLIndexDelete" ); 60DeclareGlobalFunction( "AVLToList" ); 61 62