// ---------------------------------------------------------------------------
//  Includes for all the program files to see
// ---------------------------------------------------------------------------
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <xercesc/util/PlatformUtils.hpp>

// ---------------------------------------------------------------------------
//  Includes
// ---------------------------------------------------------------------------
#include <xercesc/framework/StdInInputSource.hpp>
#include <xercesc/parsers/SAXParser.hpp>
#include <xercesc/util/OutOfMemoryException.hpp>

// ---------------------------------------------------------------------------
//  Includes
// ---------------------------------------------------------------------------
#include <xercesc/sax/AttributeList.hpp>
#include <xercesc/sax/SAXParseException.hpp>
#include <xercesc/sax/SAXException.hpp>

#include "ViewCellsParser.h"

#include "ViewCellsParserXerces.h"
#include "Mesh.h"
#include "VspBspTree.h"
#include "ViewCellBsp.h"
#include "ViewCellsManager.h"
#include "GzFileInputSource.h"
#include "OspTree.h"
#include "VspTree.h"
#include "KdTree.h"
#include "BvHierarchy.h"
#include "HierarchyManager.h"


using namespace std;

namespace GtpVisibilityPreprocessor {


// ---------------------------------------------------------------------------
//  Local data
//
//  doNamespaces
//      Indicates whether namespace processing should be enabled or not.
//      The default is no, but -n overrides that.
//
//  doSchema
//      Indicates whether schema processing should be enabled or not.
//      The default is no, but -s overrides that.
//
//  schemaFullChecking
//      Indicates whether full schema constraint checking should be enabled or not.
//      The default is no, but -s overrides that.
//
//  valScheme
//      Indicates what validation scheme to use. It defaults to 'auto', but
//      can be set via the -v= command.
// ---------------------------------------------------------------------------
static bool doNamespaces = false;
static bool doSchema = false;
static bool schemaFullChecking = false;
static SAXParser::ValSchemes valScheme = SAXParser::Val_Auto;

// hack for loading bvh nodes
#define PVS_HACK 0
#define USE_HASH_COMPARE 1


inline static bool ilt(Intersectable *obj1, Intersectable *obj2)
{
	return obj1->mId < obj2->mId;
}


// ---------------------------------------------------------------------------
//  StdInParseHandlers: Constructors and Destructor
// ---------------------------------------------------------------------------
ViewCellsParseHandlers::ViewCellsParseHandlers(ObjectContainer &pvsObjects, 
											   ObjectContainer &preprocessorObjects,
											   BoundingBoxConverter *bconverter
											   ):
  mElementCount(0)
  , mAttrCount(0)
  , mCharacterCount(0)
  , mSpaceCount(0)
  , mViewCellsManager(NULL)
  , mVspBspTree(NULL)
  , mBspTree(NULL)
  , mViewCellsTree(NULL)
  , mCurrentState(PARSE_OPTIONS)
  , mCurrentViewCell(NULL)
  , mCurrentBspNode(NULL)
  , mCurrentVspNode(NULL)
  , mCurrentOspNode(NULL)
  , mCurrentBvhNode(NULL)
  , mPvsObjects(pvsObjects)
  , mPreprocessorObjects(preprocessorObjects)
  , mBoundingBoxConverter(bconverter)
  , mHierarchyManager(NULL)
  , nViewCells(0)
  , nObjects(0)
{
}


ViewCellsParseHandlers::~ViewCellsParseHandlers()
{
}


void ViewCellsParseHandlers::CreateHashVector()
{
	ObjectContainer::const_iterator oit, oit_end = mPvsObjects.end();

	for (oit = mPvsObjects.begin(); oit != oit_end; ++ oit)
	{
		mHashPvs[(*oit)->GetId()] = (*oit);
	}
	//Debug<<"\nhsize: " << mHashPvs.size() << endl;
}


// ---------------------------------------------------------------------------
//  StdInParseHandlers: Implementation of the SAX DocumentHandler interface
// ---------------------------------------------------------------------------


void ViewCellsParseHandlers::endElement(const XMLCh* const name)
{
	StrX lname(name);
	string element(lname.LocalForm());

	if (element == "BoundingBoxes")
	{
		EndBoundingBoxes();
	}
	else if (element == "ViewCells")
	{	
		EndViewCells();
		Debug << "view cell hierarchy parsed" << endl;
	}
	else if (element == "ObjectSpaceHierarchy")
	{
		EndObjectSpaceHierarchy();
		Debug << "object space hierarchy parsed" << endl;
#ifdef PERFTIMER  
		mObjectTimer.Exit();
#endif
	}
	// finished paring, create view cells manager
	else if (element == "VisibilitySolution")
	{
		CreateViewCellsManager();

#ifdef PERFTIMER  
		Debug << "pvs time: " << mPvsTimer.TotalTime() << endl;
		Debug << "object time: " << mObjectTimer.TotalTime() << endl;
		Debug << "box time: " << mBoxTimer.TotalTime() << endl;
#endif
	}
	else if (element == "Interior")
	{
		switch (mCurrentState)
		{
		case PARSE_VIEWCELLS:
			EndViewCellInterior();
			break;
		case PARSE_OBJECTSPACE_HIERARCHY:
			EndObjectSpaceHierarchyInterior();
			break;
		case PARSE_VIEWSPACE_HIERARCHY:	
			EndViewSpaceHierarchyInterior();
			break;
		default:
			break;
		}
	}
}


void ViewCellsParseHandlers::EndObjectSpaceHierarchy()
{
	if (mObjectSpaceHierarchyType == OSP)
	{
		// for a spatial subdivision, it is not necessary to store
		// the objects with the leaves, they can be classified geometrically
		mHierarchyManager->mOspTree->
			InsertObjects(mHierarchyManager->mOspTree->mRoot, mPvsObjects);
	}
}


void ViewCellsParseHandlers::EndViewSpaceHierarchyInterior()
{
	switch (mViewSpaceHierarchyType)
	{
	case BSP:
		EndBspInterior();
		break;
	case VSP:
		EndVspInterior();
		break;	
	default:
		Debug << "not implemented view space hierarchy type " << mViewSpaceHierarchyType << endl;
		break;
	}
}


void ViewCellsParseHandlers::EndObjectSpaceHierarchyInterior()
{
	switch (mObjectSpaceHierarchyType)
	{
	case OSP:
		EndOspInterior();
		break;
	case BVH:
		EndBvhInterior();
		break;	
	default:
		Debug << "not implemented object space hierarchy type " << mViewSpaceHierarchyType << endl;
		break;
	}
}


void ViewCellsParseHandlers::EndBspInterior()
{
	// go one up in the tree
	if (mCurrentBspNode->GetParent())
	{	//cout << "]";
		mCurrentBspNode = mCurrentBspNode->GetParent();
	}
}


void ViewCellsParseHandlers::EndBvhInterior()
{
	// go one up in the tree
	if (mCurrentBvhNode->GetParent())
	{	//cout << "]";
		mCurrentBvhNode = mCurrentBvhNode->GetParent();
	}
}


void ViewCellsParseHandlers::EndOspInterior()
{
	// go one up in the tree
	if (mCurrentOspNode->mParent)
	{	
		//cout << "]";
		mCurrentOspNode = mCurrentOspNode->mParent;
	}
}


void ViewCellsParseHandlers::EndVspInterior()
{
	// go one up in the tree
	if (mCurrentVspNode->GetParent())
	{	
		//cout << "]";
		mCurrentVspNode = mCurrentVspNode->GetParent();
	}
}


void ViewCellsParseHandlers::EndViewCellInterior()
{
	// go one up in the tree
	if (mCurrentViewCell->GetParent())
	{	
		//cout << "]";
		mCurrentViewCell = mCurrentViewCell->GetParent();
	}
}


inline static bool vlt(ViewCell *v1, ViewCell *v2)
{
	return v1->mId < v2->mId;
}


void ViewCellsParseHandlers::EndViewCells()
{
	// sort view cells to help associating view cells according to their id
	sort(mViewCells.begin(), mViewCells.end(), vlt);

	// not parsing view cells anymore
	mCurrentState = PARSE_OPTIONS;
}


void ViewCellsParseHandlers::EndBoundingBoxes()
{
	const long startTime = GetTime();
	
#ifdef PERFTIMER  
	mBoxTimer.Entry();
#endif
	if (mBoundingBoxConverter)
	{
		// all bounding boxes gathered in this step => 
		// associate object ids with bounding boxes
		mBoundingBoxConverter->IdentifyObjects(mIBoundingBoxes, mPvsObjects);
	}

	if (USE_HASH_COMPARE)
	{
		CreateHashVector();
	}
	else
	{
		// sort objects by id
		sort(mPvsObjects.begin(), mPvsObjects.end(), ilt);
	}

	Debug << "\nconverted bounding boxes to objects in "
		  << TimeDiff(startTime, GetTime()) * 1e-6 << " secs" << endl;

#ifdef PERFTIMER  
	mBoxTimer.Exit();
#endif
}


void ViewCellsParseHandlers::StartBspElement(string element,
											 AttributeList& attributes)
{
	if (element == "Interior") 
	{
		//cout << "[";
		StartBspInterior(attributes);
	}

	if (element == "Leaf") 
	{
		//cout << "l";
		StartBspLeaf(attributes);
	}
}


void ViewCellsParseHandlers::StartVspElement(string element,
											 AttributeList& attributes)
{
	if (element == "Interior") 
	{
		//cout << "[";
		StartVspInterior(attributes);
	}
	if (element == "Leaf") 
	{
		//cout << "l";
		StartVspLeaf(attributes);
	}
}


void ViewCellsParseHandlers::StartOspElement(string element,
											 AttributeList& attributes)
{
	if (element == "Interior") 
	{
		//cout << "[";
		StartOspInterior(attributes);
	}

	if (element == "Leaf") 
	{
		//cout << "l";
		StartOspLeaf(attributes);
	}
}


void ViewCellsParseHandlers::StartBvhElement(string element,
											 AttributeList& attributes)
{
	if (element == "Interior") 
	{
		//cout << "[";
		StartBvhInterior(attributes);
	}

	if (element == "Leaf") 
	{
		//cout << "l";
		StartBvhLeaf(attributes);
	}
}


void ViewCellsParseHandlers::StartViewSpaceHierarchyElement(const std::string &element,
															AttributeList& attributes)
{
	//-- use cell type according to the chosen method
	switch (mViewSpaceHierarchyType)
	{
	case BSP:
		StartBspElement(element, attributes);
		break;
	case VSP:
		StartVspElement(element, attributes);
		break;
	default:
		Debug << "not implemented" << endl;
		break;
	}
}


void ViewCellsParseHandlers::StartObjectSpaceHierarchyElement(const std::string &element,
															  AttributeList& attributes)
{
	//-- use cell type according to the chosen method
	switch (mObjectSpaceHierarchyType)
	{
		case OSP:
			StartOspElement(element, attributes);
			break;
		case BVH:
			StartBvhElement(element, attributes);
			break;
		default:
			Debug << "not implemented" << endl;
			break;
	}
}


void ViewCellsParseHandlers::StartViewCellHierarchyElement(const std::string &element,
														   AttributeList& attributes)
{
	// interiors + leaves interpreted view cells else
	if (element == "Interior") 
	{
		StartViewCell(attributes, false);
		return;
	}

	if (element == "Leaf") 
	{
		StartViewCell(attributes, true);
		return;
	}

	Debug << "StartViewCellHierarchyElement: should not come here: " << element << endl;
}


void ViewCellsParseHandlers::startElement(const XMLCh* const name,
										  AttributeList& attributes)
{
	StrX lname(name);
	string element(lname.LocalForm());

	if (element == "ViewCells")
	{
		cout << "\nparsing view cells" << endl;
		Debug << "\nparsing view cells" << endl;
		
		mCurrentState = PARSE_VIEWCELLS;

		// create new view cells hierarchy
		mViewCellsTree = new ViewCellsTree();
	}
	// decides about the view cell hierarchy
	else if (element == "ViewSpaceHierarchy")
	{		
		Debug << "\nparsing view space hierarchy" << endl;
		cout  << "\nparsing view space hierarchy" << endl;

		mCurrentState = PARSE_VIEWSPACE_HIERARCHY;
		StartViewSpaceHierarchy(attributes);
	}
	// decides about the view cell hierarchy
	else if (element == "ObjectSpaceHierarchy")
	{
		cout  << "\nparsing object space hierarchy" << endl;
		Debug << "\nparsing object space hierarchy" << endl;

		mCurrentState = PARSE_OBJECTSPACE_HIERARCHY;
#ifdef PERFTIMER  
		mObjectTimer.Entry();
#endif
		StartObjectSpaceHierarchy(attributes);
	}
	// decides the used view cell hierarchy
	else if (element == "BoundingBox")
	{
		StartBoundingBox(attributes);
	}
	else
	{
		// parse view space hierarchy
		switch (mCurrentState)
		{
		case PARSE_VIEWSPACE_HIERARCHY:
			if ((++ nViewCells % 1000) == 0)
			{
				cout << "\r" << nViewCells << " view cells parsed\r";
				Debug << nViewCells << " view cells parsed" << endl;
			}
			StartViewSpaceHierarchyElement(element, attributes);
			break;
		case PARSE_OBJECTSPACE_HIERARCHY:
			if ((++ nObjects % 1000) == 0)
				cout <<"\r" << nObjects << " objects parsed\r";
		
			StartObjectSpaceHierarchyElement(element, attributes);
			break;
		case PARSE_VIEWCELLS:
			StartViewCellHierarchyElement(element, attributes);
			break;
		default:
			break;
		}
	}
	
	++ mElementCount;
	mAttrCount += attributes.getLength();
}


void ViewCellsParseHandlers::StartViewCellPvs(ObjectPvs &pvs, const char *ptr)
{
	// handle object indices
	vector<int> objIndices;
	char *endptr;
			
	while (1)
	{	
		// read object ids
		const int index = strtol(ptr, &endptr, 10);
		
		if (ptr == endptr) 
			break;
		
		objIndices.push_back(index);
		ptr = endptr;
	}

#ifdef PERFTIMER  
	mPvsTimer.Entry();
#endif
	Intersectable::NewMail();

	// TODO: 
	// 1) find objects and add them to pvs
	// 2) get view cell with specified id
	MeshInstance dummyInst(NULL);
	pair<ObjectContainer::const_iterator, ObjectContainer::const_iterator> result;

	vector<int>::const_iterator it, it_end = objIndices.end();
	
	for (it = objIndices.begin(); it != it_end; ++ it)
	{
		const int objId = *it;	
	
#if USE_HASH_COMPARE
		pvs_hash::iterator oit = mHashPvs.find(objId);

		if ((oit != mHashPvs.end()) && ((*oit).second->GetId() == objId))
		{
			pvs.AddSample((*oit).second, 1.0f);
		}
#else
	#if 0
		dummyInst.SetId(objId);

		ObjectContainer::iterator oit =	
							lower_bound(mPvsObjects.begin(), 
										mPvsObjects.end(), 
										(Intersectable *)&dummyInst, 
										ilt);	

		if ((oit != mPvsObjects.end()) && ((*oit)->GetId() == objId))
		{
			pvs.AddSample(*oit, 1.0f);
		}
	#else
		pvs.AddSample(mPvsObjects[objId], 1.0f);
	#endif
#endif
	}
	
#ifdef PERFTIMER  
	mPvsTimer.Exit();
#endif
}


void ViewCellsParseHandlers::StartViewSpaceHierarchy(AttributeList& attributes)
{
	int len = attributes.getLength();

	Vector3 bmin, bmax;

	for (int i = 0; i < len; ++ i) 
	{
		string attrName(StrX(attributes.getName(i)).LocalForm());
		StrX attrValue(attributes.getValue(i));
		const char *ptr = attrValue.LocalForm();

		// hierarchy type
		if (attrName == "type")
		{
			if (strcmp(ptr, "bsp") == 0)
			{
				Debug << "\nview space hierarchy: Bsp" << endl;
				mViewSpaceHierarchyType = BSP;
			}
			else if (strcmp(ptr, "vsp") == 0)
			{
				Debug << "\nview space hierarchy: Vsp" << endl;
				mViewSpaceHierarchyType = VSP;
			}
		}
		else if (attrName == "min") // the view space extent
		{
			sscanf(ptr, "%f %f %f",
				   &bmin.x, &bmin.y, &bmin.z);
		}
		else if (attrName == "max") 
		{
			sscanf(ptr, "%f %f %f",
				   &bmax.x, &bmax.y, &bmax.z);
		}
	}

	mViewSpaceBox = AxisAlignedBox3(bmin, bmax);

	// create the hierarchy based on this information
	CreateViewSpaceHierarchy();
}


void ViewCellsParseHandlers::StartObjectSpaceHierarchy(AttributeList& attributes)
{
	const int len = attributes.getLength();
	Vector3 bmin, bmax;

	for (int i = 0; i < len; ++ i) 
	{
		string attrName(StrX(attributes.getName(i)).LocalForm());
		StrX attrValue(attributes.getValue(i));
		const char *ptr = attrValue.LocalForm();

		// hierarchy type
		if (attrName == "type")
		{
			if (strcmp(ptr, "osp") == 0)
			{
				Debug << "\nobject space hierarchy: Osp" << endl;

				mHierarchyManager = 
					new HierarchyManager(HierarchyManager::KD_BASED_OBJ_SUBDIV);

				DEL_PTR(mHierarchyManager->mVspTree);
				mHierarchyManager->mVspTree = mVspTree;

				mObjectSpaceHierarchyType = OSP;

				//std::stable_sort(objects.begin(), objects.end(), ilt);
				mHierarchyManager->mOspTree->mBoundingBox.Initialize();
				ObjectContainer::const_iterator oit, oit_end = mPvsObjects.end();
				
				//-- compute bounding box
				for (oit = mPvsObjects.begin(); oit != oit_end; ++ oit)
				{
					Intersectable *obj = *oit;
					// compute bounding box of view space
					mHierarchyManager->mOspTree->mBoundingBox.Include(obj->GetBox());
				}
			}
			else if (strcmp(ptr, "bvh") == 0)
			{
				Debug << "\nobject space hierarchy: Bvh" << endl;

				mObjectSpaceHierarchyType = BVH;
				mHierarchyManager = 
					new HierarchyManager(HierarchyManager::BV_BASED_OBJ_SUBDIV);

				DEL_PTR(mHierarchyManager->mVspTree);
				mHierarchyManager->mVspTree = mVspTree;
			}
		}
	}
}


void ViewCellsParseHandlers::StartBoundingBox(AttributeList& attributes)
{
	int len = attributes.getLength();

	Vector3 bmin, bmax;
	int id;

	for (int i = 0; i < len; ++ i) 
	{
		string attrName(StrX(attributes.getName(i)).LocalForm());
		StrX attrValue(attributes.getValue(i));

		const char *ptr = attrValue.LocalForm();

		if (attrName == "id")
		{
			sscanf(ptr, "%d", &id);
		}
		if (attrName == "min") 
		{
			sscanf(ptr, "%f %f %f", &bmin.x, &bmin.y, &bmin.z);
		}
		else if (attrName == "max") 
		{
			sscanf(ptr, "%f %f %f", &bmax.x, &bmax.y, &bmax.z);
		}
	}

	AxisAlignedBox3 box(bmin, bmax);
	mIBoundingBoxes.push_back(IndexedBoundingBox(id, box));
}


void ViewCellsParseHandlers::StartBspLeaf(AttributeList& attributes)
{
	BspLeaf * leaf;

	if (mCurrentBspNode) // replace front or (if not NULL) back child
	{
		BspInterior *interior = static_cast<BspInterior *>(mCurrentBspNode);

		leaf = new BspLeaf(interior);
		interior->ReplaceChildLink(NULL, leaf);
	}
	else
	{
		leaf = new BspLeaf();
		mVspBspTree->mRoot = leaf;
	}

	///////////
	//-- find associated view cell

	int viewCellId;
	const int len = attributes.getLength();
	  
	for (int i = 0; i < len; ++ i) 
	{
		string attrName(StrX(attributes.getName(i)).LocalForm());
		StrX attrValue(attributes.getValue(i));

		const char *ptr = attrValue.LocalForm();
		char *endptr = NULL;

		if (attrName == "viewCellId") 
		{
			viewCellId = strtol(ptr, &endptr, 10);
		}
	}
	
	if (viewCellId >= 0) // valid view cell found
	{
		// TODO: get view cell with specified id
		ViewCellInterior dummyVc;
		dummyVc.SetId(viewCellId);

		ViewCellContainer::iterator vit =
			lower_bound(mViewCells.begin(), mViewCells.end(), &dummyVc, vlt);
		
		//ViewCellsMap::iterator vit = mViewCells.find(viewCellId);
//		BspViewCell *viewCell = static_cast<BspViewCell *>((*vit).second);

		BspViewCell *viewCell = static_cast<BspViewCell *>(*vit);
		if (viewCell->GetId() == viewCellId)
		{
			// create new view cell for bsp nodes
			leaf->SetViewCell(viewCell);
			viewCell->mLeaves.push_back(leaf);
		}
		else
		{
			cerr << "error: view cell does not exist" << endl;
		}
	}
	else
	{
		// add to invalid view space
		leaf->SetViewCell(mVspBspTree->GetOrCreateOutOfBoundsCell());
		leaf->SetTreeValid(false);
		mVspBspTree->PropagateUpValidity(leaf);
	}
}


void ViewCellsParseHandlers::StartBspInterior(AttributeList& attributes)
{
	Plane3 plane;
	int len = attributes.getLength();

	for (int i = 0; i < len; ++ i) 
	{
		string attrName(StrX(attributes.getName(i)).LocalForm());
		StrX attrValue(attributes.getValue(i));
		const char *ptr = attrValue.LocalForm();

		if (attrName == "plane") 
		{
			sscanf(ptr, "%f %f %f %f",
				   &plane.mNormal.x, &plane.mNormal.y, &plane.mNormal.z, &plane.mD);
		}
	}

	BspInterior* interior = new BspInterior(plane);
	
	if (mCurrentBspNode) // replace NULL child of parent with current node
	{
		BspInterior *parent = static_cast<BspInterior *>(mCurrentBspNode);

		parent->ReplaceChildLink(NULL, interior);
		interior->SetParent(parent);
	}
	else
	{
		mVspBspTree->mRoot = interior;
	}

	mCurrentBspNode = interior;
}


void ViewCellsParseHandlers::StartViewCell(AttributeList& attributes, const bool isLeaf)
{
	ViewCell *viewCell = NULL;
	const int len = attributes.getLength();
	float mergeCost;
	
	if (isLeaf)
	{
		viewCell = new ViewCellLeaf();
	}
	else
	{
		viewCell = new ViewCellInterior();
	}

	for (int i = 0; i < len; ++ i) 
	{
		const string attrName(StrX(attributes.getName(i)).LocalForm());
	
		if (attrName == "id") 
		{
			const StrX attrValue(attributes.getValue(i));
			const char *ptr = attrValue.LocalForm();
			char *endptr = NULL;
			const int id = strtol(ptr, &endptr, 10);

			// create new view cell, otherwise use reference.
			viewCell->SetId(id);

			if (mCurrentViewCell) 
			{	// replace front or (if not NULL) back child
				ViewCellInterior *interior = 
					static_cast<ViewCellInterior *>(mCurrentViewCell);
				interior->SetupChildLink(viewCell);
			}
			else 
			{	// set the new root
				mViewCellsTree->SetRoot(viewCell);
			}
			
			if (!isLeaf)
			{
				mCurrentViewCell = viewCell;
			}
		}
		if (attrName == "pvs") 
		{
			StrX attrValue(attributes.getValue(i));
			const char *ptr = attrValue.LocalForm();

			// hack: assume that view cell id comes before pvs
			// otherwise view cell is undefined

			StartViewCellPvs(viewCell->GetPvs(), ptr); 
			//StartViewCellPvs(pvs, ptr);
		}
		else if (attrName == "active")
		{
			StrX attrValue(attributes.getValue(i));
			const char *ptr = attrValue.LocalForm();
			char *endptr = NULL;
			const bool isActive = (bool)strtol(ptr, &endptr, 10);

			if (isActive)
			{
				// TODO
			}
		}
		else if (attrName == "mergecost")
		{
			StrX attrValue(attributes.getValue(i));
			
			const char *ptr = attrValue.LocalForm();
			char *endptr = NULL;
			mergeCost = (float)strtod(ptr, &endptr);
		}
	}

	viewCell->SetMergeCost(mergeCost);
	//viewCell->SetPvs(pvs);
	mViewCells.push_back(viewCell);
}


void ViewCellsParseHandlers::CreateViewSpaceHierarchy()
{
	if (mViewSpaceHierarchyType == BSP)
	{
		Debug << "hierarchy type: Bsp" << endl;
		mVspBspTree = new VspBspTree();

		// set view space box
		mVspBspTree->mBoundingBox = mViewSpaceBox;

		//ViewCellsMap::iterator vit, vit_end = mViewCells.end();
		ViewCellContainer::iterator vit, vit_end = mViewCells.end();

		int i = 0;
		// remove view cells and exchange them with the 
		// view cells specialized for the current hierarchy node type
		for (vit = mViewCells.begin(); vit != vit_end; ++ vit, ++ i)
		{
			ViewCell *vc = (*vit);

			if (!vc->IsLeaf()) // exchange only leaves
				continue;
		
			BspViewCell *bspVc = new BspViewCell();

			bspVc->SetId(vc->GetId());
			//bspVc->GetPvs().reserve(vc->GetPvs().size());
			bspVc->SetPvs(vc->GetPvs());

			if (vc->IsRoot())
			{
				mViewCellsTree->mRoot = bspVc;
			}
			else
			{
                vc->GetParent()->ReplaceChildLink(vc, bspVc);
			}

			// delete old view cell
			DEL_PTR(vc);

			//(*vit).second = bspVc;
			(*vit) = bspVc;
		}
		cout << "finished creating view space hierarchy" << endl;
	}
	else if (mViewSpaceHierarchyType == VSP) 
	{
		Debug << "hierarchy type: Vsp" << endl;
		mVspTree = new VspTree();

		// set view space box
		mVspTree->mBoundingBox = mViewSpaceBox;

		// ViewCellsMap::iterator vit, vit_end = mViewCells.end();
		ViewCellContainer::iterator vit, vit_end = mViewCells.end();

		// reset view cells using the current node type
		for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
		{
			//ViewCell *vc = (*vit).second;
			ViewCell *vc = (*vit);
			
			if (!vc->IsLeaf()) // exchange only leaves
				continue;

			VspViewCell *vspVc = new VspViewCell();

			vspVc->SetPvs(vc->GetPvs());
			vspVc->SetId(vc->GetId());

			if (vc->IsRoot())
			{
				mViewCellsTree->mRoot = vspVc;
			}
			else
			{
				vc->GetParent()->ReplaceChildLink(vc, vspVc);
			}
			
			// exchange view cell with new one
			DEL_PTR(vc);
			//(*vit).second = vspVc;
			(*vit) = vspVc;
		}

		if (mHierarchyManager)
		{
			// do this only if object hierarchy was already constructed
			mHierarchyManager->mVspTree = mVspTree;
			mVspTree->mHierarchyManager = mHierarchyManager;
		}
	}
}


void ViewCellsParseHandlers::CreateViewCellsManager()
{
	if (mViewSpaceHierarchyType == BSP)
	{
		Debug << "\ncreating view cells manager: VspBsp" << endl;
		mViewCellsManager = new VspBspViewCellsManager(mViewCellsTree, mVspBspTree);
	}
	else if (mViewSpaceHierarchyType == VSP) 
	{
		Debug << "\ncreating view cells manager: VspOsp" << endl;
		mViewCellsManager = new VspOspViewCellsManager(mViewCellsTree, mHierarchyManager);
	}

	mViewCellsManager->SetViewSpaceBox(mViewSpaceBox);
}


void ViewCellsParseHandlers::characters(const XMLCh* const chars,
										const unsigned int length)
{
	mCharacterCount += length;
}


void ViewCellsParseHandlers::ignorableWhitespace(const XMLCh* const chars,
												 const unsigned int length)
{
	mSpaceCount += length;
}


void ViewCellsParseHandlers::resetDocument()
{
	mAttrCount = 0;
	mCharacterCount = 0;
	mElementCount = 0;
	mSpaceCount = 0;
}


void ViewCellsParseHandlers::StartVspLeaf(AttributeList& attributes)
{
	VspLeaf * leaf;
		
	if (mCurrentVspNode) // replace front or (if not NULL) back child
	{
		VspInterior *interior = static_cast<VspInterior *>(mCurrentVspNode);
		leaf = new VspLeaf(interior);
		interior->ReplaceChildLink(NULL, leaf);
	}
	else
	{
		leaf = new VspLeaf();
		mVspTree->mRoot = leaf;
	}

	/////////////
	//-- find view cell associated with the id

	int viewCellId;
	const int len = attributes.getLength();
	  
	for (int i = 0; i < len; ++ i) 
	{
		string attrName(StrX(attributes.getName(i)).LocalForm());
		StrX attrValue(attributes.getValue(i));

		const char *ptr = attrValue.LocalForm();
		char *endptr = NULL;

		if (attrName == "viewCellId") 
		{
			viewCellId = strtol(ptr, &endptr, 10);
		}
	}
	
	if (viewCellId >= 0) // valid view cell found
	{
		// TODO: get view cell with specified id
		ViewCellInterior dummyVc;
		dummyVc.SetId(viewCellId);

		ViewCellContainer::iterator vit =
			lower_bound(mViewCells.begin(), mViewCells.end(), &dummyVc, vlt);
		
		//ViewCellsMap::iterator vit = mViewCells.find(viewCellId);
		if (vit == mViewCells.end())
			Debug << "error: view cell " << viewCellId << " not found" << endl;
	
		//VspViewCell *viewCell = static_cast<VspViewCell *>((*vit).second);
		VspViewCell *viewCell = static_cast<VspViewCell *>(*vit);
		
		if (viewCell->GetId() == viewCellId)
		{
			leaf->SetViewCell(viewCell);
			viewCell->mLeaves.push_back(leaf);
		}
		else
		{
			Debug << "error: view cell does not exist" << endl;
		}
	}
	else
	{	
		// add to invalid view space
		leaf->SetViewCell(mVspTree->GetOrCreateOutOfBoundsCell());
		leaf->SetTreeValid(false);
		mVspTree->PropagateUpValidity(leaf);
	}
}


void ViewCellsParseHandlers::StartVspInterior(AttributeList& attributes)
{
	AxisAlignedPlane plane;
	const int len = attributes.getLength();

	for (int i = 0; i < len; ++ i) 
	{
		string attrName(StrX(attributes.getName(i)).LocalForm());
		StrX attrValue(attributes.getValue(i));
		const char *ptr = attrValue.LocalForm();

		if (attrName == "plane") 
		{
			sscanf(ptr, "%f %d", &plane.mPosition, &plane.mAxis);
		}
	}

	VspInterior* interior = new VspInterior(plane);
	
	if (mCurrentVspNode) // replace NULL child of parent with current node
	{
		VspInterior *parent = static_cast<VspInterior *>(mCurrentVspNode);

		parent->ReplaceChildLink(NULL, interior);
		interior->SetParent(parent);
		
		AxisAlignedBox3 frontBox, backBox;

		parent->GetBoundingBox().Split(
			parent->GetPlane().mAxis, 
			parent->GetPlane().mPosition, 
			frontBox, 
			backBox);

		if (parent->GetFront() == interior)
			interior->SetBoundingBox(frontBox);
		else
			interior->SetBoundingBox(backBox);
	}
	else
	{
		mVspTree->mRoot = interior;
		interior->SetBoundingBox(mVspTree->GetBoundingBox());
	}

	mCurrentVspNode = interior;
}


void ViewCellsParseHandlers::StartOspInterior(AttributeList& attributes)
{
	AxisAlignedPlane plane;
	int len = attributes.getLength();

	for (int i = 0; i < len; ++ i) 
	{
		string attrName(StrX(attributes.getName(i)).LocalForm());
		StrX attrValue(attributes.getValue(i));
		const char *ptr = attrValue.LocalForm();

		if (attrName == "plane") 
		{
			sscanf(ptr, "%f %d", &plane.mPosition, &plane.mAxis);
		}
	}

	KdInterior* interior = new KdInterior(NULL);
	
	interior->mAxis = plane.mAxis;
	interior->mPosition = plane.mPosition;

	if (mCurrentOspNode) // replace NULL child of parent with current node
	{
		KdInterior *parent = static_cast<KdInterior *>(mCurrentOspNode);
		parent->ReplaceChildLink(NULL, interior);
		interior->mParent = parent;

		AxisAlignedBox3 frontBox, backBox;

		parent->mBox.Split(parent->mAxis, parent->mPosition, frontBox, backBox);

		if (parent->mFront == interior)
			interior->mBox = frontBox;
		else
			interior->mBox = backBox;
	}
	else
	{
		mHierarchyManager->mOspTree->mRoot = interior;
		interior->mBox = mHierarchyManager->mOspTree->mBoundingBox;
	}

	mCurrentOspNode = interior;
}


void ViewCellsParseHandlers::StartOspLeaf(AttributeList& attributes)
{
	KdLeaf * leaf = new KdLeaf(static_cast<KdInterior *>(mCurrentOspNode), NULL);

	if (mCurrentOspNode)
	{
		 // replace front or (if not NULL) back child
		static_cast<KdInterior *>(mCurrentOspNode)->ReplaceChildLink(NULL, leaf);
	}
	else
	{
		mHierarchyManager->mOspTree->mRoot = leaf;
	}
}


void ViewCellsParseHandlers::StartBvhLeaf(AttributeList& attributes)
{
	const int len = attributes.getLength();
	Vector3 minBox, maxBox;

	ObjectContainer objects;

	for (int i = 0; i < len; ++ i) 
	{
		string attrName(StrX(attributes.getName(i)).LocalForm());
		StrX attrValue(attributes.getValue(i));
		const char *ptr = attrValue.LocalForm();

		if (attrName == "min") 
		{
			sscanf(ptr, "%f %f %f", &minBox.x, &minBox.y, &minBox.z);
		}
		if (attrName == "max") 
		{
			sscanf(ptr, "%f %f %f", &maxBox.x, &maxBox.y, &maxBox.z);
		}
		if (attrName == "objects")
		{
			if (!mPreprocessorObjects.empty())
				StartBvhLeafObjects(objects, ptr);
		}
	}

	AxisAlignedBox3 box = AxisAlignedBox3(minBox, maxBox);

	BvhLeaf *leaf;

	if (mCurrentBvhNode) // replace front or (if not NULL) back child
	{
		BvhInterior *interior = static_cast<BvhInterior *>(mCurrentBvhNode);

		leaf = new BvhLeaf(box, interior, (int)objects.size());
		interior->ReplaceChildLink(NULL, leaf);
	}
	else
	{
		leaf = new BvhLeaf(box, NULL, (int)objects.size());
		mHierarchyManager->mBvHierarchy->mRoot = leaf;
	}

	leaf->mObjects = objects;
	BvHierarchy::AssociateObjectsWithLeaf(leaf);
}


void ViewCellsParseHandlers::StartBvhLeafObjects(ObjectContainer &objects, 
												 const char *ptr)
{
	vector<int> objIndices;
	char *endptr;
			
	while (1)
	{
		const int index = strtol(ptr, &endptr, 10);
		if (ptr == endptr) break;

		objIndices.push_back(index);
		ptr = endptr;
	}

	MeshInstance dummyInst(NULL);
	vector<int>::const_iterator it, it_end = objIndices.end();

	for (it = objIndices.begin(); it != it_end; ++ it)
	{
		const int objId = *it;	
		dummyInst.SetId(objId);

		ObjectContainer::const_iterator oit =
			lower_bound(mPreprocessorObjects.begin(), 
						mPreprocessorObjects.end(), 
						(Intersectable *)&dummyInst, 
						ilt);	
							
		if ((oit != mPreprocessorObjects.end()) && ((*oit)->GetId() == objId))
		{
			objects.push_back(*oit);
		}
		else
		{
			//cerr << "StartBvhLeafObjects error: object with id " << objId << " does not exist" << endl;
		}
	}
}


void ViewCellsParseHandlers::StartBvhInterior(AttributeList& attributes)
{
	const int len = attributes.getLength();
	Vector3 minBox, maxBox;

	for (int i = 0; i < len; ++ i) 
	{
		string attrName(StrX(attributes.getName(i)).LocalForm());
		StrX attrValue(attributes.getValue(i));
		const char *ptr = attrValue.LocalForm();

		if (attrName == "min") 
		{
			sscanf(ptr, "%f %f %f", &minBox.x, &minBox.y, &minBox.z);
		}
		if (attrName == "max") 
		{
			sscanf(ptr, "%f %f %f", &maxBox.x, &maxBox.y, &maxBox.z);
		}
	}

	BvhInterior* interior = new BvhInterior(AxisAlignedBox3(minBox, maxBox));

	if (mCurrentBvhNode) // replace NULL child of parent with current node
	{
		BvhInterior *parent = static_cast<BvhInterior *>(mCurrentBvhNode);
		parent->ReplaceChildLink(NULL, interior);
		interior->SetParent(parent);
	}
	else
	{
		mHierarchyManager->mBvHierarchy->mRoot = interior;
	}

	mCurrentBvhNode = interior;
}


// ---------------------------------------------------------------------------
//  StdInParseHandlers: Overrides of the SAX ErrorHandler interface
// ---------------------------------------------------------------------------


void
ViewCellsParseHandlers::error(const SAXParseException& e)
{
  XERCES_STD_QUALIFIER cerr << "\nError at (file " << StrX(e.getSystemId())
			    << ", line " << e.getLineNumber()
			    << ", char " << e.getColumnNumber()
			    << "): " << StrX(e.getMessage()) << XERCES_STD_QUALIFIER endl;
}

void
ViewCellsParseHandlers::fatalError(const SAXParseException& e)
{
  XERCES_STD_QUALIFIER cerr << "\nFatal Error at (file " << StrX(e.getSystemId())
			    << ", line " << e.getLineNumber()
			    << ", char " << e.getColumnNumber()
			    << "): " << StrX(e.getMessage()) << XERCES_STD_QUALIFIER endl;
}

void
ViewCellsParseHandlers::warning(const SAXParseException& e)
{
  XERCES_STD_QUALIFIER cerr << "\nWarning at (file " << StrX(e.getSystemId())
			    << ", line " << e.getLineNumber()
			    << ", char " << e.getColumnNumber()
			    << "): " << StrX(e.getMessage()) << XERCES_STD_QUALIFIER endl;
}


bool ViewCellsParser::ParseViewCellsFile(const string &filename, 
										 ViewCellsManager **viewCells,
										 ObjectContainer &pvsObjects,
										 ObjectContainer &preprocessorObjects,
										 BoundingBoxConverter *bconverter)
{
	// Initialize the XML4C system
	try {
		XMLPlatformUtils::Initialize();
	}

	catch (const XMLException& toCatch)
	{
		XERCES_STD_QUALIFIER cerr << "Error during initialization! Message:\n"
			<< StrX(toCatch.getMessage()) << XERCES_STD_QUALIFIER endl;
		return false;
	}

	//  cout<<"parsing started"<<endl<<flush;

	//
	//  Create a SAX parser object. Then, according to what we were told on
	//  the command line, set the options.
	//
	SAXParser* parser = new SAXParser;
	parser->setValidationScheme(valScheme);
	parser->setDoNamespaces(doNamespaces);
	parser->setDoSchema(doSchema);
	parser->setValidationSchemaFullChecking(schemaFullChecking);


	//
	//  Create our SAX handler object and install it on the parser, as the
	//  document and error handler. We are responsible for cleaning them
	//  up, but since its just stack based here, there's nothing special
	//  to do.
	//
	ViewCellsParseHandlers handler(pvsObjects, preprocessorObjects, bconverter);
	parser->setDocumentHandler(&handler);
	parser->setErrorHandler(&handler);

	unsigned long duration;
	int errorCount = 0;
	// create a faux scope so that 'src' destructor is called before
	// XMLPlatformUtils::Terminate
	{
		//
		//  Kick off the parse and catch any exceptions. Create a standard
		//  input input source and tell the parser to parse from that.
		//
		//    StdInInputSource src;
		try
		{
			const unsigned long startMillis = XMLPlatformUtils::getCurrentMillis();

#if USE_GZLIB
			XMLCh *myFilePath = XMLString::transcode(filename.c_str());

			GzFileInputSource isource(myFilePath);
			parser->parse(isource);
#else
			parser->parse(filename.c_str());

#endif

			//if (mCreatePvsObjects)
			//	handler.ReplacePvs();

			const unsigned long endMillis = XMLPlatformUtils::getCurrentMillis();
			duration = endMillis - startMillis;
			errorCount = parser->getErrorCount();
		}
		catch (const OutOfMemoryException&)
		{
			XERCES_STD_QUALIFIER cerr << "OutOfMemoryException" << XERCES_STD_QUALIFIER endl;
			errorCount = 2;
			return false;
		}
		catch (const XMLException& e)
		{
			XERCES_STD_QUALIFIER cerr << "\nError during parsing: \n"
				<< StrX(e.getMessage())
				<< "\n" << XERCES_STD_QUALIFIER endl;
			errorCount = 1;
			return false;
		}


		// Print out the stats that we collected and time taken
		if (!errorCount) 
		{
			XERCES_STD_QUALIFIER cerr << filename << ": " << duration << " ms ("
				<< handler.GetElementCount() << " elems, "
				<< handler.GetAttrCount() << " attrs, "
				<< handler.GetSpaceCount() << " spaces, "
				<< handler.GetCharacterCount() << " chars)" << XERCES_STD_QUALIFIER endl;
		}
	}

	//
	//  Delete the parser itself.  Must be done prior to calling Terminate, below.
	//
	delete parser;

	XMLPlatformUtils::Terminate();

	//-- assign new view cells manager
	*viewCells = handler.mViewCellsManager;

	if (errorCount > 0)
		return false;
	else
		return true;
}

}