diff options
author | peter <peter@FreeBSD.org> | 2008-06-01 00:03:21 +0000 |
---|---|---|
committer | peter <peter@FreeBSD.org> | 2008-06-01 00:03:21 +0000 |
commit | a2be5f0c15218b0177d73b17d9bcb7589965d685 (patch) | |
tree | c9f0cd9c22378356a1716d32e13e70bc90f98b9c /libg++/libstdc++/stl | |
parent | 9e0f3cc19c9df1594c9cc36cfd8fddc83c52ad12 (diff) | |
download | FreeBSD-src-a2be5f0c15218b0177d73b17d9bcb7589965d685.zip FreeBSD-src-a2be5f0c15218b0177d73b17d9bcb7589965d685.tar.gz |
Reorganize the gcc vendor import work area. This flattens out a bunch
of unnecessary path components that are relics of cvs2svn.
(These are directory moves)
Diffstat (limited to 'libg++/libstdc++/stl')
55 files changed, 9296 insertions, 0 deletions
diff --git a/libg++/libstdc++/stl/ChangeLog b/libg++/libstdc++/stl/ChangeLog new file mode 100644 index 0000000..786989d --- /dev/null +++ b/libg++/libstdc++/stl/ChangeLog @@ -0,0 +1,86 @@ +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/libg++/libstdc++/stl/Makefile.in b/libg++/libstdc++/stl/Makefile.in new file mode 100644 index 0000000..438d81d --- /dev/null +++ b/libg++/libstdc++/stl/Makefile.in @@ -0,0 +1,12 @@ +#### 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/libg++/libstdc++/stl/README b/libg++/libstdc++/stl/README new file mode 100644 index 0000000..fad26de --- /dev/null +++ b/libg++/libstdc++/stl/README @@ -0,0 +1,86 @@ +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/libg++/libstdc++/stl/algo.h b/libg++/libstdc++/stl/algo.h new file mode 100644 index 0000000..e038d71 --- /dev/null +++ b/libg++/libstdc++/stl/algo.h @@ -0,0 +1,2386 @@ +/* + * + * 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/libg++/libstdc++/stl/algobase.h b/libg++/libstdc++/stl/algobase.h new file mode 100644 index 0000000..21cea93 --- /dev/null +++ b/libg++/libstdc++/stl/algobase.h @@ -0,0 +1,232 @@ +/* + * + * 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/libg++/libstdc++/stl/bool.h b/libg++/libstdc++/stl/bool.h new file mode 100644 index 0000000..9d86aac --- /dev/null +++ b/libg++/libstdc++/stl/bool.h @@ -0,0 +1,20 @@ +#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/libg++/libstdc++/stl/bvector.h b/libg++/libstdc++/stl/bvector.h new file mode 100644 index 0000000..f9fe106 --- /dev/null +++ b/libg++/libstdc++/stl/bvector.h @@ -0,0 +1,421 @@ +/* + * + * 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/libg++/libstdc++/stl/configure.in b/libg++/libstdc++/stl/configure.in new file mode 100644 index 0000000..d452935 --- /dev/null +++ b/libg++/libstdc++/stl/configure.in @@ -0,0 +1,37 @@ +# 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/libg++/libstdc++/stl/defalloc.h b/libg++/libstdc++/stl/defalloc.h new file mode 100644 index 0000000..388e58f --- /dev/null +++ b/libg++/libstdc++/stl/defalloc.h @@ -0,0 +1,176 @@ +/* + * + * 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/libg++/libstdc++/stl/deque.h b/libg++/libstdc++/stl/deque.h new file mode 100644 index 0000000..dc79014 --- /dev/null +++ b/libg++/libstdc++/stl/deque.h @@ -0,0 +1,684 @@ +/* + * + * 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/libg++/libstdc++/stl/faralloc.h b/libg++/libstdc++/stl/faralloc.h new file mode 100644 index 0000000..b29602c --- /dev/null +++ b/libg++/libstdc++/stl/faralloc.h @@ -0,0 +1,120 @@ +/* + * + * 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/libg++/libstdc++/stl/fdeque.h b/libg++/libstdc++/stl/fdeque.h new file mode 100644 index 0000000..7b512b6 --- /dev/null +++ b/libg++/libstdc++/stl/fdeque.h @@ -0,0 +1,39 @@ +/* + * + * 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/libg++/libstdc++/stl/flist.h b/libg++/libstdc++/stl/flist.h new file mode 100644 index 0000000..35fe9bf --- /dev/null +++ b/libg++/libstdc++/stl/flist.h @@ -0,0 +1,39 @@ +/* + * + * 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/libg++/libstdc++/stl/fmap.h b/libg++/libstdc++/stl/fmap.h new file mode 100644 index 0000000..65aa209 --- /dev/null +++ b/libg++/libstdc++/stl/fmap.h @@ -0,0 +1,44 @@ +/* + * + * 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/libg++/libstdc++/stl/fmultmap.h b/libg++/libstdc++/stl/fmultmap.h new file mode 100644 index 0000000..ecb5cd4 --- /dev/null +++ b/libg++/libstdc++/stl/fmultmap.h @@ -0,0 +1,44 @@ +/* + * + * 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/libg++/libstdc++/stl/fmultset.h b/libg++/libstdc++/stl/fmultset.h new file mode 100644 index 0000000..ca98876 --- /dev/null +++ b/libg++/libstdc++/stl/fmultset.h @@ -0,0 +1,44 @@ +/* + * + * 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/libg++/libstdc++/stl/fset.h b/libg++/libstdc++/stl/fset.h new file mode 100644 index 0000000..b374bc4 --- /dev/null +++ b/libg++/libstdc++/stl/fset.h @@ -0,0 +1,44 @@ +/* + * + * 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/libg++/libstdc++/stl/function.h b/libg++/libstdc++/stl/function.h new file mode 100644 index 0000000..46fe555 --- /dev/null +++ b/libg++/libstdc++/stl/function.h @@ -0,0 +1,282 @@ +/* + * + * 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/libg++/libstdc++/stl/hdeque.h b/libg++/libstdc++/stl/hdeque.h new file mode 100644 index 0000000..0d47098 --- /dev/null +++ b/libg++/libstdc++/stl/hdeque.h @@ -0,0 +1,39 @@ +/* + * + * 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/libg++/libstdc++/stl/heap.h b/libg++/libstdc++/stl/heap.h new file mode 100644 index 0000000..7f2747f --- /dev/null +++ b/libg++/libstdc++/stl/heap.h @@ -0,0 +1,193 @@ +/* + * + * 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/libg++/libstdc++/stl/hlist.h b/libg++/libstdc++/stl/hlist.h new file mode 100644 index 0000000..543ffa7 --- /dev/null +++ b/libg++/libstdc++/stl/hlist.h @@ -0,0 +1,39 @@ +/* + * + * 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/libg++/libstdc++/stl/hmap.h b/libg++/libstdc++/stl/hmap.h new file mode 100644 index 0000000..f40abc0 --- /dev/null +++ b/libg++/libstdc++/stl/hmap.h @@ -0,0 +1,44 @@ +/* + * + * 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/libg++/libstdc++/stl/hmultmap.h b/libg++/libstdc++/stl/hmultmap.h new file mode 100644 index 0000000..0a8551e --- /dev/null +++ b/libg++/libstdc++/stl/hmultmap.h @@ -0,0 +1,44 @@ +/* + * + * 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/libg++/libstdc++/stl/hmultset.h b/libg++/libstdc++/stl/hmultset.h new file mode 100644 index 0000000..e207299 --- /dev/null +++ b/libg++/libstdc++/stl/hmultset.h @@ -0,0 +1,44 @@ +/* + * + * 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/libg++/libstdc++/stl/hset.h b/libg++/libstdc++/stl/hset.h new file mode 100644 index 0000000..11a1576 --- /dev/null +++ b/libg++/libstdc++/stl/hset.h @@ -0,0 +1,44 @@ +/* + * + * 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/libg++/libstdc++/stl/hugalloc.h b/libg++/libstdc++/stl/hugalloc.h new file mode 100644 index 0000000..a793ab2 --- /dev/null +++ b/libg++/libstdc++/stl/hugalloc.h @@ -0,0 +1,38 @@ +/* + * + * 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/libg++/libstdc++/stl/hvector.h b/libg++/libstdc++/stl/hvector.h new file mode 100644 index 0000000..e7fb415 --- /dev/null +++ b/libg++/libstdc++/stl/hvector.h @@ -0,0 +1,39 @@ +/* + * + * 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/libg++/libstdc++/stl/iterator.h b/libg++/libstdc++/stl/iterator.h new file mode 100644 index 0000000..5e51598 --- /dev/null +++ b/libg++/libstdc++/stl/iterator.h @@ -0,0 +1,395 @@ +/* + * + * 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/libg++/libstdc++/stl/lbvector.h b/libg++/libstdc++/stl/lbvector.h new file mode 100644 index 0000000..763666c --- /dev/null +++ b/libg++/libstdc++/stl/lbvector.h @@ -0,0 +1,39 @@ +/* + * + * 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/libg++/libstdc++/stl/ldeque.h b/libg++/libstdc++/stl/ldeque.h new file mode 100644 index 0000000..4c8761c --- /dev/null +++ b/libg++/libstdc++/stl/ldeque.h @@ -0,0 +1,39 @@ +/* + * + * 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/libg++/libstdc++/stl/list.h b/libg++/libstdc++/stl/list.h new file mode 100644 index 0000000..42b5d0f --- /dev/null +++ b/libg++/libstdc++/stl/list.h @@ -0,0 +1,531 @@ +/* + * + * 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/libg++/libstdc++/stl/llist.h b/libg++/libstdc++/stl/llist.h new file mode 100644 index 0000000..07ee611 --- /dev/null +++ b/libg++/libstdc++/stl/llist.h @@ -0,0 +1,39 @@ +/* + * + * 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/libg++/libstdc++/stl/lmap.h b/libg++/libstdc++/stl/lmap.h new file mode 100644 index 0000000..da1eeba --- /dev/null +++ b/libg++/libstdc++/stl/lmap.h @@ -0,0 +1,44 @@ +/* + * + * 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/libg++/libstdc++/stl/lmultmap.h b/libg++/libstdc++/stl/lmultmap.h new file mode 100644 index 0000000..1a87e33 --- /dev/null +++ b/libg++/libstdc++/stl/lmultmap.h @@ -0,0 +1,44 @@ +/* + * + * 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/libg++/libstdc++/stl/lmultset.h b/libg++/libstdc++/stl/lmultset.h new file mode 100644 index 0000000..bb1571f --- /dev/null +++ b/libg++/libstdc++/stl/lmultset.h @@ -0,0 +1,44 @@ +/* + * + * 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/libg++/libstdc++/stl/lngalloc.h b/libg++/libstdc++/stl/lngalloc.h new file mode 100644 index 0000000..6685ea5 --- /dev/null +++ b/libg++/libstdc++/stl/lngalloc.h @@ -0,0 +1,54 @@ +/* + * + * 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/libg++/libstdc++/stl/lset.h b/libg++/libstdc++/stl/lset.h new file mode 100644 index 0000000..e4d52f7 --- /dev/null +++ b/libg++/libstdc++/stl/lset.h @@ -0,0 +1,44 @@ +/* + * + * 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/libg++/libstdc++/stl/map.h b/libg++/libstdc++/stl/map.h new file mode 100644 index 0000000..5c1c30d --- /dev/null +++ b/libg++/libstdc++/stl/map.h @@ -0,0 +1,150 @@ +/* + * + * 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/libg++/libstdc++/stl/multimap.h b/libg++/libstdc++/stl/multimap.h new file mode 100644 index 0000000..2478e24 --- /dev/null +++ b/libg++/libstdc++/stl/multimap.h @@ -0,0 +1,142 @@ +/* + * + * 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/libg++/libstdc++/stl/multiset.h b/libg++/libstdc++/stl/multiset.h new file mode 100644 index 0000000..1ee6d93 --- /dev/null +++ b/libg++/libstdc++/stl/multiset.h @@ -0,0 +1,129 @@ +/* + * + * 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/libg++/libstdc++/stl/neralloc.h b/libg++/libstdc++/stl/neralloc.h new file mode 100644 index 0000000..c66e9b3 --- /dev/null +++ b/libg++/libstdc++/stl/neralloc.h @@ -0,0 +1,38 @@ +/* + * + * 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/libg++/libstdc++/stl/nmap.h b/libg++/libstdc++/stl/nmap.h new file mode 100644 index 0000000..99754c7 --- /dev/null +++ b/libg++/libstdc++/stl/nmap.h @@ -0,0 +1,44 @@ +/* + * + * 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/libg++/libstdc++/stl/nmultmap.h b/libg++/libstdc++/stl/nmultmap.h new file mode 100644 index 0000000..a6ad67c --- /dev/null +++ b/libg++/libstdc++/stl/nmultmap.h @@ -0,0 +1,44 @@ +/* + * + * 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/libg++/libstdc++/stl/nmultset.h b/libg++/libstdc++/stl/nmultset.h new file mode 100644 index 0000000..3a0ad30 --- /dev/null +++ b/libg++/libstdc++/stl/nmultset.h @@ -0,0 +1,44 @@ +/* + * + * 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/libg++/libstdc++/stl/nset.h b/libg++/libstdc++/stl/nset.h new file mode 100644 index 0000000..325d6b9 --- /dev/null +++ b/libg++/libstdc++/stl/nset.h @@ -0,0 +1,44 @@ +/* + * + * 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/libg++/libstdc++/stl/pair.h b/libg++/libstdc++/stl/pair.h new file mode 100644 index 0000000..817d9a4 --- /dev/null +++ b/libg++/libstdc++/stl/pair.h @@ -0,0 +1,46 @@ +/* + * + * 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/libg++/libstdc++/stl/projectn.h b/libg++/libstdc++/stl/projectn.h new file mode 100644 index 0000000..766796e --- /dev/null +++ b/libg++/libstdc++/stl/projectn.h @@ -0,0 +1,33 @@ +/* + * + * 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/libg++/libstdc++/stl/random.cc b/libg++/libstdc++/stl/random.cc new file mode 100644 index 0000000..e79872c --- /dev/null +++ b/libg++/libstdc++/stl/random.cc @@ -0,0 +1,60 @@ +/* + * + * 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/libg++/libstdc++/stl/set.h b/libg++/libstdc++/stl/set.h new file mode 100644 index 0000000..d108e42 --- /dev/null +++ b/libg++/libstdc++/stl/set.h @@ -0,0 +1,132 @@ +/* + * + * 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/libg++/libstdc++/stl/stack.h b/libg++/libstdc++/stl/stack.h new file mode 100644 index 0000000..83a59a4 --- /dev/null +++ b/libg++/libstdc++/stl/stack.h @@ -0,0 +1,120 @@ +/* + * + * 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/libg++/libstdc++/stl/tempbuf.cc b/libg++/libstdc++/stl/tempbuf.cc new file mode 100644 index 0000000..2e7408e --- /dev/null +++ b/libg++/libstdc++/stl/tempbuf.cc @@ -0,0 +1,18 @@ +/* + * + * 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/libg++/libstdc++/stl/tempbuf.h b/libg++/libstdc++/stl/tempbuf.h new file mode 100644 index 0000000..238b6ac --- /dev/null +++ b/libg++/libstdc++/stl/tempbuf.h @@ -0,0 +1,55 @@ +/* + * + * 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/libg++/libstdc++/stl/tree.cc b/libg++/libstdc++/stl/tree.cc new file mode 100644 index 0000000..e4a9cfe --- /dev/null +++ b/libg++/libstdc++/stl/tree.cc @@ -0,0 +1,3 @@ +#include "tree.h" + +__rb_tree_node_base __rb_NIL = { black, 0, 0, 0 }; diff --git a/libg++/libstdc++/stl/tree.h b/libg++/libstdc++/stl/tree.h new file mode 100644 index 0000000..3ae5da0 --- /dev/null +++ b/libg++/libstdc++/stl/tree.h @@ -0,0 +1,1246 @@ +/* + * + * 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/libg++/libstdc++/stl/vector.h b/libg++/libstdc++/stl/vector.h new file mode 100644 index 0000000..e609aa1 --- /dev/null +++ b/libg++/libstdc++/stl/vector.h @@ -0,0 +1,355 @@ +/* + * + * 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 + + + + + |