sources/list.h

/*
	Copyright 2014, 2015 Teemu Piippo
	All rights reserved.

	Redistribution and use in source and binary forms, with or without
	modification, are permitted provided that the following conditions
	are met:

	1. Redistributions of source code must retain the above copyright
	   notice, this list of conditions and the following disclaimer.
	2. Redistributions in binary form must reproduce the above copyright
	   notice, this list of conditions and the following disclaimer in the
	   documentation and/or other materials provided with the distribution.
	3. Neither the name of the copyright holder nor the names of its
	   contributors may be used to endorse or promote products derived from
	   this software without specific prior written permission.

	THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
	TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
	PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER
	OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
	EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
	PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
	PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
	LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
	NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
	SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

#pragma once
#include "basics.h"
#include <algorithm>
#include <deque>
#include <functional>
#include <cassert>
#include <vector>
#include "range.h"
BEGIN_ZFC_NAMESPACE

// -------------------------------------------------------------------------------------------------
//
template<typename T, typename C>
class Container
{
public:
	typedef typename C::iterator Iterator;
	typedef typename C::const_iterator ConstIterator;
	typedef typename C::reverse_iterator ReverseIterator;
	typedef typename C::const_reverse_iterator ConstReverseIterator;
	typedef Container<T, C> Self;

	Container(){}

	Container (int numvalues) :
		m_container (numvalues) {}

	Container (const C& other) :
		m_container (other) {}

	T& append (const T& value)
	{
		m_container.push_back (value);
		return m_container[m_container.size() - 1];
	}

	Iterator begin()
	{
		return m_container.begin();
	}

	ConstIterator begin() const
	{
		return m_container.begin();
	}

	void clear()
	{
		m_container.clear();
	}

	bool contains (const T& a) const
	{
		return std::find (m_container.begin(), m_container.end(), a) != m_container.end();
	}

	ConstReverseIterator crbegin() const
	{
		return m_container.rbegin();
	}

	ConstReverseIterator crend() const
	{
		return m_container.rend();
	}

	const C& container() const
	{
		return m_container;
	}

	Iterator end()
	{
		return m_container.end();
	}

	ConstIterator end() const
	{
		return m_container.end();
	}

	Iterator find (const T& needle)
	{
		auto it = std::find (m_container.begin(), m_container.end(), needle);

		if (it == m_container.end())
			return end();

		return it;
	}

	ConstIterator find (const T& needle) const
	{
		auto it = std::find (m_container.begin(), m_container.end(), needle);

		if (it == m_container.end())
			return end();

		return it;
	}

	Iterator find (bool (*func)(T const&))
	{
		for (Iterator it = begin(); it != end(); ++it)
		{
			if (func (*it))
				return it;
		}

		return end();
	}

	ConstIterator find (bool (*func)(T const&)) const
	{
		for (ConstIterator it = begin(); it != end(); ++it)
		{
			if (func (*it))
				return it;
		}

		return end();
	}

	T& first()
	{
		return *begin();
	}

	const T& first() const
	{
		return *begin();
	}

	void insert (int pos, const T& value)
	{
		m_container.insert (m_container.begin() + pos, value);
	}

	bool is_empty() const
	{
		return size() == 0;
	}

	T& last()
	{
		return *(end() - 1);
	}

	const T& last() const
	{
		return *(end() - 1);
	}

	void merge (const Self& other)
	{
		int oldsize = size();
		resize (size() + other.size());
		std::copy (other.begin(), other.end(), begin() + oldsize);
	}

	bool pop (T& val)
	{
		if (is_empty())
			return false;

		val = m_container[size() - 1];
		m_container.erase (m_container.end() - 1);
		return true;
	}

	T& prepend (const T& value)
	{
		m_container.push_front (value);
		return m_container[0];
	}

	ReverseIterator rbegin()
	{
		return m_container.rbegin();
	}

	void remove_at (int pos)
	{
		assert (pos < size());
		m_container.erase (m_container.begin() + pos);
	}

	void remove_duplicates()
	{
		sort();
		resize (std::distance (begin(), std::unique (begin(), end())));
	}

	void remove_one (const T& valueToRemove)
	{
		auto it = std::find (m_container.begin(), m_container.end(), valueToRemove);

		if (it != m_container.end())
			m_container.erase (it);
	}

	ReverseIterator rend()
	{
		return m_container.rend();
	}

	void resize (int size)
	{
		m_container.resize (size);
	}

	Self reverse() const
	{
		Self rev;
		std::copy (rbegin(), rend(), rev.begin());
		return rev;
	}

	int size() const
	{
		return m_container.size();
	}

	void sort()
	{
		std::sort (begin(), end());
	}

	Self splice (int a, int b) const
	{
		if (a < 0 or b >= size() or b < a)
			return Self();

		Self result;

		for (int i = a; i <= b; ++i)
			result << operator[] (i);

		return result;
	}

	Self splice (const Range<int>& a) const
	{
		return splice (a.min(), a.max());
	}

	Self& operator<< (const T& value)
	{
		append (value);
		return *this;
	}

	Self& operator<< (const Self& vals)
	{
		merge (vals);
		return *this;
	}

	T& operator[] (int n)
	{
		assert (n < size());
		return m_container[n];
	}

	const T& operator[] (int n) const
	{
		assert (n < size());
		return m_container[n];
	}

	Self operator[] (Range<int> const& n) const
	{
		return splice (n);
	}

	Self operator+ (const Self& other) const
	{
		Self out (*this);
		out.merge (other);
		return out;
	}

protected:
	C m_container;
};

// -------------------------------------------------------------------------------------------------
//
template<typename T, typename C>
Container<T, C>& operator>> (const T& value, Container<T, C>& haystack)
{
	haystack.prepend (value);
	return haystack;
}

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

template<typename T>
class List : public Container<T, std::deque<T> >
{
public:
	typedef Container<T, std::deque<T> > Super;

	List(){}

	List (int numvalues) :
		Super (numvalues) {}

	List (const Super& other) :
		Super (other) {}
};

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

template<typename T>
class Vector : public Container<T, std::vector<T> >
{
public:
	typedef Container<T, std::vector<T> > Super;

	Vector(){}

	Vector (T* data, size_t length) :
		Super (std::vector<T> (data, data + length)) {}

	T* data()
	{
		return Super::m_container.data();
	}

	const T* data() const
	{
		return Super::m_container.data();
	}

	operator const T*() const
	{
		return data();
	}
};

END_ZFC_NAMESPACE