Fix line endings. WHAMMY.

1 files changed, 624 insertions, 624 deletions

diff --git a/mp/src/public/tier1/utlntree.h b/mp/src/public/tier1/utlntree.h
index 7092b605..463b5e16 100644
--- a/mp/src/public/tier1/utlntree.h
+++ b/mp/src/public/tier1/utlntree.h
@@ -1,624 +1,624 @@
-//========= Copyright Valve Corporation, All rights reserved. ============//

-//

-// Purpose: N-way tree container class 

-//

-// $Revision: $

-// $NoKeywords: $

-//=============================================================================//

-

-#ifndef UTLNTREE_H

-#define UTLNTREE_H

-

-#ifdef _WIN32

-#pragma once

-#endif

-

-#include "basetypes.h"

-#include "utlmemory.h"

-#include "tier0/dbg.h"

-

-

-#define INVALID_NTREE_IDX ((I)~0)

-

-//-----------------------------------------------------------------------------

-// class CUtlNTree:

-// description:

-//		A lovely index-based linked list! T is the class type, I is the index

-//		type, which usually should be an unsigned short or smaller.

-//-----------------------------------------------------------------------------

-template <class T, class I = unsigned short> 

-class CUtlNTree

-{

-public:

-	typedef T ElemType_t;

-	typedef I IndexType_t;

-

-	// constructor, destructor

-	CUtlNTree( int growSize = 0, int initSize = 0 );

-	CUtlNTree( void *pMemory, int memsize );

-	~CUtlNTree( );

-

-	// gets particular elements

-	T&         Element( I i );

-	const T&   Element( I i ) const;

-	T&         operator[]( I i );

-	const T&   operator[]( I i ) const;

-

-	// Make sure we have a particular amount of memory

-	void EnsureCapacity( int num );

-

-	// Clears the tree, doesn't deallocate memory

-	void RemoveAll();

-

-	// Memory deallocation

-	void Purge();

-

-	// Allocation/deallocation methods

-	I		Alloc( );

-	void	Free( I elem );

-	void	FreeSubTree( I elem );

-

-	// list modification

-	void	SetRoot( I root );

-	void	LinkChildBefore( I parent, I before, I elem );

-	void	LinkChildAfter( I parent, I after, I elem );

-	void	Unlink( I elem );

-

-	// Alloc + link combined

-	I		InsertChildBefore( I parent, I before );

-	I		InsertChildAfter( I parent, I after );

-	I		InsertChildBefore( I parent, I before, const T &elem );

-	I		InsertChildAfter( I parent, I after, const T &elem );

-

-	// Unlink + free combined

-	void	Remove( I elem );

-	void	RemoveSubTree( I elem );

-

-	// invalid index

-	inline static I  InvalidIndex()  { return INVALID_NTREE_IDX; }

-	inline static size_t ElementSize() { return sizeof(Node_t); }

-

-	// list statistics

-	int	Count() const;

-	I	MaxElementIndex() const;

-

-	// Traversing the list

-	I  Root() const;

-	I  FirstChild( I i ) const;

-	I  PrevSibling( I i ) const;

-	I  NextSibling( I i ) const;

-	I  Parent( I i ) const;

-

-	// Are nodes in the list or valid?

-	bool  IsValidIndex( I i ) const;

-	bool  IsInTree( I i ) const;

-   

-protected:

-	// What the linked list element looks like

-	struct Node_t

-	{

-		T  m_Element;

-		I  m_Parent;

-		I  m_FirstChild;

-		I  m_PrevSibling;

-		I  m_NextSibling;

-

-	private:

-		// No copy constructor for these...

-		Node_t( const Node_t& );

-	};

-	

-	// constructs the class

-	void ConstructList();

-

-	// Allocates the element, doesn't call the constructor

-	I AllocInternal();

-

-	// Gets at the node element....

-	Node_t& InternalNode( I i ) { return m_Memory[i]; }

-	const Node_t& InternalNode( I i ) const { return m_Memory[i]; }

-

-	void ResetDbgInfo()

-	{

-		m_pElements = m_Memory.Base();

-	}

-	

-	// copy constructors not allowed

-	CUtlNTree( CUtlNTree<T, I> const& tree ) { Assert(0); }

-	   

-	CUtlMemory<Node_t> m_Memory;

-	I	m_Root;

-	I	m_FirstFree;

-	I	m_ElementCount;		// The number actually in the tree

-	I	m_MaxElementIndex;	// The max index we've ever assigned

-	

-	// For debugging purposes; 

-	// it's in release builds so this can be used in libraries correctly

-	Node_t  *m_pElements;

-};

-   

-   

-//-----------------------------------------------------------------------------

-// constructor, destructor

-//-----------------------------------------------------------------------------

-

-template <class T, class I>

-CUtlNTree<T,I>::CUtlNTree( int growSize, int initSize ) :

