-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathxAVLTree.h.sh
executable file
·145 lines (128 loc) · 4.91 KB
/
xAVLTree.h.sh
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#!/bin/sh
#
# xAVLTree.h.sh: Header file generator for AVLTree library.
# Copyright (C) 1998, 2001, 2008 Michael H. Buselli
# This is version 0.1.5 (alpha).
#
# This library is free software; you can redistribute it and/or
# modify it under the terms of the GNU Library General Public
# License as published by the Free Software Foundation; either
# version 2 of the License, or (at your option) any later version.
#
# This library is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
# Library General Public License for more details.
#
# You should have received a copy of the GNU Library General Public
# License along with this library; if not, write to the Free
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
#
# The author of this library can be reached by email at <[email protected]>.
# The official web page for this product is:
# http://cosine.org/project/AVLTree/
#
# Replacement variables
x=`echo "$1" | tr '[A-Z]' '[a-z]'`
X=`echo "$1" | tr '[a-z]' '[A-Z]'`
cat <<__EOF__ | \
sed -e "/^----.* ${x}AVLbegin .*----\$/,/^----.* ${x}AVLend .*----\$/d" \
-e "/^++++ [^${x}]AVLbegin ++++\$/,/^++++ [^${x}]AVLend ++++\$/d" | \
grep -v '^---- .* ----$' | \
grep -v '^++++ .* ++++$'
/*
* ${x}AVLTree.h: Header file for ${x}AVLTrees.
* Copyright (C) 1998, 2001, 2008 Michael H. Buselli
* This is version 0.1.5 (alpha).
* This file is automatically generated from xAVLTree.h.sh.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public
* License along with this library; if not, write to the Free
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
* The author of this library can be reached by email at <[email protected]>.
* The official web page for this product is:
* http://cosine.org/project/AVLTree/
*/
#ifndef _${X}AVLTREE_H_
#define _${X}AVLTREE_H_
/* typedef the keytype */
++++ iAVLbegin ++++
typedef long iAVLKey;
/* Comparison function for integers is subtraction. */
#define iAVLKey_cmp(tree, a, b) ((a) - (b))
++++ iAVLend ++++
++++ zAVLbegin ++++
typedef const char *zAVLKey;
/* Comparison function for strings is strcmp(). */
#define zAVLKey_cmp(tree, a, b) (strcmp((a), (b)))
++++ zAVLend ++++
++++ gAVLbegin ++++
typedef const void *gAVLKey;
/*
* Comparison function type for gAVLTrees. It is important that for any
* A, B, C, and D objects that if AVLCompare(A, B) < 0, AVLCompare(B, C)
* < 0, and AVLCompare(A, D) == 0, then the following are also true:
* AVLCompare(A, C) < 0, AVLCompare(B, A) > 0, AVLCompare(D, A) == 0.
* This code cannot verify that the function supplied by the user has
* this property--this is the coder's responsibility--but the code will
* by default perform some sanity checks at the cost of performance.
* Turn the sanity checks off in avlconfig.h by defining AVL_NO_SANITY.
*/
typedef int (*gAVLCompare)(gAVLKey a, gAVLKey b);
/* Comparison function for gAVLTrees is defined by the user for each
* individual gAVLTree.
*/
#define gAVLKey_cmp(tree, a, b) (((tree)->cmp)((a), (b)))
++++ gAVLend ++++
typedef struct _${x}AVLNode {
${x}AVLKey key;
long depth;
long count;
void *item;
struct _${x}AVLNode *parent;
struct _${x}AVLNode *left;
struct _${x}AVLNode *right;
} ${x}AVLNode;
typedef struct {
${x}AVLNode *top;
long count;
${x}AVLKey (*getkey)(const void *item);
++++ gAVLbegin ++++
${x}AVLCompare cmp;
++++ gAVLend ++++
} ${x}AVLTree;
typedef struct {
const ${x}AVLTree *avltree;
const ${x}AVLNode *curnode;
} ${x}AVLCursor;
---- gAVLbegin ----
extern ${x}AVLTree *${x}AVLAllocTree (${x}AVLKey (*getkey)(void const *item));
---- gAVLend ----
++++ gAVLbegin ++++
extern ${x}AVLTree *${x}AVLAllocTree (${x}AVLKey (*getkey)(void const *item),
${x}AVLCompare cmp);
++++ gAVLend ++++
extern void ${x}AVLFreeTree\
(${x}AVLTree *avltree, void (freeitem)(void *item));
extern int ${x}AVLInsert (${x}AVLTree *avltree, void *item);
extern void *${x}AVLSearch (${x}AVLTree const *avltree, ${x}AVLKey key);
extern void *${x}AVLIndex (${x}AVLTree *avltree, long index);
extern int ${x}AVLDelete (${x}AVLTree *avltree, ${x}AVLKey key);
extern void *${x}AVLFirst\
(${x}AVLCursor *avlcursor, ${x}AVLTree const *avltree);
extern void *${x}AVLNext (${x}AVLCursor *avlcursor);
extern void *${x}AVLSeek\
(${x}AVLCursor *avlcursor, ${x}AVLTree *avltree, long index);
#endif
__EOF__