<commit_before>// This code is in the public domain -- <EMAIL>

#ifndef NV_CORE_CONTAINER_H
#define NV_CORE_CONTAINER_H

/*
These containers are based on Thatcher Ulrich <<EMAIL>> containers,
donated to the Public Domain.

I've also borrowed some ideas from the Qt toolkit, specially the cool
foreach iterator.

TODO
Do not use memmove in insert & remove, use copy ctors instead.
*/


// nvcore
#include <nvcore/nvcore.h>
#include <nvcore/Memory.h>
#include <nvcore/Debug.h>

#include <string.h>	// memmove
#include <new>		// for placement new


#if NV_CC_GNUC // If typeof is available:

#define NV_FOREACH(i, container) \
	typedef typeof(container) NV_STRING_JOIN2(cont,__LINE__); \
	for(NV_STRING_JOIN2(cont,__LINE__)::PseudoIndex i((container).start()); !(container).isDone(i); (container).advance(i))
/*
#define NV_FOREACH(i, container) \
	for(typename typeof(container)::PseudoIndex i((container).start()); !(container).isDone(i); (container).advance(i))
*/

#else // If typeof not available:

struct PseudoIndexWrapper {
	template <typename T>
	PseudoIndexWrapper(const T & container) {
		nvStaticCheck(sizeof(typename T::PseudoIndex) <= sizeof(memory));
		new (memory) typename T::PseudoIndex(container.start());
	}
	// PseudoIndex cannot have a dtor!

	template <typename T> typename T::PseudoIndex & operator()(const T * container) {
		return *reinterpret_cast<typename T::PseudoIndex *>(memory);
	}
	template <typename T> const typename T::PseudoIndex & operator()(const T * container) const {
		return *reinterpret_cast<const typename T::PseudoIndex *>(memory);
	}

	uint8 memory[4];	// Increase the size if we have bigger enumerators.
};

#define NV_FOREACH(i, container) \
	for(PseudoIndexWrapper i(container); !(container).isDone(i(&(container))); (container).advance(i(&(container))))

#endif

// Declare foreach keyword.
#if !defined NV_NO_USE_KEYWORDS
#	define foreach NV_FOREACH
#endif



namespace nv 
{
	// Templates

	/// Return the maximum of two values.
	template <typename T> 
	inline const T & max(const T & a, const T & b)
	{
		//return std::max(a, b);
		if( a < b ) {
			return b; 
		}
		return a;
	}
	
	/// Return the minimum of two values.
	template <typename T> 
	inline const T & min(const T & a, const T & b)
	{
		//return std::min(a, b);
		if( b < a ) {
			return b; 
		}
		return a;
	}
	
	/// Clamp between two values.
	template <typename T> 
	inline const T & clamp(const T & x, const T & a, const T & b)
	{
		return min(max(x, a), b);
	}
	
	/// Swap two values.
	template <typename T> 
	inline void swap(T & a, T & b)
	{
		//return std::swap(a, b);
		T temp = a; 
		a = b; 
		b = temp;
	}

	template <typename Key> struct hash 
	{
		inline uint sdbm_hash(const void * data_in, uint size, uint h = 5381)
		{
			const uint8 * data = (const uint8 *) data_in;
			uint i = 0;
			while (i < size) {
				h = (h << 16) + (h << 6) - h + (uint) data[i++];
			}
			return h;
		}
		
		uint operator()(const Key & k) {
			return sdbm_hash(&k, sizeof(Key));
		}
	};
	template <> struct hash<int>
	{
		uint operator()(int x) const { return x; }
	};
	template <> struct hash<uint>
	{
		uint operator()(uint x) const { return x; }
	};
	
