Hierarchy container?

Is there any container class that can arrange objects into a hierarchy, in such a way that each object in the hierarchy knows that's above it, what's below it, what's next to it, etc?

Thanks,
wannaB_geek

Binary Tree comes to mind.

A binary tree just puts objects into a hierarchy for accessibility purposes. What I need is a container that allows you to create a specific hierarchy, more like an org-chart type of hierarchy.

Does anyone know of such a container class exists?

Thanks,
wannaB_geek

As a standard container in STL or C/C++, probably not. Has anybody ever made such a container, maybe. Could you make such a container? Depends on your skill level. If you can't, your chances of getting good advice/assistance are excellent if you can describe exactly what you want, and demonstrate a good faith effort on your part. I suspect it will be some sort of a tree, though. Maybe with nodes like this:

struct Node
{
string title;
list<Node *> underlings;
}

A tree is perhaps not general enough. If I had time, I might elaborate a bit on a type of structure you seem to be looking for, but for now, I'll just point you toward a term to search for: directed acyclic graph or DAG. Essentially, you have nodes, and you have uni-directional connections between nodes. There are a host of algorithms you can use to find properties or search them. The book Introduction to Algorithms by Rivest et al has some bits about graph algorithms, though there are certainly other (less pricey) places to get the information. There is a book published by Dover called Graph Theory on the subject of graphs. More theoretical and less practical, but, being a Dover book, it is rather affordable.

Cheers

Here's a rough framework of what I'm trying to do:

The tree class would provide the structure for the hierarchy, in addition to pointers to relatives. It would function somewhat like a forking linked list.

Code:

---

template <T>

class Tree <T> {
  T myObject;  // the object at the current level
  Tree<T>* parent;  // the parent object
  /* sorry, I'm kinda new at this.  Is the correct syntax for a pointer
  * to a container Tree<T>* or Tree*<T> ? */
  std::vector<Tree<T>*> children;    // the child objects
  std::vector<Tree<T>>::iterator sibling;
  /*  The sibling iterator should point to the first object in the
    *  parent tree's child vector */
  Tree<T>* top;
  freind T;  // is this legal?
  // friend Leaf<T> // if I use the Leaf class (below)
  // various methods
}

---

The most difficult part (it seems to me anyway) would be the means of interfacing between the Tree (structure) and the objects themselves.
One possibility that comes to mind is to create a seperate interface class:

Code:

---

template <T>;

class Leaf<T> {
  T myObject;  // the current object
  // put in references to Tree member variables
  // put in interface functions
}

---

This would allow the Tree class to provide the structure while the Leaf class would provide a way for the object itself and the Leaf class to provide the interface between the objects themselves and the Tree or another object managing the Tree and the Tree.
This would provide the added benifit of letting the object itself be independent of the Tree.

The other part I'm wondering about, which I'm not really sure how to do, is how to keep the tree accurate (when something is moved, does everything connected to it know that it's been moved?).

Does what I'm doing so far look like it will work?

In terms of a DAG, what I need for this particular purpose is just a tree hierarchy. It also seems to me that a Tree class decended from a DAG class wouldn't be as efficient as one built by itself.

Thanks for all your help,
WannaB_Geek.

If you've never written a tree class before, a leaf is usually defined as a node with no children and the root as a node with no parent. The interaction between node and container comes with the tree class methods, just like in a list class.

Here is a link to a Binary Tree tutorial: http://www.cprogramming.com/tutorial/lesson18.html
While this isn't exactly what you are looking for, you can probably learn a good bit from it.

As far as destroying a node, consider this: You have a node you want to destroy. You know its parent (even if it is NULL), and you know its children. When you destroy the node, you'll lose parts of the tree unless you make sure that some connection from the parent of the deleted node to the children of the deleted node is put in place.

Also, the root, the middle, and the leaf nodes are generally all members of the same class with NULL links in the appropriate places, but if you really wanted to make them separate classes, they should at least derive from a common base class. Note that this would make attaching things to a leaf node more complicated than necessary, though.

Also, your template syntax is a bit off. Here are two equivalent examples:

Code:

---

template<class T>
struct foo
{
};

template<typename T>
struct bar
{
};

---

Cheers