treeindexedD2node< INDX > Class Template Reference

Binary tree node with each node having an index. More...

#include <treeindexedD2.h>

Inheritance diagram for treeindexedD2node< INDX >:

Collaboration diagram for treeindexedD2node< INDX >:

List of all members.

Public Member Functions
boolc	isleaf () const
	Is this a leaf node?
boolc	isleft (INDX index2) const
	Is the node left?
boolc	isright (INDX index2) const
	Is the node right?
boolc	isleftinternal (INDX index2) const
	Is left an internal node?
boolc	isrightinternal (INDX index2) const
	Is right an internal node?
	treeindexedD2node ()
	Unconstructed, classed as a leaf.
	treeindexedD2node (INDX const index_)
	Construct a leaf.
	treeindexedD2node (treeindexedD2node *left_, treeindexedD2node *right_, INDX index_)
	Construct a node.
	~treeindexedD2node ()
	Memory cleanup if left and right are not zero.
void	unlink ()
	Set the left and right pointers to zero recursively down the tree.
	operator stringc () const
	Serialize this object by writing it out as a string.
void	printrecursive (string &s, INDX const parentindex, boolc branch) const
	Write the tree out as a linear list of nodes, where each node refers to a previous node.
void	swap ()
	Swap left and right.
void	nodecount (INDX &n)
	How many nodes are in the tree?
Public Attributes
treeindexedD2node *	left
	The left branch.
treeindexedD2node *	right
	The right branch.
INDX	index
	The index to either whats in a node or whats in a leaf.

---

Detailed Description

template<typename INDX>
class treeindexedD2node< INDX >

Binary tree node with each node having an index.

Nodes and leafs indexed independently from each other. A zero index value is used for writing out the tree when there is no node on that branch.

The client can use the index as a pointer to the real data structure. The tree manages the nodes assuming that they were created with new.

