--- a/src/list.h Sun Mar 30 22:50:25 2014 +0300
+++ b/src/list.h Fri May 02 20:37:27 2014 +0300
@@ -26,8 +26,8 @@
THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
-#ifndef BOTC_CONTAINERS_H
-#define BOTC_CONTAINERS_H
+#ifndef BOTC_LIST_H
+#define BOTC_LIST_H
#include <cassert>
#include <algorithm>
@@ -37,317 +37,303 @@
template<typename T>
class List
{
- public:
- using WrappedList = typename std::deque<T>;
- using Iterator = typename WrappedList::iterator;
- using ConstIterator = typename WrappedList::const_iterator;
- using ReverseIterator = typename WrappedList::reverse_iterator;
- using ConstReverseIterator = typename WrappedList::const_reverse_iterator;
- using ValueType = T;
- using Self = List<T>;
-
- // =====================================================================
- //
- List() {}
-
- // =====================================================================
- //
- List (std::initializer_list<ValueType> vals)
- {
- m_data = vals;
- }
-
- // =====================================================================
- //
- List (const WrappedList& a) :
- m_data (a) {}
-
- // =====================================================================
- //
- Iterator begin()
- {
- return m_data.begin();
- }
-
- // =====================================================================
- //
- ConstIterator begin() const
- {
- return m_data.cbegin();
- }
-
- // =====================================================================
- //
- Iterator end()
- {
- return m_data.end();
- }
-
- // =====================================================================
- //
- ConstIterator end() const
- {
- return m_data.cend();
- }
-
- // =====================================================================
- //
- ReverseIterator rbegin()
- {
- return m_data.rbegin();
- }
-
- // =====================================================================
- //
- ConstReverseIterator crbegin() const
- {
- return m_data.crbegin();
- }
-
- // =====================================================================
- //
- ReverseIterator rend()
- {
- return m_data.rend();
- }
+public:
+ using Iterator = typename std::deque<T>::iterator;
+ using ConstIterator = typename std::deque<T>::const_iterator;
+ using ReverseIterator = typename std::deque<T>::reverse_iterator;
+ using ConstReverseIterator = typename std::deque<T>::const_reverse_iterator;
- // =====================================================================
- //
- ConstReverseIterator crend() const
- {
- return m_data.crend();
- }
-
- // =====================================================================
- //
- inline void removeAt (int pos)
- {
- assert (pos < size());
- m_data.erase (m_data.begin() + pos);
- }
-
- // =====================================================================
- //
- ValueType& prepend (const ValueType& value)
- {
- m_data.push_front (value);
- return m_data[0];
- }
-
- // =====================================================================
- //
- ValueType& append (const ValueType& value)
- {
- m_data.push_back (value);
- return m_data[m_data.size() - 1];
- }
-
- // =====================================================================
- //
- void merge (const Self& other)
- {
- resize (size() + other.size());
- std::copy (other.begin(), other.end(), begin() + other.size());
- }
-
- // =====================================================================
- //
- bool pop (T& val)
- {
- if (isEmpty())
- return false;
-
- val = m_data[size() - 1];
- m_data.erase (m_data.end() - 1);
- return true;
- }
-
- // =====================================================================
- //
- Self& operator<< (const T& value)
- {
- append (value);
- return *this;
- }
-
- // =====================================================================
- //
- void operator<< (const Self& vals)
- {
- merge (vals);
- }
-
- // =====================================================================
- //
- bool operator>> (T& value)
- {
- return pop (value);
- }
-
- // =====================================================================
- //
- Self reverse() const
- {
- Self rev;
+ List();
+ List (const std::deque<T>& a);
+ List (std::initializer_list<T>&& a);
- for (const T & val : *this)
- val >> rev;
-
- return rev;
- }
-
- // =====================================================================
- //
- void clear()
- {
- m_data.clear();
- }
-
- // =====================================================================
- //
- void insert (int pos, const ValueType& value)
- {
- m_data.insert (m_data.begin() + pos, value);
- }
-
- // =====================================================================
- //
- void removeDuplicates()
- {
- // Remove duplicate entries. For this to be effective, the vector must be
- // sorted first.
- sort();
- Iterator pos = std::unique (begin(), end());
- resize (std::distance (begin(), pos));
- }
-
- // =====================================================================
- //
- int size() const
- {
- return m_data.size();
- }
-
- // =====================================================================
- //
- ValueType& operator[] (int n)
- {
- assert (n < size());
- return m_data[n];
- }
-
- // =====================================================================
- //
- const ValueType& operator[] (int n) const
- {
- assert (n < size());
- return m_data[n];
- }
-
- // =====================================================================
- //
- void resize (int size)
- {
- m_data.resize (size);
- }
-
- // =====================================================================
- //
- void sort()
- {
- std::sort (begin(), end());
- }
-
- // =====================================================================
- //
- int find (const ValueType& needle) const
- {
- int i = 0;
+ inline T& append (const T& value);
+ inline Iterator begin();
+ inline ConstIterator begin() const;
+ inline void clear();
+ inline bool contains (const T& a) const;
+ inline ConstReverseIterator crbegin() const;
+ inline ConstReverseIterator crend() const;
+ inline const std::deque<T>& deque() const;
+ inline Iterator end();
+ inline ConstIterator end() const;
+ int find (const T& needle) const;
+ inline const T& first() const;
+ inline void insert (int pos, const T& value);
+ inline bool isEmpty() const;
+ inline const T& last() const;
+ void merge (const List<T>& other);
+ bool pop (T& val);
+ inline T& prepend (const T& value);
+ inline ReverseIterator rbegin();
+ inline void removeAt (int pos);
+ void removeDuplicates();
+ void removeOne (const T& it);
+ inline ReverseIterator rend();
+ inline void resize (int size);
+ List<T> reverse() const;
+ inline int size() const;
+ inline void sort();
+ List<T> splice (int a, int b) const;
- for (const ValueType& hay : *this)
- {
- if (hay == needle)
- return i;
-
- i++;
- }
-
- return -1;
- }
-
- // =====================================================================
- //
- void removeOne (const ValueType& it)
- {
- int idx;
-
- if ((idx = find (it)) != -1)
- removeAt (idx);
- }
-
- // =====================================================================
- //
- inline bool isEmpty() const
- {
- return size() == 0;
- }
-
- // =====================================================================
- //
- Self splice (int a, int b) const
- {
- assert (a >= 0 && b >= 0 && a < size() && b < size() && a <= b);
- Self result;
-
- for (int i = a; i <= b; ++i)
- result << operator[] (i);
+ inline List<T>& operator<< (const T& value);
+ inline List<T>& operator<< (const List<T>& vals);
+ inline T& operator[] (int n);
+ inline const T& operator[] (int n) const;
+ inline List<T> operator+ (const List<T>& other) const;
- return result;
- }
-
- // =====================================================================
- //
- inline const WrappedList& deque() const
- {
- return m_data;
- }
-
- // =====================================================================
- //
- inline const ValueType& first() const
- {
- return *m_data.begin();
- }
-
- // =====================================================================
- //
- inline const ValueType& last() const
- {
- return *(m_data.end() - 1);
- }
-
- // =====================================================================
- //
- inline bool contains (const ValueType& a) const
- {
- return find (a) != -1;
- }
-
- // =====================================================================
- //
- Self operator+ (const Self& other) const
- {
- Self out (*this);
- out.merge (other);
- return out;
- }
-
- private:
- WrappedList m_data;
+private:
+ std::deque<T> _deque;
};
-// =============================================================================
+template<typename T>
+List<T>& operator>> (const T& value, List<T>& haystack);
+
+//
+// --- IMPLEMENTATIONS
//
+
+template<typename T>
+List<T>::List() {}
+
+template<typename T>
+List<T>::List (const std::deque<T>& other) :
+ _deque (other) {}
+
+template<typename T>
+List<T>::List (std::initializer_list<T>&& a) :
+ _deque (a) {}
+
+template<typename T>
+inline typename List<T>::Iterator List<T>::begin()
+{
+ return _deque.begin();
+}
+
+template<typename T>
+inline typename List<T>::ConstIterator List<T>::begin() const
+{
+ return _deque.cbegin();
+}
+
+template<typename T>
+inline typename List<T>::Iterator List<T>::end()
+{
+ return _deque.end();
+}
+
+template<typename T>
+inline typename List<T>::ConstIterator List<T>::end() const
+{
+ return _deque.cend();
+}
+
+template<typename T>
+inline typename List<T>::ReverseIterator List<T>::rbegin()
+{
+ return _deque.rbegin();
+}
+
+template<typename T>
+inline typename List<T>::ConstReverseIterator List<T>::crbegin() const
+{
+ return _deque.crbegin();
+}
+
+template<typename T>
+inline typename List<T>::ReverseIterator List<T>::rend()
+{
+ return _deque.rend();
+}
+
+template<typename T>
+inline typename List<T>::ConstReverseIterator List<T>::crend() const
+{
+ return _deque.crend();
+}
+
+template<typename T>
+void List<T>::removeAt (int pos)
+{
+ assert (pos < size());
+ _deque.erase (_deque.begin() + pos);
+}
+
+template<typename T>
+inline T& List<T>::prepend (const T& value)
+{
+ _deque.push_front (value);
+ return _deque[0];
+}
+
+template<typename T>
+inline T& List<T>::append (const T& value)
+{
+ _deque.push_back (value);
+ return _deque[_deque.size() - 1];
+}
+
+template<typename T>
+void List<T>::merge (const List<T>& other)
+{
+ resize (size() + other.size());
+ std::copy (other.begin(), other.end(), begin() + other.size());
+}
+
+template<typename T>
+bool List<T>::pop (T& val)
+{
+ if (isEmpty())
+ return false;
+
+ val = _deque[size() - 1];
+ _deque.erase (_deque.end() - 1);
+ return true;
+}
+
+template<typename T>
+inline List<T>& List<T>::operator<< (const T& value)
+{
+ append (value);
+ return *this;
+}
+
+template<typename T>
+inline List<T>& List<T>::operator<< (const List<T>& vals)
+{
+ merge (vals);
+ return *this;
+}
+
+template<typename T>
+List<T> List<T>::reverse() const
+{
+ List<T> rev;
+ std::copy (rbegin(), rend(), rev.begin());
+ return rev;
+}
+
+template<typename T>
+inline void List<T>::clear()
+{
+ _deque.clear();
+}
+
+template<typename T>
+inline void List<T>::insert (int pos, const T& value)
+{
+ _deque.insert (_deque.begin() + pos, value);
+}
+
+template<typename T>
+void List<T>::removeDuplicates()
+{
+ sort();
+ resize (std::distance (begin(), std::unique (begin(), end())));
+}
+
+template<typename T>
+int List<T>::size() const
+{
+ return _deque.size();
+}
+
+template<typename T>
+inline T& List<T>::operator[] (int n)
+{
+ assert (n < size());
+ return _deque[n];
+}
+
+template<typename T>
+inline const T& List<T>::operator[] (int n) const
+{
+ assert (n < size());
+ return _deque[n];
+}
+
+template<typename T>
+inline void List<T>::resize (int size)
+{
+ _deque.resize (size);
+}
+
+template<typename T>
+inline void List<T>::sort()
+{
+ std::sort (begin(), end());
+}
+
+template<typename T>
+int List<T>::find (const T& needle) const
+{
+ auto it = std::find (_deque.cbegin(), _deque.cend(), needle);
+
+ if (it == _deque.end())
+ return -1;
+
+ return it - _deque.cbegin();
+}
+
+template<typename T>
+void List<T>::removeOne (const T& a)
+{
+ auto it = std::find (_deque.begin(), _deque.end(), a);
+
+ if (it != _deque.end())
+ _deque.erase (it);
+}
+
+template<typename T>
+inline bool List<T>::isEmpty() const
+{
+ return size() == 0;
+}
+
+template<typename T>
+List<T> List<T>::splice (int a, int b) const
+{
+ assert (a >= 0 && b >= 0 && a < size() && b < size() && a <= b);
+ List<T> result;
+
+ for (int i = a; i <= b; ++i)
+ result << operator[] (i);
+
+ return result;
+}
+
+template<typename T>
+inline const std::deque<T>& List<T>::deque() const
+{
+ return _deque;
+}
+
+template<typename T>
+inline const T& List<T>::first() const
+{
+ return *_deque.cbegin();
+}
+
+template<typename T>
+inline const T& List<T>::last() const
+{
+ return *(_deque.cend() - 1);
+}
+
+template<typename T>
+inline bool List<T>::contains (const T& a) const
+{
+ return std::find (_deque.cbegin(), _deque.cend(), a) != _deque.end();
+}
+
+template<typename T>
+inline List<T> List<T>::operator+ (const List<T>& other) const
+{
+ List<T> out (*this);
+ out.merge (other);
+ return out;
+}
+
template<typename T>
List<T>& operator>> (const T& value, List<T>& haystack)
{
@@ -355,4 +341,4 @@
return haystack;
}
-#endif // BOTC_CONTAINERS_H
+#endif // BOTC_LIST_H