--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/sources/list.h Wed Dec 10 19:17:00 2014 +0200
@@ -0,0 +1,609 @@
+/*
+ Copyright 2014 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 <initializer_list>
+#include <functional>
+#include <cassert>
+#include "range.h"
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+class Container
+{
+public:
+ using Iterator = typename C::iterator;
+ using ConstIterator = typename C::const_iterator;
+ using ReverseIterator = typename C::reverse_iterator;
+ using ConstReverseIterator = typename C::const_reverse_iterator;
+ using Self = Container<T, C>;
+
+ Container();
+ Container (int numvalues);
+ Container (const C& a);
+ Container (std::initializer_list<T>&& a);
+
+ auto append (const T& value) -> T&;
+ auto begin() -> Iterator;
+ auto begin() const -> ConstIterator;
+ auto clear() -> void;
+ auto contains (const T& a) const -> bool;
+ auto crbegin() const -> ConstReverseIterator;
+ auto crend() const -> ConstReverseIterator;
+ auto container() const -> const C&;
+ auto end() -> Iterator;
+ auto end() const -> ConstIterator;
+ auto find (const T& needle) -> Iterator;
+ auto find (const T& needle) const -> ConstIterator;
+ auto find (Function<bool (T const&)> func) -> Iterator;
+ auto find (Function<bool (T const&)> func) const -> ConstIterator;
+ auto first() const -> const T&;
+ auto insert (int pos, const T& value) -> void;
+ auto is_empty() const -> bool;
+ auto last() const -> const T&;
+ auto merge (const Self& other) -> void;
+ auto pop (T& val) -> bool;
+ auto prepend (const T& value) -> T&;
+ auto rbegin() -> ReverseIterator;
+ auto remove_at (int pos) -> void;
+ auto remove_duplicates() -> void;
+ auto remove_one (const T& it) -> void;
+ auto rend() -> ReverseIterator;
+ auto resize (int size) -> void;
+ auto reverse() const -> Self;
+ auto size() const -> int;
+ auto sort() -> void;
+ auto splice (int a, int b) const -> Self;
+ auto splice (const Range<int>& a) const -> Self;
+
+ auto operator<< (const T& value) -> Self&;
+ auto operator<< (const Self& vals) -> Self&;
+ auto operator[] (int n) -> T&;
+ auto operator[] (int n) const -> const T&;
+ auto operator[] (Range<int> const& n) const -> Self;
+ auto operator+ (const Self& other) const -> Self;
+
+protected:
+ C m_container;
+};
+
+template<typename T, typename C>
+Container<T, C>& operator>> (const T& value, Container<T, C>& haystack);
+
+template<typename T>
+using List = Container<T, std::deque<T>>;
+
+template<typename T>
+class Vector : public Container<T, std::vector<T>>
+{
+public:
+ using Super = Container<T, std::vector<T>>;
+
+ template<typename... Args>
+ Vector (Args ...args) :
+ Super (args...) {}
+
+ auto data() -> T*
+ {
+ return Super::m_container.data();
+ }
+
+ auto data() const -> const T*
+ {
+ return Super::m_container.data();
+ }
+
+ operator const T*() const
+ {
+ return data();
+ }
+};
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+// IMPLEMENTATIONS
+//
+
+template<typename T, typename C>
+Container<T, C>::Container() {}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+Container<T, C>::Container (const C& other) :
+ m_container (other) {}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+Container<T, C>::Container (std::initializer_list<T> && a) :
+ m_container (a) {}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+Container<T, C>::Container (int numvalues) :
+ m_container (numvalues) {}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::begin() -> Iterator
+{
+ return m_container.begin();
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::begin() const -> ConstIterator
+{
+ return m_container.cbegin();
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::end() -> Iterator
+{
+ return m_container.end();
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::end() const -> ConstIterator
+{
+ return m_container.cend();
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::rbegin() -> ReverseIterator
+{
+ return m_container.rbegin();
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::crbegin() const -> ConstReverseIterator
+{
+ return m_container.crbegin();
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::rend() -> ReverseIterator
+{
+ return m_container.rend();
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::crend() const -> ConstReverseIterator
+{
+ return m_container.crend();
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::remove_at (int pos) -> void
+{
+ assert (pos < size());
+ m_container.erase (m_container.begin() + pos);
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::prepend (const T& value) -> T&
+{
+ m_container.push_front (value);
+ return m_container[0];
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::append (const T& value) -> T&
+{
+ m_container.push_back (value);
+ return m_container[m_container.size() - 1];
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::merge (const Self& other) -> void
+{
+ int oldsize = size();
+ resize (size() + other.size());
+ std::copy (other.begin(), other.end(), begin() + oldsize);
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::pop (T& val) -> bool
+{
+ if (is_empty())
+ return false;
+
+ val = m_container[size() - 1];
+ m_container.erase (m_container.end() - 1);
+ return true;
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::operator<< (const T& value) -> Self&
+{
+ append (value);
+ return *this;
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::operator<< (const Self& vals) -> Self&
+{
+ merge (vals);
+ return *this;
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::reverse() const -> Self
+{
+ Self rev;
+ std::copy (rbegin(), rend(), rev.begin());
+ return rev;
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::clear() -> void
+{
+ m_container.clear();
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::insert (int pos, const T& value) -> void
+{
+ m_container.insert (m_container.begin() + pos, value);
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::remove_duplicates() -> void
+{
+ sort();
+ resize (std::distance (begin(), std::unique (begin(), end())));
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::size() const -> int
+{
+ return m_container.size();
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::operator[] (int n) -> T&
+{
+ assert (n < size());
+ return m_container[n];
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::operator[] (int n) const -> const T&
+{
+ assert (n < size());
+ return m_container[n];
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::operator[] (const Range<int>& n) const -> Self
+{
+ return splice (n);
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::resize (int size) -> void
+{
+ m_container.resize (size);
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::sort() -> void
+{
+ std::sort (begin(), end());
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::find (const T& needle) -> Iterator
+{
+ auto it = std::find (m_container.begin(), m_container.end(), needle);
+
+ if (it == m_container.end())
+ return end();
+
+ return it;
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::find (const T& needle) const -> ConstIterator
+{
+ auto it = std::find (m_container.cbegin(), m_container.cend(), needle);
+
+ if (it == m_container.cend())
+ return end();
+
+ return it;
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::find (Function<bool (T const&)> func) -> Iterator
+{
+ for (Iterator it = begin(); it != end(); ++it)
+ {
+ if (func (*it))
+ return it;
+ }
+
+ return end();
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::find (Function<bool (T const&)> func) const -> ConstIterator
+{
+ for (ConstIterator it = begin(); it != end(); ++it)
+ {
+ if (func (*it))
+ return it;
+ }
+
+ return end();
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::remove_one (const T& a) -> void
+{
+ auto it = std::find (m_container.begin(), m_container.end(), a);
+
+ if (it != m_container.end())
+ m_container.erase (it);
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::is_empty() const -> bool
+{
+ return size() == 0;
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::splice (int a, int b) const -> Self
+{
+ 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;
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::splice (const Range<int>& a) const -> Self
+{
+ return splice (a.min(), a.max());
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::container() const -> const C&
+{
+ return m_container;
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::first() const -> const T&
+{
+ return *m_container.cbegin();
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::last() const -> const T&
+{
+ return *(m_container.cend() - 1);
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::contains (const T& a) const -> bool
+{
+ return std::find (m_container.cbegin(), m_container.cend(), a) != m_container.end();
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto Container<T, C>::operator+ (const Self& other) const -> Self
+{
+ Self out (*this);
+ out.merge (other);
+ return out;
+}
+
+//
+// -------------------------------------------------------------------------------------------------
+//
+
+template<typename T, typename C>
+auto operator>> (const T& value, Container<T, C>& haystack) -> Container<T, C>&
+{
+ haystack.prepend (value);
+ return haystack;
+}