1/*
2 * Copyright (c) 1997
3 * Silicon Graphics Computer Systems, Inc.
4 *
5 * Permission to use, copy, modify, distribute and sell this software
6 * and its documentation for any purpose is hereby granted without fee,
7 * provided that the above copyright notice appear in all copies and
8 * that both that copyright notice and this permission notice appear
9 * in supporting documentation.  Silicon Graphics makes no
10 * representations about the suitability of this software for any
11 * purpose.  It is provided "as is" without express or implied warranty.
12 *
13 */
14
15/* NOTE: This is an internal header file, included by other STL headers.
16 *   You should not attempt to use it directly.
17 */
18
19#ifndef __SGI_STL_INTERNAL_SLIST_H
20#define __SGI_STL_INTERNAL_SLIST_H
21
22
23__STL_BEGIN_NAMESPACE
24
25#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
26#pragma set woff 1174
27#pragma set woff 1375
28#endif
29
30struct _Slist_node_base
31{
32  _Slist_node_base* _M_next;
33};
34
35inline _Slist_node_base*
36__slist_make_link(_Slist_node_base* __prev_node,
37                  _Slist_node_base* __new_node)
38{
39  __new_node->_M_next = __prev_node->_M_next;
40  __prev_node->_M_next = __new_node;
41  return __new_node;
42}
43
44inline _Slist_node_base*
45__slist_previous(_Slist_node_base* __head,
46                 const _Slist_node_base* __node)
47{
48  while (__head && __head->_M_next != __node)
49    __head = __head->_M_next;
50  return __head;
51}
52
53inline const _Slist_node_base*
54__slist_previous(const _Slist_node_base* __head,
55                 const _Slist_node_base* __node)
56{
57  while (__head && __head->_M_next != __node)
58    __head = __head->_M_next;
59  return __head;
60}
61
62inline void __slist_splice_after(_Slist_node_base* __pos,
63                                 _Slist_node_base* __before_first,
64                                 _Slist_node_base* __before_last)
65{
66  if (__pos != __before_first && __pos != __before_last) {
67    _Slist_node_base* __first = __before_first->_M_next;
68    _Slist_node_base* __after = __pos->_M_next;
69    __before_first->_M_next = __before_last->_M_next;
70    __pos->_M_next = __first;
71    __before_last->_M_next = __after;
72  }
73}
74
75inline _Slist_node_base* __slist_reverse(_Slist_node_base* __node)
76{
77  _Slist_node_base* __result = __node;
78  __node = __node->_M_next;
79  __result->_M_next = 0;
80  while(__node) {
81    _Slist_node_base* __next = __node->_M_next;
82    __node->_M_next = __result;
83    __result = __node;
84    __node = __next;
85  }
86  return __result;
87}
88
89inline size_t __slist_size(_Slist_node_base* __node)
90{
91  size_t __result = 0;
92  for ( ; __node != 0; __node = __node->_M_next)
93    ++__result;
94  return __result;
95}
96
97template <class _Tp>
98struct _Slist_node : public _Slist_node_base
99{
100  _Tp _M_data;
101};
102
103struct _Slist_iterator_base
104{
105  typedef size_t               size_type;
106  typedef ptrdiff_t            difference_type;
107  typedef forward_iterator_tag iterator_category;
108
109  _Slist_node_base* _M_node;
110
111  _Slist_iterator_base(_Slist_node_base* __x) : _M_node(__x) {}
112  void _M_incr() { _M_node = _M_node->_M_next; }
113
114  bool operator==(const _Slist_iterator_base& __x) const {
115    return _M_node == __x._M_node;
116  }
117  bool operator!=(const _Slist_iterator_base& __x) const {
118    return _M_node != __x._M_node;
119  }
120};
121
122template <class _Tp, class _Ref, class _Ptr>
123struct _Slist_iterator : public _Slist_iterator_base
124{
125  typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;
126  typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
127  typedef _Slist_iterator<_Tp, _Ref, _Ptr>             _Self;
128
129  typedef _Tp              value_type;
130  typedef _Ptr             pointer;
131  typedef _Ref             reference;
132  typedef _Slist_node<_Tp> _Node;
133
134  _Slist_iterator(_Node* __x) : _Slist_iterator_base(__x) {}
135  _Slist_iterator() : _Slist_iterator_base(0) {}
136  _Slist_iterator(const iterator& __x) : _Slist_iterator_base(__x._M_node) {}
137
138  reference operator*() const { return ((_Node*) _M_node)->_M_data; }
139#ifndef __SGI_STL_NO_ARROW_OPERATOR
140  pointer operator->() const { return &(operator*()); }
141#endif /* __SGI_STL_NO_ARROW_OPERATOR */
142
143  _Self& operator++()
144  {
145    _M_incr();
146    return *this;
147  }
148  _Self operator++(int)
149  {
150    _Self __tmp = *this;
151    _M_incr();
152    return __tmp;
153  }
154};
155
156#ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
157
158inline ptrdiff_t* distance_type(const _Slist_iterator_base&) {
159  return 0;
160}
161
162inline forward_iterator_tag iterator_category(const _Slist_iterator_base&) {
163  return forward_iterator_tag();
164}
165
166template <class _Tp, class _Ref, class _Ptr>
167inline _Tp* value_type(const _Slist_iterator<_Tp, _Ref, _Ptr>&) {
168  return 0;
169}
170
171#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
172
173// Base class that encapsulates details of allocators.  Three cases:
174// an ordinary standard-conforming allocator, a standard-conforming
175// allocator with no non-static data, and an SGI-style allocator.
176// This complexity is necessary only because we're worrying about backward
177// compatibility and because we want to avoid wasting storage on an
178// allocator instance if it isn't necessary.
179
180#ifdef __STL_USE_STD_ALLOCATORS
181
182// Base for general standard-conforming allocators.
183template <class _Tp, class _Allocator, bool _IsStatic>
184class _Slist_alloc_base {
185public:
186  typedef typename _Alloc_traits<_Tp,_Allocator>::allocator_type
187          allocator_type;
188  allocator_type get_allocator() const { return _M_node_allocator; }
189
190  _Slist_alloc_base(const allocator_type& __a) : _M_node_allocator(__a) {}
191
192protected:
193  _Slist_node<_Tp>* _M_get_node()
194    { return _M_node_allocator.allocate(1); }
195  void _M_put_node(_Slist_node<_Tp>* __p)
196    { _M_node_allocator.deallocate(__p, 1); }
197
198protected:
199  typename _Alloc_traits<_Slist_node<_Tp>,_Allocator>::allocator_type
200           _M_node_allocator;
201  _Slist_node_base _M_head;
202};
203
204// Specialization for instanceless allocators.
205template <class _Tp, class _Allocator>
206class _Slist_alloc_base<_Tp,_Allocator, true> {
207public:
208  typedef typename _Alloc_traits<_Tp,_Allocator>::allocator_type
209          allocator_type;
210  allocator_type get_allocator() const { return allocator_type(); }
211
212  _Slist_alloc_base(const allocator_type&) {}
213
214protected:
215  typedef typename _Alloc_traits<_Slist_node<_Tp>, _Allocator>::_Alloc_type
216          _Alloc_type;
217  _Slist_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
218  void _M_put_node(_Slist_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
219
220protected:
221  _Slist_node_base _M_head;
222};
223
224
225template <class _Tp, class _Alloc>
226struct _Slist_base
227  : public _Slist_alloc_base<_Tp, _Alloc,
228                             _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
229{
230  typedef _Slist_alloc_base<_Tp, _Alloc,
231                            _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
232          _Base;
233  typedef typename _Base::allocator_type allocator_type;
234
235  _Slist_base(const allocator_type& __a) : _Base(__a) { _M_head._M_next = 0; }
236  ~_Slist_base() { _M_erase_after(&_M_head, 0); }
237
238protected:
239
240  _Slist_node_base* _M_erase_after(_Slist_node_base* __pos)
241  {
242    _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next);
243    _Slist_node_base* __next_next = __next->_M_next;
244    __pos->_M_next = __next_next;
245    destroy(&__next->_M_data);
246    _M_put_node(__next);
247    return __next_next;
248  }
249  _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
250};
251
252#else /* __STL_USE_STD_ALLOCATORS */
253
254template <class _Tp, class _Alloc>
255struct _Slist_base {
256  typedef _Alloc allocator_type;
257  allocator_type get_allocator() const { return allocator_type(); }
258
259  _Slist_base(const allocator_type&) { _M_head._M_next = 0; }
260  ~_Slist_base() { _M_erase_after(&_M_head, 0); }
261
262protected:
263  typedef simple_alloc<_Slist_node<_Tp>, _Alloc> _Alloc_type;
264  _Slist_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
265  void _M_put_node(_Slist_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
266
267  _Slist_node_base* _M_erase_after(_Slist_node_base* __pos)
268  {
269    _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next);
270    _Slist_node_base* __next_next = __next->_M_next;
271    __pos->_M_next = __next_next;
272    destroy(&__next->_M_data);
273    _M_put_node(__next);
274    return __next_next;
275  }
276  _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
277
278protected:
279  _Slist_node_base _M_head;
280};
281
282#endif /* __STL_USE_STD_ALLOCATORS */
283
284template <class _Tp, class _Alloc>
285_Slist_node_base*
286_Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first,
287                                        _Slist_node_base* __last_node) {
288  _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next);
289  while (__cur != __last_node) {
290    _Slist_node<_Tp>* __tmp = __cur;
291    __cur = (_Slist_node<_Tp>*) __cur->_M_next;
292    destroy(&__tmp->_M_data);
293    _M_put_node(__tmp);
294  }
295  __before_first->_M_next = __last_node;
296  return __last_node;
297}
298
299template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
300class slist : private _Slist_base<_Tp,_Alloc>
301{
302private:
303  typedef _Slist_base<_Tp,_Alloc> _Base;
304public:
305  typedef _Tp                value_type;
306  typedef value_type*       pointer;
307  typedef const value_type* const_pointer;
308  typedef value_type&       reference;
309  typedef const value_type& const_reference;
310  typedef size_t            size_type;
311  typedef ptrdiff_t         difference_type;
312
313  typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;
314  typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
315
316  typedef typename _Base::allocator_type allocator_type;
317  allocator_type get_allocator() const { return _Base::get_allocator(); }
318
319private:
320  typedef _Slist_node<_Tp>      _Node;
321  typedef _Slist_node_base      _Node_base;
322  typedef _Slist_iterator_base  _Iterator_base;
323
324  _Node* _M_create_node(const value_type& __x) {
325    _Node* __node = _M_get_node();
326    __STL_TRY {
327      construct(&__node->_M_data, __x);
328      __node->_M_next = 0;
329    }
330    __STL_UNWIND(_M_put_node(__node));
331    return __node;
332  }
333
334  _Node* _M_create_node() {
335    _Node* __node = _M_get_node();
336    __STL_TRY {
337      construct(&__node->_M_data);
338      __node->_M_next = 0;
339    }
340    __STL_UNWIND(_M_put_node(__node));
341    return __node;
342  }
343
344private:
345#ifdef __STL_USE_NAMESPACES
346  using _Base::_M_get_node;
347  using _Base::_M_put_node;
348  using _Base::_M_erase_after;
349  using _Base::_M_head;
350#endif /* __STL_USE_NAMESPACES */
351
352public:
353  explicit slist(const allocator_type& __a = allocator_type()) : _Base(__a) {}
354
355  slist(size_type __n, const value_type& __x,
356        const allocator_type& __a =  allocator_type()) : _Base(__a)
357    { _M_insert_after_fill(&_M_head, __n, __x); }
358
359  explicit slist(size_type __n) : _Base(allocator_type())
360    { _M_insert_after_fill(&_M_head, __n, value_type()); }
361
362#ifdef __STL_MEMBER_TEMPLATES
363  // We don't need any dispatching tricks here, because _M_insert_after_range
364  // already does them.
365  template <class _InputIterator>
366  slist(_InputIterator __first, _InputIterator __last,
367        const allocator_type& __a =  allocator_type()) : _Base(__a)
368    { _M_insert_after_range(&_M_head, __first, __last); }
369
370#else /* __STL_MEMBER_TEMPLATES */
371  slist(const_iterator __first, const_iterator __last,
372        const allocator_type& __a =  allocator_type()) : _Base(__a)
373    { _M_insert_after_range(&_M_head, __first, __last); }
374  slist(const value_type* __first, const value_type* __last,
375        const allocator_type& __a =  allocator_type()) : _Base(__a)
376    { _M_insert_after_range(&_M_head, __first, __last); }
377#endif /* __STL_MEMBER_TEMPLATES */
378
379  slist(const slist& __x) : _Base(__x.get_allocator())
380    { _M_insert_after_range(&_M_head, __x.begin(), __x.end()); }
381
382  slist& operator= (const slist& __x);
383
384  ~slist() {}
385
386public:
387  // assign(), a generalized assignment member function.  Two
388  // versions: one that takes a count, and one that takes a range.
389  // The range version is a member template, so we dispatch on whether
390  // or not the type is an integer.
391
392  void assign(size_type __n, const _Tp& __val);
393
394#ifdef __STL_MEMBER_TEMPLATES
395
396  template <class _InputIterator>
397  void assign(_InputIterator __first, _InputIterator __last) {
398    typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
399    _M_assign_dispatch(__first, __last, _Integral());
400  }
401
402  template <class _Integer>
403  void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
404    { assign((size_type) __n, (_Tp) __val); }
405
406  template <class _InputIterator>
407  void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
408                          __false_type);
409
410#endif /* __STL_MEMBER_TEMPLATES */
411
412public:
413
414  iterator begin() { return iterator((_Node*)_M_head._M_next); }
415  const_iterator begin() const
416    { return const_iterator((_Node*)_M_head._M_next);}
417
418  iterator end() { return iterator(0); }
419  const_iterator end() const { return const_iterator(0); }
420
421  size_type size() const { return __slist_size(_M_head._M_next); }
422
423  size_type max_size() const { return size_type(-1); }
424
425  bool empty() const { return _M_head._M_next == 0; }
426
427  void swap(slist& __x) { __STD::swap(_M_head._M_next, __x._M_head._M_next); }
428
429public:
430  friend bool operator== __STL_NULL_TMPL_ARGS (const slist<_Tp,_Alloc>& _SL1,
431                                               const slist<_Tp,_Alloc>& _SL2);
432
433public:
434
435  reference front() { return ((_Node*) _M_head._M_next)->_M_data; }
436  const_reference front() const
437    { return ((_Node*) _M_head._M_next)->_M_data; }
438  void push_front(const value_type& __x)   {
439    __slist_make_link(&_M_head, _M_create_node(__x));
440  }
441  void push_front() { __slist_make_link(&_M_head, _M_create_node());}
442  void pop_front() {
443    _Node* __node = (_Node*) _M_head._M_next;
444    _M_head._M_next = __node->_M_next;
445    destroy(&__node->_M_data);
446    _M_put_node(__node);
447  }
448
449  iterator previous(const_iterator __pos) {
450    return iterator((_Node*) __slist_previous(&_M_head, __pos._M_node));
451  }
452  const_iterator previous(const_iterator __pos) const {
453    return const_iterator((_Node*) __slist_previous(&_M_head, __pos._M_node));
454  }
455
456private:
457  _Node* _M_insert_after(_Node_base* __pos, const value_type& __x) {
458    return (_Node*) (__slist_make_link(__pos, _M_create_node(__x)));
459  }
460
461  _Node* _M_insert_after(_Node_base* __pos) {
462    return (_Node*) (__slist_make_link(__pos, _M_create_node()));
463  }
464
465  void _M_insert_after_fill(_Node_base* __pos,
466                            size_type __n, const value_type& __x) {
467    for (size_type __i = 0; __i < __n; ++__i)
468      __pos = __slist_make_link(__pos, _M_create_node(__x));
469  }
470
471#ifdef __STL_MEMBER_TEMPLATES
472
473  // Check whether it's an integral type.  If so, it's not an iterator.
474  template <class _InIter>
475  void _M_insert_after_range(_Node_base* __pos,
476                             _InIter __first, _InIter __last) {
477    typedef typename _Is_integer<_InIter>::_Integral _Integral;
478    _M_insert_after_range(__pos, __first, __last, _Integral());
479  }
480
481  template <class _Integer>
482  void _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x,
483                             __true_type) {
484    _M_insert_after_fill(__pos, __n, __x);
485  }
486
487  template <class _InIter>
488  void _M_insert_after_range(_Node_base* __pos,
489                             _InIter __first, _InIter __last,
490                             __false_type) {
491    while (__first != __last) {
492      __pos = __slist_make_link(__pos, _M_create_node(*__first));
493      ++__first;
494    }
495  }
496
497#else /* __STL_MEMBER_TEMPLATES */
498
499  void _M_insert_after_range(_Node_base* __pos,
500                             const_iterator __first, const_iterator __last) {
501    while (__first != __last) {
502      __pos = __slist_make_link(__pos, _M_create_node(*__first));
503      ++__first;
504    }
505  }
506  void _M_insert_after_range(_Node_base* __pos,
507                             const value_type* __first,
508                             const value_type* __last) {
509    while (__first != __last) {
510      __pos = __slist_make_link(__pos, _M_create_node(*__first));
511      ++__first;
512    }
513  }
514
515#endif /* __STL_MEMBER_TEMPLATES */
516
517public:
518
519  iterator insert_after(iterator __pos, const value_type& __x) {
520    return iterator(_M_insert_after(__pos._M_node, __x));
521  }
522
523  iterator insert_after(iterator __pos) {
524    return insert_after(__pos, value_type());
525  }
526
527  void insert_after(iterator __pos, size_type __n, const value_type& __x) {
528    _M_insert_after_fill(__pos._M_node, __n, __x);
529  }
530
531#ifdef __STL_MEMBER_TEMPLATES
532
533  // We don't need any dispatching tricks here, because _M_insert_after_range
534  // already does them.
535  template <class _InIter>
536  void insert_after(iterator __pos, _InIter __first, _InIter __last) {
537    _M_insert_after_range(__pos._M_node, __first, __last);
538  }
539
540#else /* __STL_MEMBER_TEMPLATES */
541
542  void insert_after(iterator __pos,
543                    const_iterator __first, const_iterator __last) {
544    _M_insert_after_range(__pos._M_node, __first, __last);
545  }
546  void insert_after(iterator __pos,
547                    const value_type* __first, const value_type* __last) {
548    _M_insert_after_range(__pos._M_node, __first, __last);
549  }
550
551#endif /* __STL_MEMBER_TEMPLATES */
552
553  iterator insert(iterator __pos, const value_type& __x) {
554    return iterator(_M_insert_after(__slist_previous(&_M_head, __pos._M_node),
555                    __x));
556  }
557
558  iterator insert(iterator __pos) {
559    return iterator(_M_insert_after(__slist_previous(&_M_head, __pos._M_node),
560                                    value_type()));
561  }
562
563  void insert(iterator __pos, size_type __n, const value_type& __x) {
564    _M_insert_after_fill(__slist_previous(&_M_head, __pos._M_node), __n, __x);
565  }
566
567#ifdef __STL_MEMBER_TEMPLATES
568
569  // We don't need any dispatching tricks here, because _M_insert_after_range
570  // already does them.
571  template <class _InIter>
572  void insert(iterator __pos, _InIter __first, _InIter __last) {
573    _M_insert_after_range(__slist_previous(&_M_head, __pos._M_node),
574                          __first, __last);
575  }
576
577#else /* __STL_MEMBER_TEMPLATES */
578
579  void insert(iterator __pos, const_iterator __first, const_iterator __last) {
580    _M_insert_after_range(__slist_previous(&_M_head, __pos._M_node),
581                          __first, __last);
582  }
583  void insert(iterator __pos, const value_type* __first,
584                              const value_type* __last) {
585    _M_insert_after_range(__slist_previous(&_M_head, __pos._M_node),
586                          __first, __last);
587  }
588
589#endif /* __STL_MEMBER_TEMPLATES */
590
591
592public:
593  iterator erase_after(iterator __pos) {
594    return iterator((_Node*) _M_erase_after(__pos._M_node));
595  }
596  iterator erase_after(iterator __before_first, iterator __last) {
597    return iterator((_Node*) _M_erase_after(__before_first._M_node,
598                                            __last._M_node));
599  }
600
601  iterator erase(iterator __pos) {
602    return (_Node*) _M_erase_after(__slist_previous(&_M_head,
603                                                    __pos._M_node));
604  }
605  iterator erase(iterator __first, iterator __last) {
606    return (_Node*) _M_erase_after(
607      __slist_previous(&_M_head, __first._M_node), __last._M_node);
608  }
609
610  void resize(size_type new_size, const _Tp& __x);
611  void resize(size_type new_size) { resize(new_size, _Tp()); }
612  void clear() { _M_erase_after(&_M_head, 0); }
613
614public:
615  // Moves the range [__before_first + 1, __before_last + 1) to *this,
616  //  inserting it immediately after __pos.  This is constant time.
617  void splice_after(iterator __pos,
618                    iterator __before_first, iterator __before_last)
619  {
620    if (__before_first != __before_last)
621      __slist_splice_after(__pos._M_node, __before_first._M_node,
622                           __before_last._M_node);
623  }
624
625  // Moves the element that follows __prev to *this, inserting it immediately
626  //  after __pos.  This is constant time.
627  void splice_after(iterator __pos, iterator __prev)
628  {
629    __slist_splice_after(__pos._M_node,
630                         __prev._M_node, __prev._M_node->_M_next);
631  }
632
633
634  // Linear in distance(begin(), __pos), and linear in __x.size().
635  void splice(iterator __pos, slist& __x) {
636    if (__x._M_head._M_next)
637      __slist_splice_after(__slist_previous(&_M_head, __pos._M_node),
638                           &__x._M_head, __slist_previous(&__x._M_head, 0));
639  }
640
641  // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i).
642  void splice(iterator __pos, slist& __x, iterator __i) {
643    __slist_splice_after(__slist_previous(&_M_head, __pos._M_node),
644                         __slist_previous(&__x._M_head, __i._M_node),
645                         __i._M_node);
646  }
647
648  // Linear in distance(begin(), __pos), in distance(__x.begin(), __first),
649  // and in distance(__first, __last).
650  void splice(iterator __pos, slist& __x, iterator __first, iterator __last)
651  {
652    if (__first != __last)
653      __slist_splice_after(__slist_previous(&_M_head, __pos._M_node),
654                           __slist_previous(&__x._M_head, __first._M_node),
655                           __slist_previous(__first._M_node, __last._M_node));
656  }
657
658public:
659  void reverse() {
660    if (_M_head._M_next)
661      _M_head._M_next = __slist_reverse(_M_head._M_next);
662  }
663
664  void remove(const _Tp& __val);
665  void unique();
666  void merge(slist& __x);
667  void sort();
668
669#ifdef __STL_MEMBER_TEMPLATES
670  template <class _Predicate>
671  void remove_if(_Predicate __pred);
672
673  template <class _BinaryPredicate>
674  void unique(_BinaryPredicate __pred);
675
676  template <class _StrictWeakOrdering>
677  void merge(slist&, _StrictWeakOrdering);
678
679  template <class _StrictWeakOrdering>
680  void sort(_StrictWeakOrdering __comp);
681#endif /* __STL_MEMBER_TEMPLATES */
682};
683
684template <class _Tp, class _Alloc>
685slist<_Tp,_Alloc>& slist<_Tp,_Alloc>::operator=(const slist<_Tp,_Alloc>& __x)
686{
687  if (&__x != this) {
688    _Node_base* __p1 = &_M_head;
689    _Node* __n1 = (_Node*) _M_head._M_next;
690    const _Node* __n2 = (const _Node*) __x._M_head._M_next;
691    while (__n1 && __n2) {
692      __n1->_M_data = __n2->_M_data;
693      __p1 = __n1;
694      __n1 = (_Node*) __n1->_M_next;
695      __n2 = (const _Node*) __n2->_M_next;
696    }
697    if (__n2 == 0)
698      _M_erase_after(__p1, 0);
699    else
700      _M_insert_after_range(__p1, const_iterator((_Node*)__n2),
701                                  const_iterator(0));
702  }
703  return *this;
704}
705
706template <class _Tp, class _Alloc>
707void slist<_Tp, _Alloc>::assign(size_type __n, const _Tp& __val) {
708  _Node_base* __prev = &_M_head;
709  _Node* __node = (_Node*) _M_head._M_next;
710  for ( ; __node != 0 && __n > 0 ; --__n) {
711    __node->_M_data = __val;
712    __prev = __node;
713    __node = (_Node*) __node->_M_next;
714  }
715  if (__n > 0)
716    _M_insert_after_fill(__prev, __n, __val);
717  else
718    _M_erase_after(__prev, 0);
719}
720
721#ifdef __STL_MEMBER_TEMPLATES
722
723template <class _Tp, class _Alloc> template <class _InputIter>
724void
725slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first, _InputIter __last,
726                                       __false_type)
727{
728  _Node_base* __prev = &_M_head;
729  _Node* __node = (_Node*) _M_head._M_next;
730  while (__node != 0 && __first != __last) {
731    __node->_M_data = *__first;
732    __prev = __node;
733    __node = (_Node*) __node->_M_next;
734    ++__first;
735  }
736  if (__first != __last)
737    _M_insert_after_range(__prev, __first, __last);
738  else
739    _M_erase_after(__prev, 0);
740}
741
742#endif /* __STL_MEMBER_TEMPLATES */
743
744template <class _Tp, class _Alloc>
745inline bool
746operator==(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2)
747{
748  typedef typename slist<_Tp,_Alloc>::_Node _Node;
749  _Node* __n1 = (_Node*) _SL1._M_head._M_next;
750  _Node* __n2 = (_Node*) _SL2._M_head._M_next;
751  while (__n1 && __n2 && __n1->_M_data == __n2->_M_data) {
752    __n1 = (_Node*) __n1->_M_next;
753    __n2 = (_Node*) __n2->_M_next;
754  }
755  return __n1 == 0 && __n2 == 0;
756}
757
758template <class _Tp, class _Alloc>
759inline bool operator<(const slist<_Tp,_Alloc>& _SL1,
760                      const slist<_Tp,_Alloc>& _SL2)
761{
762  return lexicographical_compare(_SL1.begin(), _SL1.end(),
763                                 _SL2.begin(), _SL2.end());
764}
765
766#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
767
768template <class _Tp, class _Alloc>
769inline void swap(slist<_Tp,_Alloc>& __x, slist<_Tp,_Alloc>& __y) {
770  __x.swap(__y);
771}
772
773#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
774
775
776template <class _Tp, class _Alloc>
777void slist<_Tp,_Alloc>::resize(size_type __len, const _Tp& __x)
778{
779  _Node_base* __cur = &_M_head;
780  while (__cur->_M_next != 0 && __len > 0) {
781    --__len;
782    __cur = __cur->_M_next;
783  }
784  if (__cur->_M_next)
785    _M_erase_after(__cur, 0);
786  else
787    _M_insert_after_fill(__cur, __len, __x);
788}
789
790template <class _Tp, class _Alloc>
791void slist<_Tp,_Alloc>::remove(const _Tp& __val)
792{
793  _Node_base* __cur = &_M_head;
794  while (__cur && __cur->_M_next) {
795    if (((_Node*) __cur->_M_next)->_M_data == __val)
796      _M_erase_after(__cur);
797    else
798      __cur = __cur->_M_next;
799  }
800}
801
802template <class _Tp, class _Alloc>
803void slist<_Tp,_Alloc>::unique()
804{
805  _Node_base* __cur = _M_head._M_next;
806  if (__cur) {
807    while (__cur->_M_next) {
808      if (((_Node*)__cur)->_M_data ==
809          ((_Node*)(__cur->_M_next))->_M_data)
810        _M_erase_after(__cur);
811      else
812        __cur = __cur->_M_next;
813    }
814  }
815}
816
817template <class _Tp, class _Alloc>
818void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x)
819{
820  _Node_base* __n1 = &_M_head;
821  while (__n1->_M_next && __x._M_head._M_next) {
822    if (((_Node*) __x._M_head._M_next)->_M_data <
823        ((_Node*)       __n1->_M_next)->_M_data)
824      __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
825    __n1 = __n1->_M_next;
826  }
827  if (__x._M_head._M_next) {
828    __n1->_M_next = __x._M_head._M_next;
829    __x._M_head._M_next = 0;
830  }
831}
832
833template <class _Tp, class _Alloc>
834void slist<_Tp,_Alloc>::sort()
835{
836  if (_M_head._M_next && _M_head._M_next->_M_next) {
837    slist __carry;
838    slist __counter[64];
839    int __fill = 0;
840    while (!empty()) {
841      __slist_splice_after(&__carry._M_head, &_M_head, _M_head._M_next);
842      int __i = 0;
843      while (__i < __fill && !__counter[__i].empty()) {
844        __counter[__i].merge(__carry);
845        __carry.swap(__counter[__i]);
846        ++__i;
847      }
848      __carry.swap(__counter[__i]);
849      if (__i == __fill)
850        ++__fill;
851    }
852
853    for (int __i = 1; __i < __fill; ++__i)
854      __counter[__i].merge(__counter[__i-1]);
855    this->swap(__counter[__fill-1]);
856  }
857}
858
859#ifdef __STL_MEMBER_TEMPLATES
860
861template <class _Tp, class _Alloc>
862template <class _Predicate>
863void slist<_Tp,_Alloc>::remove_if(_Predicate __pred)
864{
865  _Node_base* __cur = &_M_head;
866  while (__cur->_M_next) {
867    if (__pred(((_Node*) __cur->_M_next)->_M_data))
868      _M_erase_after(__cur);
869    else
870      __cur = __cur->_M_next;
871  }
872}
873
874template <class _Tp, class _Alloc> template <class _BinaryPredicate>
875void slist<_Tp,_Alloc>::unique(_BinaryPredicate __pred)
876{
877  _Node* __cur = (_Node*) _M_head._M_next;
878  if (__cur) {
879    while (__cur->_M_next) {
880      if (__pred(((_Node*)__cur)->_M_data,
881                 ((_Node*)(__cur->_M_next))->_M_data))
882        _M_erase_after(__cur);
883      else
884        __cur = (_Node*) __cur->_M_next;
885    }
886  }
887}
888
889template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
890void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x,
891                              _StrictWeakOrdering __comp)
892{
893  _Node_base* __n1 = &_M_head;
894  while (__n1->_M_next && __x._M_head._M_next) {
895    if (__comp(((_Node*) __x._M_head._M_next)->_M_data,
896               ((_Node*)       __n1->_M_next)->_M_data))
897      __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
898    __n1 = __n1->_M_next;
899  }
900  if (__x._M_head._M_next) {
901    __n1->_M_next = __x._M_head._M_next;
902    __x._M_head._M_next = 0;
903  }
904}
905
906template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
907void slist<_Tp,_Alloc>::sort(_StrictWeakOrdering __comp)
908{
909  if (_M_head._M_next && _M_head._M_next->_M_next) {
910    slist __carry;
911    slist __counter[64];
912    int __fill = 0;
913    while (!empty()) {
914      __slist_splice_after(&__carry._M_head, &_M_head, _M_head._M_next);
915      int __i = 0;
916      while (__i < __fill && !__counter[__i].empty()) {
917        __counter[__i].merge(__carry, __comp);
918        __carry.swap(__counter[__i]);
919        ++__i;
920      }
921      __carry.swap(__counter[__i]);
922      if (__i == __fill)
923        ++__fill;
924    }
925
926    for (int __i = 1; __i < __fill; ++__i)
927      __counter[__i].merge(__counter[__i-1], __comp);
928    this->swap(__counter[__fill-1]);
929  }
930}
931
932#endif /* __STL_MEMBER_TEMPLATES */
933
934#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
935#pragma reset woff 1174
936#pragma reset woff 1375
937#endif
938
939__STL_END_NAMESPACE
940
941#endif /* __SGI_STL_INTERNAL_SLIST_H */
942
943// Local Variables:
944// mode:C++
945// End:
946