BRL-CAD
rb_order_stats.c
Go to the documentation of this file.
1 /* R B _ O R D E R _ S T A T S . C
2  * BRL-CAD
3  *
4  * Copyright (c) 1998-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 
21 #include "common.h"
22 
23 #include <stdlib.h>
24 #include <stdio.h>
25 #include <math.h>
26 
27 #include "bu/rb.h"
28 #include "./rb_internals.h"
29 
30 
31 /**
32  * Retrieve the element of rank k in one order of a red-black tree
33  *
34  * This function has three parameters: the root of the tree to search,
35  * the order on which to do the searching, and the rank of interest.
36  * _rb_select() returns the discovered node. It is an implementation
37  * of the routine OS-SELECT on p. 282 of Cormen et al. (p. 341 in the
38  * paperback version of the 2009 edition).
39  */
40 HIDDEN struct bu_rb_node *
41 _rb_select(struct bu_rb_node *root, int order, int k)
42 {
43  int rank;
44 
45  BU_CKMAG(root, BU_RB_NODE_MAGIC, "red-black node");
46 
47  rank = RB_SIZE(RB_LEFT_CHILD(root, order), order) + 1;
49  bu_log("_rb_select(<%p>, %d, %d): rank=%d\n",
50  (void*)root, order, k, rank);
51 
52  if (rank == k)
53  return root;
54  else if (rank > k)
55  return _rb_select(RB_LEFT_CHILD(root, order), order, k);
56  else
57  return _rb_select(RB_RIGHT_CHILD(root, order), order, k - rank);
58 }
59 
60 
61 void *
62 bu_rb_select(struct bu_rb_tree *tree, int order, int k)
63 {
64  struct bu_rb_node *node;
65 
66  BU_CKMAG(tree, BU_RB_TREE_MAGIC, "red-black tree");
67  RB_CKORDER(tree, order);
68 
69  if ((k < 1) || (k > tree->rbt_nm_nodes)) {
70  if (UNLIKELY(tree->rbt_debug & BU_RB_DEBUG_OS))
71  bu_log("bu_rb_select(<%p>, %d, %d): k out of bounds [1, %d]\n",
72  (void*)tree, order, k, tree->rbt_nm_nodes);
73  RB_CURRENT(tree) = RB_NULL(tree);
74  return NULL;
75  }
76  if (UNLIKELY(tree->rbt_debug & BU_RB_DEBUG_OS))
77  bu_log("bu_rb_select(<%p>, %d, %d): root=<%p>\n",
78  (void*)tree, order, k, (void*)RB_ROOT(tree, order));
79 
80  RB_CURRENT(tree) = node
81  = _rb_select(RB_ROOT(tree, order), order, k);
82  return RB_DATA(node, order);
83 }
84 
85 
86 int bu_rb_rank(struct bu_rb_tree *tree, int order)
87 {
88  int rank;
89  struct bu_rb_node *node;
90  struct bu_rb_node *parent;
91  struct bu_rb_node *root;
92 
93  BU_CKMAG(tree, BU_RB_TREE_MAGIC, "red-black tree");
94  RB_CKORDER(tree, order);
95 
96  if ((node = RB_CURRENT(tree)) == RB_NULL(tree))
97  return 0;
98 
99  root = RB_ROOT(tree, order);
100  rank = RB_SIZE(RB_LEFT_CHILD(node, order), order) + 1;
101  while (node != root) {
102  parent = RB_PARENT(node, order);
103  if (node == RB_RIGHT_CHILD(parent, order))
104  rank += RB_SIZE(RB_LEFT_CHILD(parent, order), order) + 1;
105  node = parent;
106  }
107 
108  return rank;
109 }
110 
111 
112 /*
113  * Local Variables:
114  * mode: C
115  * tab-width: 8
116  * indent-tabs-mode: t
117  * c-file-style: "stroustrup"
118  * End:
119  * ex: shiftwidth=4 tabstop=8
120  */
#define RB_PARENT(n, o)
Definition: rb_internals.h:60
#define RB_RIGHT_CHILD(n, o)
Definition: rb_internals.h:62
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
HIDDEN struct bu_rb_node * _rb_select(struct bu_rb_node *root, int order, int k)
Definition: rb.h:109
#define BU_CKMAG(_ptr, _magic, _str)
Definition: magic.h:233
Definition: rb.h:204
#define BU_RB_DEBUG_OS
Definition: rb.h:175
Header file for the BRL-CAD common definitions.
#define RB_LEFT_CHILD(n, o)
Definition: rb_internals.h:61
#define RB_NULL(t)
Definition: rb_internals.h:48
int bu_rb_rank(struct bu_rb_tree *tree, int order)
#define HIDDEN
Definition: common.h:86
#define BU_RB_NODE_MAGIC
Definition: magic.h:61
#define RB_CURRENT(t)
Definition: rb_internals.h:47
#define BU_RB_TREE_MAGIC
Definition: magic.h:63
struct bu_rb_tree * rbn_tree
Definition: rb.h:207
#define RB_CKORDER(t, o)
Definition: rb_internals.h:33
#define RB_ROOT(t, o)
Definition: rb_internals.h:46
void * bu_rb_select(struct bu_rb_tree *tree, int order, int k)
int rbt_nm_nodes
Definition: rb.h:112
#define RB_DATA(n, o)
Definition: rb_internals.h:82
int rbt_debug
Definition: rb.h:116
#define RB_SIZE(n, o)
Definition: rb_internals.h:71
#define UNLIKELY(expression)
Definition: common.h:282