bslalg_bidirectionallinklistutil.h

Go to the documentation of this file.

/// @file bslalg_bidirectionallinklistutil.h
///
/// The content of this file has been pre-processed for Doxygen.
///
 
 
// bslalg_bidirectionallinklistutil.h                                 -*-C++-*-
#ifndef INCLUDED_BSLALG_BIDIRECTIONALLINKLISTUTIL
#define INCLUDED_BSLALG_BIDIRECTIONALLINKLISTUTIL
 
#include <bsls_ident.h>
BSLS_IDENT("$Id: $")
 
/// @defgroup bslalg_bidirectionallinklistutil bslalg_bidirectionallinklistutil
/// @brief  Provide utilities to maintain bidirectional list data structures.
/// @addtogroup bsl
/// @{
/// @addtogroup bslalg
/// @{
/// @addtogroup bslalg_bidirectionallinklistutil
/// @{
///
/// <h1> Outline </h1>
/// * <a href="#bslalg_bidirectionallinklistutil-purpose"> Purpose</a>
/// * <a href="#bslalg_bidirectionallinklistutil-classes"> Classes </a>
/// * <a href="#bslalg_bidirectionallinklistutil-description"> Description </a>
///   * <a href="#bslalg_bidirectionallinklistutil-usage"> Usage </a>
///     * <a href="#bslalg_bidirectionallinklistutil-example-1-creating-and-using-a-list-template-class"> Example 1: Creating and Using a List Template Class </a>
///
/// # Purpose {#bslalg_bidirectionallinklistutil-purpose}
/// Provide utilities to maintain bidirectional list data structures.
///
/// # Classes {#bslalg_bidirectionallinklistutil-classes}
///
/// -  bslalg::BidirectionalLinkListUtil: utilities to maintain linked lists
///
/// @see  bslalg_bidirectionallink, bslalg_hashtableimputil
///
/// # Description {#bslalg_bidirectionallinklistutil-description}
/// This component provides a namespace,
/// `bslalg::BidirectionalLinkListUtil`, containing utility functions for
/// operating on doubly linked lists with nodes of type
/// `bslalg::BidirectionalLink`.  The operations assume that the linked lists
/// are either 0 terminated (on both ends) or terminate with sentinel (valid)
/// nodes.  The main operations include insertion and removal of a node from a
/// list of nodes, and the *splicing* of ranges from one list into another one.
/// Splicing is the operation of moving a sub-list, or range, of elements from
/// one linked list and into a second list, at a specified position.
///
/// ## Usage {#bslalg_bidirectionallinklistutil-usage}
///
///
/// This section illustrates intended usage of this component.
///
/// ### Example 1: Creating and Using a List Template Class {#bslalg_bidirectionallinklistutil-example-1-creating-and-using-a-list-template-class}
///
///
/// First, since `Link` neither has a constructor nor is a POD (which would make
/// aggregate initialization possible), we create a function `makeLink` to
/// assemble a link from two pointers:
/// @code
/// Link makeLink(Link *prev, Link *next)
/// {
///     Link result;
///     result.setPreviousLink(prev);
///     result.setNextLink(    next);
///
///     return result;
/// }
/// @endcode
/// Then, we create a function that will, passed two links that are endpoints
/// of a linked list from the specified `first` to `last` though the `nextLink`
/// pointers, count the number of nodes in the list including both endpoints.
/// @code
/// int length(Link *first, Link *last)
/// {
///     int result = 0;
///     Link *p = first;
///     while (p && ++result && last != p) {
///         p = p->nextLink();
///     }
///
///     return result;
/// }
/// @endcode
/// Next, in our `main`, we declare a `typedef` for the component name and a
/// a constant `invalid` garbage pointer we use when we want data to be garbage.
/// @code
/// typedef BidirectionalLinkListUtil Util;
/// Link * const invalid = (Link *) 0XBADDEED5;
/// @endcode
/// Then, we create a linked list of links and use `isWellFormed` to verify
/// that it is well formed, and call the `length` method we just created to
/// verify its length.
/// @code
/// Link usageData[] = {
///     makeLink(0,             &usageData[1]),
///     makeLink(&usageData[0], &usageData[2]),
///     makeLink(&usageData[1], &usageData[3]),
///     makeLink(&usageData[2], 0            )  };
///
/// assert(Util::isWellFormed(      &usageData[0], &usageData[3]));
/// assert(4 == length(&usageData[0], &usageData[3]));
/// @endcode
/// Next, we create two new links `front` and `back`, and initialize them with
/// garbage:
/// @code
/// Link front = makeLink(invalid, invalid);
/// Link back  = makeLink(invalid, invalid);
/// @endcode
/// Then, we use our component's `insertLinkBeforeTarget` and
/// `insertLinkAfterTarget` to concatenate `front` to the front of the list and
/// `back` to its rear:
/// @code
/// Util::insertLinkBeforeTarget(&front, &usageData[0]);
/// Util::insertLinkAfterTarget( &back,  &usageData[3]);
/// @endcode
/// Next, We examine the new list and verify we now have a well-formed list, 2
/// longer than the old list:
/// @code
/// assert(0 == front.previousLink());
/// assert(0 == back .nextLink());
/// assert(Util::isWellFormed(          &front, &back));
/// assert(6 == length(&front, &back));
/// @endcode
/// Then, we use our component's `unlink` method to remove two nodes from our
/// list.  Note that the state of the removed nodes is undefined:
/// @code
/// Util::unlink(&usageData[1]);
/// Util::unlink(&usageData[3]);
/// @endcode
/// Next, we verify that the new list is well formed and 2 elements shorter than
/// it was before we removed those two nodes:
/// @code
/// assert(Util::isWellFormed(&front, &back));
/// assert(4 == length(&front, &back));
/// @endcode
/// Then, we weave the two discarded nodes into a new, second list of two nodes,
/// and use `isWellFormed` and `length` to verify it is as we expect:
/// @code
/// usageData[1] = makeLink(0, &usageData[3]);
/// usageData[3] = makeLink(&usageData[1], 0);
/// assert(Util::isWellFormed(&usageData[1], &usageData[3]));
/// assert(2 ==        length(&usageData[1], &usageData[3]));
/// @endcode
/// Next, we use our component's `spliceListBeforeTarget` method to remove the
/// middle nodes from the longer list and append them to the end of shorter
/// list.  Note that the splicing function not only adds the sequence to the new
/// list, it also splices the list the sequence is removed from so that both are
/// well-formed lists:
/// @code
/// Util::spliceListBeforeTarget(&usageData[0],
///                              &usageData[2],
///                              &usageData[3]);
/// @endcode
/// Then, we use `isWellFormed` and `length` to verify the state of our two
/// lists:
/// @code
/// assert(Util::isWellFormed(&usageData[1], &usageData[3]));
/// assert(4 ==        length(&usageData[1], &usageData[3]));
///
/// assert(Util::isWellFormed(&front, &back));
/// assert(2 ==        length(&front, &back));
/// @endcode
/// Next, we call `spliceListBeforeTarget` again to join our two lists into one:
/// @code
/// Util::spliceListBeforeTarget(&usageData[1],
///                              &usageData[3],
///                              &back);
/// @endcode
/// Now, we use `isWellFormed` and `length` to verify the state of our one
/// remaining list:
/// @code
/// assert(Util::isWellFormed(&front, &back));
/// assert(6 ==        length(&front, &back));
/// assert(0 == front.previousLink());
/// assert(0 == back .nextLink());
/// @endcode
/// Finally, we traverse our list in both directions, examining each node to
/// verify all the links and that the sequence is as expected:
/// @code
/// Link *p = &front;
/// assert(0 == p->previousLink());
/// p = p->nextLink();
/// assert(&usageData[1] == p);
/// p = p->nextLink();
/// assert(&usageData[0] == p);
/// p = p->nextLink();
/// assert(&usageData[2] == p);
/// p = p->nextLink();
/// assert(&usageData[3] == p);
/// p = p->nextLink();
/// assert(&back         == p);
/// assert(0 == p->nextLink());
///
/// p = p->previousLink();
/// assert(&usageData[3] == p);
/// p = p->previousLink();
/// assert(&usageData[2] == p);
/// p = p->previousLink();
/// assert(&usageData[0] == p);
/// p = p->previousLink();
/// assert(&usageData[1] == p);
/// p = p->previousLink();
/// assert(&front        == p);
/// assert(0 == p->previousLink());
/// @endcode
/// @}
/** @} */
/** @} */
 
