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-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file rbtree.h
26  * @brief intrusive red black tree datastructure
27  * @author Leona Gottwald
28  */
29 
30 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31 
32 #ifndef __SCIP_RB_TREE_H__
33 #define __SCIP_RB_TREE_H__
34 
35 #include "scip/def.h"
36 #include "scip/type_misc.h"
37 
38 #ifdef __cplusplus
39 extern "C" {
40 #endif
41 
43 
45 {
46  uintptr_t parent;
48 };
49 
50 /* macro to make any structure a node in a rbtree.
51  * It is very important that this is the first member of the structure.
52  *
53  * Example usage:
54  * struct SomeStruct
55  * {
56  * SCIP_RBTREE_HOOKS;
57  * OTHERDATA* mydata;
58  * int othermember;
59  * };
60  *
61  */
62 #define SCIP_RBTREE_HOOKS SCIP_RBTREENODE _rbtreenode
63 
64 /* convenience macros that automatically cast the given arguments to SCIP_RBTREENODE */
65 #define SCIPrbtreeFirst(root) SCIPrbtreeFirst_call((SCIP_RBTREENODE*)(root))
66 #define SCIPrbtreeLast(root) SCIPrbtreeLast_call((SCIP_RBTREENODE*)(root))
67 #define SCIPrbtreeSuccessor(x) SCIPrbtreeSuccessor_call((SCIP_RBTREENODE*)(x))
68 #define SCIPrbtreePredecessor(x) SCIPrbtreePredecessor_call((SCIP_RBTREENODE*)(x))
69 #define SCIPrbtreeDelete(root, node) SCIPrbtreeDelete_call((SCIP_RBTREENODE**)(root), (SCIP_RBTREENODE*)(node))
70 #define SCIPrbtreeInsert(r,p,c,n) SCIPrbtreeInsert_call((SCIP_RBTREENODE**)(r), (SCIP_RBTREENODE*)(p), (c), (SCIP_RBTREENODE*)(n) )
71 #define SCIPrbtreeFindInt(r,k,n) SCIPrbtreeFindInt_call((SCIP_RBTREENODE*)(r),(k),(SCIP_RBTREENODE**)(n))
72 #define SCIPrbtreeFindReal(r,k,n) SCIPrbtreeFindReal_call((SCIP_RBTREENODE*)(r),(k),(SCIP_RBTREENODE**)(n))
73 #define SCIPrbtreeFindPtr(c,r,k,n) SCIPrbtreeFindPtr_call((c),(SCIP_RBTREENODE*)(r),(void*)(k),(SCIP_RBTREENODE**)(n))
74 #define SCIPrbtreeFindElem(c,r,k,n) SCIPrbtreeFindElem_call((c),(SCIP_RBTREENODE*)(r),(SCIP_RBTREENODE*)(k),(SCIP_RBTREENODE**)(n))
75 
76 
77 #define FOR_EACH_NODE(type, n, r, body) \
78  { \
79  type n; \
80  type __next; \
81  n = (type) SCIPrbtreeFirst(r); \
82  while( n != NULL ) \
83  { \
84  __next = (type) SCIPrbtreeSuccessor(n); \
85  body \
86  n = __next; \
87  } \
88  }
89 
90 #define SCIP_DEF_RBTREE_FIND(NAME, KEYTYPE, NODETYPE, LT, GT) \
91  /** Searches for an element in the tree given by it's root. If a node equal to the given element exists in the tree, \
92  * (*node) will point to that node upon termination of this function and 0 will be returned. \
93  * If the tree is empty (*node) will be NULL. Otherwise (*node) will point to the predecessor or \
94  * successor of the given element and -1 or 1 will be returned respectively. The return value and the \
95  * predecessor or successor can then be passed to the insert function to insert the element but only if \
96  * it is not in the tree already, i.e. this function did not return 0. \
97  * \
98  * @returns 0 if the key was found, then *node is the node with the key and \
99  * -1 or 1 if the node was node found, then *node is the node with the \
100  * next smaller, or next larger key repectively. \
101  */ \
102  int NAME( \
103  NODETYPE* root, /**< root of the tree */ \
104  KEYTYPE key, /**< key to search for */ \
105  NODETYPE** node /**< pointer to return node */ \
106  ) \
107  { \
108  SCIP_RBTREENODE* x; \
109  *node = NULL; \
110  x = (SCIP_RBTREENODE*) root; \
111  while( x != NULL ) \
112  { \
113  *node = (NODETYPE*) x; \
114  if( LT(key, ((NODETYPE*)x)) ) \
115  x = x->child[0]; \
116  else if( GT(key, ((NODETYPE*)x)) ) \
117  x = x->child[1]; \
118  else \
119  return 0; \
120  } \
121  if( *node != NULL && LT(key, ((NODETYPE*)(*node)) ) ) \
122  return 1; \
123  return -1; \
124  }
125 
126 
127 /** get first element in tree with respect to sorting key */
128 SCIP_EXPORT
130  SCIP_RBTREENODE* root /**< root of the tree */
131  );
132 
133 /** get last element in tree with respect to sorting key */
134 SCIP_EXPORT
136  SCIP_RBTREENODE* root /**< root of the tree */
137  );
138 
139 /** get successor of given element in the tree */
140 SCIP_EXPORT
142  SCIP_RBTREENODE* x /**< element to get successor for */
143  );
144 
145 /** get predecessor of given element in the tree */
146 SCIP_EXPORT
148  SCIP_RBTREENODE* x /**< element to get predecessor for */
149  );
150 
151 /** delete the given node from the tree given by it's root node.
152  * The node must be contained in the tree rooted at root.
153  */
154 SCIP_EXPORT
156  SCIP_RBTREENODE** root, /**< root of the tree */
157  SCIP_RBTREENODE* node /**< node to delete from tree */
158  );
159 
160 /** insert node into the tree given by it's root. Requires the
161  * future parent and the position of the parent as returned by
162  * the tree's find function defined using the SCIP_DEF_RBTREE_FIND
163  * macro.
164  */
165 SCIP_EXPORT
167  SCIP_RBTREENODE** root, /**< root of the tree */
168  SCIP_RBTREENODE* parent, /**< future parent of node to be inserted */
169  int pos, /**< position of parent with respect to node, i.e.
170  * -1 if the parent's key comes before node and 1
171  * if the parent's key comes after the node
172  */
173  SCIP_RBTREENODE* node /**< node to insert into the tree */
174  );
175 
176 #ifdef __cplusplus
177 }
178 #endif
179 
180 #endif
SCIP_RBTREENODE * SCIPrbtreeSuccessor_call(SCIP_RBTREENODE *x)
Definition: rbtree.c:255
type definitions for miscellaneous datastructures
void SCIPrbtreeDelete_call(SCIP_RBTREENODE **root, SCIP_RBTREENODE *node)
Definition: rbtree.c:297
SCIP_RBTREENODE * SCIPrbtreeLast_call(SCIP_RBTREENODE *root)
Definition: rbtree.c:241
SCIP_VAR ** x
Definition: circlepacking.c:63
SCIP_RBTREENODE * child[2]
Definition: rbtree.h:47
void SCIPrbtreeInsert_call(SCIP_RBTREENODE **root, SCIP_RBTREENODE *parent, int pos, SCIP_RBTREENODE *node)
Definition: rbtree.c:352
SCIP_RBTREENODE * SCIPrbtreeFirst_call(SCIP_RBTREENODE *root)
Definition: rbtree.c:227
SCIP_RBTREENODE * SCIPrbtreePredecessor_call(SCIP_RBTREENODE *x)
Definition: rbtree.c:275
uintptr_t parent
Definition: rbtree.h:46
common defines and data types used in all packages of SCIP