-	m_Memory(growSize, initSize) 

-{

-	ConstructList();

-	ResetDbgInfo();

-}

-

-template <class T, class I>

-CUtlNTree<T,I>::CUtlNTree( void* pMemory, int memsize ) : 

-	m_Memory(pMemory, memsize/sizeof(T))

-{

-	ConstructList();

-	ResetDbgInfo();

-}

-

-template <class T, class I>

-CUtlNTree<T,I>::~CUtlNTree( ) 

-{

-	RemoveAll();

-}

-

-template <class T, class I>

-void CUtlNTree<T,I>::ConstructList()

-{

-	m_Root = InvalidIndex(); 

-	m_FirstFree = InvalidIndex();

-	m_ElementCount = m_MaxElementIndex = 0;

-}

-

-

-//-----------------------------------------------------------------------------

-// gets particular elements

-//-----------------------------------------------------------------------------

-template <class T, class I>

-inline T& CUtlNTree<T,I>::Element( I i )

-{

-	return m_Memory[i].m_Element; 

-}

-

-template <class T, class I>

-inline const T& CUtlNTree<T,I>::Element( I i ) const

-{

-	return m_Memory[i].m_Element; 

-}

-

-template <class T, class I>

-inline T& CUtlNTree<T,I>::operator[]( I i )        

-{ 

-	return m_Memory[i].m_Element; 

-}

-

-template <class T, class I>

-inline const T& CUtlNTree<T,I>::operator[]( I i ) const 

-{

-	return m_Memory[i].m_Element; 

-}

-

-

-//-----------------------------------------------------------------------------

-// list statistics

-//-----------------------------------------------------------------------------

-template <class T, class I>

-inline int CUtlNTree<T,I>::Count() const      

-{ 

-	return m_ElementCount; 

-}

-

-template <class T, class I>

-inline I CUtlNTree<T,I>::MaxElementIndex() const   

-{

-	return m_MaxElementIndex;

-}

-

-

-//-----------------------------------------------------------------------------

-// Traversing the list

-//-----------------------------------------------------------------------------

-template <class T, class I>

-inline I  CUtlNTree<T,I>::Root() const  

-{ 

-	return m_Root; 

-}

-

-template <class T, class I>

-inline I  CUtlNTree<T,I>::FirstChild( I i ) const  

-{ 

-	Assert( IsInTree(i) ); 

-	return InternalNode(i).m_FirstChild; 

-}

-

-template <class T, class I>

-inline I  CUtlNTree<T,I>::PrevSibling( I i ) const  

-{ 

-	Assert( IsInTree(i) ); 

-	return InternalNode(i).m_PrevSibling; 

-}

-

-template <class T, class I>

-inline I  CUtlNTree<T,I>::NextSibling( I i ) const  

-{ 

-	Assert( IsInTree(i) ); 

-	return InternalNode(i).m_NextSibling; 

-}

-

-template <class T, class I>

-inline I  CUtlNTree<T,I>::Parent( I i ) const  

-{ 

-	Assert( IsInTree(i) ); 

-	return InternalNode(i).m_Parent; 

-}

-

-

-//-----------------------------------------------------------------------------

-// Are nodes in the list or valid?

-//-----------------------------------------------------------------------------

-template <class T, class I>

-inline bool CUtlNTree<T,I>::IsValidIndex( I i ) const  

-{ 

-	return (i < m_MaxElementIndex) && (i >= 0);

-}

-

-template <class T, class I>

-inline bool CUtlNTree<T,I>::IsInTree( I i ) const

-{

-	return (i < m_MaxElementIndex) && (i >= 0) && (InternalNode(i).m_PrevSibling != i);

-}

-

-

-//-----------------------------------------------------------------------------

-// Makes sure we have enough memory allocated to store a requested # of elements

-//-----------------------------------------------------------------------------

-template< class T, class I >

-void CUtlNTree<T, I>::EnsureCapacity( int num )

-{

-	MEM_ALLOC_CREDIT_CLASS();

-	m_Memory.EnsureCapacity(num);

-	ResetDbgInfo();

-}

-

-

-//-----------------------------------------------------------------------------

-// Deallocate memory

-//-----------------------------------------------------------------------------

-template <class T, class I>

-void  CUtlNTree<T,I>::Purge()

-{

-	RemoveAll();

-	m_Memory.Purge( );

-	m_FirstFree = InvalidIndex();

-	m_MaxElementIndex = 0;

-	ResetDbgInfo();

-}

-

-

-//-----------------------------------------------------------------------------

-// Node allocation/deallocation

-//-----------------------------------------------------------------------------

-template <class T, class I>

-I CUtlNTree<T,I>::AllocInternal( )