There are deliberately no virtual functions. If a very (Designed for a large number of treeindexedD2node's. The cost is that leafs do not use left or right and nodes may or may not using index depending on the application.

Definition at line 117 of file treeindexedD2.h.

---

Constructor & Destructor Documentation

template<typename INDX >

treeindexedD2node< INDX >::treeindexedD2node

(

)

[inline]

Unconstructed, classed as a leaf.

Definition at line 652 of file treeindexedD2.h.

  : left(0), right(0), index(0) 
{
}

template<typename INDX>

treeindexedD2node< INDX >::treeindexedD2node

(

INDX const

index_

)

[inline]

Construct a leaf.

Definition at line 658 of file treeindexedD2.h.

  : left(0), right(0), index(index_) 
{
}

template<typename INDX>

treeindexedD2node< INDX >::treeindexedD2node	(	treeindexedD2node< INDX > *	left_,
		treeindexedD2node< INDX > *	right_,
		INDX	index_
	)			[inline]

Construct a node.

Definition at line 665 of file treeindexedD2.h.

  : left(left_), right(right_), index(index_) 
{
}

template<typename INDX >

treeindexedD2node< INDX >::~treeindexedD2node

(

)

[inline]

Memory cleanup if left and right are not zero.

Definition at line 676 of file treeindexedD2.h.

References treeindexedD2node< INDX >::left, and treeindexedD2node< INDX >::right.

{ 
  delete left; 
  delete right; 
  left=0;
  right=0;
}

---

Member Function Documentation

template<typename INDX >

boolc treeindexedD2node< INDX >::isleaf

(

)

const [inline]

Is this a leaf node?

Definition at line 698 of file treeindexedD2.h.

References treeindexedD2node< INDX >::left, and treeindexedD2node< INDX >::right.

Referenced by treeindexedD2< INDX >::insert(), treeindexedD2node< INDX >::isleftinternal(), treeindexedD2node< INDX >::isrightinternal(), treeindexedD2node< INDX >::nodecount(), treeindexedD2iter< T >::operator++(), and bsptreeD2< PT, PD, INDX >::serializeInverse().

{ 
  return (left==0)&&(right==0); 
}

template<typename INDX>

boolc treeindexedD2node< INDX >::isleft

(

INDX

index2

)

const [inline]

Is the node left?

Definition at line 705 of file treeindexedD2.h.

References treeindexedD2node< INDX >::index, and treeindexedD2node< INDX >::left.

{
  if (left==0) return false;
  if (left->index==index2) return true;
  return false;
}

template<typename INDX>

boolc treeindexedD2node< INDX >::isleftinternal

(

INDX

index2

)

const [inline]

Is left an internal node?

Definition at line 721 of file treeindexedD2.h.

References treeindexedD2node< INDX >::index, treeindexedD2node< INDX >::isleaf(), and treeindexedD2node< INDX >::left.

{ 
  if (left==0) return false;
  if (left->index!=index2) return false;
  if (left->isleaf()) return false;
  return true;
}

template<typename INDX>

boolc treeindexedD2node< INDX >::isright

(

INDX

index2

)

const [inline]

Is the node right?

Definition at line 713 of file treeindexedD2.h.

References treeindexedD2node< INDX >::index, and treeindexedD2node< INDX >::right.

{ 
  if (right==0) return false;
  if (right->index==index2) return true;
  return false;
}

template<typename INDX>

boolc treeindexedD2node< INDX >::isrightinternal

(

INDX

index2

)

const [inline]

Is right an internal node?

Definition at line 730 of file treeindexedD2.h.

References treeindexedD2node< INDX >::index, treeindexedD2node< INDX >::isleaf(), and treeindexedD2node< INDX >::right.

{ 
  if (right==0) return false;
  if (right->index!=index2) return false;
  if (right->isleaf()) return false;
  return true;
}

template<typename INDX>

void treeindexedD2node< INDX >::nodecount

(

INDX &

n

)

[inline]

How many nodes are in the tree?

Definition at line 639 of file treeindexedD2.h.

References treeindexedD2node< INDX >::isleaf(), treeindexedD2node< INDX >::left, treeindexedD2node< INDX >::nodecount(), and treeindexedD2node< INDX >::right.

Referenced by treeindexedD2node< INDX >::nodecount().

{
  if (isleaf())
    return;

  ++n;
  if (left!=0)
    left->nodecount(n);
  if (right!=0)
    right->nodecount(n);
}

template<typename INDX >

treeindexedD2node< INDX >::operator stringc

(

)

const [inline]

Serialize this object by writing it out as a string.

Definition at line 568 of file treeindexedD2.h.

References treeindexedD2node< INDX >::index, treeindexedD2node< INDX >::left, and treeindexedD2node< INDX >::right.

{
  stringstream ss;
  ss << index << " ";
  if (left)
  {
    ss << left->index;

    if (right)
    {
      ss << " " << right->index;
    }
    else
    {
      ss << " 0";
    }
  }
  else
  {
    ss << "0 ";
    if (right)
    {
      ss << " " << right->index;
    }
    else
    {
      ss << " 0";
    }
  }

  return ss.str();
}

template<typename INDX>

void treeindexedD2node< INDX >::printrecursive	(	string &	s,
		INDX const	parentindex,
		boolc	branch
	)			const [inline]

Write the tree out as a linear list of nodes, where each node refers to a previous node.

For uniques then parents branch that points to this node is needed.

Definition at line 603 of file treeindexedD2.h.

{
  s += (stringc)*this;

  {
    stringstream ss;
    ss << parentindex;

    s += " ";
    s += ss.str();
  }

  if (branch==false)
    s += " 0";
  else
    s += " 1";

  if ((left!=0)||(right!=0))
    s += '\n';
  if (left!=0)
  {
    if (left->isleaf()==false)
      left->printrecursive(s,index,false);
  }
  if (right!=0)
  {
    if (right->isleaf()==false)
      right->printrecursive(s,index,true);
  }
}

template<typename INDX >

void treeindexedD2node< INDX >::swap

(

)

[inline]

Swap left and right.

Definition at line 686 of file treeindexedD2.h.

References treeindexedD2node< INDX >::left, and treeindexedD2node< INDX >::right.

{ 
  treeindexedD2node * tmp=left; 
  right=left; 
  left=tmp; 
}

template<typename INDX >

void treeindexedD2node< INDX >::unlink

(

)

[inline]

Set the left and right pointers to zero recursively down the tree.

Definition at line 550 of file treeindexedD2.h.

References treeindexedD2node< INDX >::left, treeindexedD2node< INDX >::right, and treeindexedD2node< INDX >::unlink().

Referenced by treeindexedD2node< INDX >::unlink().

{
  treeindexedD2node<INDX> * p;
  p = left;
  if (left!=0)
  {
    left=0;
    p->unlink();
  }
  p = right;
  if (right!=0)
  {
    right=0;
    p->unlink();
  }
}

---

Member Data Documentation

template<typename INDX>

INDX treeindexedD2node< INDX >::index

The index to either whats in a node or whats in a leaf.

Definition at line 126 of file treeindexedD2.h.

Referenced by treeindexedD2< INDX >::insert(), treeindexedD2node< INDX >::isleft(), treeindexedD2node< INDX >::isleftinternal(), treeindexedD2node< INDX >::isright(), treeindexedD2node< INDX >::isrightinternal(), treeindexedD2node< INDX >::operator stringc(), and bsptreeD2< PT, PD, INDX >::serializeInverse().

template<typename INDX>

treeindexedD2node* treeindexedD2node< INDX >::left

The left branch.

Definition at line 122 of file treeindexedD2.h.

Referenced by treeindexedD2< INDX >::insert(), treeindexedD2node< INDX >::isleaf(), treeindexedD2node< INDX >::isleft(), treeindexedD2node< INDX >::isleftinternal(), treeindexedD2node< INDX >::nodecount(), treeindexedD2node< INDX >::operator stringc(), treeindexedD2iter< T >::operator++(), bsptreeD2< PT, PD, INDX >::serializeInverse(), treeindexedD2node< INDX >::swap(), treeindexedD2node< INDX >::unlink(), and treeindexedD2node< INDX >::~treeindexedD2node().

template<typename INDX>

treeindexedD2node* treeindexedD2node< INDX >::right

The right branch.

Definition at line 124 of file treeindexedD2.h.

Referenced by treeindexedD2< INDX >::insert(), treeindexedD2node< INDX >::isleaf(), treeindexedD2node< INDX >::isright(), treeindexedD2node< INDX >::isrightinternal(), treeindexedD2node< INDX >::nodecount(), treeindexedD2node< INDX >::operator stringc(), treeindexedD2iter< T >::operator++(), bsptreeD2< PT, PD, INDX >::serializeInverse(), treeindexedD2node< INDX >::swap(), treeindexedD2node< INDX >::unlink(), and treeindexedD2node< INDX >::~treeindexedD2node().

---

The documentation for this class was generated from the following file:

• bsptrees/treeindexedD2.h