BDE 4.14.0 Production release
Loading...
Searching...
No Matches
bslalg_rbtreeanchor.h
Go to the documentation of this file.
1/// @file bslalg_rbtreeanchor.h
2///
3/// The content of this file has been pre-processed for Doxygen.
4///
5
6
7// bslalg_rbtreeanchor.h -*-C++-*-
8#ifndef INCLUDED_BSLALG_RBTREEANCHOR
9#define INCLUDED_BSLALG_RBTREEANCHOR
10
11#include <bsls_ident.h>
12BSLS_IDENT("$Id$ $CSID$")
13
14/// @defgroup bslalg_rbtreeanchor bslalg_rbtreeanchor
15/// @brief Encapsulate root, first, and last nodes of a tree with a count.
16/// @addtogroup bsl
17/// @{
18/// @addtogroup bslalg
19/// @{
20/// @addtogroup bslalg_rbtreeanchor
21/// @{
22///
23/// <h1> Outline </h1>
24/// * <a href="#bslalg_rbtreeanchor-purpose"> Purpose</a>
25/// * <a href="#bslalg_rbtreeanchor-classes"> Classes </a>
26/// * <a href="#bslalg_rbtreeanchor-description"> Description </a>
27/// * <a href="#bslalg_rbtreeanchor-sentinel-node"> Sentinel Node </a>
28/// * <a href="#bslalg_rbtreeanchor-usage"> Usage </a>
29/// * <a href="#bslalg_rbtreeanchor-example-1-creating-a-simple-tree"> Example 1: Creating a Simple Tree </a>
30/// * <a href="#bslalg_rbtreeanchor-example-2-creating-an-insert-function-for-a-binary-tree"> Example 2: Creating an Insert Function for a Binary Tree </a>
31///
32/// # Purpose {#bslalg_rbtreeanchor-purpose}
33/// Encapsulate root, first, and last nodes of a tree with a count.
34///
35/// # Classes {#bslalg_rbtreeanchor-classes}
36///
37/// - bslalg::RbTreeAnchor: (in-core) node-addresses and node count
38///
39/// @see bslalg_rbtreenode, bslalg_rbtreeutil
40///
41/// # Description {#bslalg_rbtreeanchor-description}
42/// This component defines a single class, `RbTreeAnchor`,
43/// providing access to the addresses of the root, first, and sentinel nodes of
44/// a tree, as well as the count of the number of nodes. A sentinel node is a
45/// value-less node, owned by the `RbTreeAnchor` for the tree, that is used as
46/// the end-point for iteration over the nodes in a tree. `RbTreeAnchor`
47/// provides modifiers for the `firstNode`, `rootNode`, and `numNodes`
48/// properties, however the sentinel node for a tree is located at a fixed
49/// address and cannot be modified. An `RbTreeAnchor` is similar to an in-core
50/// unconstrained attribute class, except that it does not supply
51/// equality-comparison, copy-construction, and copy-assignment operations.
52///
53/// ## Sentinel Node {#bslalg_rbtreeanchor-sentinel-node}
54///
55///
56/// The sentinel node is an `RbTreeNode` object that does not have a value, and
57/// provides a fixed end-point for navigation over the tree. However, a
58/// sentinel node's attributes have different interpretations than those of
59/// other `RbTreeNode` objects. Specifically, a sentinel node's `leftChild`
60/// refers to the root of the tree, and its `rightChild` refers to the first
61/// node of the tree. The following diagram shows the composition of a tree
62/// with `RbTreeAnchor` and `RbTreeNode`:
63/// @code
64/// .------------------------.
65/// .------| RbTreeAnchor |-------.
66/// | | | |
67/// firstNode | | .--------------. | | rootNode
68/// | | | RbTreeNode | | |
69/// | | | (sentinel) | | |
70/// | | `--------------' | |
71/// | | / ^ \ | |
72/// | `-----/-----|-------\----' |
73/// V / | \ V
74/// __________/ | \__________
75/// | | |
76/// | | |
77/// sentinel | root | | sentinel
78/// *right*-child | parentNode | | *left*-child
79/// | | |
80/// | .--------------. |
81/// | | RbTreeNode | <----------'
82/// | | (root) |
83/// | `--------------'
84/// | / \.
85/// | .------------. .------------.
86/// | | RbTreeNode | | RbTreeNode |
87/// | `------------' `------------'
88/// | / \.
89/// | .-----------------------------.
90/// | | |
91/// | | [Tree of RbTreeNodes] |
92/// | | |
93/// | |_____________________________|
94/// V / \.
95/// .------------. .------------.
96/// | RbTreeNode | | RbTreeNode |
97/// | (first) | | (last) |
98/// `------------' `------------'
99/// @endcode
100/// Notice that, counter-intuitively, the sentinel's right-child refers to the
101/// left-most (first) node of the tree. Also notice that `RbTreeAnchor`
102/// doesn't hold a direct reference to the last (i.e., the right-most) node of
103/// the tree.
104///
105/// ## Usage {#bslalg_rbtreeanchor-usage}
106///
107///
108/// This section illustrates intended usage of this component.
109///
110/// ### Example 1: Creating a Simple Tree {#bslalg_rbtreeanchor-example-1-creating-a-simple-tree}
111///
112///
113/// This example demonstrates creating a simple tree of integer values using
114/// `RbTreeAnchor`. Note that, in practice, clients should use associated
115/// utilities to manage such a tree (see @ref bslalg_rbtreeutil ).
116///
117/// First, we define a node-type, `IntTreeNode`, that inherits from
118/// `RbTreeNode`:
119/// @code
120/// struct IntTreeNode : public RbTreeNode {
121/// // A red-black tree node containing an integer data-value.
122///
123/// int d_value; // "payload" value represented by the node
124/// };
125/// @endcode
126/// Then, we define `main` for our example, and create three nodes that we'll
127/// use to construct a tree:
128/// @code
129/// int main(int argc, const char *argv[])
130/// {
131/// IntTreeNode A, B, C;
132/// @endcode
133/// Next, we create an `RbTreeAnchor`, `myTree`, which will hold the addresses
134/// of the root node and the first node of our tree along with a count of nodes,
135/// and then verify the attribute values of the default constructed object:
136/// @code
137/// RbTreeAnchor myTree;
138/// assert(0 == myTree.rootNode());
139/// assert(myTree.sentinel() == myTree.firstNode());
140/// assert(0 == myTree.numNodes());
141/// @endcode
142/// Then, we describe the structure of the tree we wish to construct.
143/// @code
144///
145/// A (value: 2, BLACK)
146/// / \.
147/// / \.
148/// B (value: 1, RED) C ( value: 5, RED )
149/// @endcode
150/// Next, we set the properties for the nodes `A`, `B`, and `C` to form a valid
151/// tree whose structure matches that description:
152/// @code
153/// A.d_value = 2;
154/// A.makeBlack();
155/// A.setParent(myTree.sentinel());
156/// A.setLeftChild(&B);
157/// A.setRightChild(&C);
158///
159/// B.d_value = 1;
160/// B.makeRed();
161/// B.setParent(&A);
162/// B.setLeftChild(0);
163/// B.setRightChild(0);
164///
165/// C.d_value = 3;
166/// C.makeRed();
167/// C.setParent(&A);
168/// C.setLeftChild(0);
169/// C.setRightChild(0);
170/// @endcode
171/// Now, we assign the address of `A` and `B` as the root node and the first
172/// node of `myTree` respectively and set the number of nodes to 3:
173/// @code
174/// myTree.reset(&A, &B, 3);
175/// @endcode
176/// Finally, we verify the attributes of `myTree`:
177/// @code
178/// assert(&A == myTree.rootNode());
179/// assert(&B == myTree.firstNode());
180/// assert(3 == myTree.numNodes());
181/// @endcode
182///
183/// ### Example 2: Creating an Insert Function for a Binary Tree {#bslalg_rbtreeanchor-example-2-creating-an-insert-function-for-a-binary-tree}
184///
185///
186/// This example demonstrates creating a function that inserts elements into a
187/// binary search tree. Note that, for simplicity, this function does *not*
188/// create a balanced red-black tree (see @ref bslalg_rbtreeutil ).
189///
190/// First, we define a comparison functor for `IntTreeNode` objects used by the
191/// insertion function:
192/// @code
193/// struct IntTreeNodeComparator {
194/// // This class defines a comparator providing a comparison operation
195/// // between two 'IntTreeNode' objects.
196///
197/// bool operator()(const RbTreeNode& lhs, const RbTreeNode& rhs) const
198/// {
199/// return static_cast<const IntTreeNode&>(lhs).d_value <
200/// static_cast<const IntTreeNode&>(rhs).d_value;
201/// }
202/// };
203/// @endcode
204/// Then, we declare the signature of a function `insertNode`, which takes
205/// three arguments: (1) the anchor of the tree in which to insert the node (2)
206/// the new node to insert into the tree, and (3) a comparator, which is used to
207/// compare the payload values of the tree nodes. Note that the parameterized
208/// comparator is needed because a node's value is not accessible through the
209/// supplied `RbTreeNode`.
210/// @code
211/// template <class NODE_COMPARATOR>
212/// void insertNode(RbTreeAnchor *searchTree,
213/// RbTreeNode *newNode,
214/// const NODE_COMPARATOR& comparator)
215/// // Insert into the specified 'searchTree', ordered according to the
216/// // specified 'comparator', the specified 'newNode'. If there are
217/// // multiple nodes having the same value as 'newNode', insert 'newNode'
218/// // in the last position according to an infix traversal of the tree.
219/// // The behavior is undefined unless the 'comparator' provides a
220/// // strict weak ordering on the nodes in the tree.
221/// {
222/// @endcode
223/// Next, we find the location where `newNode` can be inserted into `searchTree`
224/// without violating the ordering imposed by `comparator`, and then updates
225/// `searchTree` with a potentially updated root node and first node.
226/// @code
227/// RbTreeNode *parent = searchTree->sentinel();
228/// RbTreeNode *node = searchTree->rootNode();
229/// bool isLeftChild;
230///
231/// newNode->setLeftChild(0);
232/// newNode->setRightChild(0);
233///
234/// if (!node) {
235/// @endcode
236/// If the root node of `searchTree` is 0, we use the `reset` function set the
237/// root node and the first node of `searchTree` to `newNode` and set the number
238/// of nodes to 1:
239/// @code
240/// searchTree->reset(newNode, newNode, 1);
241/// newNode->setParent(parent);
242/// return; // RETURN
243/// }
244///
245/// // Find the leaf node that would be a valid parent of 'newNode'.
246///
247/// do {
248/// parent = node;
249/// isLeftChild = comparator(*newNode, *node);
250/// if (isLeftChild) {
251/// node = parent->leftChild();
252/// }
253/// else {
254/// node = parent->rightChild();
255/// }
256/// } while (node);
257///
258/// // Insert 'newNode' into 'searchTree' and the location that's been
259/// // found.
260/// @endcode
261/// Then, we insert `newNode` into the appropriate position by setting it as a
262/// child of `parent`:
263/// @code
264/// if (isLeftChild) {
265/// // If 'newNode' is a left-child, it may be the new first node, but
266/// // cannot be the new last node.
267///
268/// parent->setLeftChild(newNode);
269/// newNode->setParent(parent);
270/// if (parent == searchTree->firstNode()) {
271/// searchTree->setFirstNode(newNode);
272/// }
273/// }
274/// else {
275/// parent->setRightChild(newNode);
276/// newNode->setParent(parent);
277/// }
278/// @endcode
279/// Next, we complete the insert function by incrementing the number of nodes in
280/// the tree:
281/// @code
282/// searchTree->incrementNumNodes();
283/// }
284/// @endcode
285/// Now, we create 5 `IntTreeNode` objects and insert them into a tree using the
286/// `insertNode` function.
287/// @code
288/// IntTreeNode nodes[5];
289///
290/// nodes[0].d_value = 3;
291/// nodes[1].d_value = 1;
292/// nodes[2].d_value = 5;
293/// nodes[3].d_value = 2;
294/// nodes[4].d_value = 0;
295///
296/// IntTreeNodeComparator comparator;
297///
298/// RbTreeAnchor anchor;
299/// for (int i = 0; i < 5; ++i) {
300/// insertNode(&anchor, nodes + i, comparator);
301/// }
302/// @endcode
303/// Finally, we verify that the `RbTreeAnchor` refers to the correct `TreeNode`
304/// with its `firstNode` and `rootNode` attributes.
305/// @code
306/// assert(0 == static_cast<IntTreeNode *>(anchor.firstNode())->d_value);
307/// assert(3 == static_cast<IntTreeNode *>(anchor.rootNode())->d_value);
308/// @endcode
309/// @}
310/** @} */
311/** @} */
312
313/** @addtogroup bsl
314 * @{
315 */
316/** @addtogroup bslalg
317 * @{
318 */
319/** @addtogroup bslalg_rbtreeanchor
320 * @{
321 */
322
323#include <bslscm_version.h>
324
325#include <bslalg_rbtreenode.h>
326
327#include <bslmf_assert.h>
328
329#include <bsls_assert.h>
330
331
332namespace bslalg {
333
334 // ==================
335 // class RbTreeAnchor
336 // ==================
337
338/// An `RbTreeAnchor` provides the addresses of the first and root nodes of
339/// a binary search tree. An `RbTreeAnchor` is similar to an in-core
340/// simply constrained (value-semantic) attribute class, except that it
341/// does not supply equality-comparison, copy-construction, and
342/// copy-assignment operations. Note that a node may not be copied because
343/// `sentinel` returns an address unique to each `RbTreeAnchor` object.
344///
345/// This class:
346/// * is *exception-neutral*
347/// * is *alias-safe*
348/// * is `const` *thread-safe*
349/// For terminology see @ref bsldoc_glossary .
350///
351/// See @ref bslalg_rbtreeanchor
353
354 // DATA
355 RbTreeNode d_sentinel; // sentinel for the tree, holding the root,
356 // first and last tree nodes
357
358 int d_numNodes; // number of nodes
359
360 private:
361 // NOT IMPLEMENTED
363 RbTreeAnchor& operator=(const RbTreeAnchor&);
364
365 public:
366 // CREATORS
367
368 /// Create a `RbTree` object having the (default) attribute values:
369 /// @code
370 /// rootNode() == 0
371 /// firstNode() == sentinel()
372 /// numNodes() == 0
373 /// @endcode
374 RbTreeAnchor();
375
376 /// Create a `RbTreeAnchor` object having the specified `rootNode`,
377 /// `firstNode`, and `numNodes` attribute values.
380 int numNodes);
381
382 /// Destroy this object.
384
385 // MANIPULATORS
386
387 /// Set the `rootNode`, `firstNode`, and `numNodes`
388 /// attributes to the specified `rootNodeValue`, `firstNodeValue`,
389 /// and `numNodes` respectively.
392 int numNodes);
393
394 /// Set the `firstNode` attribute of this object to the specified
395 /// `value`.
396 void setFirstNode(RbTreeNode *value);
397
398 /// Set the `rootNode` attribute of this object to the specified
399 /// `value`.
400 void setRootNode(RbTreeNode *value);
401
402 /// Set the `numNodes` attribute of this object to the specified
403 /// `value`. The behavior is undefined unless `0 <= value`.
404 void setNumNodes(int value);
405
406 /// Increment, by 1, the `numNodes` attribute of this object. The
407 /// behavior is undefined unless `numNodes <= INT_MAX - 1`.
408 void incrementNumNodes();
409
410 /// Decrement, by 1, the `numNodes` attribute of this object. The
411 /// behavior is undefined unless `1 <= numNodes`.
412 void decrementNumNodes();
413
414 /// Return the address of the (modifiable) node referred to by the
415 /// `rootNode` attribute of this object.
417
418 /// Return the address of the (modifiable) node referred to by the
419 /// `firstNode` attribute of this object.
421
422 /// Return the address of the (modifiable) node referred to by the
423 /// `sentinel` node for this tree.
425
426 // ACCESSORS
427
428 /// Return the address referred to by the `firstNode` attribute of this
429 /// object.
430 const RbTreeNode *firstNode() const;
431
432 /// Return the address referred to by the `rootNode` attribute of this
433 /// object.
434 const RbTreeNode *rootNode() const;
435
436 /// Return the address referred to by the `sentinel` node for this tree.
437 const RbTreeNode *sentinel() const;
438
439 /// Return the `numNodes` attribute of this object.
440 int numNodes() const;
441};
442
443// ============================================================================
444// INLINE FUNCTION DEFINITIONS
445// ============================================================================
446
447 // ------------------
448 // class RbTreeAnchor
449 // ------------------
450
451// CREATORS
452inline
454: d_numNodes(0)
455{
456 d_sentinel.setRightChild(&d_sentinel);
457 d_sentinel.setLeftChild(0);
458}
459
460inline
462 RbTreeNode *firstNode,
463 int numNodes)
464: d_numNodes(numNodes)
465{
466 d_sentinel.setRightChild(firstNode);
467 d_sentinel.setLeftChild(rootNode);
468}
469
470inline
472{
473 BSLS_ASSERT_SAFE(sentinel()->leftChild() == rootNode());
474 BSLS_ASSERT_SAFE(sentinel()->rightChild() == firstNode());
475}
476
477// MANIPULATORS
478inline
480 RbTreeNode *firstNode,
481 int numNodes)
482{
483 d_sentinel.setLeftChild(rootNode);
484 d_sentinel.setRightChild(firstNode);
485 d_numNodes = numNodes;
486}
487
488inline
490{
491 d_sentinel.setRightChild(value);
492}
493
494inline
496{
497 d_sentinel.setLeftChild(value);
498}
499
500inline
502{
503 BSLS_ASSERT_SAFE(0 <= value);
504
505 d_numNodes = value;
506}
507
508inline
510{
511 ++d_numNodes;
512}
513
514inline
516{
517 --d_numNodes;
518}
519
520inline
522{
523 return d_sentinel.rightChild();
524}
525
526inline
528{
529 return d_sentinel.leftChild();
530}
531
532inline
534{
535 return &d_sentinel;
536}
537
538// ACCESSORS
539inline
541{
542 return d_sentinel.rightChild();
543}
544
545inline
547{
548 return d_sentinel.leftChild();
549}
550
551inline
553{
554 return d_numNodes;
555}
556
557inline
559{
560 return &d_sentinel;
561}
562
563} // close package namespace
564
565
566#endif
567
568// ----------------------------------------------------------------------------
569// Copyright 2013 Bloomberg Finance L.P.
570//
571// Licensed under the Apache License, Version 2.0 (the "License");
572// you may not use this file except in compliance with the License.
573// You may obtain a copy of the License at
574//
575// http://www.apache.org/licenses/LICENSE-2.0
576//
577// Unless required by applicable law or agreed to in writing, software
578// distributed under the License is distributed on an "AS IS" BASIS,
579// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
580// See the License for the specific language governing permissions and
581// limitations under the License.
582// ----------------------------- END-OF-FILE ----------------------------------
583
584/** @} */
585/** @} */
586/** @} */
Definition bslalg_rbtreeanchor.h:352
~RbTreeAnchor()
Destroy this object.
Definition bslalg_rbtreeanchor.h:471
void decrementNumNodes()
Definition bslalg_rbtreeanchor.h:515
RbTreeNode * sentinel()
Definition bslalg_rbtreeanchor.h:533
RbTreeNode * firstNode()
Definition bslalg_rbtreeanchor.h:521
void setNumNodes(int value)
Definition bslalg_rbtreeanchor.h:501
void setFirstNode(RbTreeNode *value)
Definition bslalg_rbtreeanchor.h:489
void setRootNode(RbTreeNode *value)
Definition bslalg_rbtreeanchor.h:495
RbTreeAnchor()
Definition bslalg_rbtreeanchor.h:453
int numNodes() const
Return the numNodes attribute of this object.
Definition bslalg_rbtreeanchor.h:552
RbTreeNode * rootNode()
Definition bslalg_rbtreeanchor.h:527
void incrementNumNodes()
Definition bslalg_rbtreeanchor.h:509
void reset(RbTreeNode *rootNode, RbTreeNode *firstNode, int numNodes)
Definition bslalg_rbtreeanchor.h:479
Definition bslalg_rbtreenode.h:376
RbTreeNode * rightChild()
Definition bslalg_rbtreenode.h:598
RbTreeNode * leftChild()
Definition bslalg_rbtreenode.h:592
void setRightChild(RbTreeNode *address)
Definition bslalg_rbtreenode.h:552
void setLeftChild(RbTreeNode *address)
Definition bslalg_rbtreenode.h:546
#define BSLS_ASSERT_SAFE(X)
Definition bsls_assert.h:1762
#define BSLS_IDENT(str)
Definition bsls_ident.h:195
Definition bdlc_flathashmap.h:1805