-{

-	I elem;

-	if ( m_FirstFree == INVALID_NTREE_IDX )

-	{

-		// Nothing in the free list; add.

-		// Since nothing is in the free list, m_MaxElementIndex == total # of elements

-		// the list knows about.

-		if ((int)m_MaxElementIndex == m_Memory.NumAllocated())

-		{

-			MEM_ALLOC_CREDIT_CLASS();

-			m_Memory.Grow();

-		}

-

-		Assert( m_MaxElementIndex != INVALID_NTREE_IDX );

-

-		elem = (I)m_MaxElementIndex;

-		++m_MaxElementIndex;

-

-		if ( elem == InvalidIndex() )

-		{

-			Error("CUtlNTree overflow!\n");

-		}

-	} 

-	else

-	{

-		elem = m_FirstFree;

-		m_FirstFree = InternalNode( m_FirstFree ).m_NextSibling;

-	}

-	

-	Node_t &node = InternalNode( elem );

-	node.m_NextSibling = node.m_PrevSibling = node.m_Parent = node.m_FirstChild = INVALID_NTREE_IDX;

-	ResetDbgInfo();

-

-	// one more element baby

-	++m_ElementCount;

-

-	return elem;

-}

-

-template <class T, class I>

-I CUtlNTree<T,I>::Alloc( )

-{

-	I elem = AllocInternal();

-	Construct( &Element(elem) );

-	return elem;

-}

-

-template <class T, class I>

-void CUtlNTree<T,I>::Free( I elem )

-{

-	Assert( IsInTree( elem ) );

-	Unlink( elem );

-

-	// If there's children, this will result in leaks. Use FreeSubTree instead.

-	Assert( FirstChild( elem ) == INVALID_NTREE_IDX );

-

-	Node_t &node = InternalNode( elem );

-	Destruct( &node.m_Element );

-	node.m_NextSibling = m_FirstFree;

-	node.m_PrevSibling = elem;	// Marks it as being in the free list

-	node.m_Parent = node.m_FirstChild = INVALID_NTREE_IDX;

-	m_FirstFree = elem;

-

-	// one less element baby

-	--m_ElementCount;

-}

-

-template <class T, class I>

-void CUtlNTree<T,I>::FreeSubTree( I elem )

-{

-	Assert( IsValidIndex( elem ) );

-

-	I child = FirstChild( elem );

-	while ( child != INVALID_NTREE_IDX )

-	{

-		I next = NextSibling( child );

-		FreeSubTree( child );

-		child = next;

-	}

-

-	Free( elem );

-}

-

-

-//-----------------------------------------------------------------------------

-// Clears the tree

-//-----------------------------------------------------------------------------

-template <class T, class I>

-void CUtlNTree<T,I>::RemoveAll()

-{

-	if ( m_MaxElementIndex == 0 )

-		return;

-

-	// Put everything into the free list (even unlinked things )

-	I prev = InvalidIndex();

-	for (int i = (int)m_MaxElementIndex; --i >= 0; prev = (I)i )

-	{

-		Node_t &node = InternalNode( i );

-		if ( IsInTree( i ) )

-		{

-			Destruct( &node.m_Element );

-		}

-

-		node.m_NextSibling = prev;

-		node.m_PrevSibling = (I)i;	// Marks it as being in the free list

-		node.m_Parent = node.m_FirstChild = INVALID_NTREE_IDX;

-	}

-	

-	// First free points to the first element

-	m_FirstFree = 0;

-	

-	// Clear everything else out

-	m_Root = INVALID_NTREE_IDX; 

-	m_ElementCount = 0;

-}

-

-

-//-----------------------------------------------------------------------------

-// list modification

-//-----------------------------------------------------------------------------

-template <class T, class I>

-void CUtlNTree<T,I>::SetRoot( I root )

-{

-	// Resetting the root while it's got stuff in it is bad...

-	Assert( m_Root == InvalidIndex() );

-	m_Root = root;

-}

-

-	

-//-----------------------------------------------------------------------------

-// Links a node after a particular node

-//-----------------------------------------------------------------------------

-template <class T, class I>

-void  CUtlNTree<T,I>::LinkChildAfter( I parent, I after, I elem )

-{

-	Assert( IsInTree(elem) );

-	

-	// Unlink it if it's in the list at the moment

-	Unlink(elem);

-	

-	Node_t& newElem = InternalNode(elem);

-	newElem.m_Parent = parent;

-	newElem.m_PrevSibling = after;

-	if ( after != INVALID_NTREE_IDX )

-	{

-		Node_t& prevSiblingNode = InternalNode( after );

-		newElem.m_NextSibling = prevSiblingNode.m_NextSibling;

-		prevSiblingNode.m_NextSibling = elem;

-	}

-	else

-	{

-		if ( parent != INVALID_NTREE_IDX )

-		{

-			Node_t& parentNode = InternalNode( parent );

-			newElem.m_NextSibling = parentNode.m_FirstChild;

-			parentNode.m_FirstChild = elem;

-		}

-		else

-		{

-			newElem.m_NextSibling = m_Root;

-			if ( m_Root != INVALID_NTREE_IDX )

-			{

-				Node_t& rootNode = InternalNode( m_Root );

-				rootNode.m_PrevSibling = elem;

-			}

-			m_Root = elem;

-		}

-	}

-

-	if ( newElem.m_NextSibling != INVALID_NTREE_IDX )

-	{

-		Node_t& nextSiblingNode = InternalNode( newElem.m_NextSibling );

-		nextSiblingNode.m_PrevSibling = elem;

-	}

-}

