diff -r 792876306489 -r 4dd5bde4e777 sources/list.h --- /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 +#include +#include +#include +#include +#include "range.h" + +// +// ------------------------------------------------------------------------------------------------- +// + +template +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; + + Container(); + Container (int numvalues); + Container (const C& a); + Container (std::initializer_list&& 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 func) -> Iterator; + auto find (Function 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& 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 const& n) const -> Self; + auto operator+ (const Self& other) const -> Self; + +protected: + C m_container; +}; + +template +Container& operator>> (const T& value, Container& haystack); + +template +using List = Container>; + +template +class Vector : public Container> +{ +public: + using Super = Container>; + + template + 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 +Container::Container() {} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +Container::Container (const C& other) : + m_container (other) {} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +Container::Container (std::initializer_list && a) : + m_container (a) {} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +Container::Container (int numvalues) : + m_container (numvalues) {} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::begin() -> Iterator +{ + return m_container.begin(); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::begin() const -> ConstIterator +{ + return m_container.cbegin(); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::end() -> Iterator +{ + return m_container.end(); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::end() const -> ConstIterator +{ + return m_container.cend(); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::rbegin() -> ReverseIterator +{ + return m_container.rbegin(); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::crbegin() const -> ConstReverseIterator +{ + return m_container.crbegin(); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::rend() -> ReverseIterator +{ + return m_container.rend(); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::crend() const -> ConstReverseIterator +{ + return m_container.crend(); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::remove_at (int pos) -> void +{ + assert (pos < size()); + m_container.erase (m_container.begin() + pos); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::prepend (const T& value) -> T& +{ + m_container.push_front (value); + return m_container[0]; +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::append (const T& value) -> T& +{ + m_container.push_back (value); + return m_container[m_container.size() - 1]; +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::merge (const Self& other) -> void +{ + int oldsize = size(); + resize (size() + other.size()); + std::copy (other.begin(), other.end(), begin() + oldsize); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::pop (T& val) -> bool +{ + if (is_empty()) + return false; + + val = m_container[size() - 1]; + m_container.erase (m_container.end() - 1); + return true; +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::operator<< (const T& value) -> Self& +{ + append (value); + return *this; +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::operator<< (const Self& vals) -> Self& +{ + merge (vals); + return *this; +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::reverse() const -> Self +{ + Self rev; + std::copy (rbegin(), rend(), rev.begin()); + return rev; +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::clear() -> void +{ + m_container.clear(); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::insert (int pos, const T& value) -> void +{ + m_container.insert (m_container.begin() + pos, value); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::remove_duplicates() -> void +{ + sort(); + resize (std::distance (begin(), std::unique (begin(), end()))); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::size() const -> int +{ + return m_container.size(); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::operator[] (int n) -> T& +{ + assert (n < size()); + return m_container[n]; +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::operator[] (int n) const -> const T& +{ + assert (n < size()); + return m_container[n]; +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::operator[] (const Range& n) const -> Self +{ + return splice (n); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::resize (int size) -> void +{ + m_container.resize (size); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::sort() -> void +{ + std::sort (begin(), end()); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::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 +auto Container::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 +auto Container::find (Function func) -> Iterator +{ + for (Iterator it = begin(); it != end(); ++it) + { + if (func (*it)) + return it; + } + + return end(); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::find (Function func) const -> ConstIterator +{ + for (ConstIterator it = begin(); it != end(); ++it) + { + if (func (*it)) + return it; + } + + return end(); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::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 +auto Container::is_empty() const -> bool +{ + return size() == 0; +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::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 +auto Container::splice (const Range& a) const -> Self +{ + return splice (a.min(), a.max()); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::container() const -> const C& +{ + return m_container; +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::first() const -> const T& +{ + return *m_container.cbegin(); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::last() const -> const T& +{ + return *(m_container.cend() - 1); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::contains (const T& a) const -> bool +{ + return std::find (m_container.cbegin(), m_container.cend(), a) != m_container.end(); +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto Container::operator+ (const Self& other) const -> Self +{ + Self out (*this); + out.merge (other); + return out; +} + +// +// ------------------------------------------------------------------------------------------------- +// + +template +auto operator>> (const T& value, Container& haystack) -> Container& +{ + haystack.prepend (value); + return haystack; +}