/** @addtogroup bsl
 * @{
 */
/** @addtogroup bslalg
 * @{
 */
/** @addtogroup bslalg_bidirectionallinklistutil
 * @{
 */
 
#include <bslscm_version.h>
 
 
 
namespace bslalg {
 
class BidirectionalLink;
 
                        // ========================================
                        // struct bslalg::BidirectionalLinkListUtil
                        // ========================================
 
/// This `struct` provides a namespace for utility functions that manipulate
/// linked lists based on `bslalg::BidirectionalLink` nodes, including
/// insertion, removal, and *splicing*.
///
/// See @ref bslalg_bidirectionallinklistutil 
struct BidirectionalLinkListUtil {
 
    // CLASS METHODS
 
    /// Insert the specified `newNode` before the specified `target` node in
    /// the linked list that contains `target`.  If `target` is 0, then the
    /// value of the attributes `nextLink` and `previousLink` of `newNode`
    /// is set to 0.  After successful execution of this function the values
    /// of the `previousLink` and `nextLink` attributes of all the links in
    /// the list appropriately reflect the operation.  
    /// 
    /// \pre The behavior is undefined   unless `0 == target->previousLink()` is true or
    /// `isWellFormed(target->previousLink(), target)` is true.
    static
    void insertLinkBeforeTarget(BidirectionalLink *newNode,
                                BidirectionalLink *target);
 
