GRASS Programmer's Manual 6.4.1(2011)
|
00001 /* LIBDGL -- a Directed Graph Library implementation 00002 * Copyright (C) 2002 Roberto Micarelli 00003 * 00004 * This program is free software; you can redistribute it and/or modify 00005 * it under the terms of the GNU General Public License as published by 00006 * the Free Software Foundation; either version 2 of the License, or 00007 * (at your option) any later version. 00008 * 00009 * This program is distributed in the hope that it will be useful, 00010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 * GNU General Public License for more details. 00013 * 00014 * You should have received a copy of the GNU General Public License 00015 * along with this program; if not, write to the Free Software 00016 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 00017 */ 00018 00019 /* best view tabstop=4 00020 */ 00021 00022 #ifndef _DGL_TREE_H_ 00023 #define _DGL_TREE_H_ 00024 00025 #include "avl.h" 00026 #include "tavl.h" 00027 00028 00029 #define USE_THREADED_AVL 00030 00031 #if defined(USE_THREADED_AVL) 00032 #define avl_table tavl_table 00033 #define avl_traverser tavl_traverser 00034 #define avl_create tavl_create 00035 #define avl_copy tavl_copy 00036 #define avl_destroy tavl_destroy 00037 #define avl_probe tavl_probe 00038 #define avl_insert tavl_insert 00039 #define avl_replace tavl_replace 00040 #define avl_delete tavl_delete 00041 #define avl_find tavl_find 00042 #define avl_assert_insert tavl_assert_insert 00043 #define avl_assert_delete tavl_assert_delete 00044 #define avl_t_init tavl_t_init 00045 #define avl_t_first tavl_t_first 00046 #define avl_t_last tavl_t_last 00047 #define avl_t_find tavl_t_find 00048 #define avl_t_insert tavl_t_insert 00049 #define avl_t_copy tavl_t_copy 00050 #define avl_t_next tavl_t_next 00051 #define avl_t_prev tavl_t_prev 00052 #define avl_t_cur tavl_t_cur 00053 #define avl_t_replace tavl_t_replace 00054 #endif 00055 00056 00057 extern void *dglTreeGetAllocator(); 00058 00059 /* 00060 * Define a node as it is hosted in pNodeTree 00061 */ 00062 typedef struct _dglTreeNode 00063 { 00064 long nKey; 00065 void *pv; 00066 void *pv2; 00067 } dglTreeNode_s; 00068 extern dglTreeNode_s *dglTreeNodeAlloc(); 00069 extern void dglTreeNodeCancel(void *pvNode, void *pvParam); 00070 extern int dglTreeNodeCompare(const void *pvNodeA, const void *pvNodeB, 00071 void *pvParam); 00072 extern dglTreeNode_s *dglTreeNodeAdd(void *pvAVL, dglInt32_t nKey); 00073 00074 00075 /* 00076 * Define a version-2 node as it is hosted in pNodeTree 00077 */ 00078 typedef struct _dglTreeNode2 00079 { 00080 long nKey; 00081 void *pv; 00082 void *pv2; 00083 void *pv3; 00084 } dglTreeNode2_s; 00085 extern dglTreeNode2_s *dglTreeNode2Alloc(); 00086 extern void dglTreeNode2Cancel(void *pvNode, void *pvParam); 00087 extern int dglTreeNode2Compare(const void *pvNodeA, const void *pvNodeB, 00088 void *pvParam); 00089 extern dglTreeNode2_s *dglTreeNode2Add(void *pvAVL, dglInt32_t nKey); 00090 00091 00092 /* 00093 * Define a edge as it is hosted in pEdgeTree 00094 */ 00095 typedef struct _dglTreeEdge 00096 { 00097 dglInt32_t nKey; 00098 void *pv; 00099 } dglTreeEdge_s; 00100 extern dglTreeEdge_s *dglTreeEdgeAlloc(); 00101 extern void dglTreeEdgeCancel(void *pvEdge, void *pvParam); 00102 extern int dglTreeEdgeCompare(const void *pvEdgeA, const void *pvEdgeB, 00103 void *pvParam); 00104 extern dglTreeEdge_s *dglTreeEdgeAdd(void *pvAVL, dglInt32_t nKey); 00105 00106 00107 /* 00108 * Define a dummy entry to 'touch' selected item with a dglInt32_t key 00109 * i.e. used to mark visited nodes in a greedy or tree-growing algorithm 00110 */ 00111 typedef struct _dglTreeTouchI32 00112 { 00113 dglInt32_t nKey; 00114 } dglTreeTouchI32_s; 00115 extern dglTreeTouchI32_s *dglTreeTouchI32Alloc(); 00116 extern void dglTreeTouchI32Cancel(void *pvTouchI32, void *pvParam); 00117 extern int dglTreeTouchI32Compare(const void *pvTouchI32A, 00118 const void *pvTouchI32B, void *pvParam); 00119 extern dglTreeTouchI32_s *dglTreeTouchI32Add(void *pvAVL, dglInt32_t nKey); 00120 00121 00122 /* 00123 * Define a entry to mantain a predecessor/distance network in shortest-path computation 00124 */ 00125 typedef struct _dglTreePredist 00126 { 00127 dglInt32_t nKey; 00128 dglInt32_t nFrom; 00129 dglInt32_t nDistance; 00130 dglInt32_t nCost; 00131 dglInt32_t *pnEdge; 00132 dglByte_t bFlags; 00133 } dglTreePredist_s; 00134 extern dglTreePredist_s *dglTreePredistAlloc(); 00135 extern void dglTreePredistCancel(void *pvPredist, void *pvParam); 00136 extern int dglTreePredistCompare(const void *pvPredistA, 00137 const void *pvPredistB, void *pvParam); 00138 extern dglTreePredist_s *dglTreePredistAdd(void *pvAVL, dglInt32_t nKey); 00139 00140 00141 /* 00142 * 32bit-key Node Prioritizer 00143 */ 00144 typedef struct _dglTreeNodePri32 00145 { 00146 dglInt32_t nKey; 00147 dglInt32_t cnVal; 00148 dglInt32_t *pnVal; 00149 } dglTreeNodePri32_s; 00150 extern dglTreeNodePri32_s *dglTreeNodePri32Alloc(); 00151 extern void dglTreeNodePri32Cancel(void *pvNodePri32, void *pvParam); 00152 extern int dglTreeNodePri32Compare(const void *pvNodePri32A, 00153 const void *pvNodePri32B, void *pvParam); 00154 extern dglTreeNodePri32_s *dglTreeNodePri32Add(void *pvAVL, dglInt32_t nKey); 00155 00156 00157 /* 00158 * 32bit-key Edge Prioritizer 00159 */ 00160 typedef struct _dglTreeEdgePri32 00161 { 00162 dglInt32_t nKey; 00163 dglInt32_t cnData; 00164 dglInt32_t *pnData; 00165 } dglTreeEdgePri32_s; 00166 extern dglTreeEdgePri32_s *dglTreeEdgePri32Alloc(); 00167 extern void dglTreeEdgePri32Cancel(void *pvEdgePri32, void *pvParam); 00168 extern int dglTreeEdgePri32Compare(const void *pvEdgePri32A, 00169 const void *pvEdgePri32B, void *pvParam); 00170 extern dglTreeEdgePri32_s *dglTreeEdgePri32Add(void *pvAVL, dglInt32_t nKey); 00171 00172 00173 #endif