1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 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   	
42   	typedef struct SCIP_RBTreeNode SCIP_RBTREENODE;
43   	
44   	struct SCIP_RBTreeNode
45   	{
46   	   uintptr_t             parent;
47   	   SCIP_RBTREENODE*      child[2];
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 automtically 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
129  	SCIP_RBTREENODE* SCIPrbtreeFirst_call(
130  	   SCIP_RBTREENODE*      root                /**< root of the tree */
131  	   );
132  	
133  	/** get last element in tree with respect to sorting key */
134  	SCIP_EXPORT
135  	SCIP_RBTREENODE* SCIPrbtreeLast_call(
136  	   SCIP_RBTREENODE*      root                /**< root of the tree */
137  	   );
138  	
139  	/** get successor of given element in the tree */
140  	SCIP_EXPORT
141  	SCIP_RBTREENODE* SCIPrbtreeSuccessor_call(
142  	   SCIP_RBTREENODE*      x                   /**< element to get successor for */
143  	   );
144  	
145  	/** get predecessor of given element in the tree */
146  	SCIP_EXPORT
147  	SCIP_RBTREENODE* SCIPrbtreePredecessor_call(
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
155  	void SCIPrbtreeDelete_call(
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
166  	void SCIPrbtreeInsert_call(
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
181