www.pudn.com > tristripper-1.1.0-beta-5.zip > heap_array.h

// 
// Copyright (C) 2004 Tanguy Fautré. 
// For conditions of distribution and use, 
// see copyright notice in tri_stripper.h 
// 
////////////////////////////////////////////////////////////////////// 
// SVN: $Id: heap_array.h 86 2005-06-08 17:47:27Z gpsnoopy $ 
////////////////////////////////////////////////////////////////////// 
 
#ifndef TRI_STRIPPER_HEADER_GUARD_HEAP_ARRAY_H 
#define TRI_STRIPPER_HEADER_GUARD_HEAP_ARRAY_H 
 
#include  
 
 
 
 
namespace triangle_stripper { 
 
	namespace detail { 
 
 
 
 
// mutable heap 
// can be interfaced pretty muck like an array 
template  >  
class heap_array 
{ 
public: 
 
	// Pre = PreCondition, Post = PostCondition  
 
	heap_array() : m_Locked(false) { }		// Post: ((size() == 0) && ! locked()) 
 
	void clear();							// Post: ((size() == 0) && ! locked()) 
 
	void reserve(size_t Size); 
	size_t size() const; 
 
	bool empty() const; 
	bool locked() const; 
	bool removed(size_t i) const;			// Pre: (valid(i)) 
	bool valid(size_t i) const; 
 
	size_t position(size_t i) const;		// Pre: (valid(i)) 
 
	const T & top() const;					// Pre: (! empty()) 
	const T & peek(size_t i) const;			// Pre: (! removed(i)) 
	const T & operator [] (size_t i) const;	// Pre: (! removed(i)) 
 
	void lock();							// Pre: (! locked())   Post: (locked()) 
	size_t push(const T & Elem);			// Pre: (! locked()) 
 
	void pop();								// Pre: (locked() && ! empty()) 
	void erase(size_t i);					// Pre: (locked() && ! removed(i)) 
	void update(size_t i, const T & Elem);	// Pre: (locked() && ! removed(i)) 
 
protected: 
 
	heap_array(const heap_array &); 
	heap_array & operator = (const heap_array &); 
 
	class linker 
	{ 
	public: 
		linker(const T & Elem, size_t i) 
			: m_Elem(Elem), m_Index(i) { } 
 
		T		m_Elem; 
		size_t	m_Index; 
	}; 
 
	typedef std::vector linked_heap; 
	typedef std::vector finder; 
 
	void Adjust(size_t i); 
	void Swap(size_t a, size_t b); 
	bool Less(const linker & a, const linker & b) const; 
 
	linked_heap	m_Heap; 
	finder		m_Finder; 
	CmpT		m_Compare; 
	bool		m_Locked; 
}; 
 
 
 
 
 
////////////////////////////////////////////////////////////////////////// 
// heap_indexed inline functions 
////////////////////////////////////////////////////////////////////////// 
 
template   
inline void heap_array::clear() 
{ 
	m_Heap.clear(); 
	m_Finder.clear(); 
	m_Locked = false; 
} 
 
 
template   
inline bool heap_array::empty() const 
{ 
	return m_Heap.empty(); 
} 
 
 
template  
inline bool heap_array::locked() const 
{ 
	return m_Locked; 
} 
 
 
template  
inline void heap_array::reserve(const size_t Size) 
{ 
	m_Heap.reserve(Size); 
	m_Finder.reserve(Size); 
} 
 
 
template   
inline size_t heap_array::size() const 
{ 
	return m_Heap.size(); 
} 
 
 
template   
inline const T & heap_array::top() const 
{ 
	assert(! empty()); 
 
	return m_Heap.front().m_Elem; 
} 
 
 
template   
inline const T & heap_array::peek(const size_t i) const 
{ 
	assert(! removed(i)); 
 
	return (m_Heap[m_Finder[i]].m_Elem); 
} 
 
 
template   
inline const T & heap_array::operator [] (const size_t i) const 
{ 
	return peek(i); 
} 
 
 
template   
inline void heap_array::pop() 
{ 
	assert(locked()); 
	assert(! empty()); 
 
	Swap(0, size() - 1); 
	m_Heap.pop_back(); 
 
	if (! empty()) 
		Adjust(0); 
} 
 
 
template  
inline void heap_array::lock() 
{ 
	assert(! locked()); 
 
	m_Locked =true; 
} 
 
 
template   
inline size_t heap_array::push(const T & Elem) 
{ 
	assert(! locked()); 
 
	const size_t Id = size(); 
	m_Finder.push_back(Id); 
	m_Heap.push_back(linker(Elem, Id)); 
	Adjust(Id); 
 
	return Id; 
} 
 
 
template  
inline void heap_array::erase(const size_t i) 
{ 
	assert(locked()); 
	assert(! removed(i)); 
 
	const size_t j = m_Finder[i]; 
	Swap(j, size() - 1); 
	m_Heap.pop_back(); 
 
	if (j != size()) 
		Adjust(j); 
} 
 
 
template  
inline bool heap_array::removed(const size_t i) const 
{ 
	assert(valid(i)); 
 
	return (m_Finder[i] >= m_Heap.size()); 
} 
 
 
template  
inline bool heap_array::valid(const size_t i) const 
{ 
	return (i < m_Finder.size()); 
} 
 
 
template  
inline size_t heap_array::position(const size_t i) const 
{ 
	assert(valid(i)); 
 
	return (m_Heap[i].m_Index); 
} 
 
 
template   
inline void heap_array::update(const size_t i, const T & Elem) 
{ 
	assert(locked()); 
	assert(! removed(i)); 
 
	const size_t j = m_Finder[i]; 
	m_Heap[j].m_Elem = Elem; 
	Adjust(j); 
} 
 
 
template   
inline void heap_array::Adjust(size_t i) 
{ 
	assert(i < m_Heap.size()); 
 
	size_t j; 
 
	// Check the upper part of the heap 
	for (j = i; (j > 0) && (Less(m_Heap[(j - 1) / 2], m_Heap[j])); j = ((j - 1) / 2)) 
		Swap(j, (j - 1) / 2); 
 
	// Check the lower part of the heap 
	for (i = j; (j = 2 * i + 1) < size(); i = j) { 
 		if ((j + 1 < size()) && (Less(m_Heap[j], m_Heap[j + 1]))) 
			++j; 
 
		if (Less(m_Heap[j], m_Heap[i])) 
			return; 
 
		Swap(i, j); 
	} 
} 
 
 
template   
inline void heap_array::Swap(const size_t a, const size_t b) 
{ 
	std::swap(m_Heap[a], m_Heap[b]); 
 
	m_Finder[(m_Heap[a].m_Index)] = a; 
	m_Finder[(m_Heap[b].m_Index)] = b; 
} 
 
 
template  
inline bool heap_array::Less(const linker & a, const linker & b) const 
{ 
	return m_Compare(a.m_Elem, b.m_Elem); 
} 
 
 
 
 
	} // namespace detail 
 
} // namespace triangle_stripper 
 
 
 
 
#endif // TRI_STRIPPER_HEADER_GUARD_HEAP_ARRAY_H