ChangeTree.h

//========================================================================================
// 
// $File$
// 
// Owner: Ryan Gano
// 
// $Author$
// 
// $DateTime$
// 
// $Revision$
// 
// $Change$
// 
// Copyright 1997-2010 Adobe Systems Incorporated. All rights reserved.
// 
// NOTICE: Adobe permits you to use, modify, and distribute this file in accordance 
// with the terms of the Adobe license agreement accompanying it. If you have received
// this file from a source other than Adobe, then your use, modification, or 
// distribution of it requires the prior written permission of Adobe.
// 
//========================================================================================

#ifndef __ChangeTree__
#define __ChangeTree__

#include "TreeNode.h"
#include <map>
#ifdef DEBUG
//#define VALIDATE_TREE
#endif
#ifdef VALIDATE_TREE
#include <queue>
#include <boost/bind.hpp>
#endif

template<class ItemType>
class ChangeTree
{
public:
 typedef TreeNode<ItemType> Node;
 
 ChangeTree() : fRoot(nil) {}

 ChangeTree(const ChangeTree &o);

 ~ChangeTree()
 {
 if (fRoot != nil)
 Remove(fRoot);
 }

 ChangeTree &operator=(const ChangeTree &o);

 void swap(ChangeTree &o);

 int size() const;

 void CloneBranch(Node *myStart, const Node *otherStart);

 void Insert(Node *node, Node *parent);

 void Remove(Node *node);

 Node *find(ItemType item);

 Node *GetRoot();

private:

 Node *fRoot;

 typedef std::map<ItemType, Node *> NodeMap;
 NodeMap fLookup;

public:
#ifdef VALIDATE_TREE 
 // Validator for fLookup map -- check for fRoot's tree and fLookup being out of sync 
 template<class SameItemType>
 class ChangeTreeValidator : public std::unary_function<SameItemType, void>
 {
 public:
 ChangeTreeValidator(NodeMap lookup, Node *root) : fMyLookup(lookup),fMyRoot(root)
 {
 //ASSERT(fMyRoot != nil);
 }
 void operator()()
 {
 typename NodeMap::iterator iter;
 for (iter = fMyLookup.begin(); iter != fMyLookup.end(); ++iter)
 {
 // Check fMyRoot and its descendants for a match on current iter
 std::queue<Node*> treeQueue;
 treeQueue.push(fMyRoot);
 Node* targetNode = iter->second;
 bool16 bFound = kFalse;
 while (!treeQueue.empty())
 {
 // Get the current node
 Node *curNode = treeQueue.front();
 treeQueue.pop();
 
 if (curNode->fItem == targetNode->fItem)
 {
 bFound = kTrue;
 break; // Found map item in tree... this is good
 }
 // Add its direct descendents to the queue
 std::for_each(curNode->fChildren.begin(), curNode->fChildren.end(), boost::bind(&std::queue<Node*>::push, &treeQueue, _1));
 }
 ASSERT_MSG(bFound, "ChangeTree out of sync -- some fLookup node not found in fRoot's tree!");
 }
 }
 
 // void operator()(ItemType const& item);
 private:
 Node *fMyRoot;
 NodeMap fMyLookup;
 };
#endif

};
#endif