-

-

-//-----------------------------------------------------------------------------

-// Links a node before a particular node

-//-----------------------------------------------------------------------------

-template <class T, class I>

-void CUtlNTree<T,I>::LinkChildBefore( I parent, I before, I elem )

-{

-	Assert( IsValidIndex(elem) );

-	

-	if ( before != INVALID_NTREE_IDX )

-	{

-		LinkChildAfter( parent, InternalNode( before ).m_PrevSibling, elem );

-		return;

-	}

-

-	// NOTE: I made the choice to do an O(n) operation here

-	// instead of store more data per node (LastChild).

-	// This might not be the right choice. Revisit if we get perf problems.

-	I after;

-	if ( parent != INVALID_NTREE_IDX )

-	{

-		after = InternalNode( parent ).m_FirstChild;

-	}

-	else

-	{

-		after = m_Root;

-	}

-

-	if ( after == INVALID_NTREE_IDX )

-	{

-		LinkChildAfter( parent, after, elem );

-		return;

-	}

-

-	I next = InternalNode( after ).m_NextSibling;

-	while ( next != InvalidIndex() )

-	{

-		after = next;

-		next = InternalNode( next ).m_NextSibling;

-	}

-

-	LinkChildAfter( parent, after, elem );

-}

-

-

-//-----------------------------------------------------------------------------

-// Unlinks a node from the tree

-//-----------------------------------------------------------------------------

-template <class T, class I>

-void CUtlNTree<T,I>::Unlink( I elem )

-{

-	Assert( IsInTree(elem) );

-

-	Node_t *pOldNode = &InternalNode( elem );

-	

-	// If we're the first guy, reset the head

-	// otherwise, make our previous node's next pointer = our next

-	if ( pOldNode->m_PrevSibling != INVALID_NTREE_IDX )

-	{

-		InternalNode( pOldNode->m_PrevSibling ).m_NextSibling = pOldNode->m_NextSibling;

-	}

-	else

-	{

-		if ( pOldNode->m_Parent	!= INVALID_NTREE_IDX )

-		{

-			InternalNode( pOldNode->m_Parent ).m_FirstChild = pOldNode->m_NextSibling;

-		}

-		else if ( m_Root == elem )

-		{

-			m_Root = pOldNode->m_NextSibling;

-		}

-	}

-	

-	// If we're the last guy, reset the tail

-	// otherwise, make our next node's prev pointer = our prev

-	if ( pOldNode->m_NextSibling != INVALID_NTREE_IDX )

-	{

-		InternalNode( pOldNode->m_NextSibling ).m_PrevSibling = pOldNode->m_PrevSibling;

-	}

-	

-	// Unlink everything except children

-	pOldNode->m_Parent = pOldNode->m_PrevSibling = pOldNode->m_NextSibling = INVALID_NTREE_IDX;

-}

-

-

-//-----------------------------------------------------------------------------

-// Alloc + link combined

-//-----------------------------------------------------------------------------

-template <class T, class I>

-I CUtlNTree<T,I>::InsertChildBefore( I parent, I before )

-{

-	I elem = AllocInternal();

-	Construct( &Element( elem ) );

-	LinkChildBefore( parent, before, elem );

-	return elem;

-}

-

-template <class T, class I>

-I CUtlNTree<T,I>::InsertChildAfter( I parent, I after )

-{

-	I elem = AllocInternal();

-	Construct( &Element( elem ) );

-	LinkChildAfter( parent, after, elem );

-	return elem;

-}

-

-template <class T, class I>

-I CUtlNTree<T,I>::InsertChildBefore( I parent, I before, const T &data )

-{

-	I elem = AllocInternal();

-	CopyConstruct( &Element( elem ), data );

-	LinkChildBefore( parent, before, elem );

-	return elem;

-}

-

-template <class T, class I>

-I CUtlNTree<T,I>::InsertChildAfter( I parent, I after, const T &data )

-{

-	I elem = AllocInternal();

-	CopyConstruct( &Element( elem ), data );

-	LinkChildAfter( parent, after, elem );

-	return elem;

-}

-

-

-//-----------------------------------------------------------------------------

-// Unlink + free combined

-//-----------------------------------------------------------------------------

-template <class T, class I>

-void CUtlNTree<T,I>::Remove( I elem )

-{

-	Unlink( elem );

-	Free( elem );

-}

