GenericTreeNode.h File Reference

#include "pup.h"
#include <map>
#include <vector>
#include <algorithm>
#include <set>
#include <list>
#include "OrientedBox.h"
#include "MultipoleMoments.h"
#include "keytype.h"
#include "GravityParticle.h"

Go to the source code of this file.

Classes
class	Tree::GenericTreeNode
	Base class for tree nodes. More...
class	Tree::NodePool
	Utility to pool allocations of tree nodes. More...
class	Tree::BinaryTreeNode
	A TreeNode with two children. More...
class	Tree::OctTreeNode
	Class for Oct tree where each node has 8 direct children. More...
class	Tree::compare

Typedefs
typedef KeyType	Tree::NodeKey
	This key is the identification of a node inside the global tree, and it is unique for the node. This is used to lookup nodes in any hash or cache table.
typedef std::map< NodeKey, GenericTreeNode * >	Tree::NodeLookupType

Enumerations
enum	Tree::NodeType {   Invalid = 1 , Bucket , Internal , Boundary ,   NonLocal , Empty , Top , NonLocalBucket ,   Cached , CachedBucket , CachedEmpty }
	This enumeration determines the different types of node a GenericTreeNode can be.
enum	Tree::GenericTrees { Binary_Oct , Oct_Oct , Binary_ORB }

Functions
void	Tree::operator| (PUP::er &p, NodeType &nt)
	PUP a NodeType.
void	Tree::operator| (PUP::er &p, GenericTrees &gt)
	PUP a tree type.

Variables
int	Tree::numEmptyNodes
	A simple counter for how many nodes are empty - statistics.

Detailed Description

This file defines the generic tree structures.

Author

Filippo Gioachin (previously Graeme Lufkin and Chao Huang)

Version

2.0

Typedef Documentation

NodeKey

typedef KeyType Tree::NodeKey

This key is the identification of a node inside the global tree, and it is unique for the node. This is used to lookup nodes in any hash or cache table.

The position of the leftmost bit which is 1 represents the depth of the node into the tree, all the bits at its right describe the path of this node into the tree, and the bits at its left are clearly 0 and unused.

NodeLookupType

typedef std::map<NodeKey, GenericTreeNode *> Tree::NodeLookupType

A table of the nodes in my tree, indexed by their keys.

Todo

XXX: Make this lookup a hash table, so we get O(1) behavior instead of O(log N).

Enumeration Type Documentation

GenericTrees

enum Tree::GenericTrees

Possible types of trees: the first word means the physical structure used to implement the tree (Binary or Oct), the second work means the logic used to decompose the particles of the space amoung the nodes (Oct or ORB). Notice that the SFC domain decomposition builds an oct-tree!