Merge branch 'main' of feistymeow.org:feisty_meow
[feisty_meow.git] / 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