	/// Delete all the elements of a container.
	template <typename T>
	void deleteAll(T & container)
	{
		for(typename T::PseudoIndex i = container.start(); !container.isDone(i); container.advance(i))
		{
			delete container[i];
		}
	}

	
	/** Return the next power of two. 
	* @see http://graphics.stanford.edu/~seander/bithacks.html
	* @warning Behaviour for 0 is undefined.
	* @note isPowerOfTwo(x) == true -> nextPowerOfTwo(x) == x
	* @note nextPowerOfTwo(x) = 2 << log2(x-1)
	*/
	inline uint nextPowerOfTwo( uint x )
	{
		nvDebugCheck( x != 0 );
	#if 1	// On modern CPUs this is as fast as using the bsr instruction.
		x--;
		x |= x >> 1;
		x |= x >> 2;
		x |= x >> 4;
		x |= x >> 8;
		x |= x >> 16;
		return x+1;	
	#else
		uint p = 1;
		while( x > p ) {
			p += p;
		}
		return p;
	#endif
	}

	/// Return true if @a n is a power of two.
	inline bool isPowerOfTwo( uint n )
	{
		return (n & (n-1)) == 0;
	}

	/// Simple iterator interface.
	template <typename T>
	struct Iterator
	{
		virtual void advance();
		virtual bool isDone();
		virtual T current();
	};


	/**
	* Replacement for std::vector that is easier to debug and provides
	* some nice foreach enumerators. 
	*/
	template<typename T>
	class NVCORE_CLASS Array {
	public:
		
		/// Ctor.
		Array() : m_buffer(NULL), m_size(0), m_buffer_size(0)
		{
		}
	
		/// Copy ctor.
		Array( const Array & a ) : m_buffer(NULL), m_size(0), m_buffer_size(0)
		{
			copy(a.m_buffer, a.m_size); 
		}
	
		/// Ctor that initializes the vector with the given elements.
		Array( const T * ptr, int num ) : m_buffer(NULL), m_size(0), m_buffer_size(0)
		{
			copy(ptr, num);
		}
	
		/// Allocate array.
		explicit Array(uint capacity) : m_buffer(NULL), m_size(0), m_buffer_size(0)
		{
			allocate(capacity);
		}
		
	
		/// Dtor.
		~Array()
		{
			clear();
			allocate(0);
		}
	
	
		/// Const and save vector access.
		const T & operator[]( uint index ) const
		{
			nvDebugCheck(index < m_size);
			return m_buffer[index];
		}
	
		/// Safe vector access.
		T & operator[] ( uint index )
		{
			nvDebugCheck(index < m_size);
			return m_buffer[index];
		}
	
	
		/// Get vector size.
		uint size() const { return m_size; }
		
		/// Get vector size.
		uint count() const { return m_size; }
	
		/// Get const vector pointer.
		const T * buffer() const { return m_buffer; }
	
		/// Get vector pointer.
		T * unsecureBuffer() { return m_buffer; }
	
		/// Is vector empty.
		bool isEmpty() const { return m_size == 0; }
	
		/// Is a null vector.
		bool isNull() const	{ return m_buffer == NULL; }
	
	
		/// Push an element at the end of the vector.
		void push_back( const T & val )
		{
			uint new_size = m_size + 1;

			if (new_size > m_buffer_size)
			{
				const T copy(val);	// create a copy in case value is inside of this array.
				resize(new_size);
				m_buffer[new_size-1] = copy;
			}
			else
			{
				m_size = new_size;
				new(m_buffer+new_size-1) T(val);
			}
		}
		void pushBack( const T & val )
		{
			push_back(val);
		}
		void append( const T & val )
		{
			push_back(val);
		}
		
		/// Qt like push operator.
		Array<T> & operator<< ( T & t )
		{
			push_back(t);
			return *this;
		}
		
		/// Pop and return element at the end of the vector.
		void pop_back()
		{
			nvDebugCheck( m_size > 0 );
			resize( m_size - 1 );
		}
		void popBack()
		{
			pop_back();
		}
		
		/// Get back element.
		const T & back() const
		{
			nvDebugCheck( m_size > 0 );
			return m_buffer[m_size-1];
		}
		
		/// Get back element.
		T & back()
		{
			nvDebugCheck( m_size > 0 );
			return m_buffer[m_size-1];
		}
		
		/// Get front element.
		const T & front() const
		{
			nvDebugCheck( m_size > 0 );
			return m_buffer[0];
		}
		
