/*!****************************************************************************
|
|
@file PVRTSkipGraph.h
|
@copyright Copyright (c) Imagination Technologies Limited.
|
@brief A "tree-like" structure for storing data which, unlike a tree, can
|
reference any other node.
|
|
******************************************************************************/
|
#ifndef __PVRTSKIPGRAPH_H__
|
#define __PVRTSKIPGRAPH_H__
|
|
|
#include "PVRTArray.h"
|
#include "PVRTHash.h"
|
|
/*!***************************************************************************
|
@class CPVRTSkipGraphNode
|
@brief Stores a pointer to the node's data and also uses a dynamic
|
array to store pointer to nodes this node depends on and
|
another to store pointers to nodes that are dependant on this node
|
*****************************************************************************/
|
template<class T>
|
class CPVRTSkipGraphNode
|
{
|
private:
|
T m_pData;
|
CPVRTArray<CPVRTSkipGraphNode*> m_apDependencies; // What I depend on
|
CPVRTArray<CPVRTSkipGraphNode*> m_apDependents; // What depends on me
|
|
public:
|
/*!***************************************************************************
|
@brief Constructor
|
*****************************************************************************/
|
CPVRTSkipGraphNode()
|
{}
|
|
/*!***************************************************************************
|
@brief Overloaded constructor
|
@param[in] data Pointer to a node
|
*****************************************************************************/
|
CPVRTSkipGraphNode(const T& data) : m_pData(data)
|
{}
|
|
/*!***************************************************************************
|
@brief Destructor
|
*****************************************************************************/
|
~CPVRTSkipGraphNode()
|
{}
|
|
/*!***************************************************************************
|
@fn GetNumDependencies
|
@return unsigned int
|
@brief Returns the number of dependencies referenced by this node.
|
*****************************************************************************/
|
unsigned int GetNumDependencies() const
|
{
|
return (unsigned int)m_apDependencies.GetSize();
|
}
|
|
/*!***************************************************************************
|
@fn GetDependency
|
@param[in] ui32Id
|
@return CPVRTSkipGraphNode &
|
@brief Returns given dependency.
|
*****************************************************************************/
|
CPVRTSkipGraphNode& GetDependency(const unsigned int ui32Id) const
|
{
|
_ASSERT(ui32Id >= 0 && ui32Id < (unsigned int)m_apDependencies.GetSize());
|
return *m_apDependencies[ui32Id];
|
}
|
|
|
/*!***************************************************************************
|
@fn AddDependency
|
@param[out] pDependentNode
|
@return bool
|
@brief Adds a dependency to this node.
|
*****************************************************************************/
|
bool AddDependency(CPVRTSkipGraphNode* pDependentNode)
|
{
|
unsigned int ui(0);
|
|
if(pDependentNode == this)
|
return false;
|
|
if(!pDependentNode)
|
return false;
|
|
/*
|
Check the dependency doesn't already exist
|
*/
|
for(ui = 0; ui < (unsigned int)m_apDependencies.GetSize(); ++ui)
|
{
|
if(m_apDependencies[ui] == pDependentNode)
|
{
|
return true;
|
}
|
}
|
|
/*
|
Add the dependency and also set this node as a dependent of
|
the referenced node
|
*/
|
m_apDependencies.Append(pDependentNode);
|
pDependentNode->AddDependent(this);
|
|
return true;
|
}
|
|
/*!***************************************************************************
|
@fn GetData
|
@return T &
|
@brief Returns the data associated with this node.
|
*****************************************************************************/
|
T& GetData()
|
{
|
return m_pData;
|
}
|
|
private:
|
/*!***************************************************************************
|
@fn AddDependent
|
@param[out] pDependancyNode
|
@return bool
|
@brief Adds a dependent to this node.
|
*****************************************************************************/
|
bool AddDependent(CPVRTSkipGraphNode* pDependencyNode)
|
{
|
unsigned int ui(0);
|
|
if(!pDependencyNode)
|
return false;
|
|
/*
|
Check the dependency doesn't already exist
|
*/
|
for(ui = 0; ui < (unsigned int)m_apDependents.GetSize(); ++ui)
|
{
|
if(m_apDependencies[ui] == pDependencyNode)
|
{
|
return true;
|
}
|
}
|
|
/*
|
Add the dependancy
|
*/
|
m_apDependents.Append(pDependencyNode);
|
return true;
|
}
|
};
|
|
/*!***************************************************************************
|
@class CPVRTSkipGraphRoot
|
@brief This class is the entry point for creating and accessing
|
the elements of a skip graph. It uses a hash table to store
|
the nodes of the structure and a hash value that allows
|
fast searching of the skip graph
|
*****************************************************************************/
|
template<class T>
|
class CPVRTSkipGraphRoot
|
{
|
//-------------------------------------------------------------------------//
|
private:
|
|
/*!***************************************************************************
|
@struct SPVRTHashElement
|
@brief A struct to store data and a hash value generated from the
|
data. The hash value allows faster searching of the skip graph.
|
*****************************************************************************/
|
struct SPVRTHashElement
|
{
|
public:
|
/*!***************************************************************************
|
@fn SPVRTHashElement
|
@param[in] hash
|
@param[in] data
|
@brief Overloaded constructor.
|
*****************************************************************************/
|
SPVRTHashElement(const CPVRTHash& hash, const T& data)
|
:
|
m_hash(hash),
|
m_skipGraphNode(data)
|
{}
|
|
/*!***************************************************************************
|
@fn SPVRTHashElement
|
@brief Constructor
|
*****************************************************************************/
|
SPVRTHashElement()
|
{}
|
|
/*!***************************************************************************
|
@fn ~SPVRTHashElement
|
@brief Destructor
|
*****************************************************************************/
|
~SPVRTHashElement()
|
{}
|
|
/*!***************************************************************************
|
@fn GetHash
|
@return unsigned int
|
@brief Returns the element's hash value.
|
*****************************************************************************/
|
const CPVRTHash& GetHash() const
|
{
|
return m_hash;
|
}
|
|
/*!***************************************************************************
|
@fn GetNode
|
@return CPVRTSkipGraphNode<T>&
|
@brief Return the node associated with this element.
|
*****************************************************************************/
|
CPVRTSkipGraphNode<T>& GetNode()
|
{
|
return m_skipGraphNode;
|
}
|
|
/*!***************************************************************************
|
@fn GetNode
|
@return CPVRTSkipGraphNode<T>&
|
@brief Return the node associated with this element.
|
*****************************************************************************/
|
const CPVRTSkipGraphNode<T>& GetNode() const
|
{
|
return m_skipGraphNode;
|
}
|
|
private:
|
CPVRTHash m_hash;
|
CPVRTSkipGraphNode<T> m_skipGraphNode;
|
};
|
|
|
CPVRTArray<SPVRTHashElement> m_aHashTable;
|
|
//-------------------------------------------------------------------------//
|
public:
|
|
/*!***************************************************************************
|
@fn AddNode
|
@param[in] data The data of the node to be added
|
@return CPVRTSkipGraphNode<T>* const A handle to the added node
|
@brief Searches through the hash table to see if the added node already
|
exists. If it doesn't, it creates a node.
|
The function returns true if the node was found or was created
|
successfully.
|
*****************************************************************************/
|
bool AddNode(const T& data)
|
{
|
CPVRTHash NewNodeHash((void*)&data, sizeof(T), 1);
|
int iArrayElement(-1);
|
/*
|
First, search the hash table to see
|
if the node already exists
|
*/
|
CPVRTSkipGraphNode<T>* skipGraphNode(FindNode(NewNodeHash));
|
|
if(skipGraphNode == NULL)
|
{
|
/*
|
The node wasn't found, so a new node needs to be
|
created
|
*/
|
iArrayElement = m_aHashTable.Append(SPVRTHashElement(NewNodeHash, data));
|
|
/*
|
Now point to the new instance
|
*/
|
skipGraphNode = &m_aHashTable[iArrayElement].GetNode();
|
}
|
|
return skipGraphNode ? true : false;
|
}
|
|
|
/*!***************************************************************************
|
@brief Adds a node dependency.
|
@param[in] nodeData
|
@param[in] dependantData
|
@return bool
|
*****************************************************************************/
|
bool AddNodeDependency(const T& nodeData, const T& dependantData)
|
{
|
CPVRTSkipGraphNode<T>* pNode(NULL);
|
CPVRTSkipGraphNode<T>* pDependantNode(NULL);
|
|
pNode = FindNode(nodeData);
|
if(!pNode)
|
{
|
return false;
|
}
|
|
pDependantNode = FindNode(dependantData);
|
if(!pDependantNode)
|
{
|
return false;
|
}
|
|
/*
|
Nodes are not allowed to self reference
|
*/
|
if(pNode == pDependantNode)
|
{
|
return false;
|
}
|
pNode->AddDependency(pDependantNode);
|
|
return true;
|
}
|
|
/*!***************************************************************************
|
@fn GetNumNodes
|
@return unsigned int The total number of nodes
|
@brief Returns the total number of nodes in the skip graph.
|
*****************************************************************************/
|
unsigned int GetNumNodes() const
|
{
|
return (unsigned int)m_aHashTable.GetSize();
|
}
|
|
/*!***************************************************************************
|
@brief Returns a sorted list of dependencies for the specified
|
node. The list is ordered with the leaf nodes at the front,
|
followed by nodes that depend on them and so forth until
|
the root node is reached and added at the end of the list
|
@param[in] aOutputArray The dynamic array to store
|
the sorted results in
|
@param[in] ui32NodeID The ID of the root node for
|
the dependency search
|
*****************************************************************************/
|
void RetreiveSortedDependencyList(CPVRTArray<T> &aOutputArray,
|
const unsigned int ui32NodeID)
|
{
|
_ASSERT(ui32NodeID >= 0 && ui32NodeID < (unsigned int)m_aHashTable.GetSize());
|
RecursiveSortedListAdd(aOutputArray, m_aHashTable[ui32NodeID].GetNode());
|
}
|
|
/*!***************************************************************************
|
@brief Overloads operator[] to returns a handle to the node data
|
for the specified ID
|
@return T& Handle to the node data
|
*****************************************************************************/
|
T& operator[](const unsigned int ui32NodeID)
|
{
|
return *(GetNodeData(ui32NodeID));
|
}
|
|
/*!***************************************************************************
|
@brief Overloads operator[] to returns a const handle to the node
|
data for the specified ID
|
@return T& Handle to the node data
|
*****************************************************************************/
|
const T& operator[](const unsigned int ui32NodeID) const
|
{
|
return *(GetNodeData(ui32NodeID));
|
}
|
|
//-------------------------------------------------------------------------//
|
private:
|
/*!***************************************************************************
|
@brief Recursively adds node dependancies to aOutputArray.
|
By doing so, aOutputArray will be ordered from leaf nodes to
|
the root node that started the recursive chain
|
@param[in] aOutputArray The dynamic array to store
|
the sorted results in
|
@param[in] currentNode The current node to process
|
*****************************************************************************/
|
void RecursiveSortedListAdd(CPVRTArray<T> &aOutputArray,
|
CPVRTSkipGraphNode<T> ¤tNode)
|
{
|
unsigned int ui(0);
|
|
/*
|
Recursively add dependancies first
|
*/
|
for(ui = 0; ui < currentNode.GetNumDependencies(); ++ui)
|
{
|
RecursiveSortedListAdd(aOutputArray, currentNode.GetDependency(ui));
|
}
|
|
/*
|
Then add this node to the array
|
*/
|
aOutputArray.Append(currentNode.GetData());
|
}
|
|
/*!***************************************************************************
|
@fn GetNodeData
|
@param[in,out] ui32NodeID The node's ID
|
@return T* A handle to node's data
|
@brief Retrieve a handle to the specified node's data
|
*****************************************************************************/
|
T* GetNodeData(unsigned int ui32NodeID)
|
{
|
_ASSERT(ui32NodeID >= 0 && ui32NodeID < (unsigned int)m_aHashTable.GetSize());
|
return &m_aHashTable[ui32NodeID].GetNode().GetData();
|
}
|
|
/*!***************************************************************************
|
@brief Use the input hash to search the hash table and see if the
|
node already exists. If it does, the function returns a pointer
|
to the node. If it doesn't, it returns NULL
|
@param[in,out] ui32Hash The hash value to search with
|
@return CPVRTSkipGraphNode<T>* const A handle to the found node
|
*****************************************************************************/
|
CPVRTSkipGraphNode<T>* FindNode(const CPVRTHash& Hash)
|
{
|
int i(0);
|
int i32HashTableSize(m_aHashTable.GetSize());
|
|
/*
|
A NULL hash means the node has not initialised
|
correctly
|
*/
|
if(Hash == 0)
|
return NULL;
|
|
/*
|
NOTE:
|
In the future, the hash table could be sorted from
|
lowest hash value to highest so that binary search could
|
be used to find a given node. It should be possible to
|
use a bool (or some other mechanism) to toggle this form of search
|
(if the skip graph is small, it might be faster to just use a brute
|
force for loop to search through)
|
*/
|
for(i = 0; i < i32HashTableSize; i++)
|
{
|
if(m_aHashTable[i].GetHash() == Hash)
|
{
|
return &m_aHashTable[i].GetNode();
|
}
|
}
|
|
/*
|
The element wasn't found, so return null
|
*/
|
return NULL;
|
}
|
|
/*!***************************************************************************
|
@brief Use the input data to generate a hash and then
|
search the hash table and see if the node already exists.
|
If it does, the function returns a pointer
|
to the node. If it doesn't, it returns NULL
|
@param[in,out] data Data to use as a source for the hash
|
@return CPVRTSkipGraphNode<T>* const A handle to the found node
|
*****************************************************************************/
|
CPVRTSkipGraphNode<T>* FindNode(const T& data)
|
{
|
CPVRTHash inputHash((void*)&data, sizeof(T), 1); // Generate hash for searching
|
return FindNode(inputHash);
|
}
|
};
|
|
#endif //__PVRTSKIPGRAPH_H__
|
|
/*****************************************************************************
|
End of file (PVRTSkipGraph.h)
|
*****************************************************************************/
|
