An object representing the interstitial cell in most linked data structures. More...

#include <node.h>

Inheritance diagram for nodes::node:

[legend]

Collaboration diagram for nodes::node:

Public Member Functions
	node (int number_of_links=0)
	the constructor provides for "number_of_links" links initially. More...

virtual	~node ()
	the destructor simply invalidates the node. More...

int	links () const
	Returns the number of links the node currently holds. More...

void	set_link (int link_number, node *new_link)
	Connects the node "new_link" to this node. More...

node *	get_link (int link_number) const
	Returns the node that is connected to the specified "link_number". More...

void	zap_link (int link_number)
	the specified link is removed from the node. More...

void	insert_link (int where, node *to_add=NULL_POINTER)
	adds a new link prior to the position specified in "where". More...

int	which (node *to_find) const
	locates the index where "to_find" lives in our list of links. More...

Detailed Description

An object representing the interstitial cell in most linked data structures.

The node is intended as an extensible base class that provides general connectivity support. Nodes can be connected to each other in arbitrary ways, but often a derived data type provides more structured organization. When a node's link is zapped, only the connection is cut; no destruction is performed.

Examples: A linked list can be represented as a node with one link that connects to the succeeding item in the list. A doubly linked list can be represented by a node with two links; one to the previous node and the other to the next node. The most general structure might be an arbitrary graph that can connect nodes to any number of other nodes.

Definition at line 40 of file node.h.

Constructor & Destructor Documentation

◆ node()

nodes::node::node ( int number_of_links = 0 )

the constructor provides for "number_of_links" links initially.

the table below gives some common numbers for links for a variety of data structures:

Links   Data Structure             Purpose of Link(s)
------  -------------------------  ----------------------------------
  1     singly linked list         points to next node in list
  2     doubly linked list         one to previous node, one to next
  2     binary tree                point to the two children
  n     n-ary tree                 point to the n children
 n+1    n-ary doubly linked tree   point to n children and 1 parent
  m     m-ary graph node           point to m relatives.

Definition at line 41 of file node.cpp.

◆ ~node()

nodes::node::~node ( )

virtual

the destructor simply invalidates the node.

this does not rearrange the links as would be appropriate for a data structure in which only the node to be destroyed is being eliminated. policies regarding the correct management of the links must be made in objects derived from node.

Definition at line 45 of file node.cpp.

References basis::WHACK().

Member Function Documentation

◆ get_link()

node * nodes::node::get_link ( int link_number ) const

Returns the node that is connected to the specified "link_number".

if the link is not set, then NULL_POINTER is returned.

Definition at line 85 of file node.cpp.

References bounds_return, and NULL_POINTER.

◆ insert_link()

void nodes::node::insert_link	(	int	where,
		node *	to_add = `NULL_POINTER`
	)

adds a new link prior to the position specified in "where".

thus a "where" value of less than or equal to zero will add a new link as the first element. a "where" value greater than or equal to links() will add a new link after the last element. the node "to_add" will be stored in the new link.

Definition at line 74 of file node.cpp.

References links(), and set_link().

Referenced by nodes::doubly_linked_list::append(), nodes::tree::attach(), nodes::tree::insert(), and nodes::doubly_linked_list::insert().

◆ links()

int nodes::node::links ( ) const

Returns the number of links the node currently holds.

Definition at line 51 of file node.cpp.

Referenced by nodes::doubly_linked_list::append(), nodes::tree::attach(), nodes::tree::branches(), nodes::tree::insert(), nodes::doubly_linked_list::insert(), insert_link(), and which().

◆ set_link()

void nodes::node::set_link	(	int	link_number,
		node *	new_link
	)

Connects the node "new_link" to this node.

the previous link is lost, but not modified in any way. the address of the new link is used directly–no copy of the node is made. setting a link to a null node pointer clears that link.

Definition at line 62 of file node.cpp.

References test_arg.

Referenced by nodes::doubly_linked_list::append(), nodes::tree::attach(), nodes::doubly_linked_list::doubly_linked_list(), nodes::tree::insert(), nodes::doubly_linked_list::insert(), insert_link(), nodes::tree::prune_index(), nodes::doubly_linked_list::remove(), nodes::singly_linked_list::set_next(), and nodes::tree::tree().

◆ which()

int nodes::node::which ( node * to_find ) const

locates the index where "to_find" lives in our list of links.

returns the link number for a particular node that is supposedly connected to this node or common::NOT_FOUND if the node is not one of the children.

Definition at line 91 of file node.cpp.

References get_link(), and links().

Referenced by nodes::tree::which().

◆ zap_link()

void nodes::node::zap_link ( int link_number )

the specified link is removed from the node.

Definition at line 68 of file node.cpp.