A heap to keep track of the max N of a stream of values.

heap-filter.cpp

#ifndef HEAP_FILTER_HPP
#define HEAP_FILTER_HPP

#include <algorithm>
#include <cstddef>
#include <initializer_list>
#include <stdexcept>

template<typename T>
class HeapFilter
{
public:
	
	using size_t = std::size_t;
	
	HeapFilter(size_t limit = 10)
	: _size(0)
	, _limit(limit)
	, _data(new T[limit])
	{ }
	
	HeapFilter(std::initializer_list<T> list,
			   size_t limit = 10)
	: _size(0)
	, _limit(std::max(limit, list.size()))
	, _data(new T[_limit])
	{
		for (const auto& item : list) push(item);
	}
	
	HeapFilter(const HeapFilter& other)
	: _size(other._size)
	, _limit(other._limit)
	, _data(new T[other._limit])
	{
		std::copy(other._data, other._data + other._size, _data);
	}
	
	HeapFilter(HeapFilter&& other) noexcept
	: HeapFilter()
	{
		swap(other);
	}
	
	HeapFilter& operator=(HeapFilter other)
	{
		swap(other);
		
		return *this;
	}
	
	void swap(HeapFilter& other) noexcept
	{
		using std::swap;
		
		swap(_size, other._size);
		
		swap(_limit, other._limit);
		
		swap(_data, other._data);
	}
	
	friend void swap(HeapFilter& first, HeapFilter& second) noexcept
	{
		first.swap(second);
	}
	
	~HeapFilter()
	{
		delete [] _data;
	}
	
	
	void push(const T& item)
	{
		if (_size < _limit)
		{
			_data[++_size] = item;
			
			_swim(_size);
		}
		
		else if (item > _data[1])
		{
			_data[1] = item;
			
			_sink(1);
		}
	}
	
	
	const T& top()
	{
		if (is_empty())
		{
			throw std::out_of_range("Nothing at top!");
		}
		
		return _data[1];
	}
	
	T pop()
	{
		if (is_empty())
		{
			throw std::out_of_range("Nothing at top!");
		}
		
		_swap(1, _size--);
		
		_sink(1);
		
		return _data[_size + 1];
	}
	
	void clear()
	{
		delete [] _data;
		
		_data = new T[_limit];
		
		_size = 0;
	}
	
	
	size_t limit() const
	{
		return _limit;
	}
	
	void limit(size_t new_limit)
	{
		auto old = _data;
		
		_limit = new_limit;
		
		_data = new T[_limit];
		
		std::copy(old, old + _size, _data);
		
		delete [] old;
	}
	
	
	size_t size() const
	{
		return _size;
	}
	
	bool is_empty()
	{
		return _size == 0;
	}
	
private:
	
	constexpr inline size_t _parent(size_t index) const
	{
		return index == 1 ? index : index / 2;
	}
	
	constexpr inline size_t _left(size_t index) const
	{
		return 2 * index;
	}
	
	constexpr inline size_t _right(size_t index) const
	{
		return 2 * index + 1;
	}
	
	void _sink(size_t index)
	{
		while (index < _size)
		{
			auto left = _left(index);
			
			if (left > _size) return;
			
			auto right = _right(index);
			
			size_t child;
			
			if (right > _size || _data[left] <= _data[right]) child = left;
			
			else child = right;
			
			if (_data[child] < _data[index])
			{
				_swap(child, index);
			}
			
			else break;
			
			index = child;
		}
	}
	
	void _swim(size_t index)
	{
		auto parent = _parent(index);
		
		while (_data[parent] > _data[index])
		{
			_swap(parent, index);
			
			index = parent;
			
			parent = _parent(index);
		}
	}
	
	inline void _swap(size_t first, size_t second)
	{
		using std::swap;
		
		swap(_data[first], _data[second]);
	}
	
	
	size_t _size;
	
	size_t _limit;
	
	T* _data;
	
};

#endif /* HEAP_FILTER_HPP */