-

-template <class T, class I>

-void CUtlNTree<T,I>::RemoveSubTree( I elem )

-{

-	UnlinkSubTree( elem );

-	Free( elem );

-}

-  

-

-#endif // UTLNTREE_H

+//========= Copyright Valve Corporation, All rights reserved. ============//
+//
+// Purpose: N-way tree container class 
+//
+// $Revision: $
+// $NoKeywords: $
+//=============================================================================//
+
+#ifndef UTLNTREE_H
+#define UTLNTREE_H
+
+#ifdef _WIN32
+#pragma once
+#endif
+
+#include "basetypes.h"
+#include "utlmemory.h"
+#include "tier0/dbg.h"
+
+
+#define INVALID_NTREE_IDX ((I)~0)
+
+//-----------------------------------------------------------------------------
+// class CUtlNTree:
+// description:
+//		A lovely index-based linked list! T is the class type, I is the index
+//		type, which usually should be an unsigned short or smaller.
+//-----------------------------------------------------------------------------
+template <class T, class I = unsigned short> 
+class CUtlNTree
+{
+public:
+	typedef T ElemType_t;
+	typedef I IndexType_t;
+
+	// constructor, destructor
+	CUtlNTree( int growSize = 0, int initSize = 0 );
+	CUtlNTree( void *pMemory, int memsize );
+	~CUtlNTree( );
+
+	// gets particular elements
+	T&         Element( I i );
+	const T&   Element( I i ) const;
+	T&         operator[]( I i );
+	const T&   operator[]( I i ) const;
+
+	// Make sure we have a particular amount of memory
+	void EnsureCapacity( int num );
+
+	// Clears the tree, doesn't deallocate memory
+	void RemoveAll();
+
+	// Memory deallocation
+	void Purge();
+
+	// Allocation/deallocation methods
+	I		Alloc( );
+	void	Free( I elem );
+	void	FreeSubTree( I elem );
+
+	// list modification
+	void	SetRoot( I root );
+	void	LinkChildBefore( I parent, I before, I elem );
+	void	LinkChildAfter( I parent, I after, I elem );
+	void	Unlink( I elem );
+
+	// Alloc + link combined
+	I		InsertChildBefore( I parent, I before );
+	I		InsertChildAfter( I parent, I after );
+	I		InsertChildBefore( I parent, I before, const T &elem );
+	I		InsertChildAfter( I parent, I after, const T &elem );
+
+	// Unlink + free combined
+	void	Remove( I elem );
+	void	RemoveSubTree( I elem );
+
+	// invalid index
+	inline static I  InvalidIndex()  { return INVALID_NTREE_IDX; }
+	inline static size_t ElementSize() { return sizeof(Node_t); }
+
+	// list statistics
+	int	Count() const;
+	I	MaxElementIndex() const;
+
+	// Traversing the list
+	I  Root() const;
+	I  FirstChild( I i ) const;
+	I  PrevSibling( I i ) const;
+	I  NextSibling( I i ) const;
+	I  Parent( I i ) const;
+
+	// Are nodes in the list or valid?
+	bool  IsValidIndex( I i ) const;
+	bool  IsInTree( I i ) const;
+   
+protected:
+	// What the linked list element looks like
+	struct Node_t
+	{
+		T  m_Element;
+		I  m_Parent;
+		I  m_FirstChild;
+		I  m_PrevSibling;
+		I  m_NextSibling;
+
+	private:
+		// No copy constructor for these...
+		Node_t( const Node_t& );
+	};
+	
+	// constructs the class
+	void ConstructList();
+
+	// Allocates the element, doesn't call the constructor
+	I AllocInternal();
+
+	// Gets at the node element....
+	Node_t& InternalNode( I i ) { return m_Memory[i]; }
+	const Node_t& InternalNode( I i ) const { return m_Memory[i]; }
+
+	void ResetDbgInfo()
+	{
+		m_pElements = m_Memory.Base();
+	}
+	
+	// copy constructors not allowed
+	CUtlNTree( CUtlNTree<T, I> const& tree ) { Assert(0); }
+	   
+	CUtlMemory<Node_t> m_Memory;
+	I	m_Root;
+	I	m_FirstFree;
+	I	m_ElementCount;		// The number actually in the tree
+	I	m_MaxElementIndex;	// The max index we've ever assigned
+	
+	// For debugging purposes; 
+	// it's in release builds so this can be used in libraries correctly
+	Node_t  *m_pElements;
+};
+   
+   
+//-----------------------------------------------------------------------------
+// constructor, destructor
+//-----------------------------------------------------------------------------
+
+template <class T, class I>
+CUtlNTree<T,I>::CUtlNTree( int growSize, int initSize ) :
+	m_Memory(growSize, initSize) 
+{
+	ConstructList();
+	ResetDbgInfo();
+}
+
+template <class T, class I>
+CUtlNTree<T,I>::CUtlNTree( void* pMemory, int memsize ) : 
+	m_Memory(pMemory, memsize/sizeof(T))
+{
+	ConstructList();
+	ResetDbgInfo();
+}
+
+template <class T, class I>
+CUtlNTree<T,I>::~CUtlNTree( ) 
+{
+	RemoveAll();
+}
+
+template <class T, class I>
+void CUtlNTree<T,I>::ConstructList()
+{
+	m_Root = InvalidIndex(); 
+	m_FirstFree = InvalidIndex();
+	m_ElementCount = m_MaxElementIndex = 0;
+}
+
+
+//-----------------------------------------------------------------------------
+// gets particular elements
+//-----------------------------------------------------------------------------
+template <class T, class I>
+inline T& CUtlNTree<T,I>::Element( I i )
+{
+	return m_Memory[i].m_Element; 
+}
+
+template <class T, class I>
+inline const T& CUtlNTree<T,I>::Element( I i ) const
+{
+	return m_Memory[i].m_Element; 
+}
+
+template <class T, class I>
+inline T& CUtlNTree<T,I>::operator[]( I i )        
+{ 
+	return m_Memory[i].m_Element; 
+}
+
+template <class T, class I>
+inline const T& CUtlNTree<T,I>::operator[]( I i ) const 
+{
+	return m_Memory[i].m_Element; 
+}
+
+
+//-----------------------------------------------------------------------------
+// list statistics
+//-----------------------------------------------------------------------------
+template <class T, class I>
+inline int CUtlNTree<T,I>::Count() const      
+{ 
+	return m_ElementCount; 
+}
+
+template <class T, class I>
+inline I CUtlNTree<T,I>::MaxElementIndex() const   
+{
+	return m_MaxElementIndex;
+}
+
+
+//-----------------------------------------------------------------------------
+// Traversing the list
+//-----------------------------------------------------------------------------
+template <class T, class I>
+inline I  CUtlNTree<T,I>::Root() const  
+{ 
+	return m_Root; 
+}
+
+template <class T, class I>
+inline I  CUtlNTree<T,I>::FirstChild( I i ) const  
+{ 
+	Assert( IsInTree(i) ); 
+	return InternalNode(i).m_FirstChild; 
+}
+
+template <class T, class I>
+inline I  CUtlNTree<T,I>::PrevSibling( I i ) const  
+{ 
+	Assert( IsInTree(i) ); 
+	return InternalNode(i).m_PrevSibling; 
+}
+
+template <class T, class I>
+inline I  CUtlNTree<T,I>::NextSibling( I i ) const  
+{ 
+	Assert( IsInTree(i) ); 
+	return InternalNode(i).m_NextSibling; 
+}
+
+template <class T, class I>
+inline I  CUtlNTree<T,I>::Parent( I i ) const  
+{ 
+	Assert( IsInTree(i) ); 
+	return InternalNode(i).m_Parent; 
+}
+
+
+//-----------------------------------------------------------------------------
+// Are nodes in the list or valid?
+//-----------------------------------------------------------------------------
+template <class T, class I>
+inline bool CUtlNTree<T,I>::IsValidIndex( I i ) const  
+{ 
+	return (i < m_MaxElementIndex) && (i >= 0);
+}
+
+template <class T, class I>
+inline bool CUtlNTree<T,I>::IsInTree( I i ) const
+{
+	return (i < m_MaxElementIndex) && (i >= 0) && (InternalNode(i).m_PrevSibling != i);
+}
+
+
+//-----------------------------------------------------------------------------
+// Makes sure we have enough memory allocated to store a requested # of elements
+//-----------------------------------------------------------------------------
+template< class T, class I >
+void CUtlNTree<T, I>::EnsureCapacity( int num )
+{
+	MEM_ALLOC_CREDIT_CLASS();
+	m_Memory.EnsureCapacity(num);
+	ResetDbgInfo();
+}
+
+
+//-----------------------------------------------------------------------------
+// Deallocate memory
+//-----------------------------------------------------------------------------
+template <class T, class I>
+void  CUtlNTree<T,I>::Purge()
+{
+	RemoveAll();
+	m_Memory.Purge( );
+	m_FirstFree = InvalidIndex();
+	m_MaxElementIndex = 0;
+	ResetDbgInfo();
+}
+
+
+//-----------------------------------------------------------------------------
+// Node allocation/deallocation
+//-----------------------------------------------------------------------------
+template <class T, class I>
+I CUtlNTree<T,I>::AllocInternal( )
+{
+	I elem;
+	if ( m_FirstFree == INVALID_NTREE_IDX )
+	{
+		// Nothing in the free list; add.
+		// Since nothing is in the free list, m_MaxElementIndex == total # of elements
+		// the list knows about.
+		if ((int)m_MaxElementIndex == m_Memory.NumAllocated())
+		{
+			MEM_ALLOC_CREDIT_CLASS();
+			m_Memory.Grow();
+		}
+
+		Assert( m_MaxElementIndex != INVALID_NTREE_IDX );
+
+		elem = (I)m_MaxElementIndex;
+		++m_MaxElementIndex;
+
+		if ( elem == InvalidIndex() )
+		{
+			Error("CUtlNTree overflow!\n");
+		}
+	} 
+	else
+	{
+		elem = m_FirstFree;
+		m_FirstFree = InternalNode( m_FirstFree ).m_NextSibling;
+	}
+	
+	Node_t &node = InternalNode( elem );
+	node.m_NextSibling = node.m_PrevSibling = node.m_Parent = node.m_FirstChild = INVALID_NTREE_IDX;
+	ResetDbgInfo();
+
+	// one more element baby
+	++m_ElementCount;
+
+	return elem;
+}
+
+template <class T, class I>
+I CUtlNTree<T,I>::Alloc( )
+{
+	I elem = AllocInternal();
+	Construct( &Element(elem) );
+	return elem;
+}
+
+template <class T, class I>
+void CUtlNTree<T,I>::Free( I elem )
+{
+	Assert( IsInTree( elem ) );
+	Unlink( elem );
+
+	// If there's children, this will result in leaks. Use FreeSubTree instead.
+	Assert( FirstChild( elem ) == INVALID_NTREE_IDX );
+
+	Node_t &node = InternalNode( elem );
+	Destruct( &node.m_Element );
+	node.m_NextSibling = m_FirstFree;
+	node.m_PrevSibling = elem;	// Marks it as being in the free list
+	node.m_Parent = node.m_FirstChild = INVALID_NTREE_IDX;
+	m_FirstFree = elem;
+
+	// one less element baby
+	--m_ElementCount;
+}
+
+template <class T, class I>
+void CUtlNTree<T,I>::FreeSubTree( I elem )
+{
+	Assert( IsValidIndex( elem ) );
+
+	I child = FirstChild( elem );
+	while ( child != INVALID_NTREE_IDX )
+	{
+		I next = NextSibling( child );
+		FreeSubTree( child );
+		child = next;
+	}
+
+	Free( elem );
+}
+
+
+//-----------------------------------------------------------------------------
+// Clears the tree
+//-----------------------------------------------------------------------------
+template <class T, class I>
+void CUtlNTree<T,I>::RemoveAll()
+{
+	if ( m_MaxElementIndex == 0 )
+		return;
+
+	// Put everything into the free list (even unlinked things )
+	I prev = InvalidIndex();
+	for (int i = (int)m_MaxElementIndex; --i >= 0; prev = (I)i )
+	{
+		Node_t &node = InternalNode( i );
+		if ( IsInTree( i ) )
+		{
+			Destruct( &node.m_Element );
+		}
+
+		node.m_NextSibling = prev;
+		node.m_PrevSibling = (I)i;	// Marks it as being in the free list
+		node.m_Parent = node.m_FirstChild = INVALID_NTREE_IDX;
+	}
+	
+	// First free points to the first element
+	m_FirstFree = 0;
+	
+	// Clear everything else out
+	m_Root = INVALID_NTREE_IDX; 
+	m_ElementCount = 0;
+}
+
+
+//-----------------------------------------------------------------------------
+// list modification
+//-----------------------------------------------------------------------------
+template <class T, class I>
+void CUtlNTree<T,I>::SetRoot( I root )
+{
+	// Resetting the root while it's got stuff in it is bad...
+	Assert( m_Root == InvalidIndex() );
+	m_Root = root;
+}
+
+	
+//-----------------------------------------------------------------------------
+// Links a node after a particular node
+//-----------------------------------------------------------------------------
+template <class T, class I>
+void  CUtlNTree<T,I>::LinkChildAfter( I parent, I after, I elem )
+{
+	Assert( IsInTree(elem) );
+	
+	// Unlink it if it's in the list at the moment
+	Unlink(elem);
+	
+	Node_t& newElem = InternalNode(elem);
+	newElem.m_Parent = parent;
+	newElem.m_PrevSibling = after;
+	if ( after != INVALID_NTREE_IDX )
+	{
+		Node_t& prevSiblingNode = InternalNode( after );
+		newElem.m_NextSibling = prevSiblingNode.m_NextSibling;
+		prevSiblingNode.m_NextSibling = elem;
+	}
+	else
+	{
+		if ( parent != INVALID_NTREE_IDX )
+		{
+			Node_t& parentNode = InternalNode( parent );
+			newElem.m_NextSibling = parentNode.m_FirstChild;
+			parentNode.m_FirstChild = elem;
+		}
+		else
+		{
+			newElem.m_NextSibling = m_Root;
+			if ( m_Root != INVALID_NTREE_IDX )
+			{
+				Node_t& rootNode = InternalNode( m_Root );
+				rootNode.m_PrevSibling = elem;
+			}
+			m_Root = elem;
+		}
+	}
+
+	if ( newElem.m_NextSibling != INVALID_NTREE_IDX )
+	{
+		Node_t& nextSiblingNode = InternalNode( newElem.m_NextSibling );
+		nextSiblingNode.m_PrevSibling = elem;
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Links a node before a particular node
+//-----------------------------------------------------------------------------
+template <class T, class I>
+void CUtlNTree<T,I>::LinkChildBefore( I parent, I before, I elem )
+{
+	Assert( IsValidIndex(elem) );
+	
+	if ( before != INVALID_NTREE_IDX )
+	{
+		LinkChildAfter( parent, InternalNode( before ).m_PrevSibling, elem );
+		return;
+	}
+
+	// NOTE: I made the choice to do an O(n) operation here
+	// instead of store more data per node (LastChild).
+	// This might not be the right choice. Revisit if we get perf problems.
+	I after;
+	if ( parent != INVALID_NTREE_IDX )
+	{
+		after = InternalNode( parent ).m_FirstChild;
+	}
+	else
+	{
+		after = m_Root;
+	}
+
+	if ( after == INVALID_NTREE_IDX )
+	{
+		LinkChildAfter( parent, after, elem );
+		return;
+	}
+
+	I next = InternalNode( after ).m_NextSibling;
+	while ( next != InvalidIndex() )
+	{
+		after = next;
+		next = InternalNode( next ).m_NextSibling;
+	}
+
+	LinkChildAfter( parent, after, elem );
+}
+
+
+//-----------------------------------------------------------------------------
+// Unlinks a node from the tree
+//-----------------------------------------------------------------------------
+template <class T, class I>
+void CUtlNTree<T,I>::Unlink( I elem )
+{
+	Assert( IsInTree(elem) );
+
+	Node_t *pOldNode = &InternalNode( elem );
+	
+	// If we're the first guy, reset the head
+	// otherwise, make our previous node's next pointer = our next
+	if ( pOldNode->m_PrevSibling != INVALID_NTREE_IDX )
+	{
+		InternalNode( pOldNode->m_PrevSibling ).m_NextSibling = pOldNode->m_NextSibling;
+	}
+	else
+	{
+		if ( pOldNode->m_Parent	!= INVALID_NTREE_IDX )
+		{
+			InternalNode( pOldNode->m_Parent ).m_FirstChild = pOldNode->m_NextSibling;
+		}
+		else if ( m_Root == elem )
+		{
+			m_Root = pOldNode->m_NextSibling;
+		}
+	}
+	
+	// If we're the last guy, reset the tail
+	// otherwise, make our next node's prev pointer = our prev
+	if ( pOldNode->m_NextSibling != INVALID_NTREE_IDX )
+	{
+		InternalNode( pOldNode->m_NextSibling ).m_PrevSibling = pOldNode->m_PrevSibling;
+	}
+	
+	// Unlink everything except children
+	pOldNode->m_Parent = pOldNode->m_PrevSibling = pOldNode->m_NextSibling = INVALID_NTREE_IDX;
+}
+
+
+//-----------------------------------------------------------------------------
+// Alloc + link combined
+//-----------------------------------------------------------------------------
+template <class T, class I>
+I CUtlNTree<T,I>::InsertChildBefore( I parent, I before )
+{
+	I elem = AllocInternal();
+	Construct( &Element( elem ) );
+	LinkChildBefore( parent, before, elem );
+	return elem;
+}
+
+template <class T, class I>
+I CUtlNTree<T,I>::InsertChildAfter( I parent, I after )
+{
+	I elem = AllocInternal();
+	Construct( &Element( elem ) );
+	LinkChildAfter( parent, after, elem );
+	return elem;
+}
+
+template <class T, class I>
+I CUtlNTree<T,I>::InsertChildBefore( I parent, I before, const T &data )
+{
+	I elem = AllocInternal();
+	CopyConstruct( &Element( elem ), data );
+	LinkChildBefore( parent, before, elem );
+	return elem;
+}
+
+template <class T, class I>
+I CUtlNTree<T,I>::InsertChildAfter( I parent, I after, const T &data )
+{
+	I elem = AllocInternal();
+	CopyConstruct( &Element( elem ), data );
+	LinkChildAfter( parent, after, elem );
+	return elem;
+}
+
+
+//-----------------------------------------------------------------------------
+// Unlink + free combined
+//-----------------------------------------------------------------------------
+template <class T, class I>
+void CUtlNTree<T,I>::Remove( I elem )
+{
+	Unlink( elem );
+	Free( elem );
+}
+
+template <class T, class I>
+void CUtlNTree<T,I>::RemoveSubTree( I elem )
+{
+	UnlinkSubTree( elem );
+	Free( elem );
+}
+  
+
+#endif // UTLNTREE_H