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