--- /dev/null
+/*
+ * Acess2 C++ Library
+ * - By John Hodge (thePowersGang)
+ *
+ * list (header)
+ * - List container
+ */
+#ifndef _LIBCXX_LIST_
+#define _LIBCXX_LIST_
+
+#include <cstddef>
+#include "allocator"
+#include "stdexcept"
+#include "utility"
+
+namespace std {
+
+namespace _bits {
+template <class ListType, class T> class list_iterator;
+template <class T> class list_item;
+}
+
+template <class T, class Alloc = allocator<T> >
+class list
+{
+ typedef ::std::_bits::list_item<T> item_type;
+ typedef ::std::_bits::list_item<const T> const_item_type;
+ friend class ::std::_bits::list_iterator<list, T>;
+
+ typedef typename Alloc::template rebind<item_type>::other item_allocator;
+public:
+ typedef T value_type;
+ typedef Alloc allocator_type;
+ typedef typename allocator_type::reference reference;
+ typedef typename allocator_type::const_reference const_reference;
+ typedef typename allocator_type::pointer pointer;
+ typedef typename allocator_type::const_pointer const_pointer;
+ typedef _bits::list_iterator<list,T> iterator;
+ typedef _bits::list_iterator<list,const T> const_iterator;
+ typedef int difference_type;
+ typedef size_t size_type;
+
+private:
+ item_allocator m_item_allocator;
+ allocator_type m_allocator;
+ item_type *m_start;
+ item_type *m_end;
+ size_type m_item_count;
+
+public:
+ list(const allocator_type& alloc = allocator_type()):
+ m_item_allocator(),
+ m_allocator(alloc),
+ m_start(0), m_end(0)
+ {
+ }
+ list(size_t n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type()):
+ list()
+ {
+ assign(n, val);
+ }
+ list(const list& x);
+ ~list() {
+ clear();
+ }
+
+ list& operator =(const list& x);
+
+ iterator begin() {
+ return iterator(*this, m_start);
+ }
+ const_iterator begin() const {
+ return const_iterator(*this, m_start);
+ }
+
+ iterator end() {
+ return iterator(*this, 0);
+ }
+ const_iterator end() const {
+ return const_iterator(*this, 0);
+ }
+
+ bool empty() const {
+ return !m_start;
+ }
+ size_t size() const {
+ return m_item_count;
+ }
+ size_t max_size() const {
+ return (size_type)-1 / sizeof(item_type);
+ }
+
+ T& front() {
+ return m_start->value;
+ }
+ const T& front() const {
+ return m_start->value;
+ }
+ T& back() {
+ return m_end->value;
+ }
+ const T& back() const {
+ return m_end->value;
+ }
+
+ void assign(size_type n, const value_type& val) {
+ clear();
+ for( size_t i = 0; i < n; i ++ )
+ {
+ push_back(val);
+ }
+ }
+
+ void push_front(const value_type& val) {
+ insert(front(), val);
+ }
+ void pop_front() {
+ erase(front());
+ }
+ void push_back(const value_type& val) {
+ insert(end(), val);
+ }
+ void pop_back() {
+ erase(end());
+ }
+
+ template <class... Args>
+ iterator emplace(iterator position, Args&&... args) {
+ item_type *newi = m_item_allocator.allocate(1);
+ m_allocator.construct(&newi->value, ::std::forward<Args>(args)...);
+ return insert_item(position, newi);
+ }
+
+ iterator insert(iterator position, const value_type& val) {
+ item_type *newi = m_item_allocator.allocate(1);
+ m_allocator.construct(&newi->value, val);
+ return insert_item(position, newi);
+ }
+ void insert(iterator position, size_type n, const value_type& val) {
+ for( size_type i = 0; i < n; i ++ )
+ {
+ position = insert(position, val);
+ }
+ }
+ iterator erase(iterator position) {
+ if( position == end() ) {
+ }
+ else {
+ item_type *oldi = position.m_cur;
+ ++ position;
+
+ if(oldi->prev)
+ oldi->prev->next = oldi->next;
+ else
+ m_start = oldi->next;
+ if(oldi->next)
+ oldi->next->prev = oldi->prev;
+ else
+ m_end = oldi->prev;
+
+ m_item_count --;
+ m_allocator.destroy(&oldi->value);
+ m_item_allocator.deallocate(oldi, 1);
+ }
+ return position;
+ }
+
+ void clear() {
+ while( m_start ) {
+ item_type* item = m_start;
+ m_start = m_start->next;
+ delete item;
+ }
+ m_item_count = 0;
+ }
+
+ void splice(iterator position, list& x) {
+ splice(position, x, x.begin(), x.end());
+ }
+ void splice(iterator position, list& x, iterator i) {
+ splice(position, x, i, x.end());
+ }
+ void splice(iterator position, list& x, iterator first, iterator last);
+
+private:
+ class _equal
+ {
+ const value_type& m_val;
+ public:
+ _equal(const value_type& val):
+ m_val(val)
+ {
+ };
+ bool operator() (const value_type& v1)
+ {
+ return m_val == v1;
+ }
+ };
+public:
+ void remove(const value_type& val) {
+ remove_if(_equal(val));
+ }
+ template <class Predicate> void remove_if(Predicate pred) {
+ for( iterator it = begin(); it != end(); )
+ {
+ if( pred(*it) )
+ it = erase(it);
+ else
+ ++ it;
+ }
+ }
+
+ void unique();
+ template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);
+
+ void merge(list& x);
+ template <class Compare> void merge(list& x, Compare comp);
+
+ void sort();
+ template <class Compare> void sort(Compare comp);
+
+ void reverse() throw();
+private:
+ iterator insert_item(iterator position, item_type *newi) {
+ m_item_count ++;
+ if( m_start == 0 ) {
+ newi->next = 0;
+ newi->prev = m_end;
+ m_start = newi;
+ m_end = newi;
+ return end();
+ }
+ if( position == end() ) {
+ newi->next = 0;
+ newi->prev = m_end;
+ //assert(m_end);
+ m_end->next = newi;
+ m_end = newi;
+ }
+ else if( position == begin() ) {
+ newi->next = m_start;
+ newi->prev = 0;
+ //assert(m_start);
+ m_start->prev = newi;
+ m_start = newi;
+ }
+ else {
+ newi->prev = position.m_cur->prev;
+ newi->next = position.m_cur;
+ position.m_cur->prev->next = newi;
+ position.m_cur->prev = newi;
+ }
+ return ++iterator(*this, newi);
+ }
+};
+
+
+namespace _bits {
+
+template <class T>
+struct list_item
+{
+ typedef T value_type;
+ list_item<T> *next;
+ list_item<T> *prev;
+ value_type value;
+};
+
+template <class ListType, class T>
+class list_iterator//:
+ //public bidirectional_iterator_tag;
+{
+ const ListType* m_list;
+ list_item<T> *m_cur;
+ friend ListType;
+public:
+ list_iterator(const list_iterator& x):
+ m_list(x.m_list),
+ m_cur (x.m_cur)
+ {
+ }
+ list_iterator& operator=(const list_iterator& x) {
+ m_list = x.m_list;
+ m_cur = x.m_cur;
+ }
+
+ bool operator == (const list_iterator& other) const {
+ return m_cur == other.m_cur;
+ }
+ bool operator != (const list_iterator& other) const {
+ return !(*this == other);
+ }
+
+ T& operator * () {
+ return m_cur->value;
+ }
+ T& operator -> () {
+ return m_cur->value;
+ }
+ list_iterator& operator ++ () {
+ if(!m_cur)
+ throw ::std::logic_error("list iterator ++ on end");
+ m_cur = m_cur->next;
+ return *this;
+ }
+ list_iterator& operator -- () {
+ if( m_cur == m_list->m_start )
+ throw ::std::logic_error("list iterator -- on start");
+ if(!m_cur)
+ m_cur = m_list->m_end;
+ else
+ m_cur = m_cur->prev;
+ return *this;
+ }
+
+private:
+ list_iterator(const ListType& list, list_item<T> *item):
+ m_list(&list),
+ m_cur(item)
+ {
+ }
+};
+
+}; // namespace _bits
+
+}; // namespace std
+
+#endif
+
+// vim: ft=cpp
+
git.ucc.asn.au / tpg / acess2.git / blobdiff
UCC git Repository :: git.ucc.asn.au