diff options
Diffstat (limited to 'contrib/libg++/libstdc++/stl')
55 files changed, 0 insertions, 9296 deletions
diff --git a/contrib/libg++/libstdc++/stl/ChangeLog b/contrib/libg++/libstdc++/stl/ChangeLog deleted file mode 100644 index 786989d766935..0000000000000 --- a/contrib/libg++/libstdc++/stl/ChangeLog +++ /dev/null @@ -1,86 +0,0 @@ -Wed Apr 24 10:45:22 1996 Doug Evans <dje@blues.cygnus.com> - - * Makefile.in (tempbuf.o,random.o): Add rules for SunOS VPATH. - -Fri Apr 5 17:52:31 1996 Per Bothner <bothner@kalessin.cygnus.com> - - * configure.in (EXTRA_MOSTLYCLEAN): New, to remove stl.list. - -Sun Mar 10 07:49:03 1996 Jason Merrill <jason@yorick.cygnus.com> - - * deque.h (distance_type): Add overload for g++. - From Joe Buck. - -Thu Nov 9 17:05:23 1995 Jason Merrill <jason@yorick.cygnus.com> - - * algo.h algobase.h bvector.h defalloc.h deque.h function.h heap.h - iterator.h list.h map.h multimap.h multiset.h pair.h projectn.h - set.h stack.h tempbuf.h tree.h vector.h: Wrap #include <bool.h> - with #ifndef __GNUG__. - -Thu Nov 2 17:05:44 1995 Jason Merrill <jason@yorick.cygnus.com> - - * deque.h (deque<T>::insert): Fix merge typo. - * vector.h (value_type): Lose. - -Thu Nov 2 14:33:47 1995 Per Bothner <bothner@kalessin.cygnus.com> - - * algo.h, algobase.h, deque.h, function.h, list.h, pair.h, random.cc: - Merge in Oct 31 1995 release from HP. - -Fri Aug 11 17:11:12 1995 Per Bothner <bothner@kalessin.cygnus.com> - - * list.h: Avoid duplicate construction and destruction of list_nodes. - Patch from Klamer Schutte <klamer@ph.tn.tudelft.nl>. - -Fri Aug 11 16:45:18 1995 Per Bothner <bothner@kalessin.cygnus.com> - - * algo.h, algobase.h, deque.h: Merged in Jul 12 1995 release from HP. - -Mon Jun 5 18:38:56 1995 Jason Merrill <jason@phydeaux.cygnus.com> - - * Makefile.in (stl.list): Depend on stamp-picdir. - -Wed May 17 02:30:47 1995 Jason Merrill <jason@phydeaux.cygnus.com> - - * tree.h: Rearrange member initializers in rb_tree constructors. - - * Update to HP's February 7, 1995 release. - -Fri May 5 10:45:31 1995 Mike Stump <mrs@cygnus.com> - - * random.cc (seed): Move `for' decl out of `for' statement. - -Wed Apr 26 13:09:16 1995 Jason Merrill <jason@phydeaux.cygnus.com> - - * configure.in (XCXXINCLUDES): Rename. - -Wed Mar 29 19:24:56 1995 Jason Merrill <jason@phydeaux.cygnus.com> - - * tree.h (insert): Return a value. - - * vector.h (insert): Cast iterator difference to size_type to - avoid warning. - -Sun Feb 12 09:12:17 1995 Mike Stump <mrs@cygnus.com> - - * tree.h (rb_tree::max_size): Add definition when using GNU - workaround. - -Thu Jan 12 01:37:42 1995 deanm@medulla.LABS.TEK.COM (Dean Messing) - - * configure.in (LIBDIR): Set to yes. - -Fri Dec 30 18:26:20 1994 Mike Stump <mrs@cygnus.com> - - * iterator.h: Add default template parameters where possible. - -Fri Dec 30 16:29:39 1994 Mike Stump <mrs@cygnus.com> - - * algo.h: Change rand to __rand to fix make check on linux systems. - -Tue Nov 29 15:30:30 1994 Per Bothner <bothner@kalessin.cygnus.com> - - * Initial check-in, based on HP's October 21, 1994. - - diff --git a/contrib/libg++/libstdc++/stl/Makefile.in b/contrib/libg++/libstdc++/stl/Makefile.in deleted file mode 100644 index 438d81df2d77a..0000000000000 --- a/contrib/libg++/libstdc++/stl/Makefile.in +++ /dev/null @@ -1,12 +0,0 @@ -#### package, host, target, and site dependent Makefile fragments come in here. -## - -STL_OBJECTS = tempbuf.o tree.o random.o - -stl.list: stamp-picdir $(STL_OBJECTS) - @echo "$(STL_OBJECTS)" >stl.list - -# These are here for SunOS VPATH. -tempbuf.o: tempbuf.cc -random.o: random.cc -tree.o: tree.cc diff --git a/contrib/libg++/libstdc++/stl/README b/contrib/libg++/libstdc++/stl/README deleted file mode 100644 index fad26dec0c0d3..0000000000000 --- a/contrib/libg++/libstdc++/stl/README +++ /dev/null @@ -1,86 +0,0 @@ -This directory contains Hewlett-Packard's implementation of -the C++ Standard Template Library. -It is the October 31, 1995 version. -It has been extensively modified so it can be compiled by g++. -(Version 2.6.1 or newer is recommended.) -Some of these hacks are pretty ugly, but are needed to work around -bugs in g++ (which we are working on). -Thanks to Carsten Bormann <cabo@informatik.uni-bremen.de> for -coming up with many of these work-arounds. However, I have -come up with alternate (possibly inferior!) work-arounds in some cases. - -Note that this is based on a pre-Draft Standard for C++. -Things are likely to change. For example, the header file names -are very likely to change. The Allocator interface will change. Etc, etc. -CYGNUS MAKES NO COMMITTMENT (yet) TO SUPPORT BACKWARD COMPATIBILITY FOR STL. - -For examples if things that should work, look in the ../tests directory. - -DOCUMENTATION: -See http://www.cs.rpi.edu/~musser/stl.html on the World-Wide Web, -or anonymous ftp to butler.hpl.hp.com, directory stl, file sharfile.Z. - - --Per Bothner -Cygnus Support bothner@cygnus.com - ------------ -Here is Carsten Bormann's notes on his changes: - -This is a set of seriously bletcherous hacks to HP's wonderful STL -library. The objective is to hammer STL through GCC 2.6.1 (2.6.0 -seems to work, too, until you run into one of its bugs) so that us -academic types can play with STL, not to make STL better in any way. - -Many of these changes make the library much less efficient. All -changes (except vector<bool> -- see below) are due to bugs (or -non-features) in GCC, not due to any problems in STL. Do not judge -the performance of STL (code space, data space, compile time -complexity, run time complexity) from these hacks -- they will be much -better when GCC implements more of Standard C++. May the authors of -STL forgive me. - -The class templates generally have been hacked in the following ways: - -1) Static data members have been eliminated, generally by making them -non-static members or member functions (both of which generally -seriously impairs performance -- e.g., each rb_tree iterator now -carries a copy of NIL since there is no other place to put it). The -template list<> has suffered most. - -Allocators are still static members, since I changed defalloc.h to -have static members only. (This makes allocators less useful, but -still useable.) (Note that a static member without data need not be -initialized.) - -2) For member functions defined outside the class template, parameters -of type tmpl<T>::something have been changed. In some cases, a class -derived from the type has been used; in some cases the function simply -has been made inline (again causing code bloat). - -3) A number of function templates in iterator.h have been declared -again for derived classes defined by templates, usually by making them -friend functions and using the name injection feature of GCC. I don't -understand the relevant sections of the WP, so I don't know if this -hack will cease to work in more conforming versions of GCC or become -unneccessary or simply STL won't work with standard C++. Some of -the necessary friends may still be missing... - -defalloc.h has lost much of its functionality: see above. - -bool.h has been made ineffective, since GCC supports bool. - -Finally, bit_vector has been changed into a proper specialization of -vector<bool>. -[Not in this libstdc++ release. -PB] - -demo.cc and Makefile build a small demo program for a number of -features of STL. This is not a test suite, so I certainly have not -found all my mistakes (could anyone in possession of such a test suite -please run it over these hacks?). Send bug reports (that follow GNU -bug reporting conventions) to - - cabo@informatik.uni-bremen.de - -Note that I generally do not have time to answer questions about STL. - -Carsten Bormann diff --git a/contrib/libg++/libstdc++/stl/algo.h b/contrib/libg++/libstdc++/stl/algo.h deleted file mode 100644 index e038d715a2503..0000000000000 --- a/contrib/libg++/libstdc++/stl/algo.h +++ /dev/null @@ -1,2386 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef ALGO_H -#define ALGO_H - -#include <stdlib.h> -#ifndef __GNUG__ -#include <bool.h> -#endif -#include <pair.h> -#include <iterator.h> -#include <algobase.h> -#include <heap.h> -#include <tempbuf.h> - -template <class T> -inline const T& __median(const T& a, const T& b, const T& c) { - if (a < b) - if (b < c) - return b; - else if (a < c) - return c; - else - return a; - else if (a < c) - return a; - else if (b < c) - return c; - else - return b; -} - -template <class T, class Compare> -inline const T& __median(const T& a, const T& b, const T& c, Compare comp) { - if (comp(a, b)) - if (comp(b, c)) - return b; - else if (comp(a, c)) - return c; - else - return a; - else if (comp(a, c)) - return a; - else if (comp(b, c)) - return c; - else - return b; -} - -template <class InputIterator, class Function> -Function for_each(InputIterator first, InputIterator last, Function f) { - while (first != last) f(*first++); - return f; -} - -template <class InputIterator, class T> -InputIterator find(InputIterator first, InputIterator last, const T& value) { - while (first != last && *first != value) ++first; - return first; -} - -template <class InputIterator, class Predicate> -InputIterator find_if(InputIterator first, InputIterator last, - Predicate pred) { - while (first != last && !pred(*first)) ++first; - return first; -} - -template <class ForwardIterator> -ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last) { - if (first == last) return last; - ForwardIterator next = first; - while(++next != last) { - if (*first == *next) return first; - first = next; - } - return last; -} - -template <class ForwardIterator, class BinaryPredicate> -ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, - BinaryPredicate binary_pred) { - if (first == last) return last; - ForwardIterator next = first; - while(++next != last) { - if (binary_pred(*first, *next)) return first; - first = next; - } - return last; -} - -template <class InputIterator, class T, class Size> -void count(InputIterator first, InputIterator last, const T& value, - Size& n) { - while (first != last) - if (*first++ == value) ++n; -} - -template <class InputIterator, class Predicate, class Size> -void count_if(InputIterator first, InputIterator last, Predicate pred, - Size& n) { - while (first != last) - if (pred(*first++)) ++n; -} - -template <class ForwardIterator1, class ForwardIterator2, class Distance1, - class Distance2> -ForwardIterator1 __search(ForwardIterator1 first1, ForwardIterator1 last1, - ForwardIterator2 first2, ForwardIterator2 last2, - Distance1*, Distance2*) { - Distance1 d1 = 0; - distance(first1, last1, d1); - Distance2 d2 = 0; - distance(first2, last2, d2); - - if (d1 < d2) return last1; - - ForwardIterator1 current1 = first1; - ForwardIterator2 current2 = first2; - - while (current2 != last2) - if (*current1++ != *current2++) - if (d1-- == d2) - return last1; - else { - current1 = ++first1; - current2 = first2; - } - return (current2 == last2) ? first1 : last1; -} - -template <class ForwardIterator1, class ForwardIterator2> -inline ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, - ForwardIterator2 first2, ForwardIterator2 last2) -{ - return __search(first1, last1, first2, last2, distance_type(first1), - distance_type(first2)); -} - -template <class ForwardIterator1, class ForwardIterator2, - class BinaryPredicate, class Distance1, class Distance2> -ForwardIterator1 __search(ForwardIterator1 first1, ForwardIterator1 last1, - ForwardIterator2 first2, ForwardIterator2 last2, - BinaryPredicate binary_pred, Distance1*, Distance2*) { - Distance1 d1 = 0; - distance(first1, last1, d1); - Distance2 d2 = 0; - distance(first2, last2, d2); - - if (d1 < d2) return last1; - - ForwardIterator1 current1 = first1; - ForwardIterator2 current2 = first2; - - while (current2 != last2) - if (!binary_pred(*current1++, *current2++)) - if (d1-- == d2) - return last1; - else { - current1 = ++first1; - current2 = first2; - } - return (current2 == last2) ? first1 : last1; -} - -template <class ForwardIterator1, class ForwardIterator2, - class BinaryPredicate> -inline ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, - ForwardIterator2 first2, ForwardIterator2 last2, - BinaryPredicate binary_pred) { - return __search(first1, last1, first2, last2, binary_pred, - distance_type(first1), distance_type(first2)); -} - -template <class ForwardIterator1, class ForwardIterator2> -ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, - ForwardIterator2 first2) { - while (first1 != last1) iter_swap(first1++, first2++); - return first2; -} - -template <class InputIterator, class OutputIterator, class UnaryOperation> -OutputIterator transform(InputIterator first, InputIterator last, - OutputIterator result, UnaryOperation op) { - while (first != last) *result++ = op(*first++); - return result; -} - -template <class InputIterator1, class InputIterator2, class OutputIterator, - class BinaryOperation> -OutputIterator transform(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, OutputIterator result, - BinaryOperation binary_op) { - while (first1 != last1) *result++ = binary_op(*first1++, *first2++); - return result; -} - -template <class ForwardIterator, class T> -void replace(ForwardIterator first, ForwardIterator last, const T& old_value, - const T& new_value) { - while (first != last) { - if (*first == old_value) *first = new_value; - ++first; - } -} - -template <class ForwardIterator, class Predicate, class T> -void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, - const T& new_value) { - while (first != last) { - if (pred(*first)) *first = new_value; - ++first; - } -} - -template <class InputIterator, class OutputIterator, class T> -OutputIterator replace_copy(InputIterator first, InputIterator last, - OutputIterator result, const T& old_value, - const T& new_value) { - while (first != last) { - *result++ = *first == old_value ? new_value : *first; - ++first; - } - return result; -} - -template <class Iterator, class OutputIterator, class Predicate, class T> -OutputIterator replace_copy_if(Iterator first, Iterator last, - OutputIterator result, Predicate pred, - const T& new_value) { - while (first != last) { - *result++ = pred(*first) ? new_value : *first; - ++first; - } - return result; -} - -template <class ForwardIterator, class Generator> -void generate(ForwardIterator first, ForwardIterator last, Generator gen) { - while (first != last) *first++ = gen(); -} - -template <class OutputIterator, class Size, class Generator> -OutputIterator generate_n(OutputIterator first, Size n, Generator gen) { - while (n-- > 0) *first++ = gen(); - return first; -} - -template <class InputIterator, class OutputIterator, class T> -OutputIterator remove_copy(InputIterator first, InputIterator last, - OutputIterator result, const T& value) { - while (first != last) { - if (*first != value) *result++ = *first; - ++first; - } - return result; -} - -template <class InputIterator, class OutputIterator, class Predicate> -OutputIterator remove_copy_if(InputIterator first, InputIterator last, - OutputIterator result, Predicate pred) { - while (first != last) { - if (!pred(*first)) *result++ = *first; - ++first; - } - return result; -} - -template <class ForwardIterator, class T> -ForwardIterator remove(ForwardIterator first, ForwardIterator last, - const T& value) { - first = find(first, last, value); - ForwardIterator next = first; - return first == last ? first : remove_copy(++next, last, first, value); -} - -template <class ForwardIterator, class Predicate> -ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, - Predicate pred) { - first = find_if(first, last, pred); - ForwardIterator next = first; - return first == last ? first : remove_copy_if(++next, last, first, pred); -} - -template <class InputIterator, class ForwardIterator> -ForwardIterator __unique_copy(InputIterator first, InputIterator last, - ForwardIterator result, forward_iterator_tag) { - *result = *first; - while (++first != last) - if (*result != *first) *++result = *first; - return ++result; -} - -template <class InputIterator, class BidirectionalIterator> -inline BidirectionalIterator __unique_copy(InputIterator first, - InputIterator last, - BidirectionalIterator result, - bidirectional_iterator_tag) { - return __unique_copy(first, last, result, forward_iterator_tag()); -} - -template <class InputIterator, class RandomAccessIterator> -inline RandomAccessIterator __unique_copy(InputIterator first, - InputIterator last, - RandomAccessIterator result, - random_access_iterator_tag) { - return __unique_copy(first, last, result, forward_iterator_tag()); -} - -template <class InputIterator, class OutputIterator, class T> -OutputIterator __unique_copy(InputIterator first, InputIterator last, - OutputIterator result, T*) { - T value = *first; - *result = value; - while (++first != last) - if (value != *first) { - value = *first; - *++result = value; - } - return ++result; -} - -template <class InputIterator, class OutputIterator> -inline OutputIterator __unique_copy(InputIterator first, InputIterator last, - OutputIterator result, - output_iterator_tag) { - return __unique_copy(first, last, result, value_type(first)); -} - -template <class InputIterator, class OutputIterator> -inline OutputIterator unique_copy(InputIterator first, InputIterator last, - OutputIterator result) { - if (first == last) return result; - return __unique_copy(first, last, result, iterator_category(result)); -} -template <class InputIterator, class ForwardIterator, class BinaryPredicate> -ForwardIterator __unique_copy(InputIterator first, InputIterator last, - ForwardIterator result, - BinaryPredicate binary_pred, - forward_iterator_tag) { - *result = *first; - while (++first != last) - if (!binary_pred(*result, *first)) *++result = *first; - return ++result; -} - -template <class InputIterator, class BidirectionalIterator, - class BinaryPredicate> -inline BidirectionalIterator __unique_copy(InputIterator first, - InputIterator last, - BidirectionalIterator result, - BinaryPredicate binary_pred, - bidirectional_iterator_tag) { - return __unique_copy(first, last, result, binary_pred, - forward_iterator_tag()); -} - -template <class InputIterator, class RandomAccessIterator, - class BinaryPredicate> -inline RandomAccessIterator __unique_copy(InputIterator first, - InputIterator last, - RandomAccessIterator result, - BinaryPredicate binary_pred, - random_access_iterator_tag) { - return __unique_copy(first, last, result, binary_pred, - forward_iterator_tag()); -} - -template <class InputIterator, class OutputIterator, class BinaryPredicate, - class T> -OutputIterator __unique_copy(InputIterator first, InputIterator last, - OutputIterator result, - BinaryPredicate binary_pred, T*) { - T value = *first; - *result = value; - while (++first != last) - if (!binary_pred(value, *first)) { - value = *first; - *++result = value; - } - return ++result; -} - -template <class InputIterator, class OutputIterator, class BinaryPredicate> -inline OutputIterator __unique_copy(InputIterator first, InputIterator last, - OutputIterator result, - BinaryPredicate binary_pred, - output_iterator_tag) { - return __unique_copy(first, last, result, binary_pred, value_type(first)); -} - -template <class InputIterator, class OutputIterator, class BinaryPredicate> -inline OutputIterator unique_copy(InputIterator first, InputIterator last, - OutputIterator result, - BinaryPredicate binary_pred) { - if (first == last) return result; - return __unique_copy(first, last, result, binary_pred, - iterator_category(result)); -} - -template <class ForwardIterator> -ForwardIterator unique(ForwardIterator first, ForwardIterator last) { - first = adjacent_find(first, last); - return unique_copy(first, last, first); -} - -template <class ForwardIterator, class BinaryPredicate> -ForwardIterator unique(ForwardIterator first, ForwardIterator last, - BinaryPredicate binary_pred) { - first = adjacent_find(first, last, binary_pred); - return unique_copy(first, last, first, binary_pred); -} - -template <class BidirectionalIterator> -void __reverse(BidirectionalIterator first, BidirectionalIterator last, - bidirectional_iterator_tag) { - while (true) - if (first == last || first == --last) - return; - else - iter_swap(first++, last); -} - -template <class RandomAccessIterator> -void __reverse(RandomAccessIterator first, RandomAccessIterator last, - random_access_iterator_tag) { - while (first < last) iter_swap(first++, --last); -} - -template <class BidirectionalIterator> -inline void reverse(BidirectionalIterator first, BidirectionalIterator last) { - __reverse(first, last, iterator_category(first)); -} - -template <class BidirectionalIterator, class OutputIterator> -OutputIterator reverse_copy(BidirectionalIterator first, - BidirectionalIterator last, - OutputIterator result) { - while (first != last) *result++ = *--last; - return result; -} - -template <class ForwardIterator, class Distance> -void __rotate(ForwardIterator first, ForwardIterator middle, - ForwardIterator last, Distance*, forward_iterator_tag) { - for (ForwardIterator i = middle; ;) { - iter_swap(first++, i++); - if (first == middle) { - if (i == last) return; - middle = i; - } else if (i == last) - i = middle; - } -} - -template <class BidirectionalIterator, class Distance> -void __rotate(BidirectionalIterator first, BidirectionalIterator middle, - BidirectionalIterator last, Distance*, - bidirectional_iterator_tag) { - reverse(first, middle); - reverse(middle, last); - reverse(first, last); -} - -template <class EuclideanRingElement> -EuclideanRingElement __gcd(EuclideanRingElement m, EuclideanRingElement n) -{ - while (n != 0) { - EuclideanRingElement t = m % n; - m = n; - n = t; - } - return m; -} - -template <class RandomAccessIterator, class Distance, class T> -void __rotate_cycle(RandomAccessIterator first, RandomAccessIterator last, - RandomAccessIterator initial, Distance shift, T*) { - T value = *initial; - RandomAccessIterator ptr1 = initial; - RandomAccessIterator ptr2 = ptr1 + shift; - while (ptr2 != initial) { - *ptr1 = *ptr2; - ptr1 = ptr2; - if (last - ptr2 > shift) - ptr2 += shift; - else - ptr2 = first + (shift - (last - ptr2)); - } - *ptr1 = value; -} - -template <class RandomAccessIterator, class Distance> -void __rotate(RandomAccessIterator first, RandomAccessIterator middle, - RandomAccessIterator last, Distance*, - random_access_iterator_tag) { - Distance n = __gcd(last - first, middle - first); - while (n--) - __rotate_cycle(first, last, first + n, middle - first, - value_type(first)); -} - -template <class ForwardIterator> -inline void rotate(ForwardIterator first, ForwardIterator middle, - ForwardIterator last) { - if (first == middle || middle == last) return; - __rotate(first, middle, last, distance_type(first), - iterator_category(first)); -} - -template <class ForwardIterator, class OutputIterator> -OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, - ForwardIterator last, OutputIterator result) { - return copy(first, middle, copy(middle, last, result)); -} - -unsigned long __long_random(unsigned long); - -template <class RandomAccessIterator, class Distance> -void __random_shuffle(RandomAccessIterator first, RandomAccessIterator last, - Distance*) { - if (first == last) return; - for (RandomAccessIterator i = first + 1; i != last; ++i) - iter_swap(i, first + Distance(__long_random((i - first) + 1))); -} - -template <class RandomAccessIterator> -inline void random_shuffle(RandomAccessIterator first, - RandomAccessIterator last) { - __random_shuffle(first, last, distance_type(first)); -} - -template <class RandomAccessIterator, class RandomNumberGenerator> -void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, - RandomNumberGenerator& __rand) { - if (first == last) return; - for (RandomAccessIterator i = first + 1; i != last; ++i) - iter_swap(i, first + __rand((i - first) + 1)); -} - -template <class BidirectionalIterator, class Predicate> -BidirectionalIterator partition(BidirectionalIterator first, - BidirectionalIterator last, Predicate pred) { - while (true) { - while (true) - if (first == last) - return first; - else if (pred(*first)) - ++first; - else - break; - --last; - while (true) - if (first == last) - return first; - else if (!pred(*last)) - --last; - else - break; - iter_swap(first, last); - ++first; - } -} - -template <class ForwardIterator, class Predicate, class Distance> -ForwardIterator __inplace_stable_partition(ForwardIterator first, - ForwardIterator last, - Predicate pred, Distance len) { - if (len == 1) return pred(*first) ? last : first; - ForwardIterator middle = first; - advance(middle, len / 2); - ForwardIterator - first_cut = __inplace_stable_partition(first, middle, pred, len / 2); - ForwardIterator - second_cut = __inplace_stable_partition(middle, last, pred, - len - len / 2); - rotate(first_cut, middle, second_cut); - len = 0; - distance(middle, second_cut, len); - advance(first_cut, len); - return first_cut; -} - -template <class ForwardIterator, class Pointer, class Predicate, - class Distance, class T> -ForwardIterator __stable_partition_adaptive(ForwardIterator first, - ForwardIterator last, - Predicate pred, Distance len, - Pointer buffer, - Distance buffer_size, - Distance& fill_pointer, T*) { - if (len <= buffer_size) { - len = 0; - ForwardIterator result1 = first; - Pointer result2 = buffer; - while (first != last && len < fill_pointer) - if (pred(*first)) - *result1++ = *first++; - else { - *result2++ = *first++; - ++len; - } - if (first != last) { - raw_storage_iterator<Pointer, T> result3 = result2; - while (first != last) - if (pred(*first)) - *result1++ = *first++; - else { - *result3++ = *first++; - ++len; - } - fill_pointer = len; - } - copy(buffer, buffer + len, result1); - return result1; - } - ForwardIterator middle = first; - advance(middle, len / 2); - ForwardIterator first_cut = __stable_partition_adaptive - (first, middle, pred, len / 2, buffer, buffer_size, fill_pointer, - (T*)0); - ForwardIterator second_cut = __stable_partition_adaptive - (middle, last, pred, len - len / 2, buffer, buffer_size, - fill_pointer, (T*)0); - rotate(first_cut, middle, second_cut); - len = 0; - distance(middle, second_cut, len); - advance(first_cut, len); - return first_cut; -} - -template <class ForwardIterator, class Predicate, class Pointer, - class Distance> -ForwardIterator __stable_partition(ForwardIterator first, ForwardIterator last, - Predicate pred, Distance len, - pair<Pointer, Distance> p) { - if (p.first == 0) - return __inplace_stable_partition(first, last, pred, len); - Distance fill_pointer = 0; - ForwardIterator result = - __stable_partition_adaptive(first, last, pred, len, p.first, p.second, - fill_pointer, value_type(first)); - destroy(p.first, p.first + fill_pointer); - return_temporary_buffer(p.first); - return result; -} - -template <class ForwardIterator, class Predicate, class Distance> -inline ForwardIterator __stable_partition_aux(ForwardIterator first, - ForwardIterator last, - Predicate pred, Distance*) { - Distance len = 0; - distance(first, last, len); - return __stable_partition(first, last, pred, len, - get_temporary_buffer(len, value_type(first))); -} - -template <class ForwardIterator, class Predicate> -inline ForwardIterator stable_partition(ForwardIterator first, - ForwardIterator last, - Predicate pred) { - return __stable_partition_aux(first, last, pred, distance_type(first)); -} - -template <class RandomAccessIterator, class T> -RandomAccessIterator __unguarded_partition(RandomAccessIterator first, - RandomAccessIterator last, - T pivot) { - while (1) { - while (*first < pivot) ++first; - --last; - while (pivot < *last) --last; - if (!(first < last)) return first; - iter_swap(first, last); - ++first; - } -} - -template <class RandomAccessIterator, class T, class Compare> -RandomAccessIterator __unguarded_partition(RandomAccessIterator first, - RandomAccessIterator last, - T pivot, Compare comp) { - while (1) { - while (comp(*first, pivot)) ++first; - --last; - while (comp(pivot, *last)) --last; - if (!(first < last)) return first; - iter_swap(first, last); - ++first; - } -} - -const int __stl_threshold = 16; - -template <class RandomAccessIterator, class T> -void __quick_sort_loop_aux(RandomAccessIterator first, - RandomAccessIterator last, T*) { - while (last - first > __stl_threshold) { - RandomAccessIterator cut = __unguarded_partition - (first, last, T(__median(*first, *(first + (last - first)/2), - *(last - 1)))); - if (cut - first >= last - cut) { - __quick_sort_loop(cut, last); - last = cut; - } else { - __quick_sort_loop(first, cut); - first = cut; - } - } -} - -template <class RandomAccessIterator> -inline void __quick_sort_loop(RandomAccessIterator first, - RandomAccessIterator last) { - __quick_sort_loop_aux(first, last, value_type(first)); -} - -template <class RandomAccessIterator, class T, class Compare> -void __quick_sort_loop_aux(RandomAccessIterator first, - RandomAccessIterator last, T*, Compare comp) { - while (last - first > __stl_threshold) { - RandomAccessIterator cut = __unguarded_partition - (first, last, T(__median(*first, *(first + (last - first)/2), - *(last - 1), comp)), comp); - if (cut - first >= last - cut) { - __quick_sort_loop(cut, last, comp); - last = cut; - } else { - __quick_sort_loop(first, cut, comp); - first = cut; - } - } -} - -template <class RandomAccessIterator, class Compare> -inline void __quick_sort_loop(RandomAccessIterator first, - RandomAccessIterator last, Compare comp) { - __quick_sort_loop_aux(first, last, value_type(first), comp); -} - -template <class RandomAccessIterator, class T> -void __unguarded_linear_insert(RandomAccessIterator last, T value) { - RandomAccessIterator next = last; - --next; - while (value < *next) { - *last = *next; - last = next--; - } - *last = value; -} - -template <class RandomAccessIterator, class T, class Compare> -void __unguarded_linear_insert(RandomAccessIterator last, T value, - Compare comp) { - RandomAccessIterator next = last; - --next; - while (comp(value , *next)) { - *last = *next; - last = next--; - } - *last = value; -} - -template <class RandomAccessIterator, class T> -inline void __linear_insert(RandomAccessIterator first, - RandomAccessIterator last, T*) { - T value = *last; - if (value < *first) { - copy_backward(first, last, last + 1); - *first = value; - } else - __unguarded_linear_insert(last, value); -} - -template <class RandomAccessIterator, class T, class Compare> -inline void __linear_insert(RandomAccessIterator first, - RandomAccessIterator last, T*, Compare comp) { - T value = *last; - if (comp(value, *first)) { - copy_backward(first, last, last + 1); - *first = value; - } else - __unguarded_linear_insert(last, value, comp); -} - -template <class RandomAccessIterator> -void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last) { - if (first == last) return; - for (RandomAccessIterator i = first + 1; i != last; ++i) - __linear_insert(first, i, value_type(first)); -} - -template <class RandomAccessIterator, class Compare> -void __insertion_sort(RandomAccessIterator first, - RandomAccessIterator last, Compare comp) { - if (first == last) return; - for (RandomAccessIterator i = first + 1; i != last; ++i) - __linear_insert(first, i, value_type(first), comp); -} - -template <class RandomAccessIterator, class T> -void __unguarded_insertion_sort_aux(RandomAccessIterator first, - RandomAccessIterator last, T*) { - for (RandomAccessIterator i = first; i != last; ++i) - __unguarded_linear_insert(i, T(*i)); -} - -template <class RandomAccessIterator> -inline void __unguarded_insertion_sort(RandomAccessIterator first, - RandomAccessIterator last) { - __unguarded_insertion_sort_aux(first, last, value_type(first)); -} - -template <class RandomAccessIterator, class T, class Compare> -void __unguarded_insertion_sort_aux(RandomAccessIterator first, - RandomAccessIterator last, - T*, Compare comp) { - for (RandomAccessIterator i = first; i != last; ++i) - __unguarded_linear_insert(i, T(*i), comp); -} - -template <class RandomAccessIterator, class Compare> -inline void __unguarded_insertion_sort(RandomAccessIterator first, - RandomAccessIterator last, - Compare comp) { - __unguarded_insertion_sort_aux(first, last, value_type(first), comp); -} - -template <class RandomAccessIterator> -void __final_insertion_sort(RandomAccessIterator first, - RandomAccessIterator last) { - if (last - first > __stl_threshold) { - __insertion_sort(first, first + __stl_threshold); - __unguarded_insertion_sort(first + __stl_threshold, last); - } else - __insertion_sort(first, last); -} - -template <class RandomAccessIterator, class Compare> -void __final_insertion_sort(RandomAccessIterator first, - RandomAccessIterator last, Compare comp) { - if (last - first > __stl_threshold) { - __insertion_sort(first, first + __stl_threshold, comp); - __unguarded_insertion_sort(first + __stl_threshold, last, comp); - } else - __insertion_sort(first, last, comp); -} - -template <class RandomAccessIterator> -void sort(RandomAccessIterator first, RandomAccessIterator last) { - __quick_sort_loop(first, last); - __final_insertion_sort(first, last); -} - -template <class RandomAccessIterator, class Compare> -void sort(RandomAccessIterator first, RandomAccessIterator last, - Compare comp) { - __quick_sort_loop(first, last, comp); - __final_insertion_sort(first, last, comp); -} - -template <class RandomAccessIterator> -void __inplace_stable_sort(RandomAccessIterator first, - RandomAccessIterator last) { - if (last - first < 15) { - __insertion_sort(first, last); - return; - } - RandomAccessIterator middle = first + (last - first) / 2; - __inplace_stable_sort(first, middle); - __inplace_stable_sort(middle, last); - __merge_without_buffer(first, middle, last, middle - first, last - middle); -} - -template <class RandomAccessIterator, class Compare> -void __inplace_stable_sort(RandomAccessIterator first, - RandomAccessIterator last, Compare comp) { - if (last - first < 15) { - __insertion_sort(first, last, comp); - return; - } - RandomAccessIterator middle = first + (last - first) / 2; - __inplace_stable_sort(first, middle, comp); - __inplace_stable_sort(middle, last, comp); - __merge_without_buffer(first, middle, last, middle - first, - last - middle, comp); -} - -template <class RandomAccessIterator1, class RandomAccessIterator2, - class Distance> -void __merge_sort_loop(RandomAccessIterator1 first, - RandomAccessIterator1 last, - RandomAccessIterator2 result, Distance step_size) { - Distance two_step = 2 * step_size; - - while (last - first >= two_step) { - result = merge(first, first + step_size, - first + step_size, first + two_step, result); - first += two_step; - } - step_size = min(Distance(last - first), step_size); - - merge(first, first + step_size, first + step_size, last, result); -} - -template <class RandomAccessIterator1, class RandomAccessIterator2, - class Distance, class Compare> -void __merge_sort_loop(RandomAccessIterator1 first, - RandomAccessIterator1 last, - RandomAccessIterator2 result, Distance step_size, - Compare comp) { - Distance two_step = 2 * step_size; - - while (last - first >= two_step) { - result = merge(first, first + step_size, - first + step_size, first + two_step, result, comp); - first += two_step; - } - step_size = min(Distance(last - first), step_size); - - merge(first, first + step_size, first + step_size, last, result, comp); -} - -const int __stl_chunk_size = 7; - -template <class RandomAccessIterator, class Distance> -void __chunk_insertion_sort(RandomAccessIterator first, - RandomAccessIterator last, Distance chunk_size) { - while (last - first >= chunk_size) { - __insertion_sort(first, first + chunk_size); - first += chunk_size; - } - __insertion_sort(first, last); -} - -template <class RandomAccessIterator, class Distance, class Compare> -void __chunk_insertion_sort(RandomAccessIterator first, - RandomAccessIterator last, - Distance chunk_size, Compare comp) { - while (last - first >= chunk_size) { - __insertion_sort(first, first + chunk_size, comp); - first += chunk_size; - } - __insertion_sort(first, last, comp); -} - -template <class RandomAccessIterator, class Pointer, class Distance, class T> -void __merge_sort_with_buffer(RandomAccessIterator first, - RandomAccessIterator last, - Pointer buffer, Distance*, T*) { - Distance len = last - first; - Pointer buffer_last = buffer + len; - - Distance step_size = __stl_chunk_size; - __chunk_insertion_sort(first, last, step_size); - - while (step_size < len) { - __merge_sort_loop(first, last, buffer, step_size); - step_size *= 2; - __merge_sort_loop(buffer, buffer_last, first, step_size); - step_size *= 2; - } -} - -template <class RandomAccessIterator, class Pointer, class Distance, class T, - class Compare> -void __merge_sort_with_buffer(RandomAccessIterator first, - RandomAccessIterator last, Pointer buffer, - Distance*, T*, Compare comp) { - Distance len = last - first; - Pointer buffer_last = buffer + len; - - Distance step_size = __stl_chunk_size; - __chunk_insertion_sort(first, last, step_size, comp); - - while (step_size < len) { - __merge_sort_loop(first, last, buffer, step_size, comp); - step_size *= 2; - __merge_sort_loop(buffer, buffer_last, first, step_size, comp); - step_size *= 2; - } -} - -template <class RandomAccessIterator, class Pointer, class Distance, class T> -void __stable_sort_adaptive(RandomAccessIterator first, - RandomAccessIterator last, Pointer buffer, - Distance buffer_size, T*) { - Distance len = (last - first + 1) / 2; - RandomAccessIterator middle = first + len; - if (len > buffer_size) { - __stable_sort_adaptive(first, middle, buffer, buffer_size, (T*)0); - __stable_sort_adaptive(middle, last, buffer, buffer_size, (T*)0); - } else { - __merge_sort_with_buffer(first, middle, buffer, (Distance*)0, (T*)0); - __merge_sort_with_buffer(middle, last, buffer, (Distance*)0, (T*)0); - } - __merge_adaptive(first, middle, last, Distance(middle - first), - Distance(last - middle), buffer, buffer_size, (T*)0); -} - -template <class RandomAccessIterator, class Pointer, class Distance, class T, - class Compare> -void __stable_sort_adaptive(RandomAccessIterator first, - RandomAccessIterator last, Pointer buffer, - Distance buffer_size, T*, Compare comp) { - Distance len = (last - first + 1) / 2; - RandomAccessIterator middle = first + len; - if (len > buffer_size) { - __stable_sort_adaptive(first, middle, buffer, buffer_size, (T*)0, comp); - __stable_sort_adaptive(middle, last, buffer, buffer_size, (T*)0, comp); - } else { - __merge_sort_with_buffer(first, middle, buffer, (Distance*)0, (T*)0, - comp); - __merge_sort_with_buffer(middle, last, buffer, (Distance*)0, (T*)0, - comp); - } - __merge_adaptive(first, middle, last, Distance(middle - first), - Distance(last - middle), buffer, buffer_size, (T*)0, comp); -} - -template <class RandomAccessIterator, class Pointer, class Distance, class T> -inline void __stable_sort(RandomAccessIterator first, - RandomAccessIterator last, - pair<Pointer, Distance> p, T*) { - if (p.first == 0) { - __inplace_stable_sort(first, last); - return; - } - Distance len = min(p.second, last - first); - copy(first, first + len, raw_storage_iterator<Pointer, T>(p.first)); - __stable_sort_adaptive(first, last, p.first, p.second, (T*)0); - destroy(p.first, p.first + len); - return_temporary_buffer(p.first); -} - -template <class RandomAccessIterator, class Pointer, class Distance, class T, - class Compare> -inline void __stable_sort(RandomAccessIterator first, - RandomAccessIterator last, - pair<Pointer, Distance> p, T*, Compare comp) { - if (p.first == 0) { - __inplace_stable_sort(first, last, comp); - return; - } - Distance len = min(p.second, last - first); - copy(first, first + len, raw_storage_iterator<Pointer, T>(p.first)); - __stable_sort_adaptive(first, last, p.first, p.second, (T*)0, comp); - destroy(p.first, p.first + len); - return_temporary_buffer(p.first); -} - -template <class RandomAccessIterator, class T, class Distance> -inline void __stable_sort_aux(RandomAccessIterator first, - RandomAccessIterator last, T*, Distance*) { - __stable_sort(first, last, get_temporary_buffer(Distance(last - first), - (T*)0), (T*)0); -} - -template <class RandomAccessIterator, class T, class Distance, class Compare> -inline void __stable_sort_aux(RandomAccessIterator first, - RandomAccessIterator last, T*, Distance*, - Compare comp) { - __stable_sort(first, last, get_temporary_buffer(Distance(last - first), - (T*)0), (T*)0, comp); -} - -template <class RandomAccessIterator> -inline void stable_sort(RandomAccessIterator first, - RandomAccessIterator last) { - __stable_sort_aux(first, last, value_type(first), distance_type(first)); -} - -template <class RandomAccessIterator, class Compare> -inline void stable_sort(RandomAccessIterator first, - RandomAccessIterator last, Compare comp) { - __stable_sort_aux(first, last, value_type(first), distance_type(first), - comp); -} - -template <class RandomAccessIterator, class T> -void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle, - RandomAccessIterator last, T*) { - make_heap(first, middle); - for (RandomAccessIterator i = middle; i < last; ++i) - if (*i < *first) - __pop_heap(first, middle, i, T(*i), distance_type(first)); - sort_heap(first, middle); -} - -template <class RandomAccessIterator> -inline void partial_sort(RandomAccessIterator first, - RandomAccessIterator middle, - RandomAccessIterator last) { - __partial_sort(first, middle, last, value_type(first)); -} - -template <class RandomAccessIterator, class T, class Compare> -void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle, - RandomAccessIterator last, T*, Compare comp) { - make_heap(first, middle, comp); - for (RandomAccessIterator i = middle; i < last; ++i) - if (comp(*i, *first)) - __pop_heap(first, middle, i, T(*i), comp, distance_type(first)); - sort_heap(first, middle, comp); -} - -template <class RandomAccessIterator, class Compare> -inline void partial_sort(RandomAccessIterator first, - RandomAccessIterator middle, - RandomAccessIterator last, Compare comp) { - __partial_sort(first, middle, last, value_type(first), comp); -} - -template <class InputIterator, class RandomAccessIterator, class Distance, - class T> -RandomAccessIterator __partial_sort_copy(InputIterator first, - InputIterator last, - RandomAccessIterator result_first, - RandomAccessIterator result_last, - Distance*, T*) { - if (result_first == result_last) return result_last; - RandomAccessIterator result_real_last = result_first; - while(first != last && result_real_last != result_last) - *result_real_last++ = *first++; - make_heap(result_first, result_real_last); - while (first != last) { - if (*first < *result_first) - __adjust_heap(result_first, Distance(0), - Distance(result_real_last - result_first), T(*first)); - ++first; - } - sort_heap(result_first, result_real_last); - return result_real_last; -} - -template <class InputIterator, class RandomAccessIterator> -inline RandomAccessIterator -partial_sort_copy(InputIterator first, InputIterator last, - RandomAccessIterator result_first, - RandomAccessIterator result_last) { - return __partial_sort_copy(first, last, result_first, result_last, - distance_type(result_first), value_type(first)); -} - -template <class InputIterator, class RandomAccessIterator, class Compare, - class Distance, class T> -RandomAccessIterator __partial_sort_copy(InputIterator first, - InputIterator last, - RandomAccessIterator result_first, - RandomAccessIterator result_last, - Compare comp, Distance*, T*) { - if (result_first == result_last) return result_last; - RandomAccessIterator result_real_last = result_first; - while(first != last && result_real_last != result_last) - *result_real_last++ = *first++; - make_heap(result_first, result_real_last, comp); - while (first != last) { - if (comp(*first, *result_first)) - __adjust_heap(result_first, Distance(0), - Distance(result_real_last - result_first), T(*first), - comp); - ++first; - } - sort_heap(result_first, result_real_last, comp); - return result_real_last; -} - -template <class InputIterator, class RandomAccessIterator, class Compare> -inline RandomAccessIterator -partial_sort_copy(InputIterator first, InputIterator last, - RandomAccessIterator result_first, - RandomAccessIterator result_last, Compare comp) { - return __partial_sort_copy(first, last, result_first, result_last, comp, - distance_type(result_first), value_type(first)); -} - -template <class RandomAccessIterator, class T> -void __nth_element(RandomAccessIterator first, RandomAccessIterator nth, - RandomAccessIterator last, T*) { - while (last - first > 3) { - RandomAccessIterator cut = __unguarded_partition - (first, last, T(__median(*first, *(first + (last - first)/2), - *(last - 1)))); - if (cut <= nth) - first = cut; - else - last = cut; - } - __insertion_sort(first, last); -} - -template <class RandomAccessIterator> -inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth, - RandomAccessIterator last) { - __nth_element(first, nth, last, value_type(first)); -} - -template <class RandomAccessIterator, class T, class Compare> -void __nth_element(RandomAccessIterator first, RandomAccessIterator nth, - RandomAccessIterator last, T*, Compare comp) { - while (last - first > 3) { - RandomAccessIterator cut = __unguarded_partition - (first, last, T(__median(*first, *(first + (last - first)/2), - *(last - 1), comp)), comp); - if (cut <= nth) - first = cut; - else - last = cut; - } - __insertion_sort(first, last, comp); -} - -template <class RandomAccessIterator, class Compare> -inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth, - RandomAccessIterator last, Compare comp) { - __nth_element(first, nth, last, value_type(first), comp); -} - -template <class ForwardIterator, class T, class Distance> -ForwardIterator __lower_bound(ForwardIterator first, ForwardIterator last, - const T& value, Distance*, - forward_iterator_tag) { - Distance len = 0; - distance(first, last, len); - Distance half; - ForwardIterator middle; - - while (len > 0) { - half = len / 2; - middle = first; - advance(middle, half); - if (*middle < value) { - first = middle; - ++first; - len = len - half - 1; - } else - len = half; - } - return first; -} - -template <class ForwardIterator, class T, class Distance> -inline ForwardIterator __lower_bound(ForwardIterator first, - ForwardIterator last, - const T& value, Distance*, - bidirectional_iterator_tag) { - return __lower_bound(first, last, value, (Distance*)0, - forward_iterator_tag()); -} - -template <class RandomAccessIterator, class T, class Distance> -RandomAccessIterator __lower_bound(RandomAccessIterator first, - RandomAccessIterator last, const T& value, - Distance*, random_access_iterator_tag) { - Distance len = last - first; - Distance half; - RandomAccessIterator middle; - - while (len > 0) { - half = len / 2; - middle = first + half; - if (*middle < value) { - first = middle + 1; - len = len - half - 1; - } else - len = half; - } - return first; -} - -template <class ForwardIterator, class T> -inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, - const T& value) { - return __lower_bound(first, last, value, distance_type(first), - iterator_category(first)); -} - -template <class ForwardIterator, class T, class Compare, class Distance> -ForwardIterator __lower_bound(ForwardIterator first, ForwardIterator last, - const T& value, Compare comp, Distance*, - forward_iterator_tag) { - Distance len = 0; - distance(first, last, len); - Distance half; - ForwardIterator middle; - - while (len > 0) { - half = len / 2; - middle = first; - advance(middle, half); - if (comp(*middle, value)) { - first = middle; - ++first; - len = len - half - 1; - } else - len = half; - } - return first; -} - -template <class ForwardIterator, class T, class Compare, class Distance> -inline ForwardIterator __lower_bound(ForwardIterator first, - ForwardIterator last, - const T& value, Compare comp, Distance*, - bidirectional_iterator_tag) { - return __lower_bound(first, last, value, comp, (Distance*)0, - forward_iterator_tag()); -} - -template <class RandomAccessIterator, class T, class Compare, class Distance> -RandomAccessIterator __lower_bound(RandomAccessIterator first, - RandomAccessIterator last, - const T& value, Compare comp, Distance*, - random_access_iterator_tag) { - Distance len = last - first; - Distance half; - RandomAccessIterator middle; - - while (len > 0) { - half = len / 2; - middle = first + half; - if (comp(*middle, value)) { - first = middle + 1; - len = len - half - 1; - } else - len = half; - } - return first; -} - -template <class ForwardIterator, class T, class Compare> -inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, - const T& value, Compare comp) { - return __lower_bound(first, last, value, comp, distance_type(first), - iterator_category(first)); -} - -template <class ForwardIterator, class T, class Distance> -ForwardIterator __upper_bound(ForwardIterator first, ForwardIterator last, - const T& value, Distance*, - forward_iterator_tag) { - Distance len = 0; - distance(first, last, len); - Distance half; - ForwardIterator middle; - - while (len > 0) { - half = len / 2; - middle = first; - advance(middle, half); - if (value < *middle) - len = half; - else { - first = middle; - ++first; - len = len - half - 1; - } - } - return first; -} - -template <class ForwardIterator, class T, class Distance> -inline ForwardIterator __upper_bound(ForwardIterator first, - ForwardIterator last, - const T& value, Distance*, - bidirectional_iterator_tag) { - return __upper_bound(first, last, value, (Distance*)0, - forward_iterator_tag()); -} - -template <class RandomAccessIterator, class T, class Distance> -RandomAccessIterator __upper_bound(RandomAccessIterator first, - RandomAccessIterator last, const T& value, - Distance*, random_access_iterator_tag) { - Distance len = last - first; - Distance half; - RandomAccessIterator middle; - - while (len > 0) { - half = len / 2; - middle = first + half; - if (value < *middle) - len = half; - else { - first = middle + 1; - len = len - half - 1; - } - } - return first; -} - -template <class ForwardIterator, class T> -inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, - const T& value) { - return __upper_bound(first, last, value, distance_type(first), - iterator_category(first)); -} - -template <class ForwardIterator, class T, class Compare, class Distance> -ForwardIterator __upper_bound(ForwardIterator first, ForwardIterator last, - const T& value, Compare comp, Distance*, - forward_iterator_tag) { - Distance len = 0; - distance(first, last, len); - Distance half; - ForwardIterator middle; - - while (len > 0) { - half = len / 2; - middle = first; - advance(middle, half); - if (comp(value, *middle)) - len = half; - else { - first = middle; - ++first; - len = len - half - 1; - } - } - return first; -} - -template <class ForwardIterator, class T, class Compare, class Distance> -inline ForwardIterator __upper_bound(ForwardIterator first, - ForwardIterator last, - const T& value, Compare comp, Distance*, - bidirectional_iterator_tag) { - return __upper_bound(first, last, value, comp, (Distance*)0, - forward_iterator_tag()); -} - -template <class RandomAccessIterator, class T, class Compare, class Distance> -RandomAccessIterator __upper_bound(RandomAccessIterator first, - RandomAccessIterator last, - const T& value, Compare comp, Distance*, - random_access_iterator_tag) { - Distance len = last - first; - Distance half; - RandomAccessIterator middle; - - while (len > 0) { - half = len / 2; - middle = first + half; - if (comp(value, *middle)) - len = half; - else { - first = middle + 1; - len = len - half - 1; - } - } - return first; -} - -template <class ForwardIterator, class T, class Compare> -inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, - const T& value, Compare comp) { - return __upper_bound(first, last, value, comp, distance_type(first), - iterator_category(first)); -} - -template <class ForwardIterator, class T, class Distance> -pair<ForwardIterator, ForwardIterator> -__equal_range(ForwardIterator first, ForwardIterator last, const T& value, - Distance*, forward_iterator_tag) { - Distance len = 0; - distance(first, last, len); - Distance half; - ForwardIterator middle, left, right; - - while (len > 0) { - half = len / 2; - middle = first; - advance(middle, half); - if (*middle < value) { - first = middle; - ++first; - len = len - half - 1; - } else if (value < *middle) - len = half; - else { - left = lower_bound(first, middle, value); - advance(first, len); - right = upper_bound(++middle, first, value); - return pair<ForwardIterator, ForwardIterator>(left, right); - } - } - return pair<ForwardIterator, ForwardIterator>(first, first); -} - -template <class ForwardIterator, class T, class Distance> -inline pair<ForwardIterator, ForwardIterator> -__equal_range(ForwardIterator first, ForwardIterator last, const T& value, - Distance*, bidirectional_iterator_tag) { - return __equal_range(first, last, value, (Distance*)0, - forward_iterator_tag()); -} - -template <class RandomAccessIterator, class T, class Distance> -pair<RandomAccessIterator, RandomAccessIterator> -__equal_range(RandomAccessIterator first, RandomAccessIterator last, - const T& value, Distance*, random_access_iterator_tag) { - Distance len = last - first; - Distance half; - RandomAccessIterator middle, left, right; - - while (len > 0) { - half = len / 2; - middle = first + half; - if (*middle < value) { - first = middle + 1; - len = len - half - 1; - } else if (value < *middle) - len = half; - else { - left = lower_bound(first, middle, value); - right = upper_bound(++middle, first + len, value); - return pair<RandomAccessIterator, RandomAccessIterator>(left, - right); - } - } - return pair<RandomAccessIterator, RandomAccessIterator>(first, first); -} - -template <class ForwardIterator, class T> -inline pair<ForwardIterator, ForwardIterator> -equal_range(ForwardIterator first, ForwardIterator last, const T& value) { - return __equal_range(first, last, value, distance_type(first), - iterator_category(first)); -} - -template <class ForwardIterator, class T, class Compare, class Distance> -pair<ForwardIterator, ForwardIterator> -__equal_range(ForwardIterator first, ForwardIterator last, const T& value, - Compare comp, Distance*, forward_iterator_tag) { - Distance len = 0; - distance(first, last, len); - Distance half; - ForwardIterator middle, left, right; - - while (len > 0) { - half = len / 2; - middle = first; - advance(middle, half); - if (comp(*middle, value)) { - first = middle; - ++first; - len = len - half - 1; - } else if (comp(value, *middle)) - len = half; - else { - left = lower_bound(first, middle, value, comp); - advance(first, len); - right = upper_bound(++middle, first, value, comp); - return pair<ForwardIterator, ForwardIterator>(left, right); - } - } - return pair<ForwardIterator, ForwardIterator>(first, first); -} - -template <class ForwardIterator, class T, class Compare, class Distance> -inline pair<ForwardIterator, ForwardIterator> -__equal_range(ForwardIterator first, ForwardIterator last, const T& value, - Compare comp, Distance*, bidirectional_iterator_tag) { - return __equal_range(first, last, value, comp, (Distance*)0, - forward_iterator_tag()); -} - -template <class RandomAccessIterator, class T, class Compare, class Distance> -pair<RandomAccessIterator, RandomAccessIterator> -__equal_range(RandomAccessIterator first, RandomAccessIterator last, - const T& value, Compare comp, Distance*, - random_access_iterator_tag) { - Distance len = last - first; - Distance half; - RandomAccessIterator middle, left, right; - - while (len > 0) { - half = len / 2; - middle = first + half; - if (comp(*middle, value)) { - first = middle + 1; - len = len - half - 1; - } else if (comp(value, *middle)) - len = half; - else { - left = lower_bound(first, middle, value, comp); - right = upper_bound(++middle, first + len, value, comp); - return pair<RandomAccessIterator, RandomAccessIterator>(left, - right); - } - } - return pair<RandomAccessIterator, RandomAccessIterator>(first, first); -} - -template <class ForwardIterator, class T, class Compare> -inline pair<ForwardIterator, ForwardIterator> -equal_range(ForwardIterator first, ForwardIterator last, const T& value, - Compare comp) { - return __equal_range(first, last, value, comp, distance_type(first), - iterator_category(first)); -} - -template <class ForwardIterator, class T> -bool binary_search(ForwardIterator first, ForwardIterator last, - const T& value) { - ForwardIterator i = lower_bound(first, last, value); - return i != last && !(value < *i); -} - -template <class ForwardIterator, class T, class Compare> -bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, - Compare comp) { - ForwardIterator i = lower_bound(first, last, value, comp); - return i != last && !comp(value, *i); -} - -template <class InputIterator1, class InputIterator2, class OutputIterator> -OutputIterator merge(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, - OutputIterator result) { - while (first1 != last1 && first2 != last2) - if (*first2 < *first1) - *result++ = *first2++; - else - *result++ = *first1++; - return copy(first2, last2, copy(first1, last1, result)); -} - -template <class InputIterator1, class InputIterator2, class OutputIterator, - class Compare> -OutputIterator merge(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, - OutputIterator result, Compare comp) { - while (first1 != last1 && first2 != last2) - if (comp(*first2, *first1)) - *result++ = *first2++; - else - *result++ = *first1++; - return copy(first2, last2, copy(first1, last1, result)); -} - -template <class BidirectionalIterator, class Distance> -void __merge_without_buffer(BidirectionalIterator first, - BidirectionalIterator middle, - BidirectionalIterator last, - Distance len1, Distance len2) { - if (len1 == 0 || len2 == 0) return; - if (len1 + len2 == 2) { - if (*middle < *first) iter_swap(first, middle); - return; - } - BidirectionalIterator first_cut = first; - BidirectionalIterator second_cut = middle; - Distance len11 = 0; - Distance len22 = 0; - if (len1 > len2) { - len11 = len1 / 2; - advance(first_cut, len11); - second_cut = lower_bound(middle, last, *first_cut); - distance(middle, second_cut, len22); - } else { - len22 = len2 / 2; - advance(second_cut, len22); - first_cut = upper_bound(first, middle, *second_cut); - distance(first, first_cut, len11); - } - rotate(first_cut, middle, second_cut); - BidirectionalIterator new_middle = first_cut; - advance(new_middle, len22); - __merge_without_buffer(first, first_cut, new_middle, len11, len22); - __merge_without_buffer(new_middle, second_cut, last, len1 - len11, - len2 - len22); -} - -template <class BidirectionalIterator, class Distance, class Compare> -void __merge_without_buffer(BidirectionalIterator first, - BidirectionalIterator middle, - BidirectionalIterator last, - Distance len1, Distance len2, Compare comp) { - if (len1 == 0 || len2 == 0) return; - if (len1 + len2 == 2) { - if (comp(*middle, *first)) iter_swap(first, middle); - return; - } - BidirectionalIterator first_cut = first; - BidirectionalIterator second_cut = middle; - Distance len11 = 0; - Distance len22 = 0; - if (len1 > len2) { - len11 = len1 / 2; - advance(first_cut, len11); - second_cut = lower_bound(middle, last, *first_cut, comp); - distance(middle, second_cut, len22); - } else { - len22 = len2 / 2; - advance(second_cut, len22); - first_cut = upper_bound(first, middle, *second_cut, comp); - distance(first, first_cut, len11); - } - rotate(first_cut, middle, second_cut); - BidirectionalIterator new_middle = first_cut; - advance(new_middle, len22); - __merge_without_buffer(first, first_cut, new_middle, len11, len22, comp); - __merge_without_buffer(new_middle, second_cut, last, len1 - len11, - len2 - len22, comp); -} - - -template <class InputIterator, class OutputIterator> -OutputIterator __borland_bugfix_copy(InputIterator first, InputIterator last, - OutputIterator result) { -// this is used in __rotate_adaptive to work around some obscure Borland -// bug. It is the same as copy, but with a different (and appropriate) name. - while (first != last) *result++ = *first++; - return result; -} - -template <class BidirectionalIterator1, class BidirectionalIterator2, - class Distance> -BidirectionalIterator1 __rotate_adaptive(BidirectionalIterator1 first, - BidirectionalIterator1 middle, - BidirectionalIterator1 last, - Distance len1, Distance len2, - BidirectionalIterator2 buffer, - Distance buffer_size) { - BidirectionalIterator2 buffer_end; - if (len1 > len2 && len2 <= buffer_size) { - buffer_end = __borland_bugfix_copy(middle, last, buffer); - copy_backward(first, middle, last); - return copy(buffer, buffer_end, first); - } else if (len1 <= buffer_size) { - buffer_end = __borland_bugfix_copy(first, middle, buffer); - copy(middle, last, first); - return copy_backward(buffer, buffer_end, last); - } else { - rotate(first, middle, last); - advance(first, len2); - return first; - } -} - -template <class BidirectionalIterator1, class BidirectionalIterator2, - class BidirectionalIterator3> -BidirectionalIterator3 __merge_backward(BidirectionalIterator1 first1, - BidirectionalIterator1 last1, - BidirectionalIterator2 first2, - BidirectionalIterator2 last2, - BidirectionalIterator3 result) { - if (first1 == last1) return copy_backward(first2, last2, result); - if (first2 == last2) return copy_backward(first1, last1, result); - --last1; - --last2; - while (true) { - if (*last2 < *last1) { - *--result = *last1; - if (first1 == last1) return copy_backward(first2, ++last2, result); - --last1; - } else { - *--result = *last2; - if (first2 == last2) return copy_backward(first1, ++last1, result); - --last2; - } - } -} - -template <class BidirectionalIterator1, class BidirectionalIterator2, - class BidirectionalIterator3, class Compare> -BidirectionalIterator3 __merge_backward(BidirectionalIterator1 first1, - BidirectionalIterator1 last1, - BidirectionalIterator2 first2, - BidirectionalIterator2 last2, - BidirectionalIterator3 result, - Compare comp) { - if (first1 == last1) return copy_backward(first2, last2, result); - if (first2 == last2) return copy_backward(first1, last1, result); - --last1; - --last2; - while (true) { - if (comp(*last2, *last1)) { - *--result = *last1; - if (first1 == last1) return copy_backward(first2, ++last2, result); - --last1; - } else { - *--result = *last2; - if (first2 == last2) return copy_backward(first1, ++last1, result); - --last2; - } - } -} - -template <class BidirectionalIterator, class Distance, class Pointer, class T> -void __merge_adaptive(BidirectionalIterator first, - BidirectionalIterator middle, - BidirectionalIterator last, Distance len1, Distance len2, - Pointer buffer, Distance buffer_size, T*) { - if (len1 <= len2 && len1 <= buffer_size) { - Pointer end_buffer = copy(first, middle, buffer); - merge(buffer, end_buffer, middle, last, first); - } else if (len2 <= buffer_size) { - Pointer end_buffer = copy(middle, last, buffer); - __merge_backward(first, middle, buffer, end_buffer, last); - } else { - BidirectionalIterator first_cut = first; - BidirectionalIterator second_cut = middle; - Distance len11 = 0; - Distance len22 = 0; - if (len1 > len2) { - len11 = len1 / 2; - advance(first_cut, len11); - second_cut = lower_bound(middle, last, *first_cut); - distance(middle, second_cut, len22); - } else { - len22 = len2 / 2; - advance(second_cut, len22); - first_cut = upper_bound(first, middle, *second_cut); - distance(first, first_cut, len11); - } - BidirectionalIterator new_middle = - __rotate_adaptive(first_cut, middle, second_cut, len1 - len11, - len22, buffer, buffer_size); - __merge_adaptive(first, first_cut, new_middle, len11, len22, buffer, - buffer_size, (T*)0); - __merge_adaptive(new_middle, second_cut, last, len1 - len11, - len2 - len22, buffer, buffer_size, (T*)0); - } -} - -template <class BidirectionalIterator, class Distance, class Pointer, class T, - class Compare> -void __merge_adaptive(BidirectionalIterator first, - BidirectionalIterator middle, - BidirectionalIterator last, Distance len1, Distance len2, - Pointer buffer, Distance buffer_size, T*, Compare comp) { - if (len1 <= len2 && len1 <= buffer_size) { - Pointer end_buffer = copy(first, middle, buffer); - merge(buffer, end_buffer, middle, last, first, comp); - } else if (len2 <= buffer_size) { - Pointer end_buffer = copy(middle, last, buffer); - __merge_backward(first, middle, buffer, end_buffer, last, comp); - } else { - BidirectionalIterator first_cut = first; - BidirectionalIterator second_cut = middle; - Distance len11 = 0; - Distance len22 = 0; - if (len1 > len2) { - len11 = len1 / 2; - advance(first_cut, len11); - second_cut = lower_bound(middle, last, *first_cut, comp); - distance(middle, second_cut, len22); - } else { - len22 = len2 / 2; - advance(second_cut, len22); - first_cut = upper_bound(first, middle, *second_cut, comp); - distance(first, first_cut, len11); - } - BidirectionalIterator new_middle = - __rotate_adaptive(first_cut, middle, second_cut, len1 - len11, - len22, buffer, buffer_size); - __merge_adaptive(first, first_cut, new_middle, len11, len22, buffer, - buffer_size, (T*)0, comp); - __merge_adaptive(new_middle, second_cut, last, len1 - len11, - len2 - len22, buffer, buffer_size, (T*)0, comp); - } -} - -template <class BidirectionalIterator, class Distance, class Pointer, class T> -void __inplace_merge(BidirectionalIterator first, - BidirectionalIterator middle, - BidirectionalIterator last, Distance len1, Distance len2, - pair<Pointer, Distance> p, T*) { - if (p.first == 0) { - __merge_without_buffer(first, middle, last, len1, len2); - return; - } - Distance len = min(p.second, len1 + len2); - fill_n(raw_storage_iterator<Pointer, T>(p.first), len, *first); - __merge_adaptive(first, middle, last, len1, len2, p.first, p.second, (T*)0); - destroy(p.first, p.first + len); - return_temporary_buffer(p.first); -} - -template <class BidirectionalIterator, class Distance, class Pointer, class T, - class Compare> -void __inplace_merge(BidirectionalIterator first, - BidirectionalIterator middle, - BidirectionalIterator last, Distance len1, Distance len2, - pair<Pointer, Distance> p, T*, Compare comp) { - if (p.first == 0) { - __merge_without_buffer(first, middle, last, len1, len2, comp); - return; - } - Distance len = min(p.second, len1 + len2); - fill_n(raw_storage_iterator<Pointer, T>(p.first), len, *first); - __merge_adaptive(first, middle, last, len1, len2, p.first, p.second, (T*)0, - comp); - destroy(p.first, p.first + len); - return_temporary_buffer(p.first); -} - -template <class BidirectionalIterator, class T, class Distance> -inline void __inplace_merge_aux(BidirectionalIterator first, - BidirectionalIterator middle, - BidirectionalIterator last, T*, Distance*) { - Distance len1 = 0; - distance(first, middle, len1); - Distance len2 = 0; - distance(middle, last, len2); - __inplace_merge(first, middle, last, len1, len2, - get_temporary_buffer(len1 + len2, (T*)0), (T*)0); -} - -template <class BidirectionalIterator, class T, class Distance, class Compare> -inline void __inplace_merge_aux(BidirectionalIterator first, - BidirectionalIterator middle, - BidirectionalIterator last, T*, Distance*, - Compare comp) { - Distance len1 = 0; - distance(first, middle, len1); - Distance len2 = 0; - distance(middle, last, len2); - __inplace_merge(first, middle, last, len1, len2, - get_temporary_buffer(len1 + len2, (T*)0), (T*)0, - comp); -} - -template <class BidirectionalIterator> -inline void inplace_merge(BidirectionalIterator first, - BidirectionalIterator middle, - BidirectionalIterator last) { - if (first == middle || middle == last) return; - __inplace_merge_aux(first, middle, last, value_type(first), - distance_type(first)); -} - -template <class BidirectionalIterator, class Compare> -inline void inplace_merge(BidirectionalIterator first, - BidirectionalIterator middle, - BidirectionalIterator last, Compare comp) { - if (first == middle || middle == last) return; - __inplace_merge_aux(first, middle, last, value_type(first), - distance_type(first), comp); -} - -template <class InputIterator1, class InputIterator2> -bool includes(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2) { - while (first1 != last1 && first2 != last2) - if (*first2 < *first1) - return false; - else if(*first1 < *first2) - ++first1; - else - ++first1, ++first2; - - return first2 == last2; -} - -template <class InputIterator1, class InputIterator2, class Compare> -bool includes(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, Compare comp) { - while (first1 != last1 && first2 != last2) - if (comp(*first2, *first1)) - return false; - else if(comp(*first1, *first2)) - ++first1; - else - ++first1, ++first2; - - return first2 == last2; -} - -template <class InputIterator1, class InputIterator2, class OutputIterator> -OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, - OutputIterator result) { - while (first1 != last1 && first2 != last2) - if (*first1 < *first2) - *result++ = *first1++; - else if (*first2 < *first1) - *result++ = *first2++; - else { - *result++ = *first1++; - first2++; - } - return copy(first2, last2, copy(first1, last1, result)); -} - -template <class InputIterator1, class InputIterator2, class OutputIterator, - class Compare> -OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, - OutputIterator result, Compare comp) { - while (first1 != last1 && first2 != last2) - if (comp(*first1, *first2)) - *result++ = *first1++; - else if (comp(*first2, *first1)) - *result++ = *first2++; - else { - *result++ = *first1++; - ++first2; - } - return copy(first2, last2, copy(first1, last1, result)); -} - -template <class InputIterator1, class InputIterator2, class OutputIterator> -OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, - OutputIterator result) { - while (first1 != last1 && first2 != last2) - if (*first1 < *first2) - ++first1; - else if (*first2 < *first1) - ++first2; - else { - *result++ = *first1++; - ++first2; - } - return result; -} - -template <class InputIterator1, class InputIterator2, class OutputIterator, - class Compare> -OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, - OutputIterator result, Compare comp) { - while (first1 != last1 && first2 != last2) - if (comp(*first1, *first2)) - ++first1; - else if (comp(*first2, *first1)) - ++first2; - else { - *result++ = *first1++; - ++first2; - } - return result; -} - -template <class InputIterator1, class InputIterator2, class OutputIterator> -OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, - OutputIterator result) { - while (first1 != last1 && first2 != last2) - if (*first1 < *first2) - *result++ = *first1++; - else if (*first2 < *first1) - ++first2; - else { - ++first1; - ++first2; - } - return copy(first1, last1, result); -} - -template <class InputIterator1, class InputIterator2, class OutputIterator, - class Compare> -OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, - OutputIterator result, Compare comp) { - while (first1 != last1 && first2 != last2) - if (comp(*first1, *first2)) - *result++ = *first1++; - else if (comp(*first2, *first1)) - ++first2; - else { - ++first1; - ++first2; - } - return copy(first1, last1, result); -} - -template <class InputIterator1, class InputIterator2, class OutputIterator> -OutputIterator set_symmetric_difference(InputIterator1 first1, - InputIterator1 last1, - InputIterator2 first2, - InputIterator2 last2, - OutputIterator result) { - while (first1 != last1 && first2 != last2) - if (*first1 < *first2) - *result++ = *first1++; - else if (*first2 < *first1) - *result++ = *first2++; - else { - ++first1; - ++first2; - } - return copy(first2, last2, copy(first1, last1, result)); -} - -template <class InputIterator1, class InputIterator2, class OutputIterator, - class Compare> -OutputIterator set_symmetric_difference(InputIterator1 first1, - InputIterator1 last1, - InputIterator2 first2, - InputIterator2 last2, - OutputIterator result, Compare comp) { - while (first1 != last1 && first2 != last2) - if (comp(*first1, *first2)) - *result++ = *first1++; - else if (comp(*first2, *first1)) - *result++ = *first2++; - else { - ++first1; - ++first2; - } - return copy(first2, last2, copy(first1, last1, result)); -} - -template <class ForwardIterator> -ForwardIterator max_element(ForwardIterator first, ForwardIterator last) { - if (first == last) return first; - ForwardIterator result = first; - while (++first != last) - if (*result < *first) result = first; - return result; -} - -template <class ForwardIterator, class Compare> -ForwardIterator max_element(ForwardIterator first, ForwardIterator last, - Compare comp) { - if (first == last) return first; - ForwardIterator result = first; - while (++first != last) - if (comp(*result, *first)) result = first; - return result; -} - -template <class ForwardIterator> -ForwardIterator min_element(ForwardIterator first, ForwardIterator last) { - if (first == last) return first; - ForwardIterator result = first; - while (++first != last) - if (*first < *result) result = first; - return result; -} - -template <class ForwardIterator, class Compare> -ForwardIterator min_element(ForwardIterator first, ForwardIterator last, - Compare comp) { - if (first == last) return first; - ForwardIterator result = first; - while (++first != last) - if (comp(*first, *result)) result = first; - return result; -} - -template <class BidirectionalIterator> -bool next_permutation(BidirectionalIterator first, - BidirectionalIterator last) { - if (first == last) return false; - BidirectionalIterator i = first; - ++i; - if (i == last) return false; - i = last; - --i; - - for(;;) { - BidirectionalIterator ii = i--; - if (*i < *ii) { - BidirectionalIterator j = last; - while (!(*i < *--j)); - iter_swap(i, j); - reverse(ii, last); - return true; - } - if (i == first) { - reverse(first, last); - return false; - } - } -} - -template <class BidirectionalIterator, class Compare> -bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, - Compare comp) { - if (first == last) return false; - BidirectionalIterator i = first; - ++i; - if (i == last) return false; - i = last; - --i; - - for(;;) { - BidirectionalIterator ii = i--; - if (comp(*i, *ii)) { - BidirectionalIterator j = last; - while (!comp(*i, *--j)); - iter_swap(i, j); - reverse(ii, last); - return true; - } - if (i == first) { - reverse(first, last); - return false; - } - } -} - -template <class BidirectionalIterator> -bool prev_permutation(BidirectionalIterator first, - BidirectionalIterator last) { - if (first == last) return false; - BidirectionalIterator i = first; - ++i; - if (i == last) return false; - i = last; - --i; - - for(;;) { - BidirectionalIterator ii = i--; - if (*ii < *i) { - BidirectionalIterator j = last; - while (!(*--j < *i)); - iter_swap(i, j); - reverse(ii, last); - return true; - } - if (i == first) { - reverse(first, last); - return false; - } - } -} - -template <class BidirectionalIterator, class Compare> -bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, - Compare comp) { - if (first == last) return false; - BidirectionalIterator i = first; - ++i; - if (i == last) return false; - i = last; - --i; - - for(;;) { - BidirectionalIterator ii = i--; - if (comp(*ii, *i)) { - BidirectionalIterator j = last; - while (!comp(*--j, *i)); - iter_swap(i, j); - reverse(ii, last); - return true; - } - if (i == first) { - reverse(first, last); - return false; - } - } -} - -template <class InputIterator, class T> -T accumulate(InputIterator first, InputIterator last, T init) { - while (first != last) - init = init + *first++; - return init; -} - -template <class InputIterator, class T, class BinaryOperation> -T accumulate(InputIterator first, InputIterator last, T init, - BinaryOperation binary_op) { - while (first != last) - init = binary_op(init, *first++); - return init; -} - -template <class InputIterator1, class InputIterator2, class T> -T inner_product(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, T init) { - while (first1 != last1) - init = init + (*first1++ * *first2++); - return init; -} - -template <class InputIterator1, class InputIterator2, class T, - class BinaryOperation1, class BinaryOperation2> -T inner_product(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, T init, BinaryOperation1 binary_op1, - BinaryOperation2 binary_op2) { - while (first1 != last1) - init = binary_op1(init, binary_op2(*first1++, *first2++)); - return init; -} - -template <class InputIterator, class OutputIterator, class T> -OutputIterator __partial_sum(InputIterator first, InputIterator last, - OutputIterator result, T*) { - T value = *first; - while (++first != last) { - value = value + *first; - *++result = value; - } - return ++result; -} - -template <class InputIterator, class OutputIterator> -OutputIterator partial_sum(InputIterator first, InputIterator last, - OutputIterator result) { - if (first == last) return result; - *result = *first; - return __partial_sum(first, last, result, value_type(first)); -} - -template <class InputIterator, class OutputIterator, class T, - class BinaryOperation> -OutputIterator __partial_sum(InputIterator first, InputIterator last, - OutputIterator result, T*, - BinaryOperation binary_op) { - T value = *first; - while (++first != last) { - value = binary_op(value, *first); - *++result = value; - } - return ++result; -} - -template <class InputIterator, class OutputIterator, class BinaryOperation> -OutputIterator partial_sum(InputIterator first, InputIterator last, - OutputIterator result, BinaryOperation binary_op) { - if (first == last) return result; - *result = *first; - return __partial_sum(first, last, result, value_type(first), binary_op); -} - -template <class InputIterator, class OutputIterator, class T> -OutputIterator __adjacent_difference(InputIterator first, InputIterator last, - OutputIterator result, T*) { - T value = *first; - while (++first != last) { - T tmp = *first; - *++result = tmp - value; - value = tmp; - } - return ++result; -} - -template <class InputIterator, class OutputIterator> -OutputIterator adjacent_difference(InputIterator first, InputIterator last, - OutputIterator result) { - if (first == last) return result; - *result = *first; - return __adjacent_difference(first, last, result, value_type(first)); -} - -template <class InputIterator, class OutputIterator, class T, - class BinaryOperation> -OutputIterator __adjacent_difference(InputIterator first, InputIterator last, - OutputIterator result, T*, - BinaryOperation binary_op) { - T value = *first; - while (++first != last) { - T tmp = *first; - *++result = binary_op(tmp, value); - value = tmp; - } - return ++result; -} - -template <class InputIterator, class OutputIterator, class BinaryOperation> -OutputIterator adjacent_difference(InputIterator first, InputIterator last, - OutputIterator result, - BinaryOperation binary_op) { - if (first == last) return result; - *result = *first; - return __adjacent_difference(first, last, result, value_type(first), - binary_op); -} - -template <class ForwardIterator, class T> -void iota(ForwardIterator first, ForwardIterator last, T value) { - while (first != last) *first++ = value++; -} - -#endif - diff --git a/contrib/libg++/libstdc++/stl/algobase.h b/contrib/libg++/libstdc++/stl/algobase.h deleted file mode 100644 index 21cea93b5f887..0000000000000 --- a/contrib/libg++/libstdc++/stl/algobase.h +++ /dev/null @@ -1,232 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef ALGOBASE_H -#define ALGOBASE_H - -#include <pair.h> -#include <iterator.h> - -template <class ForwardIterator1, class ForwardIterator2, class T> -inline void __iter_swap(ForwardIterator1 a, ForwardIterator2 b, T*) { - T tmp = *a; - *a = *b; - *b = tmp; -} - -template <class ForwardIterator1, class ForwardIterator2> -inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b) { - __iter_swap(a, b, value_type(a)); -} - -template <class T> -inline void swap(T& a, T& b) { - T tmp = a; - a = b; - b = tmp; -} - -template <class T> -inline const T& min(const T& a, const T& b) { - return b < a ? b : a; -} - -template <class T, class Compare> -inline const T& min(const T& a, const T& b, Compare comp) { - return comp(b, a) ? b : a; -} - -template <class T> -inline const T& max(const T& a, const T& b) { - return a < b ? b : a; -} - -template <class T, class Compare> -inline const T& max(const T& a, const T& b, Compare comp) { - return comp(a, b) ? b : a; -} - -template <class InputIterator, class Distance> -void __distance(InputIterator first, InputIterator last, Distance& n, - input_iterator_tag) { - while (first != last) { ++first; ++n; } -} - -template <class ForwardIterator, class Distance> -void __distance(ForwardIterator first, ForwardIterator last, Distance& n, - forward_iterator_tag) { - while (first != last) { ++first; ++n; } -} - -template <class BidirectionalIterator, class Distance> -void __distance(BidirectionalIterator first, BidirectionalIterator last, - Distance& n, bidirectional_iterator_tag) { - while (first != last) { ++first; ++n; } -} - -template <class RandomAccessIterator, class Distance> -inline void __distance(RandomAccessIterator first, RandomAccessIterator last, - Distance& n, random_access_iterator_tag) { - n += last - first; -} - -template <class InputIterator, class Distance> -inline void distance(InputIterator first, InputIterator last, Distance& n) { - __distance(first, last, n, iterator_category(first)); -} - -template <class InputIterator, class Distance> -void __advance(InputIterator& i, Distance n, input_iterator_tag) { - while (n--) ++i; -} - -template <class ForwardIterator, class Distance> -void __advance(ForwardIterator& i, Distance n, forward_iterator_tag) { - while (n--) ++i; -} - -template <class BidirectionalIterator, class Distance> -void __advance(BidirectionalIterator& i, Distance n, - bidirectional_iterator_tag) { - if (n >= 0) - while (n--) ++i; - else - while (n++) --i; -} - -template <class RandomAccessIterator, class Distance> -inline void __advance(RandomAccessIterator& i, Distance n, - random_access_iterator_tag) { - i += n; -} - -template <class InputIterator, class Distance> -inline void advance(InputIterator& i, Distance n) { - __advance(i, n, iterator_category(i)); -} - -template <class ForwardIterator> -void destroy(ForwardIterator first, ForwardIterator last) { - while (first != last) { - /* Borland bug */ - destroy(&*first); - ++first; - //destroy(&*first++); - } -} - -template <class InputIterator, class ForwardIterator> -ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, - ForwardIterator result) { - while (first != last) construct(&*result++, *first++); - return result; -} - -template <class ForwardIterator, class T> -void uninitialized_fill(ForwardIterator first, ForwardIterator last, - const T& x) { - while (first != last) construct(&*first++, x); -} - -template <class ForwardIterator, class Size, class T> -ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n, - const T& x) { - while (n--) construct(&*first++, x); - return first; -} - -template <class InputIterator, class OutputIterator> -OutputIterator copy(InputIterator first, InputIterator last, - OutputIterator result) { - while (first != last) *result++ = *first++; - return result; -} - -template <class BidirectionalIterator1, class BidirectionalIterator2> -BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, - BidirectionalIterator1 last, - BidirectionalIterator2 result) { - while (first != last) *--result = *--last; - return result; -} - -template <class ForwardIterator, class T> -void fill(ForwardIterator first, ForwardIterator last, const T& value) { - while (first != last) *first++ = value; -} - -template <class OutputIterator, class Size, class T> -OutputIterator fill_n(OutputIterator first, Size n, const T& value) { - while (n-- > 0) *first++ = value; - return first; -} - -template <class InputIterator1, class InputIterator2> -pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, - InputIterator1 last1, - InputIterator2 first2) { - while (first1 != last1 && *first1 == *first2) { - ++first1; - ++first2; - } - return pair<InputIterator1, InputIterator2>(first1, first2); -} - -template <class InputIterator1, class InputIterator2, class BinaryPredicate> -pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, - InputIterator1 last1, - InputIterator2 first2, - BinaryPredicate binary_pred) { - while (first1 != last1 && binary_pred(*first1, *first2)) { - ++first1; - ++first2; - } - return pair<InputIterator1, InputIterator2>(first1, first2); -} - -template <class InputIterator1, class InputIterator2> -inline bool equal(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2) { - return mismatch(first1, last1, first2).first == last1; -} - -template <class InputIterator1, class InputIterator2, class BinaryPredicate> -inline bool equal(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, BinaryPredicate binary_pred) { - return mismatch(first1, last1, first2, binary_pred).first == last1; -} - -template <class InputIterator1, class InputIterator2> -bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2) { - while (first1 != last1 && first2 != last2) { - if (*first1 < *first2) return true; - if (*first2++ < *first1++) return false; - } - return first1 == last1 && first2 != last2; -} - -template <class InputIterator1, class InputIterator2, class Compare> -bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, - Compare comp) { - while (first1 != last1 && first2 != last2) { - if (comp(*first1, *first2)) return true; - if (comp(*first2++, *first1++)) return false; - } - return first1 == last1 && first2 != last2; -} - -#endif diff --git a/contrib/libg++/libstdc++/stl/bool.h b/contrib/libg++/libstdc++/stl/bool.h deleted file mode 100644 index 9d86aac99c684..0000000000000 --- a/contrib/libg++/libstdc++/stl/bool.h +++ /dev/null @@ -1,20 +0,0 @@ -#ifndef __GNUC__ -/* - * - * 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. - * - */ - -#define bool int -#define true 1 -#define false 0 -#endif diff --git a/contrib/libg++/libstdc++/stl/bvector.h b/contrib/libg++/libstdc++/stl/bvector.h deleted file mode 100644 index f9fe10655cbcd..0000000000000 --- a/contrib/libg++/libstdc++/stl/bvector.h +++ /dev/null @@ -1,421 +0,0 @@ -/* - * - * 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. - * - */ - -// vector<bool> is replaced by bit_vector at present because bool is not -// implemented. - -#ifndef BVECTOR_H -#define BVECTOR_H - -#include <function.h> -#include <algobase.h> -#include <iterator.h> -#ifndef __GNUG__ -#include <bool.h> -#endif - -#ifndef Allocator -#define Allocator allocator -#include <defalloc.h> -#endif - -#define __WORD_BIT (int(CHAR_BIT*sizeof(unsigned int))) - -class bit_vector { -public: - typedef Allocator<unsigned int> vector_allocator; - typedef bool value_type; - typedef vector_allocator::size_type size_type; - typedef vector_allocator::difference_type difference_type; - - class iterator; - class const_iterator; - - class reference { - friend class iterator; - friend class const_iterator; - protected: - unsigned int* p; - unsigned int mask; - reference(unsigned int* x, unsigned int y) : p(x), mask(y) {} - public: - reference() : p(0), mask(0) {} - operator bool() const { return !(!(*p & mask)); } - reference& operator=(bool x) { - if (x) - *p |= mask; - else - *p &= ~mask; - return *this; - } - reference& operator=(const reference& x) { return *this = bool(x); } - bool operator==(const reference& x) const { - return bool(*this) == bool(x); - } - bool operator<(const reference& x) const { - return bool(*this) < bool(x); - } - void flip() { *p ^= mask; } - }; - typedef bool const_reference; - class iterator : public random_access_iterator<bool, difference_type> { - friend class bit_vector; - friend class const_iterator; - protected: - unsigned int* p; - unsigned int offset; - void bump_up() { - if (offset++ == __WORD_BIT - 1) { - offset = 0; - ++p; - } - } - void bump_down() { - if (offset-- == 0) { - offset = __WORD_BIT - 1; - --p; - } - } - public: - iterator() : p(0), offset(0) {} - iterator(unsigned int* x, unsigned int y) : p(x), offset(y) {} - reference operator*() const { return reference(p, 1U << offset); } - iterator& operator++() { - bump_up(); - return *this; - } - iterator operator++(int) { - iterator tmp = *this; - bump_up(); - return tmp; - } - iterator& operator--() { - bump_down(); - return *this; - } - iterator operator--(int) { - iterator tmp = *this; - bump_down(); - return tmp; - } - iterator& operator+=(difference_type i) { - difference_type n = i + offset; - p += n / __WORD_BIT; - n = n % __WORD_BIT; - if (n < 0) { - offset = n + __WORD_BIT; - --p; - } else - offset = n; - return *this; - } - iterator& operator-=(difference_type i) { - *this += -i; - return *this; - } - iterator operator+(difference_type i) const { - iterator tmp = *this; - return tmp += i; - } - iterator operator-(difference_type i) const { - iterator tmp = *this; - return tmp -= i; - } - difference_type operator-(iterator x) const { - return __WORD_BIT * (p - x.p) + offset - x.offset; - } - reference operator[](difference_type i) { return *(*this + i); } - bool operator==(const iterator& x) const { - return p == x.p && offset == x.offset; - } - bool operator<(iterator x) const { - return p < x.p || (p == x.p && offset < x.offset); - } - }; - - class const_iterator - : public random_access_iterator<bool, difference_type> { - friend class bit_vector; - protected: - unsigned int* p; - unsigned int offset; - void bump_up() { - if (offset++ == __WORD_BIT - 1) { - offset = 0; - ++p; - } - } - void bump_down() { - if (offset-- == 0) { - offset = __WORD_BIT - 1; - --p; - } - } - public: - const_iterator() : p(0), offset(0) {} - const_iterator(unsigned int* x, unsigned int y) : p(x), offset(y) {} - const_iterator(const iterator& x) : p(x.p), offset(x.offset) {} - const_reference operator*() const { - return reference(p, 1U << offset); - } - const_iterator& operator++() { - bump_up(); - return *this; - } - const_iterator operator++(int) { - const_iterator tmp = *this; - bump_up(); - return tmp; - } - const_iterator& operator--() { - bump_down(); - return *this; - } - const_iterator operator--(int) { - const_iterator tmp = *this; - bump_down(); - return tmp; - } - const_iterator& operator+=(difference_type i) { - difference_type n = i + offset; - p += n / __WORD_BIT; - n = n % __WORD_BIT; - if (n < 0) { - offset = n + __WORD_BIT; - --p; - } else - offset = n; - return *this; - } - const_iterator& operator-=(difference_type i) { - *this += -i; - return *this; - } - const_iterator operator+(difference_type i) const { - const_iterator tmp = *this; - return tmp += i; - } - const_iterator operator-(difference_type i) const { - const_iterator tmp = *this; - return tmp -= i; - } - difference_type operator-(const_iterator x) const { - return __WORD_BIT * (p - x.p) + offset - x.offset; - } - const_reference operator[](difference_type i) { - return *(*this + i); - } - bool operator==(const const_iterator& x) const { - return p == x.p && offset == x.offset; - } - bool operator<(const_iterator x) const { - return p < x.p || (p == x.p && offset < x.offset); - } - }; - - typedef reverse_iterator<const_iterator, value_type, const_reference, - difference_type> const_reverse_iterator; - typedef reverse_iterator<iterator, value_type, reference, difference_type> - reverse_iterator; - -protected: - static Allocator<unsigned int> static_allocator; - iterator start; - iterator finish; - unsigned int* end_of_storage; - unsigned int* bit_alloc(size_type n) { - return static_allocator.allocate((n + __WORD_BIT - 1)/__WORD_BIT); - } - void initialize(size_type n) { - unsigned int* q = bit_alloc(n); - end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT; - start = iterator(q, 0); - finish = start + n; - } - void insert_aux(iterator position, bool x); - typedef bit_vector self; -public: - iterator begin() { return start; } - const_iterator begin() const { return start; } - iterator end() { return finish; } - const_iterator end() const { return finish; } - - 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()); - } - - size_type size() const { return size_type(end() - begin()); } - size_type max_size() const { return static_allocator.max_size(); } - size_type capacity() const { - return size_type(const_iterator(end_of_storage, 0) - begin()); - } - bool empty() const { return begin() == end(); } - reference operator[](size_type n) { return *(begin() + n); } - const_reference operator[](size_type n) const { return *(begin() + n); } - bit_vector() : start(iterator()), finish(iterator()), end_of_storage(0) {} - bit_vector(size_type n, bool value = bool()) { - initialize(n); - fill(start.p, end_of_storage, value ? ~0 : 0); - } - bit_vector(const self& x) { - initialize(x.size()); - copy(x.begin(), x.end(), start); - } - bit_vector(const_iterator first, const_iterator last) { - size_type n = 0; - distance(first, last, n); - initialize(n); - copy(first, last, start); - } - ~bit_vector() { static_allocator.deallocate(start.p); } - self& operator=(const self& x) { - if (&x == this) return *this; - if (x.size() > capacity()) { - static_allocator.deallocate(start.p); - initialize(x.size()); - } - copy(x.begin(), x.end(), begin()); - finish = begin() + x.size(); - return *this; - } - void reserve(size_type n) { - if (capacity() < n) { - unsigned int* q = bit_alloc(n); - finish = copy(begin(), end(), iterator(q, 0)); - static_allocator.deallocate(start.p); - start = iterator(q, 0); - end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT; - } - } - reference front() { return *begin(); } - const_reference front() const { return *begin(); } - reference back() { return *(end() - 1); } - const_reference back() const { return *(end() - 1); } - void push_back(bool x) { - if (finish.p != end_of_storage) - *finish++ = x; - else - insert_aux(end(), x); - } - void swap(bit_vector& x) { - ::swap(start, x.start); - ::swap(finish, x.finish); - ::swap(end_of_storage, x.end_of_storage); - } - iterator insert(iterator position, bool x) { - size_type n = position - begin(); - if (finish.p != end_of_storage && position == end()) - *finish++ = x; - else - insert_aux(position, x); - return begin() + n; - } - void insert(iterator position, const_iterator first, - const_iterator last); - void insert(iterator position, size_type n, bool x); - void pop_back() { --finish; } - void erase(iterator position) { - if (position + 1 != end()) - copy(position + 1, end(), position); - --finish; - } - void erase(iterator first, iterator last) { - finish = copy(last, end(), first); - } -}; - -Allocator<unsigned int> bit_vector::static_allocator; - -inline bool operator==(const bit_vector& x, const bit_vector& y) { - return x.size() == y.size() && equal(x.begin(), x.end(), y.begin()); -} - -inline bool operator<(const bit_vector& x, const bit_vector& y) { - return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); -} - -void swap(bit_vector::reference x, bit_vector::reference y) { - bool tmp = x; - x = y; - y = tmp; -} - -void bit_vector::insert_aux(iterator position, bool x) { - if (finish.p != end_of_storage) { - copy_backward(position, finish - 1, finish); - *position = x; - ++finish; - } else { - size_type len = size() ? 2 * size() : __WORD_BIT; - unsigned int* q = bit_alloc(len); - iterator i = copy(begin(), position, iterator(q, 0)); - *i++ = x; - finish = copy(position, end(), i); - static_allocator.deallocate(start.p); - end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT; - start = iterator(q, 0); - } -} - -void bit_vector::insert(iterator position, size_type n, bool x) { - if (n == 0) return; - if (capacity() - size() >= n) { - copy_backward(position, end(), finish + n); - fill(position, position + n, x); - finish += n; - } else { - size_type len = size() + max(size(), n); - unsigned int* q = bit_alloc(len); - iterator i = copy(begin(), position, iterator(q, 0)); - fill_n(i, n, x); - finish = copy(position, end(), i + n); - static_allocator.deallocate(start.p); - end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT; - start = iterator(q, 0); - } -} - -void bit_vector::insert(iterator position, const_iterator first, - const_iterator last) { - if (first == last) return; - size_type n = 0; - distance(first, last, n); - if (capacity() - size() >= n) { - copy_backward(position, end(), finish + n); - copy(first, last, position); - finish += n; - } else { - size_type len = size() + max(size(), n); - unsigned int* q = bit_alloc(len); - iterator i = copy(begin(), position, iterator(q, 0)); - i = copy(first, last, i); - finish = copy(position, end(), i); - static_allocator.deallocate(start.p); - end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT; - start = iterator(q, 0); - } -} - -#undef Allocator -#undef __WORD_BIT - -#endif - - diff --git a/contrib/libg++/libstdc++/stl/configure.in b/contrib/libg++/libstdc++/stl/configure.in deleted file mode 100644 index d452935df77f3..0000000000000 --- a/contrib/libg++/libstdc++/stl/configure.in +++ /dev/null @@ -1,37 +0,0 @@ -# This file is a shell script fragment that supplies the information -# necessary for a configure script to process the program in -# this directory. For more information, look at ../../configure. - -configdirs= -srctrigger=iterator.h -srcname="Standard Template Library" -package_makefile_frag=Make.pack - -# per-host: - -# per-target: - -target_makefile_frag=../target-mkfrag - -LIBDIR=yes -TO_TOPDIR=../../ -ALL='stl.list' -EXTRA_MOSTLYCLEAN=stl.list -XCXXINCLUDES="-I${srcdir} -I${srcdir}/.. -I${TO_TOPDIR}libio -I${srcdir}/${TO_TOPDIR}libio" -(. ${srcdir}/${TO_TOPDIR}libio/config.shared) >${package_makefile_frag} - -# post-target: - -# We need multilib support. -case ${srcdir} in -.) - if [ "${with_target_subdir}" != "." ] ; then - . ${srcdir}/${with_multisrctop}../../../config-ml.in - else - . ${srcdir}/${with_multisrctop}../../config-ml.in - fi - ;; -*) - . ${srcdir}/../../config-ml.in - ;; -esac diff --git a/contrib/libg++/libstdc++/stl/defalloc.h b/contrib/libg++/libstdc++/stl/defalloc.h deleted file mode 100644 index 388e58fd74445..0000000000000 --- a/contrib/libg++/libstdc++/stl/defalloc.h +++ /dev/null @@ -1,176 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef DEFALLOC_H -#define DEFALLOC_H - -#include <new.h> -#include <stddef.h> -#include <stdlib.h> -#include <limits.h> -#include <iostream.h> -#include <algobase.h> - -#ifndef __GNUG__ -inline void* operator new(size_t, void* p) {return p;} -#endif - -/* - * the following template function is replaced by the following two functions - * due to the fact that the Borland compiler doesn't change prediff_t type - * to type long when compile with -ml or -mh. - -template <class T> -inline T* allocate(ptrdiff_t size, T*) { - set_new_handler(0); - T* tmp = (T*)(::operator new((size_t)(size * sizeof(T)))); - if (tmp == 0) { - cerr << "out of memory" << endl; - exit(1); - } - return tmp; -} -*/ - -template <class T> -inline T* allocate(int size, T*) { - set_new_handler(0); - T* tmp = (T*)(::operator new((unsigned int)(size * sizeof(T)))); - if (tmp == 0) { - cerr << "out of memory" << endl; - exit(1); - } - return tmp; -} - -template <class T> -inline T* allocate(long size, T*) { - set_new_handler(0); - T* tmp = (T*)(::operator new((unsigned long)(size * sizeof(T)))); - if (tmp == 0) { - cerr << "out of memory" << endl; - exit(1); - } - return tmp; -} - -template <class T> -inline void deallocate(T* buffer) { - ::operator delete(buffer); -} - -template <class T> -inline void destroy(T* pointer) { - pointer->~T(); -} - -inline void destroy(char*) {} -inline void destroy(unsigned char*) {} -inline void destroy(short*) {} -inline void destroy(unsigned short*) {} -inline void destroy(int*) {} -inline void destroy(unsigned int*) {} -inline void destroy(long*) {} -inline void destroy(unsigned long*) {} -inline void destroy(float*) {} -inline void destroy(double*) {} -inline void destroy(char**) {} -inline void destroy(unsigned char**) {} -inline void destroy(short**) {} -inline void destroy(unsigned short**) {} -inline void destroy(int**) {} -inline void destroy(unsigned int**) {} -inline void destroy(long**) {} -inline void destroy(unsigned long**) {} -inline void destroy(float**) {} -inline void destroy(double**) {} - -inline void destroy(char*, char*) {} -inline void destroy(unsigned char*, unsigned char*) {} -inline void destroy(short*, short*) {} -inline void destroy(unsigned short*, unsigned short*) {} -inline void destroy(int*, int*) {} -inline void destroy(unsigned int*, unsigned int*) {} -inline void destroy(long*, long*) {} -inline void destroy(unsigned long*, unsigned long*) {} -inline void destroy(float*, float*) {} -inline void destroy(double*, double*) {} -inline void destroy(char**, char**) {} -inline void destroy(unsigned char**, unsigned char**) {} -inline void destroy(short**, short**) {} -inline void destroy(unsigned short**, unsigned short**) {} -inline void destroy(int**, int**) {} -inline void destroy(unsigned int**, unsigned int**) {} -inline void destroy(long**, long**) {} -inline void destroy(unsigned long**, unsigned long**) {} -inline void destroy(float**, float**) {} -inline void destroy(double**, double**) {} - -template <class T1, class T2> -inline void construct(T1* p, const T2& value) { - new (p) T1(value); -} - -template <class T> -class allocator { -public: - typedef T value_type; - typedef T* pointer; - typedef const T* const_pointer; - typedef T& reference; - typedef const T& const_reference; - typedef size_t size_type; - typedef ptrdiff_t difference_type; -#ifdef __GNUG__ - static pointer allocate(size_type n) { - return ::allocate((difference_type)n, (pointer)0); - } - static void deallocate(pointer p) { ::deallocate(p); } - static pointer address(reference x) { return (pointer)&x; } - static const_pointer const_address(const_reference x) { - return (const_pointer)&x; - } - static size_type init_page_size() { - return max(size_type(1), size_type(4096/sizeof(T))); - } - static size_type max_size() { - return max(size_type(1), size_type(UINT_MAX/sizeof(T))); - } -#else - pointer allocate(size_type n) { - return ::allocate((difference_type)n, (pointer)0); - } - void deallocate(pointer p) { ::deallocate(p); } - pointer address(reference x) { return (pointer)&x; } - const_pointer const_address(const_reference x) { - return (const_pointer)&x; - } - size_type init_page_size() { - return max(size_type(1), size_type(4096/sizeof(T))); - } - size_type max_size() const { - return max(size_type(1), size_type(UINT_MAX/sizeof(T))); - } -#endif -}; - -class allocator<void> { -public: - typedef void* pointer; -}; - - - -#endif diff --git a/contrib/libg++/libstdc++/stl/deque.h b/contrib/libg++/libstdc++/stl/deque.h deleted file mode 100644 index dc790142b54d4..0000000000000 --- a/contrib/libg++/libstdc++/stl/deque.h +++ /dev/null @@ -1,684 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef DEQUE_H -#define DEQUE_H - -#include <function.h> -#include <algobase.h> -#include <iterator.h> -#ifndef __GNUG__ -#include <bool.h> -#endif - -#ifndef Allocator -#define Allocator allocator -#include <defalloc.h> -#endif - -#ifndef deque -#define deque deque -#endif - -template <class T> -class deque { -public: - class iterator; - class const_iterator; - friend class iterator; - friend class const_iterator; -public: - typedef T value_type; - typedef Allocator<T> data_allocator_type; - typedef Allocator<T>::pointer pointer; - typedef Allocator<T>::reference reference; - typedef Allocator<T>::const_reference const_reference; - typedef Allocator<T>::size_type size_type; - typedef Allocator<T>::difference_type difference_type; - typedef Allocator<pointer> map_allocator_type; -protected: - static data_allocator_type data_allocator; -#ifdef __GNUG__ - // static // Too bad -- I don't like this hack very much... - static size_type buffer_size() { - return data_allocator.init_page_size(); - } -#define __dq_buffer_size buffer_size() -#else - static size_type buffer_size; -#define __dq_buffer_size buffer_size -#endif - static map_allocator_type map_allocator; - typedef Allocator<pointer>::pointer map_pointer; -public: - class iterator : public random_access_iterator<T, difference_type> { - friend class deque<T>; - friend class const_iterator; - protected: - pointer current; - pointer first; - pointer last; - map_pointer node; - iterator(pointer x, map_pointer y) - : current(x), first(*y), last(*y + __dq_buffer_size), node(y) {} - public: - iterator() : current(0), first(0), last(0), node(0) {} - reference operator*() const { return *current; } - difference_type operator-(const iterator& x) const { - return node == x.node - ? current - x.current - : difference_type(__dq_buffer_size * (node - x.node - 1) + - (current - first) + (x.last - x.current)); - } - iterator& operator++() { - if (++current == last) { - first = *(++node); - current = first; - last = first + __dq_buffer_size; - } - return *this; - } - iterator operator++(int) { - iterator tmp = *this; - ++*this; - return tmp; - } - iterator& operator--() { - if (current == first) { - first = *(--node); - last = first + __dq_buffer_size; - current = last; - } - --current; - return *this; - } - iterator operator--(int) { - iterator tmp = *this; - --*this; - return tmp; - } - iterator& operator+=(difference_type n) { - difference_type offset = n + (current - first); - difference_type num_node_to_jump = offset >= 0 - ? offset / __dq_buffer_size - : -((-offset + __dq_buffer_size - 1) / __dq_buffer_size); - if (num_node_to_jump == 0) - current += n; - else { - node = node + num_node_to_jump; - first = *node; - last = first + __dq_buffer_size; - current = first + (offset - num_node_to_jump * __dq_buffer_size); - } - return *this; - } - iterator& operator-=(difference_type n) { return *this += -n; } - iterator operator+(difference_type n) const { - iterator tmp = *this; - return tmp += n; - } - iterator operator-(difference_type n) const { - iterator tmp = *this; - return tmp -= n; - } - reference operator[](difference_type n) { return *(*this + n); } - bool operator==(const iterator& x) const { - return current == x.current || - ((current == first || x.current == x.first) && - *this - x == 0); - } - bool operator<(const iterator& x) const { - return (node == x.node) ? (current < x.current) : (node < x.node); - } - }; - class const_iterator : public random_access_iterator<T, difference_type> { - friend class deque<T>; - protected: - pointer current; - pointer first; - pointer last; - map_pointer node; - const_iterator(pointer x, map_pointer y) - : current(x), first(*y), last(*y + __dq_buffer_size), node(y) {} - public: - const_iterator() : current(0), first(0), last(0), node(0) {} - const_iterator(const iterator& x) - : current(x.current), first(x.first), last(x.last), node(x.node) {} - const_reference operator*() const { return *current; } - difference_type operator-(const const_iterator& x) const { - return node == x.node - ? current - x.current - : difference_type(__dq_buffer_size * (node - x.node - 1) + - (current - first) + (x.last - x.current)); - } - const_iterator& operator++() { - if (++current == last) { - first = *(++node); - current = first; - last = first + __dq_buffer_size; - } - return *this; - } - const_iterator operator++(int) { - const_iterator tmp = *this; - ++*this; - return tmp; - } - const_iterator& operator--() { - if (current == first) { - first = *(--node); - last = first + __dq_buffer_size; - current = last; - } - --current; - return *this; - } - const_iterator operator--(int) { - const_iterator tmp = *this; - --*this; - return tmp; - } - const_iterator& operator+=(difference_type n) { - difference_type offset = n + (current - first); - difference_type num_node_to_jump = offset >= 0 - ? offset / __dq_buffer_size - : -((-offset + __dq_buffer_size - 1) / __dq_buffer_size); - if (num_node_to_jump == 0) - current += n; - else { - node = node + num_node_to_jump; - first = *node; - last = first + __dq_buffer_size; - current = first + (offset - num_node_to_jump * __dq_buffer_size); - } - return *this; - } - const_iterator& operator-=(difference_type n) { return *this += -n; } - const_iterator operator+(difference_type n) const { - const_iterator tmp = *this; - return tmp += n; - } - const_iterator operator-(difference_type n) const { - const_iterator tmp = *this; - return tmp -= n; - } - const_reference operator[](difference_type n) { - return *(*this + n); - } - bool operator==(const const_iterator& x) const { - return current == x.current || - ((current == first || x.current == x.first) && - *this - x == 0); - } - bool operator<(const const_iterator& x) const { - return (node == x.node) ? (current < x.current) : (node < x.node); - } - }; - typedef reverse_iterator<const_iterator, value_type, const_reference, - difference_type> const_reverse_iterator; - typedef reverse_iterator<iterator, value_type, reference, difference_type> - reverse_iterator; -protected: - iterator start; - iterator finish; - size_type length; - map_pointer map; - size_type map_size; - - void allocate_at_begin(); - void allocate_at_end(); - void deallocate_at_begin(); - void deallocate_at_end(); - -public: - deque() : start(), finish(), length(0), map(0), map_size(0) { -#ifndef __GNUG__ - __dq_buffer_size = data_allocator.init_page_size(); -#endif - } - iterator begin() { return start; } - const_iterator begin() const { return start; } - iterator end() { return finish; } - const_iterator end() const { return finish; } - 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 length == 0; } - size_type size() const { return length; } - size_type max_size() const { return data_allocator.max_size(); } - reference operator[](size_type n) { return *(begin() + n); } - const_reference operator[](size_type n) const { return *(begin() + n); } - reference front() { return *begin(); } - const_reference front() const { return *begin(); } - reference back() { return *(end() - 1); } - const_reference back() const { return *(end() - 1); } - void push_front(const T& x) { - if (empty() || begin().current == begin().first) - allocate_at_begin(); - --start.current; - construct(start.current, x); - ++length; - if (end().current == end().last) allocate_at_end(); - } - void push_back(const T& x) { - if (empty()) allocate_at_end(); - construct(finish.current, x); - ++finish.current; - ++length; - if (end().current == end().last) allocate_at_end(); - } - void pop_front() { - destroy(start.current); - ++start.current; - --length; - if (empty() || begin().current == begin().last) - deallocate_at_begin(); - } - void pop_back() { - if (end().current == end().first) deallocate_at_end(); - --finish.current; - destroy(finish.current); - --length; - if (empty()) deallocate_at_end(); - } - void swap(deque<T>& x) { - ::swap(start, x.start); - ::swap(finish, x.finish); - ::swap(length, x.length); - ::swap(map, x.map); - ::swap(map_size, x.map_size); - } -#ifdef __GNUG__ - iterator insert(iterator position, const T& x) { - return insert(deque_iterator<T>(position), x); - } - deque_iterator<T> insert(deque_iterator<T> position, const T& x); - void insert(iterator position, size_type n, const T& x) { - insert(deque_iterator<T>(position), n, x); - } - void insert(deque_iterator<T>(position), size_type n, const T& x); -// template <class Iterator> void insert(iterator position, -// Iterator first, Iterator last); - void insert(iterator position, const T* first, const T* last) { - insert(deque_iterator<T>(position), first, last); - } - void insert(deque_iterator<T> position, const T* first, const T* last); - void erase(iterator position) { - erase(deque_iterator<T>(position)); - } - void erase(deque_iterator<T> position); - void erase(iterator first, iterator last) { - erase(deque_iterator<T>(first), deque_iterator<T>(last)); - } - void erase(deque_iterator<T> first, deque_iterator<T> last); -#else - iterator insert(iterator position, const T& x); - void insert(iterator position, size_type n, const T& x); -// template <class Iterator> void insert(iterator position, -// Iterator first, Iterator last); - void insert(iterator position, const T* first, const T* last); - void erase(iterator position); - void erase(iterator first, iterator last); -#endif - deque(size_type n, const T& value = T()) - : start(), finish(), length(0), map(0), map_size(0) { -#ifndef __GNUG__ - __dq_buffer_size = data_allocator.init_page_size(); -#endif - insert(begin(), n, value); - } -// template <class Iterator> deque(Iterator first, Iterator last); - deque(const T* first, const T* last) - : start(), finish(), length(0), map(0), map_size(0) { -#ifndef __GNUG__ - __dq_buffer_size = data_allocator.init_page_size(); -#endif - copy(first, last, back_inserter(*this)); - } - deque(const deque<T>& x) - : start(), finish(), length(0), map(0), map_size(0) { -#ifndef __GNUG__ - __dq_buffer_size = data_allocator.init_page_size(); -#endif - copy(x.begin(), x.end(), back_inserter(*this)); - } - deque<T>& operator=(const deque<T>& x) { - if (this != &x) - if (size() >= x.size()) - erase(copy(x.begin(), x.end(), begin()), end()); - else - copy(x.begin() + size(), x.end(), - inserter(*this, copy(x.begin(), x.begin() + size(), - begin()))); - return *this; - } - ~deque(); -#ifdef __GNUG__ - friend T* value_type(const iterator&) { - return (T*)(0); - } - friend inline difference_type* distance_type(const iterator&) { - return (difference_type*)(0); - } -#endif -}; - -#ifdef __GNUG__ -template <class T> -struct deque_iterator: deque<T>::iterator { - deque_iterator(deque<T>::iterator i) : deque<T>::iterator(i) {} -}; - -template <class T> -inline T* value_type(const deque_iterator<T>&) { - return (T*)(0); -} -#else -template <class T> -deque<T>::data_allocator_type deque<T>::data_allocator; - -template <class T> -deque<T>::map_allocator_type deque<T>::map_allocator; - -template <class T> -deque<T>::size_type deque<T>::__dq_buffer_size = 0; -// should be data_allocator.init_page_size(); // Borland bug -#endif - -template <class T> -bool operator==(const deque<T>& x, const deque<T>& y) { - return x.size() == y.size() && equal(x.begin(), x.end(), y.begin()); -} - -template <class T> -bool operator<(const deque<T>& x, const deque<T>& y) { - return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); -} - -template <class T> -deque<T>::~deque() { while (!empty()) pop_front(); } - -template <class T> -void deque<T>::allocate_at_begin() { - pointer p = data_allocator.allocate(__dq_buffer_size); - if (!empty()) { - if (start.node == map) { - difference_type i = finish.node - start.node; - map_size = (i + 1) * 2; -#ifdef __GNU_G__ - map_pointer tmp = map_allocator_type::allocate(map_size); - copy(start.node, finish.node + 1, tmp + map_size / 4 + 1); - map_allocator_type::deallocate(map); -#else - map_pointer tmp = map_allocator.allocate(map_size); - copy(start.node, finish.node + 1, tmp + map_size / 4 + 1); - map_allocator.deallocate(map); -#endif - map = tmp; - map[map_size / 4] = p; - start = iterator(p + __dq_buffer_size, map + map_size / 4); - finish = iterator(finish.current, map + map_size / 4 + i + 1); - } else { -#ifdef __GNUG__ - map_size = map_allocator_type::init_page_size(); - map = map_allocator_type::allocate(map_size); -#else - *--start.node = p; - start = iterator(p + __dq_buffer_size, start.node); -#endif - } - } else { -#ifdef __GNUG__ - map_size = map_allocator_type::init_page_size(); - map = map_allocator_type::allocate(map_size); -#else - map_size = map_allocator.init_page_size(); - map = map_allocator.allocate(map_size); -#endif - map[map_size / 2] = p; - start = iterator(p + __dq_buffer_size / 2 + 1, map + map_size / 2); - finish = start; - } -} - -template <class T> -void deque<T>::allocate_at_end() { - pointer p = data_allocator.allocate(__dq_buffer_size); - if (!empty()) { - if (finish.node == map + map_size - 1) { - difference_type i = finish.node - start.node; - map_size = (i + 1) * 2; -#ifdef __GNUG__ - map_pointer tmp = map_allocator_type::allocate(map_size); - copy(start.node, finish.node + 1, tmp + map_size / 4); - map_allocator_type::deallocate(map); -#else - map_pointer tmp = map_allocator.allocate(map_size); - copy(start.node, finish.node + 1, tmp + map_size / 4); - map_allocator.deallocate(map); -#endif - map = tmp; - map[map_size / 4 + i + 1] = p; - start = iterator(start.current, map + map_size / 4); - finish = iterator(p, map + map_size / 4 + i + 1); - } else { - *++finish.node = p; - finish = iterator(p, finish.node); - } - } else { -#ifdef __GNUG__ - map_size = map_allocator_type::init_page_size(); - map = map_allocator_type::allocate(map_size); -#else - map_size = map_allocator.init_page_size(); - map = map_allocator.allocate(map_size); -#endif - map[map_size / 2] = p; - start = iterator(p + __dq_buffer_size / 2, map + map_size / 2); - finish = start; - } -} - -template <class T> -void deque<T>::deallocate_at_begin() { - data_allocator.deallocate(*start.node++); - if (empty()) { - if (finish.current == finish.first) - data_allocator.deallocate(*start.node); - start = iterator(); - finish = start; -#ifdef __GNUG__ - map_allocator.deallocate(map); -#else - map_allocator.deallocate(map); -#endif - } else - start = iterator(*start.node, start.node); -} - -template <class T> -void deque<T>::deallocate_at_end() { - data_allocator.deallocate(*finish.node--); - if (empty()) { - start = iterator(); - finish = start; -#ifdef __GNUG__ - map_allocator.deallocate(map); -#else - map_allocator.deallocate(map); -#endif - } else - finish = iterator(*finish.node + __dq_buffer_size, finish.node); -} - -template <class T> -#ifdef __GNUG__ -deque_iterator<T> -deque<T>::insert(deque_iterator<T> posn, const T& x) { - iterator position = posn; -#else -deque<T>::iterator deque<T>::insert(iterator position, const T& x) { -#endif - if (position == begin()) { - push_front(x); - return begin(); - } else if (position == end()) { - push_back(x); - return end() - 1; - } else { - difference_type index = position - begin(); - if (index < length) { - push_front(*begin()); - copy(begin() + 2, begin() + index + 1, begin() + 1); - } else { - push_back(*(end() - 1)); - copy_backward(begin() + index, end() - 2, end() - 1); - } - *(begin() + index) = x; - return begin() + index; - } -} - -template <class T> -#ifdef __GNUG__ -void deque<T>::insert(deque_iterator<T> posn, - size_t n, // BAD HACK - const T& x) { - iterator position = posn; -#else -void deque<T>::insert(iterator position, size_type n, const T& x) { -#endif - difference_type index = position - begin(); - difference_type remainder = length - index; - if (remainder > index) { - if (n > index) { - difference_type m = n - index; - while (m-- > 0) push_front(x); - difference_type i = index; - while (i--) push_front(*(begin() + n - 1)); - fill(begin() + n, begin() + n + index, x); - } else { - difference_type i = n; - while (i--) push_front(*(begin() + n - 1)); - copy(begin() + n + n, begin() + n + index, begin() + n); - fill(begin() + index, begin() + n + index, x); - } - } else { - difference_type orig_len = index + remainder; - if (n > remainder) { - difference_type m = n - remainder; - while (m-- > 0) push_back(x); - difference_type i = 0; - while (i < remainder) push_back(*(begin() + index + i++)); - fill(begin() + index, begin() + orig_len, x); - } else { - difference_type i = 0; - while (i < n) push_back(*(begin() + orig_len - n + i++)); - copy_backward(begin() + index, begin() + orig_len - n, - begin() + orig_len); - fill(begin() + index, begin() + index + n, x); - } - } -} - -template <class T> -void deque<T>::insert -#ifdef __GNUG__ -(deque_iterator<T> posn, const T* first, const T* last) -{ - iterator position = posn; -#else -(iterator position, const T* first, const T* last) -{ -#endif - difference_type index = position - begin(); - difference_type remainder = length - index; - size_type n = 0; - distance(first, last, n); - if (remainder > index) { - if (n > index) { - const T* m = last - index; - while (m != first) push_front(*--m); - difference_type i = index; - while (i--) push_front(*(begin() + n - 1)); - copy(last - index, last, begin() + n); - } else { - difference_type i = n; - while (i--) push_front(*(begin() + n - 1)); - copy(begin() + n + n, begin() + n + index, begin() + n); - copy(first, last, begin() + index); - } - } else { - difference_type orig_len = index + remainder; - if (n > remainder) { - const T* m = first + remainder; - while (m != last) push_back(*m++); - difference_type i = 0; - while (i < remainder) push_back(*(begin() + index + i++)); - copy(first, first + remainder, begin() + index); - } else { - difference_type i = 0; - while (i < n) push_back(*(begin() + orig_len - n + i++)); - copy_backward(begin() + index, begin() + orig_len - n, - begin() + orig_len); - copy(first, last, begin() + index); - } - } -} - -template <class T> -#ifdef __GNUG__ -void deque<T>::erase(deque_iterator<T> posn) { - iterator position = posn; -#else -void deque<T>::erase(iterator position) { -#endif - if (end() - position > position - begin()) { - copy_backward(begin(), position, position + 1); - pop_front(); - } else { - copy(position + 1, end(), position); - pop_back(); - } -} - -template <class T> -#ifdef __GNUG__ -void deque<T>::erase(deque_iterator<T> fi, deque_iterator<T> la) { - iterator first = fi; - iterator last = la; - difference_type n = last - first; -#else -void deque<T>::erase(iterator first, iterator last) { - difference_type n = last - first; -#endif - if (end() - last > first - begin()) { - copy_backward(begin(), first, last); - while(n-- > 0) pop_front(); - } else { - copy(last, end(), first); - while(n-- > 0) pop_back(); - } -} - -#undef Allocator -#undef deque - -#endif diff --git a/contrib/libg++/libstdc++/stl/faralloc.h b/contrib/libg++/libstdc++/stl/faralloc.h deleted file mode 100644 index b29602cc63273..0000000000000 --- a/contrib/libg++/libstdc++/stl/faralloc.h +++ /dev/null @@ -1,120 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef FARALLOC_H -#define FARALLOC_H - -#include <new.h> -#include <stddef.h> -#include <stdlib.h> -#include <limits.h> -#include <iostream.h> -#include <algobase.h> - -template <class T> -inline random_access_iterator_tag iterator_category(const T __far *) { - return random_access_iterator_tag(); -} - -template <class T> -inline T* value_type(const T __far *) { return (T*)(0); } - -template <class T> -inline long* distance_type(const T __far*) { return (long*)(0); } - -inline void destroy(char __far *) {} -inline void destroy(unsigned char __far *) {} -inline void destroy(short __far *) {} -inline void destroy(unsigned short __far *) {} -inline void destroy(int __far *) {} -inline void destroy(unsigned int __far *) {} -inline void destroy(long __far *) {} -inline void destroy(unsigned long __far *) {} -inline void destroy(float __far *) {} -inline void destroy(double __far *) {} - -inline void destroy(char __far *, char __far *) {} -inline void destroy(unsigned char __far *, unsigned char __far *) {} -inline void destroy(short __far *, short __far *) {} -inline void destroy(unsigned short __far *, unsigned short __far *) {} -inline void destroy(int __far *, int __far *) {} -inline void destroy(unsigned int __far *, unsigned int __far *) {} -inline void destroy(long __far *, long __far *) {} -inline void destroy(unsigned long __far *, unsigned long __far *) {} -inline void destroy(float __far *, float __far *) {} -inline void destroy(double __far *, double __far *) {} - -inline void __far * operator new(size_t, void __far *p) { return p; } - -template <class T> -inline T __far * allocate(long size, T __far * p) { - set_new_handler(0); - T __far * tmp = - (T __far *)(::operator new((unsigned long)(size * sizeof(T)))); - if (tmp == 0) { - cerr << "out of memory" << endl; - exit(1); - } - return tmp; -} - -template <class T> -inline void deallocate(T __far * buffer) { - ::operator delete(buffer); -} - -template <class T1, class T2> -inline void construct( T1 __far *p, const T2& value ) -{ - new(p)T1(value); -} - -template <class T> -inline void destroy( T __far * pointer ) { - pointer->~T(); -} - -template <class T> -class far_allocator { -public: - typedef T value_type; - typedef T __far * pointer; - typedef const T __far * const_pointer; - typedef T __far & reference; - typedef const T __far & const_reference; - typedef unsigned long size_type; - typedef long difference_type; - pointer allocate(size_type n) { - return ::allocate((difference_type)n, (pointer)0); - } - void deallocate(pointer p) { ::deallocate(p); } - pointer address(reference x) { return (pointer)&x; } - const_pointer const_address(const_reference x) { - return (const_pointer)&x; - } - size_type init_page_size() { - return max(size_type(1), size_type(4096/sizeof(T))); - } - size_type max_size() const { - return max(size_type(1), size_type(ULONG_MAX/sizeof(T))); - } -}; - -class far_allocator<void> { -public: - typedef void __far * pointer; -}; - -#endif diff --git a/contrib/libg++/libstdc++/stl/fdeque.h b/contrib/libg++/libstdc++/stl/fdeque.h deleted file mode 100644 index 7b512b62dc2a9..0000000000000 --- a/contrib/libg++/libstdc++/stl/fdeque.h +++ /dev/null @@ -1,39 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef FDEQUE_H -#define FDEQUE_H - -#ifdef DEQUE_H -#undef DEQUE_H -#define __DEQUE_WAS_DEFINED -#endif - -#define Allocator far_allocator -#define deque far_deque -#include <faralloc.h> -#include <deque.h> - -#undef DEQUE_H - -#ifdef __DEQUE_WAS_DEFINED -#define DEQUE_H -#undef __DEQUE_WAS_DEFINED -#endif - -#undef Allocator -#undef deque - -#endif diff --git a/contrib/libg++/libstdc++/stl/flist.h b/contrib/libg++/libstdc++/stl/flist.h deleted file mode 100644 index 35fe9bf6288f8..0000000000000 --- a/contrib/libg++/libstdc++/stl/flist.h +++ /dev/null @@ -1,39 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef FLIST_H -#define FLIST_H - -#ifdef LIST_H -#undef LIST_H -#define __LIST_WAS_DEFINED -#endif - -#define Allocator far_allocator -#define list far_list -#include <faralloc.h> -#include <list.h> - -#undef LIST_H - -#ifdef __LIST_WAS_DEFINED -#define LIST_H -#undef __LIST_WAS_DEFINED -#endif - -#undef Allocator -#undef list - -#endif diff --git a/contrib/libg++/libstdc++/stl/fmap.h b/contrib/libg++/libstdc++/stl/fmap.h deleted file mode 100644 index 65aa2091fc20f..0000000000000 --- a/contrib/libg++/libstdc++/stl/fmap.h +++ /dev/null @@ -1,44 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef FMAP_H -#define FMAP_H - -#ifdef MAP_H -#undef MAP_H -#undef TREE_H -#define __MAP_WAS_DEFINED -#endif - -#define Allocator far_allocator -#define map far_map -#define rb_tree far_rb_tree -#include <faralloc.h> -#include <map.h> - -#undef MAP_H -#undef TREE_H - -#ifdef __MAP_WAS_DEFINED -#define MAP_H -#define TREE_H -#undef __MAP_WAS_DEFINED -#endif - -#undef Allocator -#undef map -#undef rb_tree - -#endif diff --git a/contrib/libg++/libstdc++/stl/fmultmap.h b/contrib/libg++/libstdc++/stl/fmultmap.h deleted file mode 100644 index ecb5cd4fdeff1..0000000000000 --- a/contrib/libg++/libstdc++/stl/fmultmap.h +++ /dev/null @@ -1,44 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef FMULTIMAP_H -#define FMULTIMAP_H - -#ifdef MULTIMAP_H -#undef MULTIMAP_H -#undef TREE_H -#define __MULTIMAP_WAS_DEFINED -#endif - -#define Allocator far_allocator -#define multimap far_multimap -#define rb_tree far_rb_tree -#include <faralloc.h> -#include <multimap.h> - -#undef MULTIMAP_H -#undef TREE_H - -#ifdef __MULTIMAP_WAS_DEFINED -#define MULTIMAP_H -#define TREE_H -#undef __MULTIMAP_WAS_DEFINED -#endif - -#undef Allocator -#undef multimap -#undef rb_tree - -#endif diff --git a/contrib/libg++/libstdc++/stl/fmultset.h b/contrib/libg++/libstdc++/stl/fmultset.h deleted file mode 100644 index ca9887646ce7b..0000000000000 --- a/contrib/libg++/libstdc++/stl/fmultset.h +++ /dev/null @@ -1,44 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef FMULTISET_H -#define FMULTISET_H - -#ifdef MULTISET_H -#undef MULTISET_H -#undef TREE_H -#define __MULTISET_WAS_DEFINED -#endif - -#define Allocator far_allocator -#define multiset far_multiset -#define rb_tree far_rb_tree -#include <faralloc.h> -#include <multiset.h> - -#undef MULTISET_H -#undef TREE_H - -#ifdef __MULTISET_WAS_DEFINED -#define MULTISET_H -#define TREE_H -#undef __MULTISET_WAS_DEFINED -#endif - -#undef Allocator -#undef multiset -#undef rb_tree - -#endif diff --git a/contrib/libg++/libstdc++/stl/fset.h b/contrib/libg++/libstdc++/stl/fset.h deleted file mode 100644 index b374bc435a6c0..0000000000000 --- a/contrib/libg++/libstdc++/stl/fset.h +++ /dev/null @@ -1,44 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef FSET_H -#define FSET_H - -#ifdef SET_H -#undef SET_H -#undef TREE_H -#define __SET_WAS_DEFINED -#endif - -#define Allocator far_allocator -#define set far_set -#define rb_tree far_rb_tree -#include <faralloc.h> -#include <set.h> - -#undef SET_H -#undef TREE_H - -#ifdef __SET_WAS_DEFINED -#define SET_H -#define TREE_H -#undef __SET_WAS_DEFINED -#endif - -#undef Allocator -#undef set -#undef rb_tree - -#endif diff --git a/contrib/libg++/libstdc++/stl/function.h b/contrib/libg++/libstdc++/stl/function.h deleted file mode 100644 index 46fe55569bbd6..0000000000000 --- a/contrib/libg++/libstdc++/stl/function.h +++ /dev/null @@ -1,282 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef FUNCTION_H -#define FUNCTION_H - -#ifndef __GNUG__ -#include <bool.h> -#endif - -template <class T1, class T2> -inline bool operator!=(const T1& x, const T2& y) { - return !(x == y); -} - -template <class T1, class T2> -inline bool operator>(const T1& x, const T2& y) { - return y < x; -} - -template <class T1, class T2> -inline bool operator<=(const T1& x, const T2& y) { - return !(y < x); -} - -template <class T1, class T2> -inline bool operator>=(const T1& x, const T2& y) { - return !(x < y); -} - -template <class Arg, class Result> -struct unary_function { - typedef Arg argument_type; - typedef Result result_type; -}; - -template <class Arg1, class Arg2, class Result> -struct binary_function { - typedef Arg1 first_argument_type; - typedef Arg2 second_argument_type; - typedef Result result_type; -}; - -template <class T> -struct plus : binary_function<T, T, T> { - T operator()(const T& x, const T& y) const { return x + y; } -}; - -template <class T> -struct minus : binary_function<T, T, T> { - T operator()(const T& x, const T& y) const { return x - y; } -}; - -template <class T> -struct times : binary_function<T, T, T> { - T operator()(const T& x, const T& y) const { return x * y; } -}; - -template <class T> -struct divides : binary_function<T, T, T> { - T operator()(const T& x, const T& y) const { return x / y; } -}; - -template <class T> -#ifdef __GNU__ -struct modulus { - typedef T first_argument_type; - typedef T second_argument_type; - typedef T result_type; - T operator()(const T& x, const T& y) const { return x % y; } -}; -#else -struct modulus : binary_function<T, T, T> { - T operator()(const T& x, const T& y) const { return x % y; } -}; -#endif - -template <class T> -struct negate : unary_function<T, T> { - T operator()(const T& x) const { return -x; } -}; - -template <class T> -struct equal_to : binary_function<T, T, bool> { - bool operator()(const T& x, const T& y) const { return x == y; } -}; - -template <class T> -struct not_equal_to : binary_function<T, T, bool> { - bool operator()(const T& x, const T& y) const { return x != y; } -}; - -template <class T> -struct greater : binary_function<T, T, bool> { - bool operator()(const T& x, const T& y) const { return x > y; } -}; - -template <class T> -struct less : binary_function<T, T, bool> { - bool operator()(const T& x, const T& y) const { return x < y; } -}; - -template <class T> -struct greater_equal : binary_function<T, T, bool> { - bool operator()(const T& x, const T& y) const { return x >= y; } -}; - -template <class T> -struct less_equal : binary_function<T, T, bool> { - bool operator()(const T& x, const T& y) const { return x <= y; } -}; - -template <class T> -struct logical_and : binary_function<T, T, bool> { - bool operator()(const T& x, const T& y) const { return x && y; } -}; - -template <class T> -struct logical_or : binary_function<T, T, bool> { - bool operator()(const T& x, const T& y) const { return x || y; } -}; - -template <class T> -struct logical_not : unary_function<T, bool> { - bool operator()(const T& x) const { return !x; } -}; - -template <class Predicate> -class unary_negate : public unary_function<Predicate::argument_type, bool> { -protected: - Predicate pred; -public: - unary_negate(const Predicate& x) : pred(x) {} - bool operator()(const argument_type& x) const { return !pred(x); } -}; - -template <class Predicate> -unary_negate<Predicate> not1(const Predicate& pred) { - return unary_negate<Predicate>(pred); -} - -template <class Predicate> -class binary_negate - : public binary_function<Predicate::first_argument_type, - Predicate::second_argument_type, bool> { -protected: - Predicate pred; -public: - binary_negate(const Predicate& x) : pred(x) {} - bool operator()(const first_argument_type& x, - const second_argument_type& y) const { - return !pred(x, y); - } -}; - -template <class Predicate> -binary_negate<Predicate> not2(const Predicate& pred) { - return binary_negate<Predicate>(pred); -} - -template <class Operation> -class binder1st : public unary_function<Operation::second_argument_type, - Operation::result_type> { -protected: - Operation op; - Operation::first_argument_type value; -public: - binder1st(const Operation& x, const Operation::first_argument_type& y) - : op(x), value(y) {} - result_type operator()(const argument_type& x) const { - return op(value, x); - } -}; - -template <class Operation, class T> -binder1st<Operation> bind1st(const Operation& op, const T& x) { - return binder1st<Operation>(op, Operation::first_argument_type(x)); -} - -template <class Operation> -class binder2nd : public unary_function<Operation::first_argument_type, - Operation::result_type> { -protected: - Operation op; - Operation::second_argument_type value; -public: - binder2nd(const Operation& x, const Operation::second_argument_type& y) - : op(x), value(y) {} - result_type operator()(const argument_type& x) const { - return op(x, value); - } -}; - -template <class Operation, class T> -binder2nd<Operation> bind2nd(const Operation& op, const T& x) { - return binder2nd<Operation>(op, Operation::second_argument_type(x)); -} - -template <class Operation1, class Operation2> -class unary_compose : public unary_function<Operation2::argument_type, - Operation1::result_type> { -protected: - Operation1 op1; - Operation2 op2; -public: - unary_compose(const Operation1& x, const Operation2& y) : op1(x), op2(y) {} - result_type operator()(const argument_type& x) const { - return op1(op2(x)); - } -}; - -template <class Operation1, class Operation2> -unary_compose<Operation1, Operation2> compose1(const Operation1& op1, - const Operation2& op2) { - return unary_compose<Operation1, Operation2>(op1, op2); -} - -template <class Operation1, class Operation2, class Operation3> -class binary_compose : public unary_function<Operation2::argument_type, - Operation1::result_type> { -protected: - Operation1 op1; - Operation2 op2; - Operation3 op3; -public: - binary_compose(const Operation1& x, const Operation2& y, - const Operation3& z) : op1(x), op2(y), op3(z) { } - result_type operator()(const argument_type& x) const { - return op1(op2(x), op3(x)); - } -}; - -template <class Operation1, class Operation2, class Operation3> -binary_compose<Operation1, Operation2, Operation3> -compose2(const Operation1& op1, const Operation2& op2, const Operation3& op3) { - return binary_compose<Operation1, Operation2, Operation3>(op1, op2, op3); -} - -template <class Arg, class Result> -class pointer_to_unary_function : public unary_function<Arg, Result> { -protected: - Result (*ptr)(Arg); -public: - pointer_to_unary_function() {} - pointer_to_unary_function(Result (*x)(Arg)) : ptr(x) {} - Result operator()(Arg x) const { return ptr(x); } -}; - -template <class Arg, class Result> -pointer_to_unary_function<Arg, Result> ptr_fun(Result (*x)(Arg)) { - return pointer_to_unary_function<Arg, Result>(x); -} - -template <class Arg1, class Arg2, class Result> -class pointer_to_binary_function : public binary_function<Arg1, Arg2, Result> { -protected: - Result (*ptr)(Arg1, Arg2); -public: - pointer_to_binary_function() {} - pointer_to_binary_function(Result (*x)(Arg1, Arg2)) : ptr(x) {} - Result operator()(Arg1 x, Arg2 y) const { return ptr(x, y); } -}; - -template <class Arg1, class Arg2, class Result> -pointer_to_binary_function<Arg1, Arg2, Result> -ptr_fun(Result (*x)(Arg1, Arg2)) { - return pointer_to_binary_function<Arg1, Arg2, Result>(x); -} - -#endif diff --git a/contrib/libg++/libstdc++/stl/hdeque.h b/contrib/libg++/libstdc++/stl/hdeque.h deleted file mode 100644 index 0d47098a06c4a..0000000000000 --- a/contrib/libg++/libstdc++/stl/hdeque.h +++ /dev/null @@ -1,39 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef HDEQUE_H -#define HDEQUE_H - -#ifdef DEQUE_H -#undef DEQUE_H -#define __DEQUE_WAS_DEFINED -#endif - -#define Allocator huge_allocator -#define deque huge_deque -#include <hugalloc.h> -#include <deque.h> - -#undef DEQUE_H - -#ifdef __DEQUE_WAS_DEFINED -#define DEQUE_H -#undef __DEQUE_WAS_DEFINED -#endif - -#undef Allocator -#undef deque - -#endif diff --git a/contrib/libg++/libstdc++/stl/heap.h b/contrib/libg++/libstdc++/stl/heap.h deleted file mode 100644 index 7f2747fc5b91b..0000000000000 --- a/contrib/libg++/libstdc++/stl/heap.h +++ /dev/null @@ -1,193 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef HEAP_H -#define HEAP_H - -template <class RandomAccessIterator, class Distance, class T> -void __push_heap(RandomAccessIterator first, Distance holeIndex, - Distance topIndex, T value) { - Distance parent = (holeIndex - 1) / 2; - while (holeIndex > topIndex && *(first + parent) < value) { - *(first + holeIndex) = *(first + parent); - holeIndex = parent; - parent = (holeIndex - 1) / 2; - } - *(first + holeIndex) = value; -} - -template <class RandomAccessIterator, class T> -inline void __push_heap_aux(RandomAccessIterator first, - RandomAccessIterator last, T*) { - __push_heap(first, (last - first) - 1, 0, T(*(last - 1))); -} - -template <class RandomAccessIterator> -inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) { - __push_heap_aux(first, last, value_type(first)); -} - -template <class RandomAccessIterator, class Distance, class T, class Compare> -void __push_heap(RandomAccessIterator first, Distance holeIndex, - Distance topIndex, T value, Compare comp) { - Distance parent = (holeIndex - 1) / 2; - while (holeIndex > topIndex && comp(*(first + parent), value)) { - *(first + holeIndex) = *(first + parent); - holeIndex = parent; - parent = (holeIndex - 1) / 2; - } - *(first + holeIndex) = value; -} - -template <class RandomAccessIterator, class Compare, class T> -inline void __push_heap_aux(RandomAccessIterator first, - RandomAccessIterator last, Compare comp, T*) { - __push_heap(first, (last - first) - 1, 0, T(*(last - 1)), comp); -} - -template <class RandomAccessIterator, class Compare> -inline void push_heap(RandomAccessIterator first, RandomAccessIterator last, - Compare comp) { - __push_heap_aux(first, last, comp, value_type(first)); -} - -template <class RandomAccessIterator, class Distance, class T> -void __adjust_heap(RandomAccessIterator first, Distance holeIndex, - Distance len, T value) { - Distance topIndex = holeIndex; - Distance secondChild = 2 * holeIndex + 2; - while (secondChild < len) { - if (*(first + secondChild) < *(first + (secondChild - 1))) - secondChild--; - *(first + holeIndex) = *(first + secondChild); - holeIndex = secondChild; - secondChild = 2 * (secondChild + 1); - } - if (secondChild == len) { - *(first + holeIndex) = *(first + (secondChild - 1)); - holeIndex = secondChild - 1; - } - __push_heap(first, holeIndex, topIndex, value); -} - -template <class RandomAccessIterator, class T, class Distance> -inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last, - RandomAccessIterator result, T value, Distance*) { - *result = *first; - __adjust_heap(first, Distance(0), Distance(last - first), value); -} - -template <class RandomAccessIterator, class T> -inline void __pop_heap_aux(RandomAccessIterator first, - RandomAccessIterator last, T*) { - __pop_heap(first, last - 1, last - 1, T(*(last - 1)), distance_type(first)); -} - -template <class RandomAccessIterator> -inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last) { - __pop_heap_aux(first, last, value_type(first)); -} - -template <class RandomAccessIterator, class Distance, class T, class Compare> -void __adjust_heap(RandomAccessIterator first, Distance holeIndex, - Distance len, T value, Compare comp) { - Distance topIndex = holeIndex; - Distance secondChild = 2 * holeIndex + 2; - while (secondChild < len) { - if (comp(*(first + secondChild), *(first + (secondChild - 1)))) - secondChild--; - *(first + holeIndex) = *(first + secondChild); - holeIndex = secondChild; - secondChild = 2 * (secondChild + 1); - } - if (secondChild == len) { - *(first + holeIndex) = *(first + (secondChild - 1)); - holeIndex = secondChild - 1; - } - __push_heap(first, holeIndex, topIndex, value, comp); -} - -template <class RandomAccessIterator, class T, class Compare, class Distance> -inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last, - RandomAccessIterator result, T value, Compare comp, - Distance*) { - *result = *first; - __adjust_heap(first, Distance(0), Distance(last - first), value, comp); -} - -template <class RandomAccessIterator, class T, class Compare> -inline void __pop_heap_aux(RandomAccessIterator first, - RandomAccessIterator last, T*, Compare comp) { - __pop_heap(first, last - 1, last - 1, T(*(last - 1)), comp, - distance_type(first)); -} - -template <class RandomAccessIterator, class Compare> -inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last, - Compare comp) { - __pop_heap_aux(first, last, value_type(first), comp); -} - -template <class RandomAccessIterator, class T, class Distance> -void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*, - Distance*) { - if (last - first < 2) return; - Distance len = last - first; - Distance parent = (len - 2)/2; - - while (true) { - __adjust_heap(first, parent, len, T(*(first + parent))); - if (parent == 0) return; - parent--; - } -} - -template <class RandomAccessIterator> -inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) { - __make_heap(first, last, value_type(first), distance_type(first)); -} - -template <class RandomAccessIterator, class Compare, class T, class Distance> -void __make_heap(RandomAccessIterator first, RandomAccessIterator last, - Compare comp, T*, Distance*) { - if (last - first < 2) return; - Distance len = last - first; - Distance parent = (len - 2)/2; - - while (true) { - __adjust_heap(first, parent, len, T(*(first + parent)), comp); - if (parent == 0) return; - parent--; - } -} - -template <class RandomAccessIterator, class Compare> -inline void make_heap(RandomAccessIterator first, RandomAccessIterator last, - Compare comp) { - __make_heap(first, last, comp, value_type(first), distance_type(first)); -} - -template <class RandomAccessIterator> -void sort_heap(RandomAccessIterator first, RandomAccessIterator last) { - while (last - first > 1) pop_heap(first, last--); -} - -template <class RandomAccessIterator, class Compare> -void sort_heap(RandomAccessIterator first, RandomAccessIterator last, - Compare comp) { - while (last - first > 1) pop_heap(first, last--, comp); -} - -#endif diff --git a/contrib/libg++/libstdc++/stl/hlist.h b/contrib/libg++/libstdc++/stl/hlist.h deleted file mode 100644 index 543ffa7a77eef..0000000000000 --- a/contrib/libg++/libstdc++/stl/hlist.h +++ /dev/null @@ -1,39 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef HLIST_H -#define HLIST_H - -#ifdef LIST_H -#undef LIST_H -#define __LIST_WAS_DEFINED -#endif - -#define Allocator huge_allocator -#define list huge_list -#include <hugalloc.h> -#include <list.h> - -#undef LIST_H - -#ifdef __LIST_WAS_DEFINED -#define LIST_H -#undef __LIST_WAS_DEFINED -#endif - -#undef Allocator -#undef list - -#endif diff --git a/contrib/libg++/libstdc++/stl/hmap.h b/contrib/libg++/libstdc++/stl/hmap.h deleted file mode 100644 index f40abc042ada6..0000000000000 --- a/contrib/libg++/libstdc++/stl/hmap.h +++ /dev/null @@ -1,44 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef HMAP_H -#define HMAP_H - -#ifdef MAP_H -#undef MAP_H -#undef TREE_H -#define __MAP_WAS_DEFINED -#endif - -#define Allocator huge_allocator -#define map huge_map -#define rb_tree huge_rb_tree -#include <hugalloc.h> -#include <map.h> - -#undef MAP_H -#undef TREE_H - -#ifdef __MAP_WAS_DEFINED -#define MAP_H -#define TREE_H -#undef __MAP_WAS_DEFINED -#endif - -#undef Allocator -#undef map -#undef rb_tree - -#endif diff --git a/contrib/libg++/libstdc++/stl/hmultmap.h b/contrib/libg++/libstdc++/stl/hmultmap.h deleted file mode 100644 index 0a8551e9ec530..0000000000000 --- a/contrib/libg++/libstdc++/stl/hmultmap.h +++ /dev/null @@ -1,44 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef HMULTIMAP_H -#define HMULTIMAP_H - -#ifdef MULTIMAP_H -#undef MULTIMAP_H -#undef TREE_H -#define __MULTIMAP_WAS_DEFINED -#endif - -#define Allocator huge_allocator -#define multimap huge_multimap -#define rb_tree huge_rb_tree -#include <hugalloc.h> -#include <multimap.h> - -#undef MULTIMAP_H -#undef TREE_H - -#ifdef __MULTIMAP_WAS_DEFINED -#define MULTIMAP_H -#define TREE_H -#undef __MULTIMAP_WAS_DEFINED -#endif - -#undef Allocator -#undef multimap -#undef rb_tree - -#endif diff --git a/contrib/libg++/libstdc++/stl/hmultset.h b/contrib/libg++/libstdc++/stl/hmultset.h deleted file mode 100644 index e207299603fbc..0000000000000 --- a/contrib/libg++/libstdc++/stl/hmultset.h +++ /dev/null @@ -1,44 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef HMULTISET_H -#define HMULTISET_H - -#ifdef MULTISET_H -#undef MULTISET_H -#undef TREE_H -#define __MULTISET_WAS_DEFINED -#endif - -#define Allocator huge_allocator -#define multiset huge_multiset -#define rb_tree huge_rb_tree -#include <hugalloc.h> -#include <multiset.h> - -#undef MULTISET_H -#undef TREE_H - -#ifdef __MULTISET_WAS_DEFINED -#define MULTISET_H -#define TREE_H -#undef __MULTISET_WAS_DEFINED -#endif - -#undef Allocator -#undef multiset -#undef rb_tree - -#endif diff --git a/contrib/libg++/libstdc++/stl/hset.h b/contrib/libg++/libstdc++/stl/hset.h deleted file mode 100644 index 11a157632168d..0000000000000 --- a/contrib/libg++/libstdc++/stl/hset.h +++ /dev/null @@ -1,44 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef HSET_H -#define HSET_H - -#ifdef SET_H -#undef SET_H -#undef TREE_H -#define __SET_WAS_DEFINED -#endif - -#define Allocator huge_allocator -#define set huge_set -#define rb_tree huge_rb_tree -#include <hugalloc.h> -#include <set.h> - -#undef SET_H -#undef TREE_H - -#ifdef __SET_WAS_DEFINED -#define SET_H -#define TREE_H -#undef __SET_WAS_DEFINED -#endif - -#undef Allocator -#undef set -#undef rb_tree - -#endif diff --git a/contrib/libg++/libstdc++/stl/hugalloc.h b/contrib/libg++/libstdc++/stl/hugalloc.h deleted file mode 100644 index a793ab27fd7cc..0000000000000 --- a/contrib/libg++/libstdc++/stl/hugalloc.h +++ /dev/null @@ -1,38 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef HUGALLOC_H -#define HUGALLOC_H - -#ifdef FARALLOC_H -#undef FARALLOC_H -#define __FARALLOC_WAS_DEFINED -#endif - -#define __far __huge -#define far_allocator huge_allocator -#include <faralloc.h> -#undef __far -#undef far_allocator - -#undef FARALLOC_H - -#ifdef __FARALLOC_WAS_DEFINED -#define FARALLOC_H -#undef __FARALLOC_WAS_DEFINED -#endif - -#endif - diff --git a/contrib/libg++/libstdc++/stl/hvector.h b/contrib/libg++/libstdc++/stl/hvector.h deleted file mode 100644 index e7fb41530db8f..0000000000000 --- a/contrib/libg++/libstdc++/stl/hvector.h +++ /dev/null @@ -1,39 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef HVECTOR_H -#define HVECTOR_H - -#ifdef VECTOR_H -#undef VECTOR_H -#define __VECTOR_WAS_DEFINED -#endif - -#define Allocator huge_allocator -#define vector huge_vector -#include <hugalloc.h> -#include <vector.h> - -#undef VECTOR_H - -#ifdef __VECTOR_WAS_DEFINED -#define VECTOR_H -#undef __VECTOR_WAS_DEFINED -#endif - -#undef Allocator -#undef vector - -#endif diff --git a/contrib/libg++/libstdc++/stl/iterator.h b/contrib/libg++/libstdc++/stl/iterator.h deleted file mode 100644 index 5e51598f200f9..0000000000000 --- a/contrib/libg++/libstdc++/stl/iterator.h +++ /dev/null @@ -1,395 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef ITERATOR_H -#define ITERATOR_H - -#include <stddef.h> -#include <iostream.h> -#ifndef __GNUG__ -#include <bool.h> -#endif -#include <function.h> - -struct input_iterator_tag {}; -struct output_iterator_tag {}; -struct forward_iterator_tag {}; -struct bidirectional_iterator_tag {}; -struct random_access_iterator_tag {}; - -template <class T, class Distance> struct input_iterator {}; -struct output_iterator {}; -template <class T, class Distance> struct forward_iterator {}; -template <class T, class Distance> struct bidirectional_iterator {}; -template <class T, class Distance> struct random_access_iterator {}; - -template <class T, class Distance> -inline input_iterator_tag -iterator_category(const input_iterator<T, Distance>&) { - return input_iterator_tag(); -} - -inline output_iterator_tag iterator_category(const output_iterator&) { - return output_iterator_tag(); -} - -template <class T, class Distance> -inline forward_iterator_tag -iterator_category(const forward_iterator<T, Distance>&) { - return forward_iterator_tag(); -} - -template <class T, class Distance> -inline bidirectional_iterator_tag -iterator_category(const bidirectional_iterator<T, Distance>&) { - return bidirectional_iterator_tag(); -} - -template <class T, class Distance> -inline random_access_iterator_tag -iterator_category(const random_access_iterator<T, Distance>&) { - return random_access_iterator_tag(); -} - -template <class T> -inline random_access_iterator_tag iterator_category(const T*) { - return random_access_iterator_tag(); -} - -template <class T, class Distance> -inline T* value_type(const input_iterator<T, Distance>&) { - return (T*)(0); -} - -template <class T, class Distance> -inline T* value_type(const forward_iterator<T, Distance>&) { - return (T*)(0); -} - -template <class T, class Distance> -inline T* value_type(const bidirectional_iterator<T, Distance>&) { - return (T*)(0); -} - -template <class T, class Distance> -inline T* value_type(const random_access_iterator<T, Distance>&) { - return (T*)(0); -} - -template <class T> -inline T* value_type(const T*) { return (T*)(0); } - -template <class T, class Distance> -inline Distance* distance_type(const input_iterator<T, Distance>&) { - return (Distance*)(0); -} - -template <class T, class Distance> -inline Distance* distance_type(const forward_iterator<T, Distance>&) { - return (Distance*)(0); -} - -template <class T, class Distance> -inline Distance* -distance_type(const bidirectional_iterator<T, Distance>&) { - return (Distance*)(0); -} - -template <class T, class Distance> -inline Distance* -distance_type(const random_access_iterator<T, Distance>&) { - return (Distance*)(0); -} - -template <class T> -inline ptrdiff_t* distance_type(const T*) { return (ptrdiff_t*)(0); } - -template <class Container> -class back_insert_iterator : public output_iterator { -protected: - Container& container; -public: - back_insert_iterator(Container& x) : container(x) {} - back_insert_iterator<Container>& - operator=(const Container::value_type& value) { - container.push_back(value); - return *this; - } - back_insert_iterator<Container>& operator*() { return *this; } - back_insert_iterator<Container>& operator++() { return *this; } - back_insert_iterator<Container>& operator++(int) { return *this; } -}; - -template <class Container> -back_insert_iterator<Container> back_inserter(Container& x) { - return back_insert_iterator<Container>(x); -} - -template <class Container> -class front_insert_iterator : public output_iterator { -protected: - Container& container; -public: - front_insert_iterator(Container& x) : container(x) {} - front_insert_iterator<Container>& - operator=(const Container::value_type& value) { - container.push_front(value); - return *this; - } - front_insert_iterator<Container>& operator*() { return *this; } - front_insert_iterator<Container>& operator++() { return *this; } - front_insert_iterator<Container>& operator++(int) { return *this; } -}; - -template <class Container> -front_insert_iterator<Container> front_inserter(Container& x) { - return front_insert_iterator<Container>(x); -} - -template <class Container> -class insert_iterator : public output_iterator { -protected: - Container& container; - Container::iterator iter; -public: - insert_iterator(Container& x, Container::iterator i) - : container(x), iter(i) {} - insert_iterator<Container>& - operator=(const Container::value_type& value) { - iter = container.insert(iter, value); - ++iter; - return *this; - } - insert_iterator<Container>& operator*() { return *this; } - insert_iterator<Container>& operator++() { return *this; } - insert_iterator<Container>& operator++(int) { return *this; } -}; - -template <class Container, class Iterator> -insert_iterator<Container> inserter(Container& x, Iterator i) { - return insert_iterator<Container>(x, Container::iterator(i)); -} - -template <class BidirectionalIterator, class T, class Reference, - class Distance = ptrdiff_t> -// Reference = T& -class reverse_bidirectional_iterator - : public bidirectional_iterator<T, Distance> { - typedef reverse_bidirectional_iterator<BidirectionalIterator, T, Reference, - Distance> self; - friend bool operator==(const self& x, const self& y); -protected: - BidirectionalIterator current; -public: - reverse_bidirectional_iterator() {} - reverse_bidirectional_iterator(BidirectionalIterator x) : current(x) {} - BidirectionalIterator base() { return current; } - Reference operator*() const { - BidirectionalIterator tmp = current; - return *--tmp; - } - self& operator++() { - --current; - return *this; - } - self operator++(int) { - self tmp = *this; - --current; - return tmp; - } - self& operator--() { - ++current; - return *this; - } - self operator--(int) { - self tmp = *this; - ++current; - return tmp; - } -}; - -template <class BidirectionalIterator, class T, class Reference, - class Distance> -inline bool operator==( - const reverse_bidirectional_iterator<BidirectionalIterator, T, Reference, - Distance>& x, - const reverse_bidirectional_iterator<BidirectionalIterator, T, Reference, - Distance>& y) { - return x.current == y.current; -} - -template <class RandomAccessIterator, class T, class Reference, - class Distance = ptrdiff_t> -// Reference = T& -class reverse_iterator : public random_access_iterator<T, Distance> { - typedef reverse_iterator<RandomAccessIterator, T, Reference, Distance> - self; - friend bool operator==(const self& x, const self& y); - friend bool operator<(const self& x, const self& y); - friend Distance operator-(const self& x, const self& y); - friend self operator+(Distance n, const self& x); -protected: - RandomAccessIterator current; -public: - reverse_iterator() {} - reverse_iterator(RandomAccessIterator x) : current(x) {} - RandomAccessIterator base() { return current; } - Reference operator*() const { return *(current - 1); } - self& operator++() { - --current; - return *this; - } - self operator++(int) { - self tmp = *this; - --current; - return tmp; - } - self& operator--() { - ++current; - return *this; - } - self operator--(int) { - self tmp = *this; - ++current; - return tmp; - } - self operator+(Distance n) const { - return self(current - n); - } - self& operator+=(Distance n) { - current -= n; - return *this; - } - self operator-(Distance n) const { - return self(current + n); - } - self& operator-=(Distance n) { - current += n; - return *this; - } - Reference operator[](Distance n) { return *(*this + n); } -}; - -template <class RandomAccessIterator, class T, class Reference, class Distance> -inline bool operator==(const reverse_iterator<RandomAccessIterator, T, - Reference, Distance>& x, - const reverse_iterator<RandomAccessIterator, T, - Reference, Distance>& y) { - return x.current == y.current; -} - -template <class RandomAccessIterator, class T, class Reference, class Distance> -inline bool operator<(const reverse_iterator<RandomAccessIterator, T, - Reference, Distance>& x, - const reverse_iterator<RandomAccessIterator, T, - Reference, Distance>& y) { - return y.current < x.current; -} - -template <class RandomAccessIterator, class T, class Reference, class Distance> -inline Distance operator-(const reverse_iterator<RandomAccessIterator, T, - Reference, Distance>& x, - const reverse_iterator<RandomAccessIterator, T, - Reference, Distance>& y) { - return y.current - x.current; -} - -template <class RandomAccessIterator, class T, class Reference, class Distance> -inline reverse_iterator<RandomAccessIterator, T, Reference, Distance> -operator+(Distance n, - const reverse_iterator<RandomAccessIterator, T, Reference, - Distance>& x) { - return reverse_iterator<RandomAccessIterator, T, Reference, Distance> - (x.current - n); -} - - -template <class OutputIterator, class T> -class raw_storage_iterator : public output_iterator { -protected: - OutputIterator iter; -public: - raw_storage_iterator(OutputIterator x) : iter(x) {} - raw_storage_iterator<OutputIterator, T>& operator*() { return *this; } - raw_storage_iterator<OutputIterator, T>& operator=(const T& element) { - construct(iter, element); - return *this; - } - raw_storage_iterator<OutputIterator, T>& operator++() { - ++iter; - return *this; - } - raw_storage_iterator<OutputIterator, T> operator++(int) { - raw_storage_iterator<OutputIterator, T> tmp = *this; - ++iter; - return tmp; - } -}; - - -template <class T, class Distance = ptrdiff_t> -class istream_iterator : public input_iterator<T, Distance> { -friend bool operator==(const istream_iterator<T, Distance>& x, - const istream_iterator<T, Distance>& y); -protected: - istream* stream; - T value; - bool end_marker; - void read() { - end_marker = (*stream) ? true : false; - if (end_marker) *stream >> value; - end_marker = (*stream) ? true : false; - } -public: - istream_iterator() : stream(&cin), end_marker(false) {} - istream_iterator(istream& s) : stream(&s) { read(); } - const T& operator*() const { return value; } - istream_iterator<T, Distance>& operator++() { - read(); - return *this; - } - istream_iterator<T, Distance> operator++(int) { - istream_iterator<T, Distance> tmp = *this; - read(); - return tmp; - } -}; - -template <class T, class Distance> -bool operator==(const istream_iterator<T, Distance>& x, - const istream_iterator<T, Distance>& y) { - return x.stream == y.stream && x.end_marker == y.end_marker || - x.end_marker == false && y.end_marker == false; -} - -template <class T> -class ostream_iterator : public output_iterator { -protected: - ostream* stream; - char* string; -public: - ostream_iterator(ostream& s) : stream(&s), string(0) {} - ostream_iterator(ostream& s, char* c) : stream(&s), string(c) {} - ostream_iterator<T>& operator=(const T& value) { - *stream << value; - if (string) *stream << string; - return *this; - } - ostream_iterator<T>& operator*() { return *this; } - ostream_iterator<T>& operator++() { return *this; } - ostream_iterator<T>& operator++(int) { return *this; } -}; - -#endif diff --git a/contrib/libg++/libstdc++/stl/lbvector.h b/contrib/libg++/libstdc++/stl/lbvector.h deleted file mode 100644 index 763666c3d39b2..0000000000000 --- a/contrib/libg++/libstdc++/stl/lbvector.h +++ /dev/null @@ -1,39 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef LBVECTOR_H -#define LBVECTOR_H - -#ifdef BVECTOR_H -#undef BVECTOR_H -#define __BVECTOR_WAS_DEFINED -#endif - -#define Allocator long_allocator -#define bit_vector long_bit_vector -#include <lngalloc.h> -#include <bvector.h> - -#undef BVECTOR_H - -#ifdef __BVECTOR_WAS_DEFINED -#define BVECTOR_H -#undef __BVECTOR_WAS_DEFINED -#endif - -#undef Allocator -#undef bit_vector - -#endif diff --git a/contrib/libg++/libstdc++/stl/ldeque.h b/contrib/libg++/libstdc++/stl/ldeque.h deleted file mode 100644 index 4c8761c9f8bed..0000000000000 --- a/contrib/libg++/libstdc++/stl/ldeque.h +++ /dev/null @@ -1,39 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef LDEQUE_H -#define LDEQUE_H - -#ifdef DEQUE_H -#undef DEQUE_H -#define __DEQUE_WAS_DEFINED -#endif - -#define Allocator long_allocator -#define deque long_deque -#include <lngalloc.h> -#include <deque.h> - -#undef DEQUE_H - -#ifdef __DEQUE_WAS_DEFINED -#define DEQUE_H -#undef __DEQUE_WAS_DEFINED -#endif - -#undef Allocator -#undef deque - -#endif diff --git a/contrib/libg++/libstdc++/stl/list.h b/contrib/libg++/libstdc++/stl/list.h deleted file mode 100644 index 42b5d0f5f6734..0000000000000 --- a/contrib/libg++/libstdc++/stl/list.h +++ /dev/null @@ -1,531 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef LIST_H -#define LIST_H - -#include <function.h> -#include <algobase.h> -#include <iterator.h> -#ifndef __GNUG__ -#include <bool.h> -#endif - -#ifndef Allocator -#define Allocator allocator -#include <defalloc.h> -#endif - -#ifndef list -#define list list -#endif - -template <class T> -class list { -protected: - typedef Allocator<void>::pointer void_pointer; - struct list_node; - friend list_node; - struct list_node { - void_pointer next; - void_pointer prev; - T data; - }; -#ifndef __GNUG__ - static Allocator<list_node> list_node_allocator; - static Allocator<T> value_allocator; -#endif -public: - typedef T value_type; - typedef Allocator<T> value_allocator_type; - typedef Allocator<T>::pointer pointer; - typedef Allocator<T>::reference reference; - typedef Allocator<T>::const_reference const_reference; - typedef Allocator<list_node> list_node_allocator_type; - typedef Allocator<list_node>::pointer link_type; - typedef Allocator<list_node>::size_type size_type; - typedef Allocator<list_node>::difference_type difference_type; -protected: -#ifdef __GNUG__ - link_type get_node() { return (link_type)(::operator new(sizeof(list_node))); } - void put_node(link_type p) { ::operator delete(p); } -#else - size_type buffer_size() { - return list_node_allocator.init_page_size(); - } - struct list_node_buffer; - friend list_node_buffer; - struct list_node_buffer { - void_pointer next_buffer; - link_type buffer; - }; -public: - typedef Allocator<list_node_buffer> buffer_allocator_type; - typedef Allocator<list_node_buffer>::pointer buffer_pointer; -protected: - static Allocator<list_node_buffer> buffer_allocator; - static buffer_pointer buffer_list; - static link_type free_list; - static link_type next_avail; - static link_type last; - void add_new_buffer() { - buffer_pointer tmp = buffer_allocator.allocate((size_type)1); - tmp->buffer = list_node_allocator.allocate(buffer_size()); - tmp->next_buffer = buffer_list; - buffer_list = tmp; - next_avail = buffer_list->buffer; - last = next_avail + buffer_size(); - } - static size_type number_of_lists; - void deallocate_buffers(); - link_type get_node() { - link_type tmp = free_list; - return free_list ? (free_list = (link_type)(free_list->next), tmp) - : (next_avail == last ? (add_new_buffer(), next_avail++) - : next_avail++); - // ugly code for inlining - avoids multiple returns - } - void put_node(link_type p) { - p->next = free_list; - free_list = p; - } -#endif - - link_type node; - size_type length; -public: - class iterator; - class const_iterator; - class iterator : public bidirectional_iterator<T, difference_type> { - friend class list<T>; - friend class const_iterator; -// friend bool operator==(const iterator& x, const iterator& y); - protected: - link_type node; - iterator(link_type x) : node(x) {} - public: - iterator() {} - bool operator==(const iterator& x) const { return node == x.node; } - reference operator*() const { return (*node).data; } - iterator& operator++() { - node = (link_type)((*node).next); - return *this; - } - iterator operator++(int) { - iterator tmp = *this; - ++*this; - return tmp; - } - iterator& operator--() { - node = (link_type)((*node).prev); - return *this; - } - iterator operator--(int) { - iterator tmp = *this; - --*this; - return tmp; - } - }; - class const_iterator : public bidirectional_iterator<T, difference_type> { - friend class list<T>; - protected: - link_type node; - const_iterator(link_type x) : node(x) {} - public: - const_iterator() {} - const_iterator(const iterator& x) : node(x.node) {} - bool operator==(const const_iterator& x) const { return node == x.node; } - const_reference operator*() const { return (*node).data; } - const_iterator& operator++() { - node = (link_type)((*node).next); - return *this; - } - const_iterator operator++(int) { - const_iterator tmp = *this; - ++*this; - return tmp; - } - const_iterator& operator--() { - node = (link_type)((*node).prev); - return *this; - } - const_iterator operator--(int) { - const_iterator tmp = *this; - --*this; - return tmp; - } - }; - 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; - list() : length(0) { -#ifndef __GNUG__ - ++number_of_lists; -#endif - node = get_node(); - (*node).next = node; - (*node).prev = node; - } - 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 length == 0; } - size_type size() const { return length; } -#ifndef __GNUG__ - size_type max_size() const { return list_node_allocator.max_size(); } -#endif - reference front() { return *begin(); } - const_reference front() const { return *begin(); } - reference back() { return *(--end()); } - const_reference back() const { return *(--end()); } - void swap(list<T>& x) { - ::swap(node, x.node); - ::swap(length, x.length); - } - iterator insert(iterator position, const T& x) { - link_type tmp = get_node(); -#ifdef __GNUG__ - construct(&(*tmp).data, x); -#else - construct(value_allocator.address((*tmp).data), x); -#endif - (*tmp).next = position.node; - (*tmp).prev = (*position.node).prev; - (*(link_type((*position.node).prev))).next = tmp; - (*position.node).prev = tmp; - ++length; - return tmp; - } -#ifdef __GNUG__ - void insert(iterator position, const T* first, const T* last) { - while (first != last) insert(position, *first++); - } - void insert(iterator position, const_iterator first, - const_iterator last) { - while (first != last) insert(position, *first++); - } - void insert(iterator position, size_type n, const T& x) { - while (n--) insert(position, x); - } -#else - void insert(iterator position, const T* first, const T* last); - void insert(iterator position, const_iterator first, - const_iterator last); - void insert(iterator position, size_type n, const T& x); -#endif - void push_front(const T& x) { insert(begin(), x); } - void push_back(const T& x) { insert(end(), x); } - void erase(iterator position) { - (*(link_type((*position.node).prev))).next = (*position.node).next; - (*(link_type((*position.node).next))).prev = (*position.node).prev; -#ifdef __GNUG__ - destroy(&(*position.node).data); -#else - destroy(value_allocator.address((*position.node).data)); -#endif - put_node(position.node); - --length; - } -#ifdef __GNUG__ - void erase(iterator first, iterator last) { - while (first != last) erase(first++); - } -#else - void erase(iterator first, iterator last); -#endif - void pop_front() { erase(begin()); } - void pop_back() { - iterator tmp = end(); - erase(--tmp); - } - list(size_type n, const T& value = T()) : length(0) { -#ifndef __GNUG__ - ++number_of_lists; -#endif - node = get_node(); - (*node).next = node; - (*node).prev = node; - insert(begin(), n, value); - } - list(const T* first, const T* last) : length(0) { -#ifndef __GNUG__ - ++number_of_lists; -#endif - node = get_node(); - (*node).next = node; - (*node).prev = node; - insert(begin(), first, last); - } - list(const list<T>& x) : length(0) { -#ifndef __GNUG__ - ++number_of_lists; -#endif - node = get_node(); - (*node).next = node; - (*node).prev = node; - insert(begin(), x.begin(), x.end()); - } - ~list() { - erase(begin(), end()); - put_node(node); -#ifndef __GNUG__ - if (--number_of_lists == 0) deallocate_buffers(); -#endif - } - list<T>& operator=(const list<T>& x); -protected: - void transfer(iterator position, iterator first, iterator 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<T>& x) { - if (!x.empty()) { - transfer(position, x.begin(), x.end()); - length += x.length; - x.length = 0; - } - } - void splice(iterator position, list<T>& x, iterator i) { - iterator j = i; - if (position == i || position == ++j) return; - transfer(position, i, j); - ++length; - --x.length; - } - void splice(iterator position, list<T>& x, iterator first, iterator last) { - if (first != last) { - if (&x != this) { - difference_type n = 0; - distance(first, last, n); - x.length -= n; - length += n; - } - transfer(position, first, last); - } - } - void remove(const T& value); - void unique(); - void merge(list<T>& x); - void reverse(); - void sort(); -#ifdef __GNUG__ - friend difference_type* distance_type(const iterator&) { - return (difference_type*)(0); - } - friend T* value_type(const iterator&) { - return (T*)(0); - } - friend bidirectional_iterator_tag iterator_category(iterator) { - return bidirectional_iterator_tag(); - } -#endif -}; - -#ifndef __GNUG__ -template <class T> -list<T>::buffer_pointer list<T>::buffer_list = 0; - -template <class T> -list<T>::link_type list<T>::free_list = 0; - -template <class T> -list<T>::link_type list<T>::next_avail = 0; - -template <class T> -list<T>::link_type list<T>::last = 0; - -template <class T> -list<T>::size_type list<T>::number_of_lists = 0; - -template <class T> -list<T>::list_node_allocator_type list<T>::list_node_allocator; - -template <class T> -list<T>::value_allocator_type list<T>::value_allocator; - -template <class T> -list<T>::buffer_allocator_type list<T>::buffer_allocator; -#endif - -/* - * currently the following does not work - made into a member function - -template <class T> -inline bool operator==(const list<T>::iterator& x, const list<T>::iterator& y) { - return x.node == y.node; -} -*/ - -template <class T> -inline bool operator==(const list<T>& x, const list<T>& y) { - return x.size() == y.size() && equal(x.begin(), x.end(), y.begin()); -} - -template <class T> -inline bool operator<(const list<T>& x, const list<T>& y) { - return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); -} - -#ifndef __GNUG__ -template <class T> -void list<T>::deallocate_buffers() { - while (buffer_list) { - buffer_pointer tmp = buffer_list; - buffer_list = (buffer_pointer)(buffer_list->next_buffer); - list_node_allocator.deallocate(tmp->buffer); - buffer_allocator.deallocate(tmp); - } - free_list = 0; - next_avail = 0; - last = 0; -} -#endif - -#ifndef __GNUG__ -template <class T> -void list<T>::insert(iterator position, const T* first, const T* last) { - while (first != last) insert(position, *first++); -} - -template <class T> -void list<T>::insert(iterator position, const_iterator first, - const_iterator last) { - while (first != last) insert(position, *first++); -} - -template <class T> -void list<T>::insert(iterator position, size_type n, const T& x) { - while (n--) insert(position, x); -} - -template <class T> -void list<T>::erase(iterator first, iterator last) { - while (first != last) erase(first++); -} -#endif - -template <class T> -list<T>& list<T>::operator=(const list<T>& 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> -void list<T>::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> -void list<T>::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> -void list<T>::merge(list<T>& 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); - length += x.length; - x.length= 0; -} - -template <class T> -void list<T>::reverse() { - if (size() < 2) return; - for (iterator first = ++begin(); first != end();) { - iterator old = first++; - transfer(begin(), old, first); - } -} - -template <class T> -void list<T>::sort() { - if (size() < 2) return; - list<T> carry; - list<T> 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]); -} - -#undef Allocator -#undef list - -#endif diff --git a/contrib/libg++/libstdc++/stl/llist.h b/contrib/libg++/libstdc++/stl/llist.h deleted file mode 100644 index 07ee6113a0963..0000000000000 --- a/contrib/libg++/libstdc++/stl/llist.h +++ /dev/null @@ -1,39 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef LLIST_H -#define LLIST_H - -#ifdef LIST_H -#undef LIST_H -#define __LIST_WAS_DEFINED -#endif - -#define Allocator long_allocator -#define list long_list -#include <lngalloc.h> -#include <list.h> - -#undef LIST_H - -#ifdef __LIST_WAS_DEFINED -#define LIST_H -#undef __LIST_WAS_DEFINED -#endif - -#undef Allocator -#undef list - -#endif diff --git a/contrib/libg++/libstdc++/stl/lmap.h b/contrib/libg++/libstdc++/stl/lmap.h deleted file mode 100644 index da1eeba6c8cc5..0000000000000 --- a/contrib/libg++/libstdc++/stl/lmap.h +++ /dev/null @@ -1,44 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef LMAP_H -#define LMAP_H - -#ifdef MAP_H -#undef MAP_H -#undef TREE_H -#define __MAP_WAS_DEFINED -#endif - -#define Allocator long_allocator -#define map long_map -#define rb_tree long_rb_tree -#include <lngalloc.h> -#include <map.h> - -#undef MAP_H -#undef TREE_H - -#ifdef __MAP_WAS_DEFINED -#define MAP_H -#define TREE_H -#undef __MAP_WAS_DEFINED -#endif - -#undef Allocator -#undef map -#undef rb_tree - -#endif diff --git a/contrib/libg++/libstdc++/stl/lmultmap.h b/contrib/libg++/libstdc++/stl/lmultmap.h deleted file mode 100644 index 1a87e3372d8d0..0000000000000 --- a/contrib/libg++/libstdc++/stl/lmultmap.h +++ /dev/null @@ -1,44 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef LMULTIMAP_H -#define LMULTIMAP_H - -#ifdef MULTIMAP_H -#undef MULTIMAP_H -#undef TREE_H -#define __MULTIMAP_WAS_DEFINED -#endif - -#define Allocator long_allocator -#define multimap long_multimap -#define rb_tree long_rb_tree -#include <lngalloc.h> -#include <multimap.h> - -#undef MULTIMAP_H -#undef TREE_H - -#ifdef __MULTIMAP_WAS_DEFINED -#define MULTIMAP_H -#define TREE_H -#undef __MULTIMAP_WAS_DEFINED -#endif - -#undef Allocator -#undef multimap -#undef rb_tree - -#endif diff --git a/contrib/libg++/libstdc++/stl/lmultset.h b/contrib/libg++/libstdc++/stl/lmultset.h deleted file mode 100644 index bb1571f6c9064..0000000000000 --- a/contrib/libg++/libstdc++/stl/lmultset.h +++ /dev/null @@ -1,44 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef LMULTISET_H -#define LMULTISET_H - -#ifdef MULTISET_H -#undef MULTISET_H -#undef TREE_H -#define __MULTISET_WAS_DEFINED -#endif - -#define Allocator long_allocator -#define multiset long_multiset -#define rb_tree long_rb_tree -#include <lngalloc.h> -#include <multiset.h> - -#undef MULTISET_H -#undef TREE_H - -#ifdef __MULTISET_WAS_DEFINED -#define MULTISET_H -#define TREE_H -#undef __MULTISET_WAS_DEFINED -#endif - -#undef Allocator -#undef multiset -#undef rb_tree - -#endif diff --git a/contrib/libg++/libstdc++/stl/lngalloc.h b/contrib/libg++/libstdc++/stl/lngalloc.h deleted file mode 100644 index 6685ea54511c5..0000000000000 --- a/contrib/libg++/libstdc++/stl/lngalloc.h +++ /dev/null @@ -1,54 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef LNGALLOC_H -#define LNGALLOC_H - -#include <limits.h> -#include <algobase.h> -#include <defalloc.h> - -template <class T> -class long_allocator { -public: - typedef T value_type; - typedef T* pointer; - typedef const T* const_pointer; - typedef T& reference; - typedef const T& const_reference; - typedef unsigned long size_type; - typedef long difference_type; - pointer allocate(size_type n) { - return ::allocate((difference_type)n, (pointer)0); - } - void deallocate(pointer p) { ::deallocate(p); } - pointer address(reference x) { return (pointer)&x; } - const_pointer const_address(const_reference x) { - return (const_pointer)&x; - } - size_type init_page_size() { - return max(size_type(1), size_type(4096/sizeof(T))); - } - size_type max_size() const { - return max(size_type(1), size_type(ULONG_MAX/sizeof(T))); - } -}; - -class long_allocator<void> { -public: - typedef void* pointer; -}; - -#endif diff --git a/contrib/libg++/libstdc++/stl/lset.h b/contrib/libg++/libstdc++/stl/lset.h deleted file mode 100644 index e4d52f7c39e19..0000000000000 --- a/contrib/libg++/libstdc++/stl/lset.h +++ /dev/null @@ -1,44 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef LSET_H -#define LSET_H - -#ifdef SET_H -#undef SET_H -#undef TREE_H -#define __SET_WAS_DEFINED -#endif - -#define Allocator long_allocator -#define set long_set -#define rb_tree long_rb_tree -#include <lngalloc.h> -#include <set.h> - -#undef SET_H -#undef TREE_H - -#ifdef __SET_WAS_DEFINED -#define SET_H -#define TREE_H -#undef __SET_WAS_DEFINED -#endif - -#undef Allocator -#undef set -#undef rb_tree - -#endif diff --git a/contrib/libg++/libstdc++/stl/map.h b/contrib/libg++/libstdc++/stl/map.h deleted file mode 100644 index 5c1c30d49e675..0000000000000 --- a/contrib/libg++/libstdc++/stl/map.h +++ /dev/null @@ -1,150 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef MAP_H -#define MAP_H - -#ifndef Allocator -#define Allocator allocator -#include <defalloc.h> -#endif - -#include <tree.h> - -template <class Key, class T, class Compare> -class map { -public: - -// typedefs: - - typedef Key key_type; - typedef pair<const Key, T> value_type; - typedef Compare key_compare; - - class value_compare - : public binary_function<value_type, value_type, bool> { - friend class map<Key, T, Compare>; - protected : - Compare comp; - value_compare(Compare c) : comp(c) {} - public: - bool operator()(const value_type& x, const value_type& y) const { - return comp(x.first, y.first); - } - }; - -private: - typedef rb_tree<key_type, value_type, - select1st<value_type, key_type>, key_compare> rep_type; - rep_type t; // red-black tree representing map -public: - typedef rep_type::pointer pointer; - typedef rep_type::reference reference; - typedef rep_type::const_reference const_reference; - typedef rep_type::iterator iterator; - typedef rep_type::const_iterator const_iterator; - typedef rep_type::reverse_iterator reverse_iterator; - typedef rep_type::const_reverse_iterator const_reverse_iterator; - typedef rep_type::size_type size_type; - typedef rep_type::difference_type difference_type; - -// allocation/deallocation - - map(const Compare& comp = Compare()) : t(comp, false) {} - map(const value_type* first, const value_type* last, - const Compare& comp = Compare()) : t(first, last, comp, false) {} - map(const map<Key, T, Compare>& x) : t(x.t, false) {} - map<Key, T, Compare>& operator=(const map<Key, T, Compare>& x) { - t = x.t; - return *this; - } - -// accessors: - - key_compare key_comp() const { return t.key_comp(); } - value_compare value_comp() const { return value_compare(t.key_comp()); } - iterator begin() { return t.begin(); } - const_iterator begin() const { return t.begin(); } - iterator end() { return t.end(); } - const_iterator end() const { return t.end(); } - reverse_iterator rbegin() { return t.rbegin(); } - const_reverse_iterator rbegin() const { return t.rbegin(); } - reverse_iterator rend() { return t.rend(); } - const_reverse_iterator rend() const { return t.rend(); } - bool empty() const { return t.empty(); } - size_type size() const { return t.size(); } -#ifndef __GNUG__ - size_type max_size() const { return t.max_size(); } -#endif - Allocator<T>::reference operator[](const key_type& k) { - return (*((insert(value_type(k, T()))).first)).second; - } - void swap(map<Key, T, Compare>& x) { t.swap(x.t); } - -// insert/erase - - typedef pair<iterator, bool> pair_iterator_bool; - // typedef done to get around compiler bug - pair_iterator_bool insert(const value_type& x) { return t.insert(x); } - iterator insert(iterator position, const value_type& x) { - return t.insert(position, x); - } - void insert(const value_type* first, const value_type* last) { - t.insert(first, last); - } - void erase(iterator position) { t.erase(position); } - size_type erase(const key_type& x) { return t.erase(x); } - void erase(iterator first, iterator last) { t.erase(first, last); } - -// map operations: - - iterator find(const key_type& x) { return t.find(x); } - const_iterator find(const key_type& x) const { return t.find(x); } - size_type count(const key_type& x) const { return t.count(x); } - iterator lower_bound(const key_type& x) {return t.lower_bound(x); } - const_iterator lower_bound(const key_type& x) const { - return t.lower_bound(x); - } - iterator upper_bound(const key_type& x) {return t.upper_bound(x); } - const_iterator upper_bound(const key_type& x) const { - return t.upper_bound(x); - } - typedef pair<iterator, iterator> pair_iterator_iterator; - // typedef done to get around compiler bug - pair_iterator_iterator equal_range(const key_type& x) { - return t.equal_range(x); - } - typedef pair<const_iterator, const_iterator> pair_citerator_citerator; - // typedef done to get around compiler bug - pair_citerator_citerator equal_range(const key_type& x) const { - return t.equal_range(x); - } -}; - -template <class Key, class T, class Compare> -inline bool operator==(const map<Key, T, Compare>& x, - const map<Key, T, Compare>& y) { - return x.size() == y.size() && equal(x.begin(), x.end(), y.begin()); -} - -template <class Key, class T, class Compare> -inline bool operator<(const map<Key, T, Compare>& x, - const map<Key, T, Compare>& y) { - return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); -} - -#undef Allocator - -#endif diff --git a/contrib/libg++/libstdc++/stl/multimap.h b/contrib/libg++/libstdc++/stl/multimap.h deleted file mode 100644 index 2478e2419fa61..0000000000000 --- a/contrib/libg++/libstdc++/stl/multimap.h +++ /dev/null @@ -1,142 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef MULTIMAP_H -#define MULTIMAP_H - -#ifndef Allocator -#define Allocator allocator -#include <defalloc.h> -#endif - -#include <tree.h> - -template <class Key, class T, class Compare> -class multimap { -public: - -// typedefs: - - typedef Key key_type; - typedef pair<const Key, T> value_type; - typedef Compare key_compare; - - class value_compare - : public binary_function<value_type, value_type, bool> { - friend class multimap<Key, T, Compare>; - protected: - Compare comp; - value_compare(Compare c) : comp(c) {} - public: - bool operator()(const value_type& x, const value_type& y) const { - return comp(x.first, y.first); - } - }; - -private: - typedef rb_tree<key_type, value_type, - select1st<value_type, key_type>, key_compare> rep_type; - rep_type t; // red-black tree representing multimap -public: - typedef rep_type::reference reference; - typedef rep_type::const_reference const_reference; - typedef rep_type::iterator iterator; - typedef rep_type::const_iterator const_iterator; - typedef rep_type::reverse_iterator reverse_iterator; - typedef rep_type::const_reverse_iterator const_reverse_iterator; - typedef rep_type::size_type size_type; - typedef rep_type::difference_type difference_type; - -// allocation/deallocation - - multimap(const Compare& comp = Compare()) : t(comp, true) { } - multimap(const value_type* first, const value_type* last, - const Compare& comp = Compare()) : t(first, last, comp, true) { } - multimap(const multimap<Key, T, Compare>& x) : t(x.t, true) { } - multimap<Key, T, Compare>& operator=(const multimap<Key, T, Compare>& x) { - t = x.t; - return *this; - } - -// accessors: - - key_compare key_comp() const { return t.key_comp(); } - value_compare value_comp() const { return value_compare(t.key_comp()); } - iterator begin() { return t.begin(); } - const_iterator begin() const { return t.begin(); } - iterator end() { return t.end(); } - const_iterator end() const { return t.end(); } - reverse_iterator rbegin() { return t.rbegin(); } - const_reverse_iterator rbegin() const { return t.rbegin(); } - reverse_iterator rend() { return t.rend(); } - const_reverse_iterator rend() const { return t.rend(); } - bool empty() const { return t.empty(); } - size_type size() const { return t.size(); } - size_type max_size() const { return t.max_size(); } - void swap(multimap<Key, T, Compare>& x) { t.swap(x.t); } - -// insert/erase - - iterator insert(const value_type& x) { return t.insert(x).first; } - iterator insert(iterator position, const value_type& x) { - return t.insert(position, x); - } - void insert(const value_type* first, const value_type* last) { - t.insert(first, last); - } - void erase(iterator position) { t.erase(position); } - size_type erase(const key_type& x) { return t.erase(x); } - void erase(iterator first, iterator last) { t.erase(first, last); } - -// multimap operations: - - iterator find(const key_type& x) { return t.find(x); } - const_iterator find(const key_type& x) const { return t.find(x); } - size_type count(const key_type& x) const { return t.count(x); } - iterator lower_bound(const key_type& x) {return t.lower_bound(x); } - const_iterator lower_bound(const key_type& x) const { - return t.lower_bound(x); - } - iterator upper_bound(const key_type& x) {return t.upper_bound(x); } - const_iterator upper_bound(const key_type& x) const { - return t.upper_bound(x); - } - typedef pair<iterator, iterator> pair_iterator_iterator; - // typedef done to get around compiler bug - pair_iterator_iterator equal_range(const key_type& x) { - return t.equal_range(x); - } - typedef pair<const_iterator, const_iterator> pair_citerator_citerator; - // typedef done to get around compiler bug - pair_citerator_citerator equal_range(const key_type& x) const { - return t.equal_range(x); - } -}; - -template <class Key, class T, class Compare> -inline bool operator==(const multimap<Key, T, Compare>& x, - const multimap<Key, T, Compare>& y) { - return x.size() == y.size() && equal(x.begin(), x.end(), y.begin()); -} - -template <class Key, class T, class Compare> -inline bool operator<(const multimap<Key, T, Compare>& x, - const multimap<Key, T, Compare>& y) { - return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); -} - -#undef Allocator - -#endif diff --git a/contrib/libg++/libstdc++/stl/multiset.h b/contrib/libg++/libstdc++/stl/multiset.h deleted file mode 100644 index 1ee6d93e352d5..0000000000000 --- a/contrib/libg++/libstdc++/stl/multiset.h +++ /dev/null @@ -1,129 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef MULTISET_H -#define MULTISET_H - -#ifndef Allocator -#define Allocator allocator -#include <defalloc.h> -#endif - -#include <tree.h> - -template <class Key, class Compare> -class multiset { -public: -// typedefs: - - typedef Key key_type; - typedef Key value_type; - typedef Compare key_compare; - typedef Compare value_compare; -private: - typedef rb_tree<key_type, value_type, - ident<value_type, key_type>, key_compare> rep_type; - rep_type t; // red-black tree representing multiset -public: - typedef rep_type::const_reference reference; - typedef rep_type::const_reference const_reference; - typedef rep_type::const_iterator iterator; - typedef rep_type::const_iterator const_iterator; - typedef rep_type::const_reverse_iterator reverse_iterator; - typedef rep_type::const_reverse_iterator const_reverse_iterator; - typedef rep_type::size_type size_type; - typedef rep_type::difference_type difference_type; - -// allocation/deallocation - - multiset(const Compare& comp = Compare()) : t(comp, true) {} - multiset(const value_type* first, const value_type* last, - const Compare& comp = Compare()) : t(comp, true) { - for (const value_type* i = first; i != last; ++i) - t.insert(*i); - } - multiset(const multiset<Key, Compare>& x) : t(x.t, true) {} - multiset<Key, Compare>& operator=(const multiset<Key, Compare>& x) { - t = x.t; - return *this; - } - -// accessors: - - key_compare key_comp() const { return t.key_comp(); } - value_compare value_comp() const { return t.key_comp(); } - iterator begin() const { return t.begin(); } - iterator end() const { return t.end(); } - reverse_iterator rbegin() const { return t.rbegin(); } - reverse_iterator rend() const { return t.rend(); } - bool empty() const { return t.empty(); } - size_type size() const { return t.size(); } - size_type max_size() const { return t.max_size(); } - void swap(multiset<Key, Compare>& x) { t.swap(x.t); } - -// insert/erase - iterator insert(const value_type& x) { - return t.insert(x).first; - } - iterator insert(iterator position, const value_type& x) { - return t.insert((rep_type::iterator&)position, x); - } - void insert(const value_type* first, const value_type* last) { - for (const value_type* i = first; i != last; ++i) - t.insert(*i); - } - void erase(iterator position) { - t.erase((rep_type::iterator&)position); - } - size_type erase(const key_type& x) { - return t.erase(x); - } - void erase(iterator first, iterator last) { - t.erase((rep_type::iterator&)first, - (rep_type::iterator&)last); - } - -// multiset operations: - - iterator find(const key_type& x) const { return t.find(x); } - size_type count(const key_type& x) const { return t.count(x); } - iterator lower_bound(const key_type& x) const { - return t.lower_bound(x); - } - iterator upper_bound(const key_type& x) const { - return t.upper_bound(x); - } - typedef pair<iterator, iterator> pair_iterator_iterator; - // typedef done to get around compiler bug - pair_iterator_iterator equal_range(const key_type& x) const { - return t.equal_range(x); - } -}; - -template <class Key, class Compare> -inline bool operator==(const multiset<Key, Compare>& x, - const multiset<Key, Compare>& y) { - return x.size() == y.size() && equal(x.begin(), x.end(), y.begin()); -} - -template <class Key, class Compare> -inline bool operator<(const multiset<Key, Compare>& x, - const multiset<Key, Compare>& y) { - return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); -} - -#undef Allocator - -#endif diff --git a/contrib/libg++/libstdc++/stl/neralloc.h b/contrib/libg++/libstdc++/stl/neralloc.h deleted file mode 100644 index c66e9b366a02e..0000000000000 --- a/contrib/libg++/libstdc++/stl/neralloc.h +++ /dev/null @@ -1,38 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef NEARALLOC_H -#define NEARALLOC_H - -#ifdef FARALLOC_H -#undef FARALLOC_H -#define __FARALLOC_WAS_DEFINED -#endif - -#define __far __near -#define far_allocator near_allocator -#include <faralloc.h> -#undef __far -#undef far_allocator - -#undef FARALLOC_H - -#ifdef __FARALLOC_WAS_DEFINED -#define FARALLOC_H -#undef __FARALLOC_WAS_DEFINED -#endif - -#endif - diff --git a/contrib/libg++/libstdc++/stl/nmap.h b/contrib/libg++/libstdc++/stl/nmap.h deleted file mode 100644 index 99754c7816924..0000000000000 --- a/contrib/libg++/libstdc++/stl/nmap.h +++ /dev/null @@ -1,44 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef NMAP_H -#define NMAP_H - -#ifdef MAP_H -#undef MAP_H -#undef TREE_H -#define __MAP_WAS_DEFINED -#endif - -#define Allocator near_allocator -#define map near_map -#define rb_tree near_rb_tree -#include <neralloc.h> -#include <map.h> - -#undef MAP_H -#undef TREE_H - -#ifdef __MAP_WAS_DEFINED -#define MAP_H -#define TREE_H -#undef __MAP_WAS_DEFINED -#endif - -#undef Allocator -#undef map -#undef rb_tree - -#endif diff --git a/contrib/libg++/libstdc++/stl/nmultmap.h b/contrib/libg++/libstdc++/stl/nmultmap.h deleted file mode 100644 index a6ad67c4fbb2e..0000000000000 --- a/contrib/libg++/libstdc++/stl/nmultmap.h +++ /dev/null @@ -1,44 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef NMULTIMAP_H -#define NMULTIMAP_H - -#ifdef MULTIMAP_H -#undef MULTIMAP_H -#undef TREE_H -#define __MULTIMAP_WAS_DEFINED -#endif - -#define Allocator near_allocator -#define multimap near_multimap -#define rb_tree near_rb_tree -#include <neralloc.h> -#include <multimap.h> - -#undef MULTIMAP_H -#undef TREE_H - -#ifdef __MULTIMAP_WAS_DEFINED -#define MULTIMAP_H -#define TREE_H -#undef __MULTIMAP_WAS_DEFINED -#endif - -#undef Allocator -#undef multimap -#undef rb_tree - -#endif diff --git a/contrib/libg++/libstdc++/stl/nmultset.h b/contrib/libg++/libstdc++/stl/nmultset.h deleted file mode 100644 index 3a0ad30db0d61..0000000000000 --- a/contrib/libg++/libstdc++/stl/nmultset.h +++ /dev/null @@ -1,44 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef NMULTISET_H -#define NMULTISET_H - -#ifdef MULTISET_H -#undef MULTISET_H -#undef TREE_H -#define __MULTISET_WAS_DEFINED -#endif - -#define Allocator near_allocator -#define multiset near_multiset -#define rb_tree near_rb_tree -#include <neralloc.h> -#include <multiset.h> - -#undef MULTISET_H -#undef TREE_H - -#ifdef __MULTISET_WAS_DEFINED -#define MULTISET_H -#define TREE_H -#undef __MULTISET_WAS_DEFINED -#endif - -#undef Allocator -#undef multiset -#undef rb_tree - -#endif diff --git a/contrib/libg++/libstdc++/stl/nset.h b/contrib/libg++/libstdc++/stl/nset.h deleted file mode 100644 index 325d6b94aacfa..0000000000000 --- a/contrib/libg++/libstdc++/stl/nset.h +++ /dev/null @@ -1,44 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef NSET_H -#define NSET_H - -#ifdef SET_H -#undef SET_H -#undef TREE_H -#define __SET_WAS_DEFINED -#endif - -#define Allocator near_allocator -#define set near_set -#define rb_tree near_rb_tree -#include <neralloc.h> -#include <set.h> - -#undef SET_H -#undef TREE_H - -#ifdef __SET_WAS_DEFINED -#define SET_H -#define TREE_H -#undef __SET_WAS_DEFINED -#endif - -#undef Allocator -#undef set -#undef rb_tree - -#endif diff --git a/contrib/libg++/libstdc++/stl/pair.h b/contrib/libg++/libstdc++/stl/pair.h deleted file mode 100644 index 817d9a4396958..0000000000000 --- a/contrib/libg++/libstdc++/stl/pair.h +++ /dev/null @@ -1,46 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef PAIR_H -#define PAIR_H - -#ifndef __GNUG__ -#include <bool.h> -#endif - -template <class T1, class T2> -struct pair { - T1 first; - T2 second; - pair() {} - pair(const T1& a, const T2& b) : first(a), second(b) {} -}; - -template <class T1, class T2> -inline bool operator==(const pair<T1, T2>& x, const pair<T1, T2>& y) { - return x.first == y.first && x.second == y.second; -} - -template <class T1, class T2> -inline bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y) { - return x.first < y.first || (!(y.first < x.first) && x.second < y.second); -} - -template <class T1, class T2> -inline pair<T1, T2> make_pair(const T1& x, const T2& y) { - return pair<T1, T2>(x, y); -} - -#endif diff --git a/contrib/libg++/libstdc++/stl/projectn.h b/contrib/libg++/libstdc++/stl/projectn.h deleted file mode 100644 index 766796e9f2189..0000000000000 --- a/contrib/libg++/libstdc++/stl/projectn.h +++ /dev/null @@ -1,33 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef PROJECTN_H -#define PROJECTN_H - -#include <function.h> - -template <class T, class U> -struct select1st : public unary_function<T, U> { - const U& operator()(const T& x) const { return x.first; } -}; - -template <class T, class U> -struct ident : public unary_function<T, U> { - const U& operator()(const T& x) const { return x; } -}; - -#endif - - diff --git a/contrib/libg++/libstdc++/stl/random.cc b/contrib/libg++/libstdc++/stl/random.cc deleted file mode 100644 index e79872ca49b17..0000000000000 --- a/contrib/libg++/libstdc++/stl/random.cc +++ /dev/null @@ -1,60 +0,0 @@ -/* - * - * 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. - * - */ - -#include <stddef.h> - -#define __SEED 161803398 - -class __random_generator { -protected: - unsigned long table[55]; - size_t index1; - size_t index2; -public: - unsigned long operator()(unsigned long limit) { - index1 = (index1 + 1) % 55; - index2 = (index2 + 1) % 55; - table[index1] = table[index1] - table[index2]; - return table[index1] % limit; - } - void seed(unsigned long j); - __random_generator(unsigned long j) { seed(j); } -}; - -void __random_generator::seed(unsigned long j) { - unsigned long k = 1; - table[54] = j; - for (size_t i = 0; i < 54; i++) { - size_t ii = 21 * i % 55; - table[ii] = k; - k = j - k; - j = table[ii]; - } - for (int loop = 0; loop < 4; loop++) { - for (size_t i = 0; i < 55; i++) - table[i] = table[i] - table[(1 + i + 30) % 55]; - } - index1 = 0; - index2 = 31; -} - -static __random_generator rd(__SEED); - -unsigned long __long_random(unsigned long limit) { - return rd(limit); -} - - - diff --git a/contrib/libg++/libstdc++/stl/set.h b/contrib/libg++/libstdc++/stl/set.h deleted file mode 100644 index d108e42371a08..0000000000000 --- a/contrib/libg++/libstdc++/stl/set.h +++ /dev/null @@ -1,132 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef SET_H -#define SET_H - -#ifndef Allocator -#define Allocator allocator -#include <defalloc.h> -#endif - -#include <tree.h> - -template <class Key, class Compare> -class set { -public: -// typedefs: - - typedef Key key_type; - typedef Key value_type; - typedef Compare key_compare; - typedef Compare value_compare; -private: - typedef rb_tree<key_type, value_type, - ident<value_type, key_type>, key_compare> rep_type; - rep_type t; // red-black tree representing set -public: - typedef rep_type::const_reference reference; - typedef rep_type::const_reference const_reference; - typedef rep_type::const_iterator iterator; - typedef rep_type::const_iterator const_iterator; - typedef rep_type::const_reverse_iterator reverse_iterator; - typedef rep_type::const_reverse_iterator const_reverse_iterator; - typedef rep_type::size_type size_type; - typedef rep_type::difference_type difference_type; - -// allocation/deallocation - - set(const Compare& comp = Compare()) : t(comp, false) {} - set(const value_type* first, const value_type* last, - const Compare& comp = Compare()) : t(comp, false) { - for (const value_type* i = first; i != last; ++i) - t.insert(*i); - } - set(const set<Key, Compare>& x) : t(x.t, false) {} - set<Key, Compare>& operator=(const set<Key, Compare>& x) { - t = x.t; - return *this; - } - -// accessors: - - key_compare key_comp() const { return t.key_comp(); } - value_compare value_comp() const { return t.key_comp(); } - iterator begin() const { return t.begin(); } - iterator end() const { return t.end(); } - reverse_iterator rbegin() const { return t.rbegin(); } - reverse_iterator rend() const { return t.rend(); } - bool empty() const { return t.empty(); } - size_type size() const { return t.size(); } - size_type max_size() const { return t.max_size(); } - void swap(set<Key, Compare>& x) { t.swap(x.t); } - -// insert/erase - typedef pair<iterator, bool> pair_iterator_bool; - // typedef done to get around compiler bug - pair_iterator_bool insert(const value_type& x) { - pair<rep_type::iterator, bool> p = t.insert(x); - return pair<iterator, bool>(p.first, p.second); - } - iterator insert(iterator position, const value_type& x) { - return t.insert((rep_type::iterator&)position, x); - } - void insert(const value_type* first, const value_type* last) { - for (const value_type* i = first; i != last; ++i) - t.insert(*i); - } - void erase(iterator position) { - t.erase((rep_type::iterator&)position); - } - size_type erase(const key_type& x) { - return t.erase(x); - } - void erase(iterator first, iterator last) { - t.erase((rep_type::iterator&)first, - (rep_type::iterator&)last); - } - -// set operations: - - iterator find(const key_type& x) const { return t.find(x); } - size_type count(const key_type& x) const { return t.count(x); } - iterator lower_bound(const key_type& x) const { - return t.lower_bound(x); - } - iterator upper_bound(const key_type& x) const { - return t.upper_bound(x); - } - typedef pair<iterator, iterator> pair_iterator_iterator; - // typedef done to get around compiler bug - pair_iterator_iterator equal_range(const key_type& x) const { - return t.equal_range(x); - } -}; - -template <class Key, class Compare> -inline bool operator==(const set<Key, Compare>& x, - const set<Key, Compare>& y) { - return x.size() == y.size() && equal(x.begin(), x.end(), y.begin()); -} - -template <class Key, class Compare> -inline bool operator<(const set<Key, Compare>& x, - const set<Key, Compare>& y) { - return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); -} - -#undef Allocator - -#endif diff --git a/contrib/libg++/libstdc++/stl/stack.h b/contrib/libg++/libstdc++/stl/stack.h deleted file mode 100644 index 83a59a4c2afcb..0000000000000 --- a/contrib/libg++/libstdc++/stl/stack.h +++ /dev/null @@ -1,120 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef STACK_H -#define STACK_H - -#ifndef __GNUG__ -#include <bool.h> -#endif -#include <heap.h> - -template <class Container> -class stack { -friend bool operator==(const stack<Container>& x, const stack<Container>& y); -friend bool operator<(const stack<Container>& x, const stack<Container>& y); -public: - typedef Container::value_type value_type; - typedef Container::size_type size_type; -protected: - Container c; -public: - bool empty() const { return c.empty(); } - size_type size() const { return c.size(); } - value_type& top() { return c.back(); } - const value_type& top() const { return c.back(); } - void push(const value_type& x) { c.push_back(x); } - void pop() { c.pop_back(); } -}; - -template <class Container> -bool operator==(const stack<Container>& x, const stack<Container>& y) { - return x.c == y.c; -} - -template <class Container> -bool operator<(const stack<Container>& x, const stack<Container>& y) { - return x.c < y.c; -} - -template <class Container> -class queue { -friend bool operator==(const queue<Container>& x, const queue<Container>& y); -friend bool operator<(const queue<Container>& x, const queue<Container>& y); -public: - typedef Container::value_type value_type; - typedef Container::size_type size_type; -protected: - Container c; -public: - bool empty() const { return c.empty(); } - size_type size() const { return c.size(); } - value_type& front() { return c.front(); } - const value_type& front() const { return c.front(); } - value_type& back() { return c.back(); } - const value_type& back() const { return c.back(); } - void push(const value_type& x) { c.push_back(x); } - void pop() { c.pop_front(); } -}; - -template <class Container> -bool operator==(const queue<Container>& x, const queue<Container>& y) { - return x.c == y.c; -} - -template <class Container> -bool operator<(const queue<Container>& x, const queue<Container>& y) { - return x.c < y.c; -} - -template <class Container, class Compare> -// Compare = less<Container::value_type> > -class priority_queue { -public: - typedef Container::value_type value_type; - typedef Container::size_type size_type; -protected: - Container c; - Compare comp; -public: - priority_queue(const Compare& x = Compare()) : c(), comp(x) {} - priority_queue(const value_type* first, const value_type* last, - const Compare& x = Compare()) : c(first, last), comp(x) { - make_heap(c.begin(), c.end(), comp); - } -/* - template <class InputIterator> - priority_queue(InputIterator first, InputIterator last, - const Compare& x = Compare()) : c(first, last), comp(x) { - make_heap(c.begin(), c.end(), comp); - } -*/ - bool empty() const { return c.empty(); } - size_type size() const { return c.size(); } - value_type& top() { return c.front(); } - const value_type& top() const { return c.front(); } - void push(const value_type& x) { - c.push_back(x); - push_heap(c.begin(), c.end(), comp); - } - void pop() { - pop_heap(c.begin(), c.end(), comp); - c.pop_back(); - } -}; - -// no equality is provided - -#endif diff --git a/contrib/libg++/libstdc++/stl/tempbuf.cc b/contrib/libg++/libstdc++/stl/tempbuf.cc deleted file mode 100644 index 2e7408eadd304..0000000000000 --- a/contrib/libg++/libstdc++/stl/tempbuf.cc +++ /dev/null @@ -1,18 +0,0 @@ -/* - * - * 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. - * - */ - -#include <tempbuf.h> - -char __stl_temp_buffer[__stl_buffer_size]; diff --git a/contrib/libg++/libstdc++/stl/tempbuf.h b/contrib/libg++/libstdc++/stl/tempbuf.h deleted file mode 100644 index 238b6acc31bb3..0000000000000 --- a/contrib/libg++/libstdc++/stl/tempbuf.h +++ /dev/null @@ -1,55 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef TEMPBUF_H -#define TEMPBUF_H - -#include <limits.h> -#include <pair.h> - -#ifndef __stl_buffer_size -#define __stl_buffer_size 16384 // 16k -#endif - -extern char __stl_temp_buffer[__stl_buffer_size]; - -//not reentrant code - -template <class T> -pair<T*, int> get_temporary_buffer(int len, T*) { - while (len > __stl_buffer_size / sizeof(T)) { - set_new_handler(0); - T* tmp = (T*)(::operator new((unsigned int)len * sizeof(T))); - if (tmp) return pair<T*, int>(tmp, len); - len = len / 2; - } - return pair<T*, int>((T*)__stl_temp_buffer, - (int)(__stl_buffer_size / sizeof(T))); -} - -template <class T> -void return_temporary_buffer(T* p) { - if ((char*)(p) != __stl_temp_buffer) deallocate(p); -} - -template <class T> -pair<T*, long> get_temporary_buffer(long len, T* p) { - if (len > INT_MAX/sizeof(T)) - len = INT_MAX/sizeof(T); - pair<T*, int> tmp = get_temporary_buffer((int)len, p); - return pair<T*, long>(tmp.first, (long)(tmp.second)); -} - -#endif diff --git a/contrib/libg++/libstdc++/stl/tree.cc b/contrib/libg++/libstdc++/stl/tree.cc deleted file mode 100644 index e4a9cfe10fa7d..0000000000000 --- a/contrib/libg++/libstdc++/stl/tree.cc +++ /dev/null @@ -1,3 +0,0 @@ -#include "tree.h" - -__rb_tree_node_base __rb_NIL = { black, 0, 0, 0 }; diff --git a/contrib/libg++/libstdc++/stl/tree.h b/contrib/libg++/libstdc++/stl/tree.h deleted file mode 100644 index 3ae5da02b08c5..0000000000000 --- a/contrib/libg++/libstdc++/stl/tree.h +++ /dev/null @@ -1,1246 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef TREE_H -#define TREE_H - -/* - -Red-black tree class, designed for use in implementing STL -associative containers (set, multiset, map, and multimap). The -insertion and deletion algorithms are based on those in Cormen, -Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990), -except that - -(1) the header cell is maintained with links not only to the root -but also to the leftmost node of the tree, to enable constant time -begin(), and to the rightmost node of the tree, to enable linear time -performance when used with the generic set algorithms (set_union, -etc.); - -(2) when a node being deleted has two children its successor node is -relinked into its place, rather than copied, so that the only -iterators invalidated are those referring to the deleted node. - -*/ - -#include <algobase.h> -#include <iterator.h> -#include <function.h> -#ifndef __GNUG__ -#include <bool.h> -#endif -#include <projectn.h> - -#ifndef rb_tree -#define rb_tree rb_tree -#endif - -enum __rb_color_type {red, black}; - -struct __rb_tree_node_base { - enum __rb_color_type color_field; - void* parent_link; - void* left_link; - void* right_link; -}; - -extern __rb_tree_node_base __rb_NIL; - -template <class Key, class Value, class KeyOfValue, class Compare> -class rb_tree { -protected: - typedef enum __rb_color_type color_type; - typedef Allocator<void>::pointer void_pointer; - struct rb_tree_node; - friend rb_tree_node; - struct rb_tree_node : public __rb_tree_node_base { - Value value_field; - }; -#ifndef __GNUG__ - static Allocator<rb_tree_node> rb_tree_node_allocator; - static Allocator<Value> value_allocator; -#endif -public: - typedef Key key_type; - typedef Value value_type; - typedef Allocator<Value>::pointer pointer; - typedef Allocator<Value>::reference reference; - typedef Allocator<Value>::const_reference const_reference; - typedef Allocator<rb_tree_node> rb_tree_node_allocator_type; - typedef Allocator<rb_tree_node>::pointer link_type; - typedef Allocator<rb_tree_node>::size_type size_type; - typedef Allocator<rb_tree_node>::difference_type difference_type; -protected: -#ifndef __GNUG__ - size_type buffer_size() { - return rb_tree_node_allocator.init_page_size(); - } -#endif - struct rb_tree_node_buffer; - friend rb_tree_node_buffer; - struct rb_tree_node_buffer { - void_pointer next_buffer; - link_type buffer; - }; -public: - typedef Allocator<rb_tree_node_buffer> buffer_allocator_type; - typedef Allocator<rb_tree_node_buffer>::pointer buffer_pointer; -protected: -#ifdef __GNUG__ - static Allocator<rb_tree_node_buffer> buffer_allocator; - static buffer_pointer buffer_list; - static link_type free_list; - static link_type next_avail; - static link_type last; - link_type get_node() { return (link_type) operator new (sizeof (rb_tree_node)); } - void put_node(link_type p) { operator delete (p); } -#else - void add_new_buffer() { - buffer_pointer tmp = buffer_allocator.allocate((size_type)1); - tmp->buffer = rb_tree_node_allocator.allocate(buffer_size()); - tmp->next_buffer = buffer_list; - buffer_list = tmp; - next_avail = buffer_list->buffer; - last = next_avail + buffer_size(); - } - static size_type number_of_trees; - void deallocate_buffers(); - link_type get_node() { - link_type tmp = free_list; - return free_list ? - (free_list = (link_type)(free_list->right_link), tmp) - : (next_avail == last ? (add_new_buffer(), next_avail++) - : next_avail++); - // ugly code for inlining - avoids multiple returns - } - void put_node(link_type p) { - p->right_link = free_list; - free_list = p; - } -#endif -protected: - link_type header; - link_type& root() { return parent(header); } - link_type& root() const { return parent(header); } - link_type& leftmost() { return left(header); } - link_type& leftmost() const { return left(header); } - link_type& rightmost() { return right(header); } - link_type& rightmost() const { return right(header); } - size_type node_count; // keeps track of size of tree - bool insert_always; // controls whether an element already in the - // tree is inserted again -//public: - Compare key_compare; - static link_type& left(link_type x) { - return (link_type&)((*x).left_link); - } - static link_type& right(link_type x) { - return (link_type&)((*x).right_link); - } - static link_type& parent(link_type x) { - return (link_type&)((*x).parent_link); - } - static reference value(link_type x) { return (*x).value_field; } - static Allocator<Key>::const_reference key(link_type x) { - return KeyOfValue()(value(x)); - } - static color_type& color(link_type x) { - return (color_type&)(*x).color_field; } - static link_type minimum(link_type x) { - while (left(x) != &__rb_NIL) - x = left(x); - return x; - } - static link_type maximum(link_type x) { - while (right(x) != &__rb_NIL) - x = right(x); - return x; - } -public: - class iterator; - friend iterator; - class const_iterator; - friend const_iterator; - class iterator : public bidirectional_iterator<Value, difference_type> { - friend class rb_tree<Key, Value, KeyOfValue, Compare>; - friend class const_iterator; -/* - friend bool operator==(const iterator& x, const iterator& y) { - return x.node == y.node; - } -*/ - protected: - link_type node; - iterator(link_type x) : node(x) {} - public: - iterator() {} - bool operator==(const iterator& y) const { return node == y.node; } - reference operator*() const { return value(node); } - iterator& operator++() { - if (right(node) != &__rb_NIL) { - node = right(node); - while (left(node) != &__rb_NIL) - node = left(node); - } else { - link_type y = parent(node); - while (node == right(y)) { - node = y; - y = parent(y); - } - if (right(node) != y) // necessary because of rightmost - node = y; - } - return *this; - } - iterator operator++(int) { - iterator tmp = *this; - ++*this; - return tmp; - } - iterator& operator--() { - if (color(node) == red && parent(parent(node)) == node) - // check for header - node = right(node); // return rightmost - else if (left(node) != &__rb_NIL) { - link_type y = left(node); - while (right(y) != &__rb_NIL) - y = right(y); - node = y; - } else { - link_type y = parent(node); - while (node == left(y)) { - node = y; - y = parent(y); - } - node = y; - } - return *this; - } - iterator operator--(int) { - iterator tmp = *this; - --*this; - return tmp; - } - }; - class const_iterator - : public bidirectional_iterator<Value,difference_type> { - friend class rb_tree<Key, Value, KeyOfValue, Compare>; - friend class iterator; -/* - friend bool operator==(const const_iterator& x, const const_iterator& y) { - return x.node == y.node; - } -*/ - protected: - link_type node; - const_iterator(link_type x) : node(x) {} - public: - const_iterator() {} - const_iterator(const iterator& x) : node(x.node) {} - bool operator==(const const_iterator& y) const { - return node == y.node; - } - bool operator!=(const const_iterator& y) const { - return node != y.node; - } - const_reference operator*() const { return value(node); } - const_iterator& operator++() { - if (right(node) != &__rb_NIL) { - node = right(node); - while (left(node) != &__rb_NIL) - node = left(node); - } else { - link_type y = parent(node); - while (node == right(y)) { - node = y; - y = parent(y); - } - if (right(node) != y) // necessary because of rightmost - node = y; - } - return *this; - } - const_iterator operator++(int) { - const_iterator tmp = *this; - ++*this; - return tmp; - } - const_iterator& operator--() { - if (color(node) == red && parent(parent(node)) == node) - // check for header - node = right(node); // return rightmost - else if (left(node) != &__rb_NIL) { - link_type y = left(node); - while (right(y) != &__rb_NIL) - y = right(y); - node = y; - } else { - link_type y = parent(node); - while (node == left(y)) { - node = y; - y = parent(y); - } - node = y; - } - return *this; - } - const_iterator operator--(int) { - const_iterator tmp = *this; - --*this; - return tmp; - } - }; - typedef reverse_bidirectional_iterator<iterator, value_type, reference, - difference_type> - reverse_iterator; - typedef reverse_bidirectional_iterator<const_iterator, value_type, - const_reference, difference_type> - const_reverse_iterator; -private: -#ifdef __GNUC__ - rb_tree_iterator<Key, Value, KeyOfValue, Compare> __insert(void* x, void* y, const value_type& v); - link_type __copy(link_type x, link_type p) { - return (link_type) __copy_hack (x, p); - } -private: - void * __copy_hack (void *, void *); -public: - void __erase(void* x); -#else - iterator __insert(link_type x, link_type y, const value_type& v); - link_type __copy(link_type x, link_type p); - void __erase(link_type x); -#endif - void init() { -#ifndef __GNUG__ - ++number_of_trees; -#endif - header = get_node(); - color(header) = red; // used to distinguish header from root, - // in iterator.operator++ - header->parent_link = &__rb_NIL; - leftmost() = header; - rightmost() = header; - } -public: - -// allocation/deallocation - - rb_tree(const Compare& comp = Compare(), bool always = true) - : node_count(0), insert_always(always), key_compare(comp) { - init(); - } - rb_tree(const value_type* first, const value_type* last, - const Compare& comp = Compare(), bool always = true) - : node_count(0), insert_always(always), key_compare(comp) { - init(); - insert(first, last); - } - rb_tree(const rb_tree<Key, Value, KeyOfValue, Compare>& x, - bool always = true) : node_count(x.node_count), - insert_always(always), key_compare(x.key_compare) { -#ifndef __GNUG__ - ++number_of_trees; -#endif - header = get_node(); - color(header) = red; - root() = __copy(x.root(), header); - if (root() == &__rb_NIL) { - leftmost() = header; - rightmost() = header; - } else { - leftmost() = minimum(root()); - rightmost() = maximum(root()); - } - } - ~rb_tree() { - erase(begin(), end()); - put_node(header); -#ifndef __GNUG__ - if (--number_of_trees == 0) { - deallocate_buffers(); - free_list = 0; - next_avail = 0; - last = 0; - } -#endif - } - rb_tree<Key, Value, KeyOfValue, Compare>& - operator=(const rb_tree<Key, Value, KeyOfValue, Compare>& x); - -// accessors: - - Compare key_comp() const { return key_compare; } - iterator begin() { return leftmost(); } - const_iterator begin() const { return leftmost(); } - iterator end() { return header; } - const_iterator end() const { return header; } - 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_count == 0; } - size_type size() const { return node_count; } -#ifndef __GNUG__ - size_type max_size() const { - return rb_tree_node_allocator.max_size(); - } -#else - size_type max_size() const { - return rb_tree_node_allocator_type::max_size(); - } -#endif - void swap(rb_tree<Key, Value, KeyOfValue, Compare>& t) { - ::swap(header, t.header); - ::swap(node_count, t.node_count); - ::swap(insert_always, t.insert_always); - ::swap(key_compare, t.key_compare); - } - -// insert/erase - - typedef pair<iterator, bool> pair_iterator_bool; - // typedef done to get around compiler bug -#ifdef __GNUG__ - pair_iterator_bool insert(const value_type& x) { - return insert_hack(x); - } -private: - rb_tree_pair_iterator_bool<Key, Value, KeyOfValue, Compare> - insert_hack(const Value& v); -public: - iterator insert(iterator position, const value_type& x) { - return insert_hack(position, x); - } -private: - rb_tree_iterator<Key, Value, KeyOfValue, Compare> - insert_hack(rb_tree_iterator<Key, Value, KeyOfValue, Compare> posn, - const Value& v); -public: - void insert(iterator first, iterator last) { - while (first != last) insert(*first++); - } - void insert(const value_type* first, const value_type* last){ - while (first != last) insert(*first++); - } - void erase(iterator position) { - erase_hack(position); - } -private: - void erase_hack(rb_tree_iterator<Key, Value, KeyOfValue, Compare> position); -public: - size_type erase(const key_type& x); - void erase(iterator first, iterator last) { - while (first != last) erase(first++); - } -#else - pair_iterator_bool insert(const value_type& x); - iterator insert(iterator position, const value_type& x); - void insert(iterator first, iterator last); - void insert(const value_type* first, const value_type* last); - void erase(iterator position); - size_type erase(const key_type& x); - void erase(iterator first, iterator last); -#endif - void erase(const key_type* first, const key_type* last); - -// set operations: - -#ifdef __GNUG__ - iterator find(const key_type& x) { - return find_hack(x); - } - const_iterator find(const key_type& x) const { - return find_hack(x); - } -private: - rb_tree_iterator<Key, Value, KeyOfValue, Compare> - find_hack(const key_type& x); - rb_tree_const_iterator<Key, Value, KeyOfValue, Compare> - find_hack(const Key& k) const; -public: - - size_type count(const key_type& x) const; - iterator lower_bound(const key_type& x) { - return lower_bound_hack(x); - } - const_iterator lower_bound(const key_type& x) const { - return lower_bound_hack(x); - } - iterator upper_bound(const key_type& x) { - return upper_bound_hack(x); - } - const_iterator upper_bound(const key_type& x) const { - return upper_bound_hack(x); - } -private: - rb_tree_iterator<Key, Value, KeyOfValue, Compare> - lower_bound_hack(const key_type& x); - rb_tree_const_iterator<Key, Value, KeyOfValue, Compare> - lower_bound_hack(const Key& k) const; - rb_tree_iterator<Key, Value, KeyOfValue, Compare> - upper_bound_hack(const key_type& x); - rb_tree_const_iterator<Key, Value, KeyOfValue, Compare> - upper_bound_hack(const Key& k) const; -public: - typedef pair<iterator, iterator> pair_iterator_iterator; - // typedef done to get around compiler bug - pair_iterator_iterator equal_range(const key_type& x) { - return pair_iterator_iterator(lower_bound(x), upper_bound(x)); - } - typedef pair<const_iterator, const_iterator> pair_citerator_citerator; - - // typedef done to get around compiler bug - pair_citerator_citerator equal_range(const key_type& x) const { - return pair_citerator_citerator(lower_bound(x), upper_bound(x)); - } - inline void rotate_left(link_type x) { - link_type y = right(x); - right(x) = left(y); - if (left(y) != &__rb_NIL) - parent(left(y)) = x; - parent(y) = parent(x); - if (x == root()) - root() = y; - else if (x == left(parent(x))) - left(parent(x)) = y; - else - right(parent(x)) = y; - left(y) = x; - parent(x) = y; - } - - inline void rotate_right(link_type x) { - link_type y = left(x); - left(x) = right(y); - if (right(y) != &__rb_NIL) - parent(right(y)) = x; - parent(y) = parent(x); - if (x == root()) - root() = y; - else if (x == right(parent(x))) - right(parent(x)) = y; - else - left(parent(x)) = y; - right(y) = x; - parent(x) = y; - } - friend bidirectional_iterator_tag iterator_category(iterator) { - return bidirectional_iterator_tag(); - } - friend bidirectional_iterator_tag iterator_category(const_iterator) { - return bidirectional_iterator_tag(); - } -#else - iterator find(const key_type& x); - const_iterator find(const key_type& x) const; - size_type count(const key_type& x) const; - iterator lower_bound(const key_type& x); - const_iterator lower_bound(const key_type& x) const; - iterator upper_bound(const key_type& x); - const_iterator upper_bound(const key_type& x) const; - typedef pair<iterator, iterator> pair_iterator_iterator; - // typedef done to get around compiler bug - pair_iterator_iterator equal_range(const key_type& x); - typedef pair<const_iterator, const_iterator> pair_citerator_citerator; - // typedef done to get around compiler bug - pair_citerator_citerator equal_range(const key_type& x) const; - inline void rotate_left(link_type x); - inline void rotate_right(link_type x); -#endif -}; - -#ifndef __GNUG__ -template <class Key, class Value, class KeyOfValue, class Compare> -rb_tree<Key, Value, KeyOfValue, Compare>::buffer_pointer - rb_tree<Key, Value, KeyOfValue, Compare>::buffer_list = 0; - -template <class Key, class Value, class KeyOfValue, class Compare> -rb_tree<Key, Value, KeyOfValue, Compare>::link_type - rb_tree<Key, Value, KeyOfValue, Compare>::free_list = 0; - -template <class Key, class Value, class KeyOfValue, class Compare> -rb_tree<Key, Value, KeyOfValue, Compare>::link_type - rb_tree<Key, Value, KeyOfValue, Compare>::next_avail = 0; - -template <class Key, class Value, class KeyOfValue, class Compare> -rb_tree<Key, Value, KeyOfValue, Compare>::link_type - rb_tree<Key, Value, KeyOfValue, Compare>::last = 0; - -template <class Key, class Value, class KeyOfValue, class Compare> -rb_tree<Key, Value, KeyOfValue, Compare>::size_type - rb_tree<Key, Value, KeyOfValue, Compare>::number_of_trees = 0; - -template <class Key, class Value, class KeyOfValue, class Compare> -rb_tree<Key, Value, KeyOfValue, Compare>::rb_tree_node_allocator_type - rb_tree<Key, Value, KeyOfValue, Compare>::rb_tree_node_allocator; - -template <class Key, class Value, class KeyOfValue, class Compare> -Allocator<Value> rb_tree<Key, Value, KeyOfValue, Compare>::value_allocator; - -template <class Key, class Value, class KeyOfValue, class Compare> -rb_tree<Key, Value, KeyOfValue, Compare>::buffer_allocator_type - rb_tree<Key, Value, KeyOfValue, Compare>::buffer_allocator; - -template <class Key, class Value, class KeyOfValue, class Compare> -void rb_tree<Key, Value, KeyOfValue, Compare>::deallocate_buffers() { - while (buffer_list) { - buffer_pointer tmp = buffer_list; - buffer_list = (buffer_pointer)(buffer_list->next_buffer); - rb_tree_node_allocator.deallocate(tmp->buffer); - buffer_allocator.deallocate(tmp); - } -} -#endif - -#ifdef __GNUC__ -template <class Key, class Value, class KeyOfValue, class Compare> -struct rb_tree_iterator { - rb_tree<Key, Value, KeyOfValue, Compare>::iterator it; - rb_tree_iterator(rb_tree<Key, Value, KeyOfValue, Compare>::iterator i) : it(i) {} - operator rb_tree<Key, Value, KeyOfValue, Compare>::iterator() { - return it; - } -}; - -template <class Key, class Value, class KeyOfValue, class Compare> -inline Value* value_type(const rb_tree_iterator<Key, Value, KeyOfValue, Compare>&) { - return (Value*)(0); -} - -template <class Key, class Value, class KeyOfValue, class Compare> -struct rb_tree_const_iterator { - rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator it; - rb_tree_const_iterator(rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator i) : it(i) {} - operator rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator() { - return it; - } -}; - -template <class Key, class Value, class KeyOfValue, class Compare> -inline Value* value_type(const rb_tree_const_iterator<Key, Value, KeyOfValue, Compare>&) { - return (Value*)(0); -} - -template <class Key, class Value, class KeyOfValue, class Compare> -struct rb_tree_pair_iterator_bool { - rb_tree<Key, Value, KeyOfValue, Compare>::pair_iterator_bool it; - rb_tree_pair_iterator_bool(rb_tree<Key, Value, KeyOfValue, Compare>::pair_iterator_bool i) : it(i) {} - operator rb_tree<Key, Value, KeyOfValue, Compare>::pair_iterator_bool() { - return it; - } -}; - -template <class Key, class Value, class KeyOfValue, class Compare> -inline Value* value_type(rb_tree_pair_iterator_bool<Key, Value, KeyOfValue, Compare>&) { - return (Value*)(0); -} -#endif - -template <class Key, class Value, class KeyOfValue, class Compare> -inline bool operator==(const rb_tree<Key, Value, KeyOfValue, Compare>& x, - const rb_tree<Key, Value, KeyOfValue, Compare>& y) { - return x.size() == y.size() && equal(x.begin(), x.end(), y.begin()); -} - -template <class Key, class Value, class KeyOfValue, class Compare> -inline bool operator<(const rb_tree<Key, Value, KeyOfValue, Compare>& x, - const rb_tree<Key, Value, KeyOfValue, Compare>& y) { - return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); -} - -template <class Key, class Value, class KeyOfValue, class Compare> -rb_tree<Key, Value, KeyOfValue, Compare>& -rb_tree<Key, Value, KeyOfValue, Compare>:: -operator=(const rb_tree<Key, Value, KeyOfValue, Compare>& x) { - if (this != &x) { - // can't be done as in list because Key may be a constant type - erase(begin(), end()); - root() = __copy(x.root(), header); - if (root() == &__rb_NIL) { - leftmost() = header; - rightmost() = header; - } else { - leftmost() = minimum(root()); - rightmost() = maximum(root()); - } - node_count = x.node_count; - } - return *this; -} - -template <class Key, class Value, class KeyOfValue, class Compare> -#ifdef __GNUC__ -rb_tree_iterator<Key, Value, KeyOfValue, Compare> -rb_tree<Key, Value, KeyOfValue, Compare>::__insert -(void* xa, void* ya, const Value& v) { - link_type x = (link_type)xa; - link_type y = (link_type)ya; -#else -rb_tree<Key, Value, KeyOfValue, Compare>::iterator -rb_tree<Key, Value, KeyOfValue, Compare>:: -__insert(link_type x, link_type y, const Value& v) { -#endif - ++node_count; - link_type z = get_node(); -#ifdef __GNUG__ - construct(&(value(z)), v); -#else - construct(value_allocator.address(value(z)), v); -#endif - if (y == header || x != &__rb_NIL || key_compare(KeyOfValue()(v), key(y))) { - left(y) = z; // also makes leftmost() = z when y == header - if (y == header) { - root() = z; - rightmost() = z; - } else if (y == leftmost()) - leftmost() = z; // maintain leftmost() pointing to minimum node - } else { - right(y) = z; - if (y == rightmost()) - rightmost() = z; // maintain rightmost() pointing to maximum node - } - parent(z) = y; - z->left_link = &__rb_NIL; - z->right_link = &__rb_NIL; - x = z; // recolor and rebalance the tree - color(x) = red; - while (x != root() && color(parent(x)) == red) - if (parent(x) == left(parent(parent(x)))) { - y = right(parent(parent(x))); - if (color(y) == red) { - color(parent(x)) = black; - color(y) = black; - color(parent(parent(x))) = red; - x = parent(parent(x)); - } else { - if (x == right(parent(x))) { - x = parent(x); - rotate_left(x); - } - color(parent(x)) = black; - color(parent(parent(x))) = red; - rotate_right(parent(parent(x))); - } - } else { - y = left(parent(parent(x))); - if (color(y) == red) { - color(parent(x)) = black; - color(y) = black; - color(parent(parent(x))) = red; - x = parent(parent(x)); - } else { - if (x == left(parent(x))) { - x = parent(x); - rotate_right(x); - } - color(parent(x)) = black; - color(parent(parent(x))) = red; - rotate_left(parent(parent(x))); - } - } - color(root()) = black; - return iterator(z); -} - -template <class Key, class Value, class KeyOfValue, class Compare> -#ifdef __GNUC__ -rb_tree_pair_iterator_bool<Key, Value, KeyOfValue, Compare> -rb_tree<Key, Value, KeyOfValue, Compare>::insert_hack(const Value& v) { -#else -rb_tree<Key, Value, KeyOfValue, Compare>::pair_iterator_bool -rb_tree<Key, Value, KeyOfValue, Compare>::insert(const Value& v) { -#endif - link_type y = header; - link_type x = root(); - bool comp = true; - while (x != &__rb_NIL) { - y = x; - comp = key_compare(KeyOfValue()(v), key(x)); - x = comp ? left(x) : right(x); - } - if (insert_always) - return pair_iterator_bool(__insert(x, y, v), true); - iterator j = iterator(y); - if (comp) - if (j == begin()) - return pair_iterator_bool(__insert(x, y, v), true); - else - --j; - if (key_compare(key(j.node), KeyOfValue()(v))) - return pair_iterator_bool(__insert(x, y, v), true); - return pair_iterator_bool(j, false); -} - -template <class Key, class Value, class KeyOfValue, class Compare> -#ifdef __GNUC__ -rb_tree_iterator<Key, Value, KeyOfValue, Compare> -rb_tree<Key, Value, KeyOfValue, Compare>::insert_hack(rb_tree_iterator<Key, Value, KeyOfValue, Compare> posn, - const Value& v) { - iterator position = posn; -#else -rb_tree<Key, Value, KeyOfValue, Compare>::iterator -rb_tree<Key, Value, KeyOfValue, Compare>::insert(iterator position, - const Value& v) { -#endif - if (position == iterator(begin())) - if (size() > 0 && key_compare(KeyOfValue()(v), key(position.node))) - return __insert(position.node, position.node, v); - // first argument just needs to be non-&__rb_NIL - else - return insert(v).first; - else if (position == iterator(end())) - if (key_compare(key(rightmost()), KeyOfValue()(v))) - return __insert(&__rb_NIL, rightmost(), v); - else - return insert(v).first; - else { - iterator before = --position; - if (key_compare(key(before.node), KeyOfValue()(v)) - && key_compare(KeyOfValue()(v), key(position.node))) - if (right(before.node) == &__rb_NIL) - return __insert(&__rb_NIL, before.node, v); - else - return __insert(position.node, position.node, v); - // first argument just needs to be non-&__rb_NIL - else - return insert(v).first; - } -} - -#ifndef __GNUC__ -template <class Key, class Value, class KeyOfValue, class Compare> -void rb_tree<Key, Value, KeyOfValue, Compare>::insert(iterator first, - iterator last) { - while (first != last) insert(*first++); -} - -template <class Key, class Value, class KeyOfValue, class Compare> -void rb_tree<Key, Value, KeyOfValue, Compare>::insert(const Value* first, - const Value* last) { - while (first != last) insert(*first++); -} -#endif - -template <class Key, class Value, class KeyOfValue, class Compare> -#ifdef __GNUC__ -void rb_tree<Key, Value, KeyOfValue, Compare>::erase_hack( - rb_tree_iterator<Key, Value, KeyOfValue, Compare> posn) { - iterator position = posn; -#else -void rb_tree<Key, Value, KeyOfValue, Compare>::erase(iterator position) { -#endif - link_type z = position.node; - link_type y = z; - link_type x; - if (left(y) == &__rb_NIL) - x = right(y); - else - if (right(y) == &__rb_NIL) - x = left(y); - else { - y = right(y); - while (left(y) != &__rb_NIL) - y = left(y); - x = right(y); - } - if (y != z) { // relink y in place of z - parent(left(z)) = y; - left(y) = left(z); - if (y != right(z)) { - parent(x) = parent(y); // possibly x == &__rb_NIL - left(parent(y)) = x; // y must be a left child - right(y) = right(z); - parent(right(z)) = y; - } else - parent(x) = y; // needed in case x == &__rb_NIL - if (root() == z) - root() = y; - else if (left(parent(z)) == z) - left(parent(z)) = y; - else - right(parent(z)) = y; - parent(y) = parent(z); - ::swap(color(y), color(z)); - ::swap(y, z); - // y points to node to be actually deleted, - // z points to old z's former successor - } else { // y == z - parent(x) = parent(y); // possibly x == &__rb_NIL - if (root() == z) - root() = x; - else - if (left(parent(z)) == z) - left(parent(z)) = x; - else - right(parent(z)) = x; - if (leftmost() == z) - if (right(z) == &__rb_NIL) // left(z) must be &__rb_NIL also - leftmost() = parent(z); - // makes leftmost() == header if z == root() - else - leftmost() = minimum(x); - if (rightmost() == z) - if (left(z) == &__rb_NIL) // right(z) must be &__rb_NIL also - rightmost() = parent(z); - // makes rightmost() == header if z == root() - else // x == left(z) - rightmost() = maximum(x); - } - if (color(y) != red) { - while (x != root() && color(x) == black) - if (x == left(parent(x))) { - link_type w = right(parent(x)); - if (color(w) == red) { - color(w) = black; - color(parent(x)) = red; - rotate_left(parent(x)); - w = right(parent(x)); - } - if (color(left(w)) == black && color(right(w)) == black) { - color(w) = red; - x = parent(x); - } else { - if (color(right(w)) == black) { - color(left(w)) = black; - color(w) = red; - rotate_right(w); - w = right(parent(x)); - } - color(w) = color(parent(x)); - color(parent(x)) = black; - color(right(w)) = black; - rotate_left(parent(x)); - break; - } - } else { // same as then clause with "right" and "left" exchanged - link_type w = left(parent(x)); - if (color(w) == red) { - color(w) = black; - color(parent(x)) = red; - rotate_right(parent(x)); - w = left(parent(x)); - } - if (color(right(w)) == black && color(left(w)) == black) { - color(w) = red; - x = parent(x); - } else { - if (color(left(w)) == black) { - color(right(w)) = black; - color(w) = red; - rotate_left(w); - w = left(parent(x)); - } - color(w) = color(parent(x)); - color(parent(x)) = black; - color(left(w)) = black; - rotate_right(parent(x)); - break; - } - } - color(x) = black; - } -#ifdef __GNUG__ - delete y; -#else - destroy(value_allocator.address(value(y))); - put_node(y); -#endif - --node_count; -} - -template <class Key, class Value, class KeyOfValue, class Compare> -#ifdef __GNUC__ -#ifndef __SIZE_TYPE__ -#define __SIZE_TYPE__ long unsigned int -#endif -__SIZE_TYPE__ -#else -rb_tree<Key, Value, KeyOfValue, Compare>::size_type -#endif -rb_tree<Key, Value, KeyOfValue, Compare>::erase(const Key& x) { - pair_iterator_iterator p = equal_range(x); - size_type n = 0; - distance(p.first, p.second, n); - erase(p.first, p.second); - return n; -} - -template <class Key, class Value, class KeyOfValue, class Compare> -#ifdef __GNUG__ -void * -rb_tree<Key, Value, KeyOfValue, Compare>::__copy_hack(void* xa, void* pa) { - link_type x = (link_type)xa; - link_type p = (link_type)pa; -#else -rb_tree<Key, Value, KeyOfValue, Compare>::link_type -rb_tree<Key, Value, KeyOfValue, Compare>::__copy(link_type x, link_type p) { -#endif - // structural copy - link_type r = x; - while (x != &__rb_NIL) { - link_type y = get_node(); - if (r == x) r = y; // save for return value -#ifdef __GNUG__ - construct(&(value(y)), value(x)); -#else - construct(value_allocator.address(value(y)), value(x)); -#endif - left(p) = y; - parent(y) = p; - color(y) = color(x); - right(y) = __copy(right(x), y); - p = y; - x = left(x); - } - left(p) = (link_type)&__rb_NIL; - return r; -} - -template <class Key, class Value, class KeyOfValue, class Compare> -#ifdef __GNUG__ -void rb_tree<Key, Value, KeyOfValue, Compare>::__erase(void* xa) { - link_type x = (link_type)xa; -#else -void rb_tree<Key, Value, KeyOfValue, Compare>::__erase(link_type x) { -#endif - // erase without rebalancing - while (x != &__rb_NIL) { - __erase(right(x)); - link_type y = left(x); -#ifdef __GNUG__ - delete x; -#else - destroy(value_allocator.address(value(x))); - put_node(x); -#endif - x = y; - } -} - -#ifndef __GNUC__ -template <class Key, class Value, class KeyOfValue, class Compare> -void rb_tree<Key, Value, KeyOfValue, Compare>::erase(iterator first, - iterator last) { - if (first == begin() && last == end() && node_count != 0) { - __erase(root()); - leftmost() = header; - root() = NIL; - rightmost() = header; - node_count = 0; - } else - while (first != last) erase(first++); -} -#endif - -template <class Key, class Value, class KeyOfValue, class Compare> -void rb_tree<Key, Value, KeyOfValue, Compare>::erase(const Key* first, - const Key* last) { - while (first != last) erase(*first++); -} - -template <class Key, class Value, class KeyOfValue, class Compare> -#ifdef __GNUC__ -rb_tree_iterator<Key, Value, KeyOfValue, Compare> -rb_tree<Key, Value, KeyOfValue, Compare>::find_hack(const Key& k) { -#else -rb_tree<Key, Value, KeyOfValue, Compare>::iterator -rb_tree<Key, Value, KeyOfValue, Compare>::find(const Key& k) { -#endif - link_type y = header; - link_type x = root(); - bool comp = false; - while (x != &__rb_NIL) { - y = x; - comp = key_compare(key(x), k); - x = comp ? right(x) : left(x); - } - iterator j = iterator(y); - if (comp) ++j; - return (j == end() || key_compare(k, key(j.node))) ? end() : j; -} - -template <class Key, class Value, class KeyOfValue, class Compare> -#ifdef __GNUC__ -rb_tree_const_iterator<Key, Value, KeyOfValue, Compare> -rb_tree<Key, Value, KeyOfValue, Compare>::find_hack(const Key& k) const { -#else -rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator -rb_tree<Key, Value, KeyOfValue, Compare>::find(const Key& k) const { -#endif - link_type y = header; - link_type x = root(); - bool comp = false; - while (x != &__rb_NIL) { - y = x; - comp = key_compare(key(x), k); - x = comp ? right(x) : left(x); - } - const_iterator j = const_iterator(y); - if (comp) ++j; - return (j == end() || key_compare(k, key(j.node))) ? end() : j; -} - -template <class Key, class Value, class KeyOfValue, class Compare> -#ifdef __GNUG__ -__SIZE_TYPE__ -#else -rb_tree<Key, Value, KeyOfValue, Compare>::size_type -#endif -rb_tree<Key, Value, KeyOfValue, Compare>::count(const Key& k) const { - pair<const_iterator, const_iterator> p = equal_range(k); - size_type n = 0; - distance(p.first, p.second, n); - return n; -} - -template <class Key, class Value, class KeyOfValue, class Compare> -#ifdef __GNUC__ -rb_tree_iterator<Key, Value, KeyOfValue, Compare> -rb_tree<Key, Value, KeyOfValue, Compare>::lower_bound_hack(const Key& k) { -#else -rb_tree<Key, Value, KeyOfValue, Compare>::iterator -rb_tree<Key, Value, KeyOfValue, Compare>::lower_bound(const Key& k) { -#endif - link_type y = header; - link_type x = root(); - bool comp = false; - while (x != &__rb_NIL) { - y = x; - comp = key_compare(key(x), k); - x = comp ? right(x) : left(x); - } - iterator j = iterator(y); - return comp ? ++j : j; -} - -template <class Key, class Value, class KeyOfValue, class Compare> -#ifdef __GNUC__ -rb_tree_const_iterator<Key, Value, KeyOfValue, Compare> -rb_tree<Key, Value, KeyOfValue, Compare>::lower_bound_hack(const Key& k) const { -#else -rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator -rb_tree<Key, Value, KeyOfValue, Compare>::lower_bound(const Key& k) const { -#endif - link_type y = header; - link_type x = root(); - bool comp = false; - while (x != &__rb_NIL) { - y = x; - comp = key_compare(key(x), k); - x = comp ? right(x) : left(x); - } - const_iterator j = const_iterator(y); - return comp ? ++j : j; -} - -template <class Key, class Value, class KeyOfValue, class Compare> -#ifdef __GNUC__ -rb_tree_iterator<Key, Value, KeyOfValue, Compare> -rb_tree<Key, Value, KeyOfValue, Compare>::upper_bound_hack(const Key& k) { -#else -rb_tree<Key, Value, KeyOfValue, Compare>::iterator -rb_tree<Key, Value, KeyOfValue, Compare>::upper_bound(const Key& k) { -#endif - link_type y = header; - link_type x = root(); - bool comp = true; - while (x != &__rb_NIL) { - y = x; - comp = key_compare(k, key(x)); - x = comp ? left(x) : right(x); - } - iterator j = iterator(y); - return comp ? j : ++j; -} - -template <class Key, class Value, class KeyOfValue, class Compare> -#ifdef __GNUC__ -rb_tree_const_iterator<Key, Value, KeyOfValue, Compare> -rb_tree<Key, Value, KeyOfValue, Compare>::upper_bound_hack(const Key& k) const { -#else -rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator -rb_tree<Key, Value, KeyOfValue, Compare>::upper_bound(const Key& k) const { -#endif - link_type y = header; - link_type x = root(); - bool comp = true; - while (x != &__rb_NIL) { - y = x; - comp = key_compare(k, key(x)); - x = comp ? left(x) : right(x); - } - const_iterator j = const_iterator(y); - return comp ? j : ++j; -} - - -#ifndef __GNUC__ -template <class Key, class Value, class KeyOfValue, class Compare> -rb_tree<Key, Value, KeyOfValue, Compare>::pair_iterator_iterator -rb_tree<Key, Value, KeyOfValue, Compare>::equal_range(const Key& k) { - return pair_iterator_iterator(lower_bound(k), upper_bound(k)); -} - -template <class Key, class Value, class KeyOfValue, class Compare> -rb_tree<Key, Value, KeyOfValue, Compare>::pair_citerator_citerator -rb_tree<Key, Value, KeyOfValue, Compare>::equal_range(const Key& k) const { - return pair_citerator_citerator(lower_bound(k), upper_bound(k)); -} - -template <class Key, class Value, class KeyOfValue, class Compare> -inline void -rb_tree<Key, Value, KeyOfValue, Compare>::rotate_left(link_type x) { - link_type y = right(x); - right(x) = left(y); - if (left(y) != &__rb_NIL) - parent(left(y)) = x; - parent(y) = parent(x); - if (x == root()) - root() = y; - else if (x == left(parent(x))) - left(parent(x)) = y; - else - right(parent(x)) = y; - left(y) = x; - parent(x) = y; -} - -template <class Key, class Value, class KeyOfValue, class Compare> -inline void -rb_tree<Key, Value, KeyOfValue, Compare>::rotate_right(link_type x) { - link_type y = left(x); - left(x) = right(y); - if (right(y) != &__rb_NIL) - parent(right(y)) = x; - parent(y) = parent(x); - if (x == root()) - root() = y; - else if (x == right(parent(x))) - right(parent(x)) = y; - else - left(parent(x)) = y; - right(y) = x; - parent(x) = y; -} -#endif - -#endif - diff --git a/contrib/libg++/libstdc++/stl/vector.h b/contrib/libg++/libstdc++/stl/vector.h deleted file mode 100644 index e609aa109a0a6..0000000000000 --- a/contrib/libg++/libstdc++/stl/vector.h +++ /dev/null @@ -1,355 +0,0 @@ -/* - * - * 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. - * - */ - -#ifndef VECTOR_H -#define VECTOR_H - -#include <function.h> -#include <algobase.h> -#ifndef __GNUG__ -#include <bool.h> -#endif - -#ifndef Allocator -#define Allocator allocator -#include <defalloc.h> -#endif - -#ifndef vector -#define vector vector -#endif - -template <class T> -class vector { -public: - - typedef Allocator<T> vector_allocator; - typedef T value_type; - typedef vector_allocator::pointer pointer; - typedef vector_allocator::pointer iterator; - typedef vector_allocator::const_pointer const_iterator; - typedef vector_allocator::reference reference; - typedef vector_allocator::const_reference const_reference; - typedef vector_allocator::size_type size_type; - typedef vector_allocator::difference_type difference_type; - typedef reverse_iterator<const_iterator, value_type, const_reference, - difference_type> const_reverse_iterator; - typedef reverse_iterator<iterator, value_type, reference, difference_type> - reverse_iterator; -protected: - static Allocator<T> static_allocator; - iterator start; - iterator finish; - iterator end_of_storage; -#ifdef __GNUG__ - void insert_aux(iterator position, const T& x) { - insert_aux(vector_iterator<T>(position), x); - } - void insert_aux(vector_iterator<T> position, const T& x); -#else - void insert_aux(iterator position, const T& x); -#endif -public: - iterator begin() { return start; } - const_iterator begin() const { return start; } - iterator end() { return finish; } - const_iterator end() const { return finish; } - 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()); - } - size_type size() const { return size_type(end() - begin()); } - size_type max_size() const { return static_allocator.max_size(); } - size_type capacity() const { return size_type(end_of_storage - begin()); } - bool empty() const { return begin() == end(); } - reference operator[](size_type n) { return *(begin() + n); } - const_reference operator[](size_type n) const { return *(begin() + n); } - vector() : start(0), finish(0), end_of_storage(0) {} - vector(size_type n, const T& value = T()) { - start = static_allocator.allocate(n); - uninitialized_fill_n(start, n, value); - finish = start + n; - end_of_storage = finish; - } - vector(const vector<T>& x) { - start = static_allocator.allocate(x.end() - x.begin()); - finish = uninitialized_copy(x.begin(), x.end(), start); - end_of_storage = finish; - } - vector(const_iterator first, const_iterator last) { - size_type n = 0; - distance(first, last, n); - start = static_allocator.allocate(n); - finish = uninitialized_copy(first, last, start); - end_of_storage = finish; - } - ~vector() { - destroy(start, finish); - static_allocator.deallocate(start); - } - vector<T>& operator=(const vector<T>& x); - void reserve(size_type n) { - if (capacity() < n) { - iterator tmp = static_allocator.allocate(n); - uninitialized_copy(begin(), end(), tmp); - destroy(start, finish); - static_allocator.deallocate(start); - finish = tmp + size(); - start = tmp; - end_of_storage = begin() + n; - } - } - reference front() { return *begin(); } - const_reference front() const { return *begin(); } - reference back() { return *(end() - 1); } - const_reference back() const { return *(end() - 1); } - void push_back(const T& x) { - if (finish != end_of_storage) { - /* Borland bug */ - construct(finish, x); - finish++; - } else - insert_aux(end(), x); - } - void swap(vector<T>& x) { - ::swap(start, x.start); - ::swap(finish, x.finish); - ::swap(end_of_storage, x.end_of_storage); - } - iterator insert(iterator position, const T& x) { - size_type n = position - begin(); - if (finish != end_of_storage && position == end()) { - /* Borland bug */ - construct(finish, x); - finish++; - } else - insert_aux(position, x); - return begin() + n; - } -#ifdef __GNUG__ - void insert (iterator position, const_iterator first, - const_iterator last) { - insert(vector_iterator<T>(position), - vector_const_iterator<T>(first), - vector_const_iterator<T>(last)); - } - void insert (vector_iterator<T> position, vector_const_iterator<T> first, - vector_const_iterator<T> last); - void insert (iterator position, size_type n, const T& x) { - insert(vector_iterator<T>(position), n, x); - } - void insert (vector_iterator<T> position, size_type n, const T& x); -#else - void insert (iterator position, const_iterator first, - const_iterator last); - void insert (iterator position, size_type n, const T& x); -#endif - void pop_back() { - /* Borland bug */ - --finish; - destroy(finish); - } - void erase(iterator position) { - if (position + 1 != end()) - copy(position + 1, end(), position); - /* Borland bug */ - --finish; - destroy(finish); - } - void erase(iterator first, iterator last) { - vector<T>::iterator i = copy(last, end(), first); - destroy(i, finish); - // work around for destroy(copy(last, end(), first), finish); - finish = finish - (last - first); - } -}; - -#ifdef __GNUG__ -template <class T> -struct vector_iterator { - vector<T>::iterator it; - vector_iterator(vector<T>::iterator i) : it(i) {} - operator vector<T>::iterator() { - return it; - } -}; - -template <class T> -inline T* value_type(const vector_iterator<T>&) { - return (T*)(0); -} - - -template <class T> -struct vector_const_iterator { - vector<T>::const_iterator it; - vector_const_iterator(vector<T>::const_iterator i) : it(i) {} - operator vector<T>::const_iterator() { - return it; - } -}; -#endif - -template <class T> -inline bool operator==(const vector<T>& x, const vector<T>& y) { - return x.size() == y.size() && equal(x.begin(), x.end(), y.begin()); -} - -template <class T> -inline bool operator<(const vector<T>& x, const vector<T>& y) { - return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); -} - -#ifndef __GNUG__ -template <class T> -vector<T>::vector_allocator vector<T>::static_allocator; -#endif - -template <class T> -vector<T>& vector<T>::operator=(const vector<T>& x) { - if (&x == this) return *this; - if (x.size() > capacity()) { - destroy(start, finish); - static_allocator.deallocate(start); - start = static_allocator.allocate(x.end() - x.begin()); - end_of_storage = uninitialized_copy(x.begin(), x.end(), start); - } else if (size() >= x.size()) { - vector<T>::iterator i = copy(x.begin(), x.end(), begin()); - destroy(i, finish); - // work around for destroy(copy(x.begin(), x.end(), begin()), finish); - } else { - copy(x.begin(), x.begin() + size(), begin()); - uninitialized_copy(x.begin() + size(), x.end(), begin() + size()); - } - finish = begin() + x.size(); - return *this; -} - -template <class T> -#ifdef __GNUG__ -void vector<T>::insert_aux(vector_iterator<T> posn, const T& x) { - iterator position = posn; -#else -void vector<T>::insert_aux(iterator position, const T& x) { -#endif - if (finish != end_of_storage) { - construct(finish, *(finish - 1)); - copy_backward(position, finish - 1, finish); - *position = x; - ++finish; - } else { - size_type len = size() ? 2 * size() - : static_allocator.init_page_size(); - iterator tmp = static_allocator.allocate(len); - uninitialized_copy(begin(), position, tmp); - construct(tmp + (position - begin()), x); - uninitialized_copy(position, end(), tmp + (position - begin()) + 1); - destroy(begin(), end()); - static_allocator.deallocate(begin()); - end_of_storage = tmp + len; - finish = tmp + size() + 1; - start = tmp; - } -} - -template <class T> -#ifdef __GNUG__ -void vector<T>::insert(vector_iterator<T> posn, - size_t n, - const T& x) { - iterator position = posn; -#else -void vector<T>::insert(iterator position, size_type n, const T& x) { -#endif - if (n == 0) return; - if ((size_type) (end_of_storage - finish) >= n) { - if ((size_type) (end() - position) > n) { - uninitialized_copy(end() - n, end(), end()); - copy_backward(position, end() - n, end()); - fill(position, position + n, x); - } else { - uninitialized_copy(position, end(), position + n); - fill(position, end(), x); - uninitialized_fill_n(end(), n - (end() - position), x); - } - finish += n; - } else { - size_type len = size() + max(size(), n); - iterator tmp = static_allocator.allocate(len); - uninitialized_copy(begin(), position, tmp); - uninitialized_fill_n(tmp + (position - begin()), n, x); - uninitialized_copy(position, end(), tmp + (position - begin() + n)); - destroy(begin(), end()); - static_allocator.deallocate(begin()); - end_of_storage = tmp + len; - finish = tmp + size() + n; - start = tmp; - } -} - -template <class T> -#ifdef __GNUG__ -void vector<T>::insert(vector_iterator<T> posn, - vector_const_iterator<T> fi, - vector_const_iterator<T> la) { - iterator position = posn; - const_iterator first = fi; - const_iterator last = la; -#else -void vector<T>::insert(iterator position, - const_iterator first, - const_iterator last) { -#endif - if (first == last) return; - size_type n = 0; - distance(first, last, n); - if ((size_type) (end_of_storage - finish) >= n) { - if ((size_type) (end() - position) > n) { - uninitialized_copy(end() - n, end(), end()); - copy_backward(position, end() - n, end()); - copy(first, last, position); - } else { - uninitialized_copy(position, end(), position + n); - copy(first, first + (end() - position), position); - uninitialized_copy(first + (end() - position), last, end()); - } - finish += n; - } else { - size_type len = size() + max(size(), n); - iterator tmp = static_allocator.allocate(len); - uninitialized_copy(begin(), position, tmp); - uninitialized_copy(first, last, tmp + (position - begin())); - uninitialized_copy(position, end(), tmp + (position - begin() + n)); - destroy(begin(), end()); - static_allocator.deallocate(begin()); - end_of_storage = tmp + len; - finish = tmp + size() + n; - start = tmp; - } -} - -#undef Allocator -#undef vector - -#endif - - - - - |