| /* |
| * Copyright (c) 1997 |
| * Silicon Graphics Computer Systems, Inc. |
| * |
| * Permission to use, copy, modify, distribute and sell this software |
| * and its documentation for any purpose is hereby granted without fee, |
| * provided that the above copyright notice appear in all copies and |
| * that both that copyright notice and this permission notice appear |
| * in supporting documentation. Silicon Graphics makes no |
| * representations about the suitability of this software for any |
| * purpose. It is provided "as is" without express or implied warranty. |
| * |
| */ |
| |
| #ifndef __SGI_STL_SLIST_H |
| #define __SGI_STL_SLIST_H |
| |
| #include <algobase.h> |
| #include <alloc.h> |
| |
| struct __slist_node_base |
| { |
| __slist_node_base* next; |
| }; |
| |
| inline __slist_node_base* __slist_make_link(__slist_node_base* prev_node, |
| __slist_node_base* new_node) |
| { |
| new_node->next = prev_node->next; |
| prev_node->next = new_node; |
| return new_node; |
| } |
| |
| inline __slist_node_base* __slist_previous(__slist_node_base* head, |
| const __slist_node_base* node) |
| { |
| while (head && head->next != node) |
| head = head->next; |
| return head; |
| } |
| |
| inline const __slist_node_base* __slist_previous(const __slist_node_base* head, |
| const __slist_node_base* node) |
| { |
| while (head && head->next != node) |
| head = head->next; |
| return head; |
| } |
| |
| inline void __slist_splice_after(__slist_node_base* pos, |
| __slist_node_base* before_first, |
| __slist_node_base* before_last) |
| { |
| if (pos != before_first && pos != before_last) { |
| __slist_node_base* first = before_first->next; |
| __slist_node_base* after = pos->next; |
| before_first->next = before_last->next; |
| pos->next = first; |
| before_last->next = after; |
| } |
| } |
| |
| inline __slist_node_base* __slist_reverse(__slist_node_base* node) |
| { |
| __slist_node_base* result = node; |
| node = node->next; |
| result->next = 0; |
| while(node) { |
| __slist_node_base* next = node->next; |
| node->next = result; |
| result = node; |
| node = next; |
| } |
| return result; |
| } |
| |
| template <class T> |
| struct __slist_node : public __slist_node_base |
| { |
| T data; |
| }; |
| |
| struct __slist_iterator_base |
| { |
| typedef size_t size_type; |
| typedef ptrdiff_t difference_type; |
| typedef forward_iterator_tag iterator_category; |
| |
| __slist_node_base* node; |
| |
| __slist_iterator_base(__slist_node_base* x) : node(x) {} |
| void incr() { node = node->next; } |
| |
| bool operator==(const __slist_iterator_base& x) const { |
| return node == x.node; |
| } |
| bool operator!=(const __slist_iterator_base& x) const { |
| return node != x.node; |
| } |
| }; |
| |
| template <class T, class Ref> |
| struct __slist_iterator : public __slist_iterator_base |
| { |
| typedef __slist_iterator<T, T&> iterator; |
| typedef __slist_iterator<T, const T&> const_iterator; |
| typedef __slist_iterator<T, Ref> self; |
| |
| typedef T value_type; |
| typedef value_type* pointer; |
| typedef value_type& reference; |
| typedef const value_type& const_reference; |
| typedef __slist_node<T> list_node; |
| |
| __slist_iterator(list_node* x) : __slist_iterator_base(x) {} |
| __slist_iterator() : __slist_iterator_base(0) {} |
| __slist_iterator(const iterator& x) : __slist_iterator_base(x.node) {} |
| |
| Ref operator*() const { return ((list_node*) node)->data; } |
| self& operator++() |
| { |
| incr(); |
| return *this; |
| } |
| self operator++(int) |
| { |
| self tmp = *this; |
| incr(); |
| return tmp; |
| } |
| }; |
| |
| inline ptrdiff_t* |
| distance_type(const __slist_iterator_base&) |
| { |
| return 0; |
| } |
| |
| inline forward_iterator_tag |
| iterator_category(const __slist_iterator_base&) |
| { |
| return forward_iterator_tag(); |
| } |
| |
| template <class T, class Ref> |
| inline T* |
| value_type(const __slist_iterator<T, Ref>&) { |
| return 0; |
| } |
| |
| inline size_t __slist_size(__slist_node_base* node) |
| { |
| size_t result = 0; |
| for ( ; node != 0; node = node->next) |
| ++result; |
| return result; |
| } |
| |
| template <class T, class Alloc = alloc> |
| class slist |
| { |
| public: |
| typedef T value_type; |
| typedef value_type* pointer; |
| typedef value_type& reference; |
| typedef const value_type& const_reference; |
| typedef size_t size_type; |
| typedef ptrdiff_t difference_type; |
| |
| typedef __slist_iterator<T, reference> iterator; |
| typedef __slist_iterator<T, const_reference> const_iterator; |
| |
| private: |
| typedef __slist_node<T> list_node; |
| typedef __slist_node_base list_node_base; |
| typedef __slist_iterator_base iterator_base; |
| typedef simple_alloc<list_node, Alloc> list_node_allocator; |
| |
| static list_node* create_node(const value_type& x) { |
| list_node* node = list_node_allocator::allocate(); |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| construct(&node->data, x); |
| node->next = 0; |
| return node; |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| list_node_allocator::deallocate(node); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| |
| static void destroy_node(list_node* node) { |
| destroy(&node->data); |
| list_node_allocator::deallocate(node); |
| } |
| |
| void fill_initialize(size_type n, const value_type& x) { |
| head.next = 0; |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| _insert_after_fill(&head, n, x); |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| clear(); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| |
| #ifdef __STL_MEMBER_TEMPLATES |
| template <class InputIterator> |
| void range_initialize(InputIterator first, InputIterator last) { |
| head.next = 0; |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| _insert_after_range(&head, first, last); |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| clear(); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| #else /* __STL_MEMBER_TEMPLATES */ |
| void range_initialize(const value_type* first, const value_type* last) { |
| head.next = 0; |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| _insert_after_range(&head, first, last); |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| clear(); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| void range_initialize(const_iterator first, const_iterator last) { |
| head.next = 0; |
| # ifdef __STL_USE_EXCEPTIONS |
| try { |
| # endif /* __STL_USE_EXCEPTIONS */ |
| _insert_after_range(&head, first, last); |
| # ifdef __STL_USE_EXCEPTIONS |
| } |
| catch(...) { |
| clear(); |
| throw; |
| } |
| # endif /* __STL_USE_EXCEPTIONS */ |
| } |
| #endif /* __STL_MEMBER_TEMPLATES */ |
| |
| private: |
| list_node_base head; |
| |
| public: |
| slist() { head.next = 0; } |
| |
| slist(size_type n, const value_type& x) { fill_initialize(n, x); } |
| slist(int n, const value_type& x) { fill_initialize(n, x); } |
| slist(long n, const value_type& x) { fill_initialize(n, x); } |
| explicit slist(size_type n) { fill_initialize(n, value_type()); } |
| |
| #ifdef __STL_MEMBER_TEMPLATES |
| template <class InputIterator> |
| slist(InputIterator first, InputIterator last) { |
| range_initialize(first, last); |
| } |
| |
| #else /* __STL_MEMBER_TEMPLATES */ |
| slist(const_iterator first, const_iterator last) { |
| range_initialize(first, last); |
| } |
| slist(const value_type* first, const value_type* last) { |
| range_initialize(first, last); |
| } |
| #endif /* __STL_MEMBER_TEMPLATES */ |
| |
| slist(const slist& L) { range_initialize(L.begin(), L.end()); } |
| |
| slist& operator= (const slist& L); |
| |
| ~slist() { clear(); } |
| |
| public: |
| |
| iterator begin() { return iterator((list_node*)head.next); } |
| const_iterator begin() const { return const_iterator((list_node*)head.next);} |
| |
| iterator end() { return iterator(0); } |
| const_iterator end() const { return const_iterator(0); } |
| |
| size_type size() const { return __slist_size(head.next); } |
| |
| size_type max_size() const { return size_type(-1); } |
| |
| bool empty() const { return head.next == 0; } |
| |
| void swap(slist& L) |
| { |
| list_node_base* tmp = head.next; |
| head.next = L.head.next; |
| L.head.next = tmp; |
| } |
| |
| public: |
| friend bool operator==(const slist<T, Alloc>& L1, const slist<T, Alloc>& L2); |
| |
| public: |
| |
| reference front() { return ((list_node*) head.next)->data; } |
| const_reference front() const { return ((list_node*) head.next)->data; } |
| void push_front(const value_type& x) { |
| __slist_make_link(&head, create_node(x)); |
| } |
| void pop_front() { |
| list_node* node = (list_node*) head.next; |
| head.next = node->next; |
| destroy_node(node); |
| } |
| |
| iterator previous(const_iterator pos) { |
| return iterator((list_node*) __slist_previous(&head, pos.node)); |
| } |
| const_iterator previous(const_iterator pos) const { |
| return const_iterator((list_node*) __slist_previous(&head, pos.node)); |
| } |
| |
| private: |
| list_node* _insert_after(list_node_base* pos, const value_type& x) { |
| return (list_node*) (__slist_make_link(pos, create_node(x))); |
| } |
| |
| void _insert_after_fill(list_node_base* pos, |
| size_type n, const value_type& x) { |
| for (size_type i = 0; i < n; ++i) |
| pos = __slist_make_link(pos, create_node(x)); |
| } |
| |
| #ifdef __STL_MEMBER_TEMPLATES |
| template <class InIter> |
| void _insert_after_range(list_node_base* pos, InIter first, InIter last) { |
| while (first != last) { |
| pos = __slist_make_link(pos, create_node(*first)); |
| ++first; |
| } |
| } |
| #else /* __STL_MEMBER_TEMPLATES */ |
| void _insert_after_range(list_node_base* pos, |
| const_iterator first, const_iterator last) { |
| while (first != last) { |
| pos = __slist_make_link(pos, create_node(*first)); |
| ++first; |
| } |
| } |
| void _insert_after_range(list_node_base* pos, |
| const value_type* first, const value_type* last) { |
| while (first != last) { |
| pos = __slist_make_link(pos, create_node(*first)); |
| ++first; |
| } |
| } |
| #endif /* __STL_MEMBER_TEMPLATES */ |
| |
| void erase_after(list_node_base* pos) { |
| list_node* next = (list_node*) (pos->next); |
| pos->next = next->next; |
| destroy_node(next); |
| } |
| |
| void erase_after(list_node_base* before_first, list_node_base* last_node) { |
| list_node* cur = (list_node*) (before_first->next); |
| while (cur != last_node) { |
| list_node* tmp = cur; |
| cur = (list_node*) cur->next; |
| destroy_node(tmp); |
| } |
| before_first->next = last_node; |
| } |
| |
| |
| public: |
| |
| iterator insert_after(iterator pos, const value_type& x) { |
| return iterator(_insert_after(pos.node, x)); |
| } |
| |
| iterator insert_after(iterator pos) { |
| return insert_after(pos, value_type()); |
| } |
| |
| void insert_after(iterator pos, size_type n, const value_type& x) { |
| _insert_after_fill(pos.node, n, x); |
| } |
| void insert_after(iterator pos, int n, const value_type& x) { |
| _insert_after_fill(pos.node, (size_type) n, x); |
| } |
| void insert_after(iterator pos, long n, const value_type& x) { |
| _insert_after_fill(pos.node, (size_type) n, x); |
| } |
| |
| #ifdef __STL_MEMBER_TEMPLATES |
| template <class InIter> |
| void insert_after(iterator pos, InIter first, InIter last) { |
| _insert_after_range(pos.node, first, last); |
| } |
| #else /* __STL_MEMBER_TEMPLATES */ |
| void insert_after(iterator pos, const_iterator first, const_iterator last) { |
| _insert_after_range(pos.node, first, last); |
| } |
| void insert_after(iterator pos, |
| const value_type* first, const value_type* last) { |
| _insert_after_range(pos.node, first, last); |
| } |
| #endif /* __STL_MEMBER_TEMPLATES */ |
| |
| iterator insert(iterator pos, const value_type& x) { |
| return iterator(_insert_after(__slist_previous(&head, pos.node), x)); |
| } |
| |
| iterator insert(iterator pos) { |
| return iterator(_insert_after(__slist_previous(&head, pos.node), |
| value_type())); |
| } |
| |
| void insert(iterator pos, size_type n, const value_type& x) { |
| _insert_after_fill(__slist_previous(&head, pos.node), n, x); |
| } |
| void insert(iterator pos, int n, const value_type& x) { |
| _insert_after_fill(__slist_previous(&head, pos.node), (size_type) n, x); |
| } |
| void insert(iterator pos, long n, const value_type& x) { |
| _insert_after_fill(__slist_previous(&head, pos.node), (size_type) n, x); |
| } |
| |
| #ifdef __STL_MEMBER_TEMPLATES |
| template <class InIter> |
| void insert(iterator pos, InIter first, InIter last) { |
| _insert_after_range(__slist_previous(&head, pos.node), first, last); |
| } |
| #else /* __STL_MEMBER_TEMPLATES */ |
| void insert(iterator pos, const_iterator first, const_iterator last) { |
| _insert_after_range(__slist_previous(&head, pos.node), first, last); |
| } |
| void insert(iterator pos, const value_type* first, const value_type* last) { |
| _insert_after_range(__slist_previous(&head, pos.node), first, last); |
| } |
| #endif /* __STL_MEMBER_TEMPLATES */ |
| |
| |
| public: |
| void erase_after(iterator pos) { erase_after(pos.node); } |
| void erase_after(iterator before_first, iterator last) { |
| erase_after(before_first.node, last.node); |
| } |
| |
| void erase(iterator pos) { erase_after(__slist_previous(&head, pos.node)); } |
| void erase(iterator first, iterator last) { |
| erase_after(__slist_previous(&head, first.node), last.node); |
| } |
| |
| void resize(size_type new_size, const T& x); |
| void resize(size_type new_size) { resize(new_size, T()); } |
| void clear() { erase_after(&head, 0); } |
| |
| public: |
| // Moves the range [before_first + 1, before_last + 1) to *this, |
| // inserting it immediately after pos. This is constant time. |
| void splice_after(iterator pos, |
| iterator before_first, iterator before_last) |
| { |
| if (before_first != before_last) |
| __slist_splice_after(pos.node, before_first.node, before_last.node); |
| } |
| |
| // Moves the element that follows prev to *this, inserting it immediately |
| // after pos. This is constant time. |
| void splice_after(iterator pos, iterator prev) |
| { |
| __slist_splice_after(pos.node, prev.node, prev.node->next); |
| } |
| |
| |
| // Linear in distance(begin(), pos), and linear in L.size(). |
| void splice(iterator pos, slist& L) { |
| if (L.head.next) |
| __slist_splice_after(__slist_previous(&head, pos.node), |
| &L.head, |
| __slist_previous(&L.head, 0)); |
| } |
| |
| // Linear in distance(begin(), pos), and in distance(L.begin(), i). |
| void splice(iterator pos, slist& L, iterator i) { |
| __slist_splice_after(__slist_previous(&head, pos.node), |
| __slist_previous(&L.head, i.node), |
| i.node); |
| } |
| |
| // Linear in distance(begin(), pos), in distance(L.begin(), first), |
| // and in distance(first, last). |
| void splice(iterator pos, slist& L, iterator first, iterator last) |
| { |
| if (first != last) |
| __slist_splice_after(__slist_previous(&head, pos.node), |
| __slist_previous(&L.head, first.node), |
| __slist_previous(first.node, last.node)); |
| } |
| |
| public: |
| void reverse() { if (head.next) head.next = __slist_reverse(head.next); } |
| |
| void remove(const T& val); |
| void unique(); |
| void merge(slist& L); |
| void sort(); |
| |
| #ifdef __STL_MEMBER_TEMPLATES |
| template <class Predicate> void remove_if(Predicate pred); |
| template <class BinaryPredicate> void unique(BinaryPredicate pred); |
| template <class StrictWeakOrdering> void merge(slist&, StrictWeakOrdering); |
| template <class StrictWeakOrdering> void sort(StrictWeakOrdering comp); |
| #endif /* __STL_MEMBER_TEMPLATES */ |
| }; |
| |
| template <class T, class Alloc> |
| slist<T, Alloc>& slist<T,Alloc>::operator=(const slist<T, Alloc>& L) |
| { |
| if (&L != this) { |
| list_node_base* p1 = &head; |
| list_node* n1 = (list_node*) head.next; |
| const list_node* n2 = (const list_node*) L.head.next; |
| while (n1 && n2) { |
| n1->data = n2->data; |
| p1 = n1; |
| n1 = (list_node*) n1->next; |
| n2 = (const list_node*) n2->next; |
| } |
| if (n2 == 0) |
| erase_after(p1, 0); |
| else |
| _insert_after_range(p1, |
| const_iterator((list_node*)n2), const_iterator(0)); |
| } |
| return *this; |
| } |
| |
| template <class T, class Alloc> |
| bool operator==(const slist<T, Alloc>& L1, const slist<T, Alloc>& L2) |
| { |
| typedef typename slist<T,Alloc>::list_node list_node; |
| list_node* n1 = (list_node*) L1.head.next; |
| list_node* n2 = (list_node*) L2.head.next; |
| while (n1 && n2 && n1->data == n2->data) { |
| n1 = (list_node*) n1->next; |
| n2 = (list_node*) n2->next; |
| } |
| return n1 == 0 && n2 == 0; |
| } |
| |
| template <class T, class Alloc> |
| inline bool operator<(const slist<T, Alloc>& L1, const slist<T, Alloc>& L2) |
| { |
| return lexicographical_compare(L1.begin(), L1.end(), L2.begin(), L2.end()); |
| } |
| |
| template <class T, class Alloc> |
| void slist<T, Alloc>::resize(size_type len, const T& x) |
| { |
| list_node_base* cur = &head; |
| while (cur->next != 0 && len > 0) { |
| --len; |
| cur = cur->next; |
| } |
| if (cur->next) |
| erase_after(cur, 0); |
| else |
| _insert_after_fill(cur, len, x); |
| } |
| |
| template <class T, class Alloc> |
| void slist<T,Alloc>::remove(const T& val) |
| { |
| list_node_base* cur = &head; |
| while (cur && cur->next) { |
| if (((list_node*) cur->next)->data == val) |
| erase_after(cur); |
| else |
| cur = cur->next; |
| } |
| } |
| |
| template <class T, class Alloc> |
| void slist<T,Alloc>::unique() |
| { |
| list_node_base* cur = head.next; |
| if (cur) { |
| while (cur->next) { |
| if (((list_node*)cur)->data == ((list_node*)(cur->next))->data) |
| erase_after(cur); |
| else |
| cur = cur->next; |
| } |
| } |
| } |
| |
| template <class T, class Alloc> |
| void slist<T,Alloc>::merge(slist<T,Alloc>& L) |
| { |
| list_node_base* n1 = &head; |
| while (n1->next && L.head.next) { |
| if (((list_node*) L.head.next)->data < ((list_node*) n1->next)->data) |
| __slist_splice_after(n1, &L.head, L.head.next); |
| n1 = n1->next; |
| } |
| if (L.head.next) { |
| n1->next = L.head.next; |
| L.head.next = 0; |
| } |
| } |
| |
| template <class T, class Alloc> |
| void slist<T,Alloc>::sort() |
| { |
| if (head.next && head.next->next) { |
| slist carry; |
| slist counter[64]; |
| int fill = 0; |
| while (!empty()) { |
| __slist_splice_after(&carry.head, &head, head.next); |
| int i = 0; |
| while (i < fill && !counter[i].empty()) { |
| counter[i].merge(carry); |
| carry.swap(counter[i]); |
| ++i; |
| } |
| carry.swap(counter[i]); |
| if (i == fill) |
| ++fill; |
| } |
| |
| for (int i = 1; i < fill; ++i) |
| counter[i].merge(counter[i-1]); |
| this->swap(counter[fill-1]); |
| } |
| } |
| |
| #ifdef __STL_MEMBER_TEMPLATES |
| |
| template <class T, class Alloc> |
| template <class Predicate> void slist<T,Alloc>::remove_if(Predicate pred) |
| { |
| list_node_base* cur = &head; |
| while (cur->next) { |
| if (pred(((list_node*) cur->next)->data)) |
| erase_after(cur); |
| else |
| cur = cur->next; |
| } |
| } |
| |
| template <class T, class Alloc> template <class BinaryPredicate> |
| void slist<T,Alloc>::unique(BinaryPredicate pred) |
| { |
| list_node* cur = (list_node*) head.next; |
| if (cur) { |
| while (cur->next) { |
| if (pred(((list_node*)cur)->data, ((list_node*)(cur->next))->data)) |
| erase_after(cur); |
| else |
| cur = (list_node*) cur->next; |
| } |
| } |
| } |
| |
| template <class T, class Alloc> template <class StrictWeakOrdering> |
| void slist<T,Alloc>::merge(slist<T,Alloc>& L, StrictWeakOrdering comp) |
| { |
| list_node_base* n1 = &head; |
| while (n1->next && L.head.next) { |
| if (comp(((list_node*) L.head.next)->data, |
| ((list_node*) n1->next)->data)) |
| __slist_splice_after(n1, &L.head, L.head.next); |
| n1 = n1->next; |
| } |
| if (L.head.next) { |
| n1->next = L.head.next; |
| L.head.next = 0; |
| } |
| } |
| |
| template <class T, class Alloc> template <class StrictWeakOrdering> |
| void slist<T,Alloc>::sort(StrictWeakOrdering comp) |
| { |
| if (head.next && head.next->next) { |
| slist carry; |
| slist counter[64]; |
| int fill = 0; |
| while (!empty()) { |
| __slist_splice_after(&carry.head, &head, head.next); |
| int i = 0; |
| while (i < fill && !counter[i].empty()) { |
| counter[i].merge(carry, comp); |
| carry.swap(counter[i]); |
| ++i; |
| } |
| carry.swap(counter[i]); |
| if (i == fill) |
| ++fill; |
| } |
| |
| for (int i = 1; i < fill; ++i) |
| counter[i].merge(counter[i-1], comp); |
| this->swap(counter[fill-1]); |
| } |
| } |
| |
| #endif /* __STL_MEMBER_TEMPLATES */ |
| |
| #endif /* __SGI_STL_SLIST_H */ |