		/// Get front element.
		T & front()
		{
			nvDebugCheck( m_size > 0 );
			return m_buffer[0];
		}
		
		/// Check if the given element is contained in the array.
		bool contains(const T & e) const
		{
			for (uint i = 0; i < m_size; i++) {
				if (m_buffer[i] == e) return true;
			}
			return false;
		}
		
		/// Remove the element at the given index. This is an expensive operation!
		void removeAt( uint index )
		{
			nvCheck(index >= 0 && index < m_size);
			
			if( m_size == 1 ) {
				clear();
			}
			else {
				m_buffer[index].~T();
				
				memmove( m_buffer+index, m_buffer+index+1, sizeof(T) * (m_size - 1 - index) );
				m_size--;
			}
		}
		
		/// Remove the first instance of the given element.
		void remove(const T & element)
		{
			for(PseudoIndex i = start(); !isDone(i); advance(i)) {
				removeAt(i);
				break;
			}
		}
		
		/// Insert the given element at the given index shifting all the elements up.
		void insertAt( uint index, const T & val = T() )
		{
			nvCheck( index >= 0 && index <= m_size );
			
			resize( m_size + 1 );
			
			if( index < m_size - 1 ) {
				memmove( m_buffer+index+1, m_buffer+index, sizeof(T) * (m_size - 1 - index) );
			}
			
			// Copy-construct into the newly opened slot.
			new(m_buffer+index) T(val);
		}
		
		/// Append the given data to our vector.
		void append(const Array<T> & other)
		{
			append(other.m_buffer, other.m_size);
		}
		
