nodes/node.h

   1 #ifndef NODE_CLASS
   2 #define NODE_CLASS
   3
   4 /*****************************************************************************\
   5 *                                                                             *
   6 *  Name   : node                                                              *
   7 *  Author : Chris Koeritz                                                     *
   8 *                                                                             *
   9 *******************************************************************************
  10 * Copyright (c) 1992-$now By Author.  This program is free software; you can  *
  11 * redistribute it and/or modify it under the terms of the GNU General Public  *
  12 * License as published by the Free Software Foundation; either version 2 of   *
  13 * the License or (at your option) any later version.  This is online at:      *
  14 *     http://www.fsf.org/copyleft/gpl.html                                    *
  15 * Please send any updates to: fred@gruntose.com                               *
  16 \*****************************************************************************/
  17
  18 #include <basis/definitions.h>
  19
  20 namespace nodes {
  21
  22 // forward:
  23 class node_link_amorph;
  24
  25 //! An object representing the interstitial cell in most linked data structures.
  26 /*!
  27   The node is intended as an extensible base class that provides general
  28   connectivity support.  Nodes can be connected to each other in
  29   arbitrary ways, but often a derived data type provides more structured
  30   organization.  When a node's link is zapped, only the connection is
  31   cut; no destruction is performed.
  32
  33   Examples: A linked list can be represented as a node with one link that
  34   connects to the succeeding item in the list.  A doubly linked list can
  35   be represented by a node with two links; one to the previous node and
  36   the other to the next node.  The most general structure might be an
  37   arbitrary graph that can connect nodes to any number of other nodes.
  38 */
  39
  40 class node : public virtual basis::root_object
  41 {
  42 public:
  43   node(int number_of_links = 0);
  44     //!< the constructor provides for "number_of_links" links initially.
  45     /*!< the table below gives some common numbers for links for a variety of
  46     data structures: @code
  47
  48     Links   Data Structure             Purpose of Link(s)
  49     ------  -------------------------  ----------------------------------
  50       1     singly linked list         points to next node in list
  51       2     doubly linked list         one to previous node, one to next
  52       2     binary tree                point to the two children
  53       n     n-ary tree                 point to the n children
  54      n+1    n-ary doubly linked tree   point to n children and 1 parent
  55       m     m-ary graph node           point to m relatives.
  56     @endcode */
  57
  58   virtual ~node();
  59     //!< the destructor simply invalidates the node.
  60     /*!< this does not rearrange the links as would be appropriate for a
  61     data structure in which only the node to be destroyed is being eliminated.
  62     policies regarding the correct management of the links must be made in
  63     objects derived from node. */
  64
  65   int links() const;
  66     //!< Returns the number of links the node currently holds.
  67
  68   void set_link(int link_number, node *new_link);
  69     //!< Connects the node "new_link" to this node.
  70     /*!< the previous link is lost, but not modified in any way.  the address
  71     of the new link is used directly--no copy of the node is made.  setting a
  72     link to a null node pointer clears that link. */
  73
  74   node *get_link(int link_number) const;
  75     //!< Returns the node that is connected to the specified "link_number".
  76     /*!< if the link is not set, then NULL_POINTER is returned. */
  77
  78   void zap_link(int link_number);
  79     //!< the specified link is removed from the node.
  80
  81   void insert_link(int where, node *to_add = NULL_POINTER);
  82     //!< adds a new link prior to the position specified in "where".
  83     /*!< thus a "where" value of less than or equal to zero will add a new
  84     link as the first element.  a "where" value greater than or equal to
  85     links() will add a new link after the last element.  the node "to_add"
  86     will be stored in the new link. */
  87
  88   int which(node *to_find) const;
  89     //!< locates the index where "to_find" lives in our list of links.
  90     /*!< returns the link number for a particular node that is supposedly
  91     connected to this node or common::NOT_FOUND if the node is not one
  92     of the children. */
  93
  94 private:
  95   node_link_amorph *_links;  //!< the list of connections to other nodes.
  96
  97   void set_empty(int link_number);
  98     //!< clears the link number specified.
  99
 100   // disallowed:
 101   node(const node &);
 102   node &operator =(const node &);
 103 };
 104
 105 //////////////
 106
 107 //! the basket class holds an object and supports connecting them as nodes.
 108 /*!
 109   the templated object is required to provide both a default constructor
 110   and a copy constructor.
 111 */
 112
 113 template <class contents>
 114 class basket : public node
 115 {
 116 public:
 117   basket(int links, const contents &to_store = contents())
 118           : node(links), _storage(to_store) {}
 119
 120   basket(const basket &to_copy) { *this = to_copy; }
 121
 122   basket &operator = (const contents &to_copy)
 123           { if (&to_copy != this) _storage = to_copy; return *this; }
 124
 125   const contents &stored() const { return _storage; }
 126     //!< allows a peek at the stored object.
 127   contents &stored() { return _storage; }
 128     //!< provides access to the stored object.
 129
 130 private:
 131   contents _storage;
 132 };
 133
 134 } // end namespace.
 135
 136 #endif
 137