Scippy

SCIP

Solving Constraint Integer Programs

rbtree.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file rbtree.h
17  * @brief intrusive red black tree datastructure
18  * @author Robert Lion Gottwald
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #ifndef __SCIP_RB_TREE_H__
24 #define __SCIP_RB_TREE_H__
25 
26 #include "scip/def.h"
27 #include "scip/type_misc.h"
28 
29 #ifdef __cplusplus
30 extern "C" {
31 #endif
32 
34 
36 {
37  uintptr_t parent;
39 };
40 
41 /* macro to make any structure a node in a rbtree.
42  * It is very important that this is the first member of the structure.
43  *
44  * Example usage:
45  * struct SomeStruct
46  * {
47  * SCIP_RBTREE_HOOKS;
48  * OTHERDATA* mydata;
49  * int othermember;
50  * };
51  *
52  */
53 #define SCIP_RBTREE_HOOKS SCIP_RBTREENODE _rbtreenode
54 
55 /* convenience macros that automtically cast the given arguments to SCIP_RBTREENODE */
56 #define SCIPrbtreeFirst(root) SCIPrbtreeFirst_call((SCIP_RBTREENODE*)(root))
57 #define SCIPrbtreeLast(root) SCIPrbtreeLast_call((SCIP_RBTREENODE*)(root))
58 #define SCIPrbtreeSuccessor(x) SCIPrbtreeSuccessor_call((SCIP_RBTREENODE*)(x))
59 #define SCIPrbtreePredecessor(x) SCIPrbtreePredecessor_call((SCIP_RBTREENODE*)(x))
60 #define SCIPrbtreeDelete(root, node) SCIPrbtreeDelete_call((SCIP_RBTREENODE**)(root), (SCIP_RBTREENODE*)(node))
61 #define SCIPrbtreeInsert(r,p,c,n) SCIPrbtreeInsert_call((SCIP_RBTREENODE**)(r), (SCIP_RBTREENODE*)(p), (c), (SCIP_RBTREENODE*)(n) )
62 #define SCIPrbtreeFindInt(r,k,n) SCIPrbtreeFindInt_call((SCIP_RBTREENODE*)(r),(k),(SCIP_RBTREENODE**)(n))
63 #define SCIPrbtreeFindReal(r,k,n) SCIPrbtreeFindReal_call((SCIP_RBTREENODE*)(r),(k),(SCIP_RBTREENODE**)(n))
64 #define SCIPrbtreeFindPtr(c,r,k,n) SCIPrbtreeFindPtr_call((c),(SCIP_RBTREENODE*)(r),(void*)(k),(SCIP_RBTREENODE**)(n))
65 #define SCIPrbtreeFindElem(c,r,k,n) SCIPrbtreeFindElem_call((c),(SCIP_RBTREENODE*)(r),(SCIP_RBTREENODE*)(k),(SCIP_RBTREENODE**)(n))
66 
67 
68 #define FOR_EACH_NODE(type, n, r, body) \
69  { \
70  type n; \
71  type __next; \
72  n = (type) SCIPrbtreeFirst(r); \
73  while( n != NULL ) \
74  { \
75  __next = (type) SCIPrbtreeSuccessor(n); \
76  body \
77  n = __next; \
78  } \
79  }
80 
81 #define SCIP_DEF_RBTREE_FIND(NAME, KEYTYPE, NODETYPE, LT, GT) \
82  /** Searches for an element in the tree given by it's root. If a node equal to the given element exists in the tree, \
83  * (*node) will point to that node upon termination of this function and 0 will be returned. \
84  * If the tree is empty (*node) will be NULL. Otherwise (*node) will point to the predecessor or \
85  * successor of the given element and -1 or 1 will be returned respectively. The return value and the \
86  * predecessor or successor can then be passed to the insert function to insert the element but only if \
87  * it is not in the tree already, i.e. this function did not return 0. \
88  * \
89  * @returns 0 if the key was found, then *node is the node with the key and \
90  * -1 or 1 if the node was node found, then *node is the node with the \
91  * next smaller, or next larger key repectively. \
92  */ \
93  int NAME( \
94  NODETYPE* root, /**< root of the tree */ \
95  KEYTYPE key, /**< key to search for */ \
96  NODETYPE** node /**< pointer to return node */ \
97  ) \
98  { \
99  SCIP_RBTREENODE* x; \
100  *node = NULL; \
101  x = (SCIP_RBTREENODE*) root; \
102  while( x != NULL ) \
103  { \
104  *node = (NODETYPE*) x; \
105  if( LT(key, ((NODETYPE*)x)) ) \
106  x = x->child[0]; \
107  else if( GT(key, ((NODETYPE*)x)) ) \
108  x = x->child[1]; \
109  else \
110  return 0; \
111  } \
112  if( *node != NULL && LT(key, ((NODETYPE*)(*node)) ) ) \
113  return 1; \
114  return -1; \
115  }
116 
117 
118 /** get first element in tree with respect to sorting key */
119 extern
121  SCIP_RBTREENODE* root /**< root of the tree */
122  );
123 
124 /** get last element in tree with respect to sorting key */
125 extern
127  SCIP_RBTREENODE* root /**< root of the tree */
128  );
129 
130 /** get successor of given element in the tree */
131 extern
133  SCIP_RBTREENODE* x /**< element to get successor for */
134  );
135 
136 /** get predecessor of given element in the tree */
137 extern
139  SCIP_RBTREENODE* x /**< element to get predecessor for */
140  );
141 
142 /** delete the given node from the tree given by it's root node.
143  * The node must be contained in the tree rooted at root.
144  */
145 extern
147  SCIP_RBTREENODE** root, /**< root of the tree */
148  SCIP_RBTREENODE* node /**< node to delete from tree */
149  );
150 
151 /** insert node into the tree given by it's root. Requires the
152  * future parent and the position of the parent as returned by
153  * the tree's find function defined using the SCIP_DEF_RBTREE_FIND
154  * macro.
155  */
156 extern
158  SCIP_RBTREENODE** root, /**< root of the tree */
159  SCIP_RBTREENODE* parent, /**< future parent of node to be inserted */
160  int pos, /**< position of parent with respect to node, i.e.
161  * -1 if the parent's key comes before node and 1
162  * if the parent's key comes after the node
163  */
164  SCIP_RBTREENODE* node /**< node to insert into the tree */
165  );
166 
167 #ifdef __cplusplus
168 }
169 #endif
170 
171 #endif
SCIP_RBTREENODE * SCIPrbtreeSuccessor_call(SCIP_RBTREENODE *x)
Definition: rbtree.c:233
type definitions for miscellaneous datastructures
void SCIPrbtreeDelete_call(SCIP_RBTREENODE **root, SCIP_RBTREENODE *node)
Definition: rbtree.c:275
SCIP_RBTREENODE * SCIPrbtreeLast_call(SCIP_RBTREENODE *root)
Definition: rbtree.c:219
SCIP_RBTREENODE * child[2]
Definition: rbtree.h:38
void SCIPrbtreeInsert_call(SCIP_RBTREENODE **root, SCIP_RBTREENODE *parent, int pos, SCIP_RBTREENODE *node)
Definition: rbtree.c:330
SCIP_RBTREENODE * SCIPrbtreeFirst_call(SCIP_RBTREENODE *root)
Definition: rbtree.c:205
SCIP_RBTREENODE * SCIPrbtreePredecessor_call(SCIP_RBTREENODE *x)
Definition: rbtree.c:253
uintptr_t parent
Definition: rbtree.h:37
common defines and data types used in all packages of SCIP