		/// Append the given data to our vector.
		void append(const T other[], uint count)
		{
			if( count > 0 ) {
				const uint old_size = m_size;
				resize(m_size + count);
				// Must use operator=() to copy elements, in case of side effects (e.g. ref-counting).
				for( uint i = 0; i < count; i++ ) {
					m_buffer[old_size + i] = other[i];
				}
			}
		}
		
		
		/// Remove the given element by replacing it with the last one.
		void replaceWithLast(uint index)
		{
			nvDebugCheck( index < m_size );
			m_buffer[index] = back();
			(m_buffer+m_size-1)->~T();
			m_size--;
		}
	
	
		/// Resize the vector preserving existing elements.
		void resize(uint new_size)
		{
			uint i;
			uint old_size = m_size;
			m_size = new_size;
			
			// Destruct old elements (if we're shrinking).
			for( i = new_size; i < old_size; i++ ) {
				(m_buffer+i)->~T();							// Explicit call to the destructor
			}
			
			if( m_size == 0 ) {
				//Allocate(0);	// Don't shrink automatically.
			}
			else if( m_size <= m_buffer_size/* && m_size > m_buffer_size >> 1*/) {
				// don't compact yet.
				nvDebugCheck(m_buffer != NULL);
			}
			else {
				uint new_buffer_size;
				if( m_buffer_size == 0 ) {
					// first allocation
					new_buffer_size = m_size;
				}
				else {
					// growing
					new_buffer_size = m_size + (m_size >> 2);
				}
				allocate( new_buffer_size );
			}
			
			// Call default constructors
			for( i = old_size; i < new_size; i++ ) {
				new(m_buffer+i) T();	// placement new
			}
		}
	
	
		/// Resize the vector preserving existing elements and initializing the
		/// new ones with the given value.
		void resize( uint new_size, const T &elem )
		{
			uint i;
			uint old_size = m_size;
			m_size = new_size;
			
			// Destruct old elements (if we're shrinking).
			for( i = new_size; i < old_size; i++ ) {
				(m_buffer+i)->~T();							// Explicit call to the destructor
			}
			
			if( m_size == 0 ) {
				//Allocate(0);	// Don't shrink automatically.
			}
			else if( m_size <= m_buffer_size && m_size > m_buffer_size >> 1 ) {
				// don't compact yet.
			}
			else {
				uint new_buffer_size;<commit_msg>Do not use constructor that initializes POD types.<commit_after>// This code is in the public domain -- <EMAIL>

#ifndef NV_CORE_CONTAINER_H
#define NV_CORE_CONTAINER_H

/*
These containers are based on Thatcher Ulrich <<EMAIL>> containers,
donated to the Public Domain.

I've also borrowed some ideas from the Qt toolkit, specially the cool
foreach iterator.

TODO
Do not use memmove in insert & remove, use copy ctors instead.
*/


// nvcore
#include <nvcore/nvcore.h>
#include <nvcore/Memory.h>
#include <nvcore/Debug.h>

#include <string.h>	// memmove
#include <new>		// for placement new


#if NV_CC_GNUC // If typeof is available:

#define NV_FOREACH(i, container) \
	typedef typeof(container) NV_STRING_JOIN2(cont,__LINE__); \
	for(NV_STRING_JOIN2(cont,__LINE__)::PseudoIndex i((container).start()); !(container).isDone(i); (container).advance(i))
/*
#define NV_FOREACH(i, container) \
	for(typename typeof(container)::PseudoIndex i((container).start()); !(container).isDone(i); (container).advance(i))
*/

#else // If typeof not available:

struct PseudoIndexWrapper {
	template <typename T>
	PseudoIndexWrapper(const T & container) {
		nvStaticCheck(sizeof(typename T::PseudoIndex) <= sizeof(memory));
		new (memory) typename T::PseudoIndex(container.start());
	}
	// PseudoIndex cannot have a dtor!

	template <typename T> typename T::PseudoIndex & operator()(const T * container) {
		return *reinterpret_cast<typename T::PseudoIndex *>(memory);
	}
	template <typename T> const typename T::PseudoIndex & operator()(const T * container) const {
		return *reinterpret_cast<const typename T::PseudoIndex *>(memory);
	}

	uint8 memory[4];	// Increase the size if we have bigger enumerators.
};

#define NV_FOREACH(i, container) \
	for(PseudoIndexWrapper i(container); !(container).isDone(i(&(container))); (container).advance(i(&(container))))

#endif

// Declare foreach keyword.
#if !defined NV_NO_USE_KEYWORDS
#	define foreach NV_FOREACH
#endif



namespace nv 
{
	// Templates

	/// Return the maximum of two values.
	template <typename T> 
	inline const T & max(const T & a, const T & b)
	{
		//return std::max(a, b);
		if( a < b ) {
			return b; 
		}
		return a;
	}
	
	/// Return the minimum of two values.
	template <typename T> 
	inline const T & min(const T & a, const T & b)
	{
		//return std::min(a, b);
		if( b < a ) {
			return b; 
		}
		return a;
	}
	
	/// Clamp between two values.
	template <typename T> 
	inline const T & clamp(const T & x, const T & a, const T & b)
	{
		return min(max(x, a), b);
	}
	
	/// Swap two values.
	template <typename T> 
	inline void swap(T & a, T & b)
	{
		//return std::swap(a, b);
		T temp = a; 
		a = b; 
		b = temp;
	}

	template <typename Key> struct hash 
	{
		inline uint sdbm_hash(const void * data_in, uint size, uint h = 5381)
		{
			const uint8 * data = (const uint8 *) data_in;
			uint i = 0;
			while (i < size) {
				h = (h << 16) + (h << 6) - h + (uint) data[i++];
			}
			return h;
		}
		
		uint operator()(const Key & k) {
			return sdbm_hash(&k, sizeof(Key));
		}
	};
	template <> struct hash<int>
	{
		uint operator()(int x) const { return x; }
	};
	template <> struct hash<uint>
	{
		uint operator()(uint x) const { return x; }
	};
	
	/// Delete all the elements of a container.
	template <typename T>
	void deleteAll(T & container)
	{
		for(typename T::PseudoIndex i = container.start(); !container.isDone(i); container.advance(i))
		{
			delete container[i];
		}
	}

	
	/** Return the next power of two. 
	* @see http://graphics.stanford.edu/~seander/bithacks.html
	* @warning Behaviour for 0 is undefined.
	* @note isPowerOfTwo(x) == true -> nextPowerOfTwo(x) == x
	* @note nextPowerOfTwo(x) = 2 << log2(x-1)
	*/
	inline uint nextPowerOfTwo( uint x )
	{
		nvDebugCheck( x != 0 );
	#if 1	// On modern CPUs this is as fast as using the bsr instruction.
		x--;
		x |= x >> 1;
		x |= x >> 2;
		x |= x >> 4;
		x |= x >> 8;
		x |= x >> 16;
		return x+1;	
	#else
		uint p = 1;
		while( x > p ) {
			p += p;
		}
		return p;
	#endif
	}

	/// Return true if @a n is a power of two.
	inline bool isPowerOfTwo( uint n )
	{
		return (n & (n-1)) == 0;
	}

	/// Simple iterator interface.
	template <typename T>
	struct Iterator
	{
		virtual void advance();
		virtual bool isDone();
		virtual T current();
	};


	/**
	* Replacement for std::vector that is easier to debug and provides
	* some nice foreach enumerators. 
	*/
	template<typename T>
	class NVCORE_CLASS Array {
	public:
		
		/// Ctor.
		Array() : m_buffer(NULL), m_size(0), m_buffer_size(0)
		{
		}
	
		/// Copy ctor.
		Array( const Array & a ) : m_buffer(NULL), m_size(0), m_buffer_size(0)
		{
			copy(a.m_buffer, a.m_size); 
		}
	
		/// Ctor that initializes the vector with the given elements.
		Array( const T * ptr, int num ) : m_buffer(NULL), m_size(0), m_buffer_size(0)
		{
			copy(ptr, num);
		}
	
		/// Allocate array.
		explicit Array(uint capacity) : m_buffer(NULL), m_size(0), m_buffer_size(0)
		{
			allocate(capacity);
		}
		
	
		/// Dtor.
		~Array()
		{
			clear();
			allocate(0);
		}
	
	
		/// Const and save vector access.
		const T & operator[]( uint index ) const
		{
			nvDebugCheck(index < m_size);
			return m_buffer[index];
		}
	
		/// Safe vector access.
		T & operator[] ( uint index )
		{
			nvDebugCheck(index < m_size);
			return m_buffer[index];
		}
	
	
		/// Get vector size.
		uint size() const { return m_size; }
		
		/// Get vector size.
		uint count() const { return m_size; }
	
		/// Get const vector pointer.
		const T * buffer() const { return m_buffer; }
	
		/// Get vector pointer.
		T * unsecureBuffer() { return m_buffer; }
	
		/// Is vector empty.
		bool isEmpty() const { return m_size == 0; }
	
		/// Is a null vector.
		bool isNull() const	{ return m_buffer == NULL; }
	
	
		/// Push an element at the end of the vector.
		void push_back( const T & val )
		{
			uint new_size = m_size + 1;

			if (new_size > m_buffer_size)
			{
				const T copy(val);	// create a copy in case value is inside of this array.
				resize(new_size);
				m_buffer[new_size-1] = copy;
			}
			else
			{
				m_size = new_size;
				new(m_buffer+new_size-1) T(val);
			}
		}
		void pushBack( const T & val )
		{
			push_back(val);
		}
		void append( const T & val )
		{
			push_back(val);
		}
		
		/// Qt like push operator.
		Array<T> & operator<< ( T & t )
		{
			push_back(t);
			return *this;
		}
		
		/// Pop and return element at the end of the vector.
		void pop_back()
		{
			nvDebugCheck( m_size > 0 );
			resize( m_size - 1 );
		}
		void popBack()
		{
			pop_back();
		}
		
		/// Get back element.
		const T & back() const
		{
			nvDebugCheck( m_size > 0 );
			return m_buffer[m_size-1];
		}
		
		/// Get back element.
		T & back()
		{
			nvDebugCheck( m_size > 0 );
			return m_buffer[m_size-1];
		}
		
		/// Get front element.
		const T & front() const
		{
			nvDebugCheck( m_size > 0 );
			return m_buffer[0];
		}
		
		/// Get front element.
		T & front()
		{
			nvDebugCheck( m_size > 0 );
			return m_buffer[0];
		}
		
		/// Check if the given element is contained in the array.
		bool contains(const T & e) const
		{
			for (uint i = 0; i < m_size; i++) {
				if (m_buffer[i] == e) return true;
			}
			return false;
		}
		
		/// Remove the element at the given index. This is an expensive operation!
		void removeAt( uint index )
		{
			nvCheck(index >= 0 && index < m_size);
			
			if( m_size == 1 ) {
				clear();
			}
			else {
				m_buffer[index].~T();
				
				memmove( m_buffer+index, m_buffer+index+1, sizeof(T) * (m_size - 1 - index) );
				m_size--;
			}
		}
		
		/// Remove the first instance of the given element.
		void remove(const T & element)
		{
			for(PseudoIndex i = start(); !isDone(i); advance(i)) {
				removeAt(i);
				break;
			}
		}
		
		/// Insert the given element at the given index shifting all the elements up.
		void insertAt( uint index, const T & val = T() )
		{
			nvCheck( index >= 0 && index <= m_size );
			
			resize( m_size + 1 );
			
			if( index < m_size - 1 ) {
				memmove( m_buffer+index+1, m_buffer+index, sizeof(T) * (m_size - 1 - index) );
			}
			
			// Copy-construct into the newly opened slot.
			new(m_buffer+index) T(val);
		}
		
		/// Append the given data to our vector.
		void append(const Array<T> & other)
		{
			append(other.m_buffer, other.m_size);
		}
		
		/// Append the given data to our vector.
		void append(const T other[], uint count)
		{
			if( count > 0 ) {
				const uint old_size = m_size;
				resize(m_size + count);
				// Must use operator=() to copy elements, in case of side effects (e.g. ref-counting).
				for( uint i = 0; i < count; i++ ) {
					m_buffer[old_size + i] = other[i];
				}
			}
		}
		
		
		/// Remove the given element by replacing it with the last one.
		void replaceWithLast(uint index)
		{
			nvDebugCheck( index < m_size );
			m_buffer[index] = back();
			(m_buffer+m_size-1)->~T();
			m_size--;
		}
	
	
		/// Resize the vector preserving existing elements.
		void resize(uint new_size)
		{
			uint i;
			uint old_size = m_size;
			m_size = new_size;
			
			// Destruct old elements (if we're shrinking).
			for( i = new_size; i < old_size; i++ ) {
				(m_buffer+i)->~T();							// Explicit call to the destructor
			}
			
			if( m_size == 0 ) {
				//Allocate(0);	// Don't shrink automatically.
			}
			else if( m_size <= m_buffer_size/* && m_size > m_buffer_size >> 1*/) {
				// don't compact yet.
				nvDebugCheck(m_buffer != NULL);
			}
			else {
				uint new_buffer_size;
				if( m_buffer_size == 0 ) {
					// first allocation
					new_buffer_size = m_size;
				}
				else {
					// growing
					new_buffer_size = m_size + (m_size >> 2);
				}
				allocate( new_buffer_size );
			}
			
			// Call default constructors
			for( i = old_size; i < new_size; i++ ) {
				new(m_buffer+i) T;	// placement new
			}
		}
	
	
		/// Resize the vector preserving existing elements and initializing the
		/// new ones with the given value.
		void resize( uint new_size, const T &elem )
		{
			uint i;
			uint old_size = m_size;
			m_size = new_size;
			
			// Destruct old elements (if we're shrinking).
			for( i = new_size; i < old_size; i++ ) {
				(m_buffer+i)->~T();							// Explicit call to the destructor
			}
			
			if( m_size == 0 ) {
				//Allocate(0);	// Don't shrink automatically.
			}
			else if( m_size <= m_buffer_size && m_size > m_buffer_size >> 1 ) {
				// don't compact yet.
			}
			else {
				uint new_buffer_size;
{'fraction_non_alphanumeric': 0.1412314962148609, 'fraction_numerical': 0.0071363132262886346, 'mean_word_length': 2.6214422909027415, 'pattern_counts': {'":': 0, '<': 107, '<?xml version=': 0, '>': 121, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5796471', 'n_tokens_mistral': 8814, 'n_tokens_neox': 7448, 'n_words': 2224}