GRASS Programmer's Manual
6.4.2(2012)
Main Page
Related Pages
Namespaces
Data Structures
Files
File List
Globals
All
Data Structures
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Macros
Pages
tree.h
Go to the documentation of this file.
1
/* LIBDGL -- a Directed Graph Library implementation
2
* Copyright (C) 2002 Roberto Micarelli
3
*
4
* This program is free software; you can redistribute it and/or modify
5
* it under the terms of the GNU General Public License as published by
6
* the Free Software Foundation; either version 2 of the License, or
7
* (at your option) any later version.
8
*
9
* This program is distributed in the hope that it will be useful,
10
* but WITHOUT ANY WARRANTY; without even the implied warranty of
11
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12
* GNU General Public License for more details.
13
*
14
* You should have received a copy of the GNU General Public License
15
* along with this program; if not, write to the Free Software
16
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
*/
18
19
/* best view tabstop=4
20
*/
21
22
#ifndef _DGL_TREE_H_
23
#define _DGL_TREE_H_
24
25
#include "
avl.h
"
26
#include "
tavl.h
"
27
28
29
#define USE_THREADED_AVL
30
31
#if defined(USE_THREADED_AVL)
32
#define avl_table tavl_table
33
#define avl_traverser tavl_traverser
34
#define avl_create tavl_create
35
#define avl_copy tavl_copy
36
#define avl_destroy tavl_destroy
37
#define avl_probe tavl_probe
38
#define avl_insert tavl_insert
39
#define avl_replace tavl_replace
40
#define avl_delete tavl_delete
41
#define avl_find tavl_find
42
#define avl_assert_insert tavl_assert_insert
43
#define avl_assert_delete tavl_assert_delete
44
#define avl_t_init tavl_t_init
45
#define avl_t_first tavl_t_first
46
#define avl_t_last tavl_t_last
47
#define avl_t_find tavl_t_find
48
#define avl_t_insert tavl_t_insert
49
#define avl_t_copy tavl_t_copy
50
#define avl_t_next tavl_t_next
51
#define avl_t_prev tavl_t_prev
52
#define avl_t_cur tavl_t_cur
53
#define avl_t_replace tavl_t_replace
54
#endif
55
56
57
extern
void
*
dglTreeGetAllocator
();
58
59
/*
60
* Define a node as it is hosted in pNodeTree
61
*/
62
typedef
struct
_dglTreeNode
63
{
64
long
nKey
;
65
void
*
pv
;
66
void
*
pv2
;
67
}
dglTreeNode_s
;
68
extern
dglTreeNode_s
*
dglTreeNodeAlloc
();
69
extern
void
dglTreeNodeCancel
(
void
*pvNode,
void
*pvParam);
70
extern
int
dglTreeNodeCompare
(
const
void
*pvNodeA,
const
void
*pvNodeB,
71
void
*pvParam);
72
extern
dglTreeNode_s
*
dglTreeNodeAdd
(
void
*pvAVL,
dglInt32_t
nKey);
73
74
75
/*
76
* Define a version-2 node as it is hosted in pNodeTree
77
*/
78
typedef
struct
_dglTreeNode2
79
{
80
long
nKey
;
81
void
*
pv
;
82
void
*
pv2
;
83
void
*
pv3
;
84
}
dglTreeNode2_s
;
85
extern
dglTreeNode2_s
*
dglTreeNode2Alloc
();
86
extern
void
dglTreeNode2Cancel
(
void
*pvNode,
void
*pvParam);
87
extern
int
dglTreeNode2Compare
(
const
void
*pvNodeA,
const
void
*pvNodeB,
88
void
*pvParam);
89
extern
dglTreeNode2_s
*
dglTreeNode2Add
(
void
*pvAVL,
dglInt32_t
nKey);
90
91
92
/*
93
* Define a edge as it is hosted in pEdgeTree
94
*/
95
typedef
struct
_dglTreeEdge
96
{
97
dglInt32_t
nKey
;
98
void
*
pv
;
99
}
dglTreeEdge_s
;
100
extern
dglTreeEdge_s
*
dglTreeEdgeAlloc
();
101
extern
void
dglTreeEdgeCancel
(
void
*pvEdge,
void
*pvParam);
102
extern
int
dglTreeEdgeCompare
(
const
void
*pvEdgeA,
const
void
*pvEdgeB,
103
void
*pvParam);
104
extern
dglTreeEdge_s
*
dglTreeEdgeAdd
(
void
*pvAVL,
dglInt32_t
nKey);
105
106
107
/*
108
* Define a dummy entry to 'touch' selected item with a dglInt32_t key
109
* i.e. used to mark visited nodes in a greedy or tree-growing algorithm
110
*/
111
typedef
struct
_dglTreeTouchI32
112
{
113
dglInt32_t
nKey
;
114
}
dglTreeTouchI32_s
;
115
extern
dglTreeTouchI32_s
*
dglTreeTouchI32Alloc
();
116
extern
void
dglTreeTouchI32Cancel
(
void
*pvTouchI32,
void
*pvParam);
117
extern
int
dglTreeTouchI32Compare
(
const
void
*pvTouchI32A,
118
const
void
*pvTouchI32B,
void
*pvParam);
119
extern
dglTreeTouchI32_s
*
dglTreeTouchI32Add
(
void
*pvAVL,
dglInt32_t
nKey);
120
121
122
/*
123
* Define a entry to mantain a predecessor/distance network in shortest-path computation
124
*/
125
typedef
struct
_dglTreePredist
126
{
127
dglInt32_t
nKey
;
128
dglInt32_t
nFrom
;
129
dglInt32_t
nDistance
;
130
dglInt32_t
nCost
;
131
dglInt32_t
*
pnEdge
;
132
dglByte_t
bFlags
;
133
}
dglTreePredist_s
;
134
extern
dglTreePredist_s
*
dglTreePredistAlloc
();
135
extern
void
dglTreePredistCancel
(
void
*pvPredist,
void
*pvParam);
136
extern
int
dglTreePredistCompare
(
const
void
*pvPredistA,
137
const
void
*pvPredistB,
void
*pvParam);
138
extern
dglTreePredist_s
*
dglTreePredistAdd
(
void
*pvAVL,
dglInt32_t
nKey);
139
140
141
/*
142
* 32bit-key Node Prioritizer
143
*/
144
typedef
struct
_dglTreeNodePri32
145
{
146
dglInt32_t
nKey
;
147
dglInt32_t
cnVal
;
148
dglInt32_t
*
pnVal
;
149
}
dglTreeNodePri32_s
;
150
extern
dglTreeNodePri32_s
*
dglTreeNodePri32Alloc
();
151
extern
void
dglTreeNodePri32Cancel
(
void
*pvNodePri32,
void
*pvParam);
152
extern
int
dglTreeNodePri32Compare
(
const
void
*pvNodePri32A,
153
const
void
*pvNodePri32B,
void
*pvParam);
154
extern
dglTreeNodePri32_s
*
dglTreeNodePri32Add
(
void
*pvAVL,
dglInt32_t
nKey);
155
156
157
/*
158
* 32bit-key Edge Prioritizer
159
*/
160
typedef
struct
_dglTreeEdgePri32
161
{
162
dglInt32_t
nKey
;
163
dglInt32_t
cnData
;
164
dglInt32_t
*
pnData
;
165
}
dglTreeEdgePri32_s
;
166
extern
dglTreeEdgePri32_s
*
dglTreeEdgePri32Alloc
();
167
extern
void
dglTreeEdgePri32Cancel
(
void
*pvEdgePri32,
void
*pvParam);
168
extern
int
dglTreeEdgePri32Compare
(
const
void
*pvEdgePri32A,
169
const
void
*pvEdgePri32B,
void
*pvParam);
170
extern
dglTreeEdgePri32_s
*
dglTreeEdgePri32Add
(
void
*pvAVL,
dglInt32_t
nKey);
171
172
173
#endif
lib
vector
dglib
tree.h
Generated on Sun Mar 16 2014 05:07:49 for GRASS Programmer's Manual by
1.8.1.2