    /// Insert the specified `newNode` after the specified `target` node in
    /// the linked list that contains `target`.  If the node following
    /// `target` is 0, then set the `nextLink` attribute of `newNode` to 0.
    /// After successful execution of this function the values of the
    /// `previousLink` and `nextLink` attributes of all the links in the
    /// list appropriately reflect the operation.  
    /// 
    /// \pre The behavior is undefined   unless `0 != newNode` and `0 != target`.  The behavior is also
    /// undefined unless `0 == target->nextLink()` is true or
    /// `isWellFormed(target, target->nextLink())` are true.
    static
    void insertLinkAfterTarget(BidirectionalLink *newNode,
                               BidirectionalLink *target);
 
    /// Return true if the bidirectional list starting from the specified
    /// `head`, and ending with the specified `tail` is well formed.  A
    /// bidirectional list is well formed if `tail == head` (0 values are
    /// allowed) or all of the following conditions are met (note that
    /// `head` is renamed to `h` and `tail` to `t` for brevity):
    ///
    /// 1. `h` and `t` are valid addresses.
    /// 2. `h->nextLink()->previousLink() == h` is true.
    /// 3. `!h->previousLink() || h->previousLink()->nextLink() == h`
    ///     is true.
    /// 4. `t->previousLink()->nextLink() == t` is true.
    /// 5. `!t->nextLink() || t->nextLink()->previousLink() == t`
    ///     is true.
    /// 6. For each `link` in the list different than `h` and `t` both
    ///    `link->nextLink()->previousLink() == link` and
    ///    `link->previousLink()->nextLink() == link` are true.
    ///
    /// 
    /// \pre The behavior is undefined  unless `tail` can be reached from `head`
    /// following the chain of `nextLink` attributes of all the nodes in the
    /// open range `[head, tail)`.
    static
    bool isWellFormed(BidirectionalLink *head, BidirectionalLink *tail);
 
    /// Unlink and move (splice) the elements of a doubly-linked list
    /// included in the closed range `[first, last]` out of their original
    /// list and into another doubly-linked list before the specified
    /// `target` node.  If `target` is 0, then the elements are extracted
    /// and form a new list such that `0 == first->previousLink()` and
    /// `0 == last->nextLink()`.  After successful execution of this
    /// function the values of the `previousLink` and `nextLink` attributes
    /// of all the links in the origin and destination lists appropriately reflect the operation.  
    /// 
    /// \pre The behavior is undefined   unless both
    /// `first` and `last` are non-zero members of the same linked list;
    /// `first` precedes `last` in the list, or `first == last`; `target` is
    /// not a node contained in the closed range `[first, last]`; and
    /// `isWellFormed(first, last)` is true.
    static
    void spliceListBeforeTarget(BidirectionalLink *first,
                                BidirectionalLink *last,
                                BidirectionalLink *target);
 
    /// Unlink the specified `node` from the linked list of which it is a
    /// member.  After successful execution of this function the values of
    /// the `previousLink` and `nextLink` attributes of all the links in the
    /// origin and destination lists appropriately reflect the operation 
    /// 
    /// \note Note that   this method does *not* change the value for the `nextLink`
    /// and `previousLink` attributes of `node`.  
    /// 
    /// \pre The behavior is undefined   unless `!node->previousLink()`, `!node->nextLink()`, or
    /// `isWellFormed(node->previousLink(), node->nextLink())` are true.
    static
    void unlink(BidirectionalLink *node);
};
 
}  // close package namespace
 
 
 
#endif
 
// ----------------------------------------------------------------------------
// Copyright 2013 Bloomberg Finance L.P.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// ----------------------------- END-OF-FILE ----------------------------------
 
/** @} */
/** @} */
/** @} */