diff options
Diffstat (limited to 'contrib/libstdc++/stl/stl_list.h')
-rw-r--r-- | contrib/libstdc++/stl/stl_list.h | 617 |
1 files changed, 617 insertions, 0 deletions
diff --git a/contrib/libstdc++/stl/stl_list.h b/contrib/libstdc++/stl/stl_list.h new file mode 100644 index 0000000..ac836b6 --- /dev/null +++ b/contrib/libstdc++/stl/stl_list.h @@ -0,0 +1,617 @@ +/* + * + * Copyright (c) 1994 + * Hewlett-Packard Company + * + * 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. Hewlett-Packard Company makes no + * representations about the suitability of this software for any + * purpose. It is provided "as is" without express or implied warranty. + * + * + * Copyright (c) 1996,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. + */ + +/* NOTE: This is an internal header file, included by other STL headers. + * You should not attempt to use it directly. + */ + +#ifndef __SGI_STL_INTERNAL_LIST_H +#define __SGI_STL_INTERNAL_LIST_H + +__STL_BEGIN_NAMESPACE + +#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) +#pragma set woff 1174 +#endif + +template <class T> +struct __list_node { + typedef void* void_pointer; + void_pointer next; + void_pointer prev; + T data; +}; + +template<class T, class Ref, class Ptr> +struct __list_iterator { + typedef __list_iterator<T, T&, T*> iterator; + typedef __list_iterator<T, const T&, const T*> const_iterator; + typedef __list_iterator<T, Ref, Ptr> self; + + typedef bidirectional_iterator_tag iterator_category; + typedef T value_type; + typedef Ptr pointer; + typedef Ref reference; + typedef __list_node<T>* link_type; + typedef size_t size_type; + typedef ptrdiff_t difference_type; + + link_type node; + + __list_iterator(link_type x) : node(x) {} + __list_iterator() {} + __list_iterator(const iterator& x) : node(x.node) {} + + bool operator==(const self& x) const { return node == x.node; } + bool operator!=(const self& x) const { return node != x.node; } + reference operator*() const { return (*node).data; } + +#ifndef __SGI_STL_NO_ARROW_OPERATOR + pointer operator->() const { return &(operator*()); } +#endif /* __SGI_STL_NO_ARROW_OPERATOR */ + + self& operator++() { + node = (link_type)((*node).next); + return *this; + } + self operator++(int) { + self tmp = *this; + ++*this; + return tmp; + } + self& operator--() { + node = (link_type)((*node).prev); + return *this; + } + self operator--(int) { + self tmp = *this; + --*this; + return tmp; + } +}; + +#ifndef __STL_CLASS_PARTIAL_SPECIALIZATION + +template <class T, class Ref, class Ptr> +inline bidirectional_iterator_tag +iterator_category(const __list_iterator<T, Ref, Ptr>&) { + return bidirectional_iterator_tag(); +} + +template <class T, class Ref, class Ptr> +inline T* +value_type(const __list_iterator<T, Ref, Ptr>&) { + return 0; +} + +template <class T, class Ref, class Ptr> +inline ptrdiff_t* +distance_type(const __list_iterator<T, Ref, Ptr>&) { + return 0; +} + +#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ + +template <class T, class Alloc = alloc> +class list { +protected: + typedef void* void_pointer; + typedef __list_node<T> list_node; + typedef simple_alloc<list_node, Alloc> list_node_allocator; +public: + typedef T value_type; + typedef value_type* pointer; + typedef const value_type* const_pointer; + typedef value_type& reference; + typedef const value_type& const_reference; + typedef list_node* link_type; + typedef size_t size_type; + typedef ptrdiff_t difference_type; + +public: + typedef __list_iterator<T, T&, T*> iterator; + typedef __list_iterator<T, const T&, const T*> const_iterator; + +#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION + typedef reverse_iterator<const_iterator> const_reverse_iterator; + typedef reverse_iterator<iterator> reverse_iterator; +#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */ + typedef reverse_bidirectional_iterator<const_iterator, value_type, + const_reference, difference_type> + const_reverse_iterator; + typedef reverse_bidirectional_iterator<iterator, value_type, reference, + difference_type> + reverse_iterator; +#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ + +protected: + link_type get_node() { return list_node_allocator::allocate(); } + void put_node(link_type p) { list_node_allocator::deallocate(p); } + + link_type create_node(const T& x) { + link_type p = get_node(); + __STL_TRY { + construct(&p->data, x); + } + __STL_UNWIND(put_node(p)); + return p; + } + void destroy_node(link_type p) { + destroy(&p->data); + put_node(p); + } + +protected: + void empty_initialize() { + node = get_node(); + node->next = node; + node->prev = node; + } + + void fill_initialize(size_type n, const T& value) { + empty_initialize(); + __STL_TRY { + insert(begin(), n, value); + } + __STL_UNWIND(clear(); put_node(node)); + } + +#ifdef __STL_MEMBER_TEMPLATES + template <class InputIterator> + void range_initialize(InputIterator first, InputIterator last) { + empty_initialize(); + __STL_TRY { + insert(begin(), first, last); + } + __STL_UNWIND(clear(); put_node(node)); + } +#else /* __STL_MEMBER_TEMPLATES */ + void range_initialize(const T* first, const T* last) { + empty_initialize(); + __STL_TRY { + insert(begin(), first, last); + } + __STL_UNWIND(clear(); put_node(node)); + } + void range_initialize(const_iterator first, const_iterator last) { + empty_initialize(); + __STL_TRY { + insert(begin(), first, last); + } + __STL_UNWIND(clear(); put_node(node)); + } +#endif /* __STL_MEMBER_TEMPLATES */ + +protected: + link_type node; + +public: + list() { empty_initialize(); } + + iterator begin() { return (link_type)((*node).next); } + const_iterator begin() const { return (link_type)((*node).next); } + iterator end() { return node; } + const_iterator end() const { return node; } + reverse_iterator rbegin() { return reverse_iterator(end()); } + const_reverse_iterator rbegin() const { + return const_reverse_iterator(end()); + } + reverse_iterator rend() { return reverse_iterator(begin()); } + const_reverse_iterator rend() const { + return const_reverse_iterator(begin()); + } + bool empty() const { return node->next == node; } + size_type size() const { + size_type result = 0; + distance(begin(), end(), result); + return result; + } + size_type max_size() const { return size_type(-1); } + reference front() { return *begin(); } + const_reference front() const { return *begin(); } + reference back() { return *(--end()); } + const_reference back() const { return *(--end()); } + void swap(list<T, Alloc>& x) { __STD::swap(node, x.node); } + iterator insert(iterator position, const T& x) { + link_type tmp = create_node(x); + tmp->next = position.node; + tmp->prev = position.node->prev; + (link_type(position.node->prev))->next = tmp; + position.node->prev = tmp; + return tmp; + } + iterator insert(iterator position) { return insert(position, T()); } +#ifdef __STL_MEMBER_TEMPLATES + template <class InputIterator> + void insert(iterator position, InputIterator first, InputIterator last); +#else /* __STL_MEMBER_TEMPLATES */ + void insert(iterator position, const T* first, const T* last); + void insert(iterator position, + const_iterator first, const_iterator last); +#endif /* __STL_MEMBER_TEMPLATES */ + void insert(iterator pos, size_type n, const T& x); + void insert(iterator pos, int n, const T& x) { + insert(pos, (size_type)n, x); + } + void insert(iterator pos, long n, const T& x) { + insert(pos, (size_type)n, x); + } + + void push_front(const T& x) { insert(begin(), x); } + void push_back(const T& x) { insert(end(), x); } + iterator erase(iterator position) { + link_type next_node = link_type(position.node->next); + link_type prev_node = link_type(position.node->prev); + prev_node->next = next_node; + next_node->prev = prev_node; + destroy_node(position.node); + return iterator(next_node); + } + iterator erase(iterator first, iterator last); + void resize(size_type new_size, const T& x); + void resize(size_type new_size) { resize(new_size, T()); } + void clear(); + + void pop_front() { erase(begin()); } + void pop_back() { + iterator tmp = end(); + erase(--tmp); + } + list(size_type n, const T& value) { fill_initialize(n, value); } + list(int n, const T& value) { fill_initialize(n, value); } + list(long n, const T& value) { fill_initialize(n, value); } + explicit list(size_type n) { fill_initialize(n, T()); } + +#ifdef __STL_MEMBER_TEMPLATES + template <class InputIterator> + list(InputIterator first, InputIterator last) { + range_initialize(first, last); + } + +#else /* __STL_MEMBER_TEMPLATES */ + list(const T* first, const T* last) { range_initialize(first, last); } + list(const_iterator first, const_iterator last) { + range_initialize(first, last); + } +#endif /* __STL_MEMBER_TEMPLATES */ + list(const list<T, Alloc>& x) { + range_initialize(x.begin(), x.end()); + } + ~list() { + clear(); + put_node(node); + } + list<T, Alloc>& operator=(const list<T, Alloc>& x); + +protected: + void transfer(iterator position, iterator first, iterator last) { + if (position != last) { + (*(link_type((*last.node).prev))).next = position.node; + (*(link_type((*first.node).prev))).next = last.node; + (*(link_type((*position.node).prev))).next = first.node; + link_type tmp = link_type((*position.node).prev); + (*position.node).prev = (*last.node).prev; + (*last.node).prev = (*first.node).prev; + (*first.node).prev = tmp; + } + } + +public: + void splice(iterator position, list& x) { + if (!x.empty()) + transfer(position, x.begin(), x.end()); + } + void splice(iterator position, list&, iterator i) { + iterator j = i; + ++j; + if (position == i || position == j) return; + transfer(position, i, j); + } + void splice(iterator position, list&, iterator first, iterator last) { + if (first != last) + transfer(position, first, last); + } + void remove(const T& value); + void unique(); + void merge(list& x); + void reverse(); + void sort(); + +#ifdef __STL_MEMBER_TEMPLATES + template <class Predicate> void remove_if(Predicate); + template <class BinaryPredicate> void unique(BinaryPredicate); + template <class StrictWeakOrdering> void merge(list&, StrictWeakOrdering); + template <class StrictWeakOrdering> void sort(StrictWeakOrdering); +#endif /* __STL_MEMBER_TEMPLATES */ + + friend bool operator== __STL_NULL_TMPL_ARGS (const list& x, const list& y); +}; + +template <class T, class Alloc> +inline bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y) { + typedef typename list<T,Alloc>::link_type link_type; + link_type e1 = x.node; + link_type e2 = y.node; + link_type n1 = (link_type) e1->next; + link_type n2 = (link_type) e2->next; + for ( ; n1 != e1 && n2 != e2 ; + n1 = (link_type) n1->next, n2 = (link_type) n2->next) + if (n1->data != n2->data) + return false; + return n1 == e1 && n2 == e2; +} + +template <class T, class Alloc> +inline bool operator<(const list<T, Alloc>& x, const list<T, Alloc>& y) { + return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); +} + +#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER + +template <class T, class Alloc> +inline void swap(list<T, Alloc>& x, list<T, Alloc>& y) { + x.swap(y); +} + +#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ + +#ifdef __STL_MEMBER_TEMPLATES + +template <class T, class Alloc> template <class InputIterator> +void list<T, Alloc>::insert(iterator position, + InputIterator first, InputIterator last) { + for ( ; first != last; ++first) + insert(position, *first); +} + +#else /* __STL_MEMBER_TEMPLATES */ + +template <class T, class Alloc> +void list<T, Alloc>::insert(iterator position, const T* first, const T* last) { + for ( ; first != last; ++first) + insert(position, *first); +} + +template <class T, class Alloc> +void list<T, Alloc>::insert(iterator position, + const_iterator first, const_iterator last) { + for ( ; first != last; ++first) + insert(position, *first); +} + +#endif /* __STL_MEMBER_TEMPLATES */ + +template <class T, class Alloc> +void list<T, Alloc>::insert(iterator position, size_type n, const T& x) { + for ( ; n > 0; --n) + insert(position, x); +} + +template <class T, class Alloc> +list<T,Alloc>::iterator list<T, Alloc>::erase(iterator first, iterator last) { + while (first != last) erase(first++); + return last; +} + +template <class T, class Alloc> +void list<T, Alloc>::resize(size_type new_size, const T& x) +{ + iterator i = begin(); + size_type len = 0; + for ( ; i != end() && len < new_size; ++i, ++len) + ; + if (len == new_size) + erase(i, end()); + else // i == end() + insert(end(), new_size - len, x); +} + +template <class T, class Alloc> +void list<T, Alloc>::clear() +{ + link_type cur = (link_type) node->next; + while (cur != node) { + link_type tmp = cur; + cur = (link_type) cur->next; + destroy_node(tmp); + } + node->next = node; + node->prev = node; +} + +template <class T, class Alloc> +list<T, Alloc>& list<T, Alloc>::operator=(const list<T, Alloc>& x) { + if (this != &x) { + iterator first1 = begin(); + iterator last1 = end(); + const_iterator first2 = x.begin(); + const_iterator last2 = x.end(); + while (first1 != last1 && first2 != last2) *first1++ = *first2++; + if (first2 == last2) + erase(first1, last1); + else + insert(last1, first2, last2); + } + return *this; +} + +template <class T, class Alloc> +void list<T, Alloc>::remove(const T& value) { + iterator first = begin(); + iterator last = end(); + while (first != last) { + iterator next = first; + ++next; + if (*first == value) erase(first); + first = next; + } +} + +template <class T, class Alloc> +void list<T, Alloc>::unique() { + iterator first = begin(); + iterator last = end(); + if (first == last) return; + iterator next = first; + while (++next != last) { + if (*first == *next) + erase(next); + else + first = next; + next = first; + } +} + +template <class T, class Alloc> +void list<T, Alloc>::merge(list<T, Alloc>& x) { + iterator first1 = begin(); + iterator last1 = end(); + iterator first2 = x.begin(); + iterator last2 = x.end(); + while (first1 != last1 && first2 != last2) + if (*first2 < *first1) { + iterator next = first2; + transfer(first1, first2, ++next); + first2 = next; + } + else + ++first1; + if (first2 != last2) transfer(last1, first2, last2); +} + +template <class T, class Alloc> +void list<T, Alloc>::reverse() { + if (node->next == node || link_type(node->next)->next == node) return; + iterator first = begin(); + ++first; + while (first != end()) { + iterator old = first; + ++first; + transfer(begin(), old, first); + } +} + +template <class T, class Alloc> +void list<T, Alloc>::sort() { + if (node->next == node || link_type(node->next)->next == node) return; + list<T, Alloc> carry; + list<T, Alloc> counter[64]; + int fill = 0; + while (!empty()) { + carry.splice(carry.begin(), *this, begin()); + int i = 0; + while(i < fill && !counter[i].empty()) { + counter[i].merge(carry); + carry.swap(counter[i++]); + } + carry.swap(counter[i]); + if (i == fill) ++fill; + } + + for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1]); + swap(counter[fill-1]); +} + +#ifdef __STL_MEMBER_TEMPLATES + +template <class T, class Alloc> template <class Predicate> +void list<T, Alloc>::remove_if(Predicate pred) { + iterator first = begin(); + iterator last = end(); + while (first != last) { + iterator next = first; + ++next; + if (pred(*first)) erase(first); + first = next; + } +} + +template <class T, class Alloc> template <class BinaryPredicate> +void list<T, Alloc>::unique(BinaryPredicate binary_pred) { + iterator first = begin(); + iterator last = end(); + if (first == last) return; + iterator next = first; + while (++next != last) { + if (binary_pred(*first, *next)) + erase(next); + else + first = next; + next = first; + } +} + +template <class T, class Alloc> template <class StrictWeakOrdering> +void list<T, Alloc>::merge(list<T, Alloc>& x, StrictWeakOrdering comp) { + iterator first1 = begin(); + iterator last1 = end(); + iterator first2 = x.begin(); + iterator last2 = x.end(); + while (first1 != last1 && first2 != last2) + if (comp(*first2, *first1)) { + iterator next = first2; + transfer(first1, first2, ++next); + first2 = next; + } + else + ++first1; + if (first2 != last2) transfer(last1, first2, last2); +} + +template <class T, class Alloc> template <class StrictWeakOrdering> +void list<T, Alloc>::sort(StrictWeakOrdering comp) { + if (node->next == node || link_type(node->next)->next == node) return; + list<T, Alloc> carry; + list<T, Alloc> counter[64]; + int fill = 0; + while (!empty()) { + carry.splice(carry.begin(), *this, begin()); + int i = 0; + while(i < fill && !counter[i].empty()) { + counter[i].merge(carry, comp); + carry.swap(counter[i++]); + } + carry.swap(counter[i]); + if (i == fill) ++fill; + } + + for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1], comp); + swap(counter[fill-1]); +} + +#endif /* __STL_MEMBER_TEMPLATES */ + +#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) +#pragma reset woff 1174 +#endif + +__STL_END_NAMESPACE + +#endif /* __SGI_STL_INTERNAL_LIST_H */ + +// Local Variables: +// mode:C++ +// End: |