diff options
author | irfan <irfan@ae88bc3d-4319-0410-8dbf-d08b4c9d3795> | 1996-10-29 07:34:51 +0000 |
---|---|---|
committer | irfan <irfan@ae88bc3d-4319-0410-8dbf-d08b4c9d3795> | 1996-10-29 07:34:51 +0000 |
commit | 60aa7663705dd9338f66fb28384e8b31900434bb (patch) | |
tree | 8abdb06b46392187d869ab1716927aa9ed8f045f /STL | |
parent | 1d10be0da172c415a8cb0c641d79b6b4bf0a0eb6 (diff) | |
download | ATCD-60aa7663705dd9338f66fb28384e8b31900434bb.tar.gz |
STL files from (modified for VC++4.0) HP's implementation of STL.
Diffstat (limited to 'STL')
-rw-r--r-- | STL/algo.h | 2593 | ||||
-rw-r--r-- | STL/algobase.h | 250 | ||||
-rw-r--r-- | STL/bool.h | 37 | ||||
-rw-r--r-- | STL/bstring.h | 2497 | ||||
-rw-r--r-- | STL/bvector.h | 438 | ||||
-rw-r--r-- | STL/defalloc.h | 198 | ||||
-rw-r--r-- | STL/deque.h | 586 | ||||
-rw-r--r-- | STL/function.h | 287 | ||||
-rw-r--r-- | STL/heap.h | 212 | ||||
-rw-r--r-- | STL/iterator.h | 414 | ||||
-rw-r--r-- | STL/list.h | 510 | ||||
-rw-r--r-- | STL/map.h | 167 | ||||
-rw-r--r-- | STL/multimap.h | 161 | ||||
-rw-r--r-- | STL/multiset.h | 148 | ||||
-rw-r--r-- | STL/pair.h | 62 | ||||
-rw-r--r-- | STL/projectn.h | 50 | ||||
-rw-r--r-- | STL/ptr.h | 338 | ||||
-rw-r--r-- | STL/random.cpp | 58 | ||||
-rw-r--r-- | STL/set.h | 151 | ||||
-rw-r--r-- | STL/stack.h | 137 | ||||
-rw-r--r-- | STL/stl.h | 206 | ||||
-rw-r--r-- | STL/tempbuf.cpp | 19 | ||||
-rw-r--r-- | STL/tempbuf.h | 74 | ||||
-rw-r--r-- | STL/tree.h | 1068 | ||||
-rw-r--r-- | STL/vector.h | 302 |
25 files changed, 10963 insertions, 0 deletions
diff --git a/STL/algo.h b/STL/algo.h new file mode 100644 index 00000000000..3e91b1375a3 --- /dev/null +++ b/STL/algo.h @@ -0,0 +1,2593 @@ +/* + * + * 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 and Microsoft + * Corporation make 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> +#include <bool.h> +#include <pair.h> +#include <iterator.h> +#include <algobase.h> +#include <heap.h> +#include <tempbuf.h> + + +/* + *Added by d:\\convert.pl --begin-- + */ +namespace std { +/* + *Added by d:\\convert.pl --end-- + */ + +template <class T> +inline T __median(T a, T b, 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 T __median(T a, T b, 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 InputIterator> +InputIterator adjacent_find(InputIterator first, InputIterator last) { + if (first == last) return last; + InputIterator next = first; + while(++next != last) { + if (*first == *next) return first; + first = next; + } + return last; +} + +template <class InputIterator, class BinaryPredicate> +InputIterator adjacent_find(InputIterator first, InputIterator last, + BinaryPredicate binary_pred) { + if (first == last) return last; + InputIterator 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 Distance> +ForwardIterator1 __search(ForwardIterator1 first1, ForwardIterator1 last1, + ForwardIterator2 first2, ForwardIterator2 last2, + Distance*) { + Distance d1 = 0; + distance(first1, last1, d1); + Distance 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)); +} + +template <class ForwardIterator1, class ForwardIterator2, + class BinaryPredicate, class Distance> +ForwardIterator1 __search(ForwardIterator1 first1, ForwardIterator1 last1, + ForwardIterator2 first2, ForwardIterator2 last2, + BinaryPredicate binary_pred, Distance*) { + Distance d1 = 0; + distance(first1, last1, d1); + Distance 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)); +} + +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> +void generate_n(OutputIterator first, Size n, Generator gen) { + while (n-- > 0) *first++ = gen(); +} + +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 RandomAccessIterator3, class Distance, class T> +RandomAccessIterator3 __merge_aux(RandomAccessIterator1 first1, + RandomAccessIterator1 last1, + RandomAccessIterator2 first2, + RandomAccessIterator2 last2, + RandomAccessIterator3 result, + Distance& fill_pointer, T*){ + Distance len = 0; + while (first1 != last1 && first2 != last2 && len < fill_pointer) { + ++len; + if (*first2 < *first1) + *result++ = *first2++; + else + *result++ = *first1++; + } + if (fill_pointer == len) { + raw_storage_iterator<RandomAccessIterator3, T> p = result; + result += (last1 - first1) + (last2 - first2); + fill_pointer += (last1 - first1) + (last2 - first2); + while (first1 != last1 && first2 != last2) + if (*first2 < *first1) + *p++ = *first2++; + else + *p++ = *first1++; + copy(first2, last2, copy(first1, last1, p)); + } else if (first2 == last2) { + while (first1 != last1 && len < fill_pointer) { + ++len; + *result++ = *first1++; + } + if (fill_pointer == len) { + raw_storage_iterator<RandomAccessIterator3, T> p = result; + result += last1 - first1; + fill_pointer += last1 - first1; + while (first1 != last1) *p++ = *first1++; + } + } else { + while (first2 != last2 && len < fill_pointer) { + ++len; + *result++ = *first2++; + } + if (fill_pointer == len) { + raw_storage_iterator<RandomAccessIterator3, T> p = result; + result += last2 - first2; + fill_pointer += last2 - first2; + while (first2 != last2) *p++ = *first2++; + } + } + return result; +} + +template <class RandomAccessIterator1, class RandomAccessIterator2, + class RandomAccessIterator3, class Distance, class T, class Compare> +RandomAccessIterator3 __merge_aux(RandomAccessIterator1 first1, + RandomAccessIterator1 last1, + RandomAccessIterator2 first2, + RandomAccessIterator2 last2, + RandomAccessIterator3 result, + Distance& fill_pointer, T*, Compare comp){ + Distance len = 0; + while (first1 != last1 && first2 != last2 && len < fill_pointer) { + ++len; + if (comp(*first2, *first1)) + *result++ = *first2++; + else + *result++ = *first1++; + } + if (fill_pointer <= len) { + raw_storage_iterator<RandomAccessIterator3, T> p = result; + result += (last1 - first1) + (last2 - first2); + fill_pointer += (last1 - first1) + (last2 - first2); + while (first1 != last1 && first2 != last2) + if (comp(*first2, *first1)) + *p++ = *first2++; + else + *p++ = *first1++; + copy(first2, last2, copy(first1, last1, p)); + } else if (first2 == last2) { + while (first1 != last1 && len < fill_pointer) { + ++len; + *result++ = *first1++; + } + if (fill_pointer == len) { + raw_storage_iterator<RandomAccessIterator3, T> p = result; + result += last1 - first1; + fill_pointer += last1 - first1; + while (first1 != last1) *p++ = *first1++; + } + } else { + while (first2 != last2 && len < fill_pointer) { + ++len; + *result++ = *first2++; + } + if (fill_pointer == len) { + raw_storage_iterator<RandomAccessIterator3, T> p = result; + result += last2 - first2; + fill_pointer += last2 - first2; + while (first2 != last2) *p++ = *first2++; + } + } + return result; +} + +template <class RandomAccessIterator1, class RandomAccessIterator2, + class Distance, class T> +void __merge_sort_loop_aux(RandomAccessIterator1 first, + RandomAccessIterator1 last, + RandomAccessIterator2 result, Distance step_size, + Distance& fill_pointer, T*) { + Distance two_step = 2 * step_size; + + while (last - first >= two_step) { + result = __merge_aux(first, first + step_size, first + step_size, + first + two_step, result, fill_pointer, (T*)0); + first += two_step; + } + step_size = min(Distance(last - first), step_size); + + __merge_aux(first, first + step_size, first + step_size, last, result, + fill_pointer, (T*)0); +} + +template <class RandomAccessIterator1, class RandomAccessIterator2, + class Distance, class T, class Compare> +void __merge_sort_loop_aux(RandomAccessIterator1 first, + RandomAccessIterator1 last, + RandomAccessIterator2 result, Distance step_size, + Distance& fill_pointer, T*, Compare comp) { + Distance two_step = 2 * step_size; + + while (last - first >= two_step) { + result = __merge_aux(first, first + step_size, first + step_size, + first + two_step, result, fill_pointer, (T*)0, + comp); + first += two_step; + } + step_size = min(Distance(last - first), step_size); + + __merge_aux(first, first + step_size, first + step_size, last, result, + fill_pointer, (T*)0, 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& fill_pointer, 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_aux(first, last, buffer, step_size, fill_pointer, + (T*)0); + 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& fill_pointer, + 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_aux(first, last, buffer, step_size, fill_pointer, + (T*)0, 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, Distance& fill_pointer, T*) { + Distance len = (last - first + 1) / 2; + RandomAccessIterator middle = first + len; + if (len > buffer_size) { + __stable_sort_adaptive(first, middle, buffer, buffer_size, + fill_pointer, (T*)0); + __stable_sort_adaptive(middle, last, buffer, buffer_size, + fill_pointer, (T*)0); + } else { + __merge_sort_with_buffer(first, middle, buffer, fill_pointer, (T*)0); + __merge_sort_with_buffer(middle, last, buffer, fill_pointer, (T*)0); + } + __merge_adaptive(first, middle, last, Distance(middle - first), + Distance(last - middle), buffer, buffer_size, + fill_pointer, (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, Distance& fill_pointer, + 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, + fill_pointer, (T*)0, comp); + __stable_sort_adaptive(middle, last, buffer, buffer_size, + fill_pointer, (T*)0, comp); + } else { + __merge_sort_with_buffer(first, middle, buffer, fill_pointer, + (T*)0, comp); + __merge_sort_with_buffer(middle, last, buffer, fill_pointer, + (T*)0, comp); + } + __merge_adaptive(first, middle, last, Distance(middle - first), + Distance(last - middle), buffer, buffer_size, + fill_pointer, (T*)0, comp); +} + +template <class RandomAccessIterator, class Pointer, class Distance> +inline void __stable_sort(RandomAccessIterator first, + RandomAccessIterator last, + pair<Pointer, Distance> p) { + if (p.first == 0) { + __inplace_stable_sort(first, last); + return; + } + Distance fill_pointer = 0; + __stable_sort_adaptive(first, last, p.first, p.second, fill_pointer, + value_type(first)); + destroy(p.first, p.first + fill_pointer); + return_temporary_buffer(p.first); +} + +template <class RandomAccessIterator, class Pointer, class Distance, + class Compare> +inline void __stable_sort(RandomAccessIterator first, + RandomAccessIterator last, + pair<Pointer, Distance> p, Compare comp) { + if (p.first == 0) { + __inplace_stable_sort(first, last, comp); + return; + } + Distance fill_pointer = 0; + __stable_sort_adaptive(first, last, p.first, p.second, fill_pointer, + value_type(first), comp); + destroy(p.first, p.first + fill_pointer); + return_temporary_buffer(p.first); +} + +template <class RandomAccessIterator, class Distance> +inline void __stable_sort_aux(RandomAccessIterator first, + RandomAccessIterator last, Distance*) { + __stable_sort(first, last, get_temporary_buffer(Distance(last - first), + value_type(first))); +} + +template <class RandomAccessIterator, class Distance, class Compare> +inline void __stable_sort_aux(RandomAccessIterator first, + RandomAccessIterator last, Distance*, + Compare comp) { + __stable_sort(first, last, get_temporary_buffer(Distance(last - first), + value_type(first)), comp); +} + +template <class RandomAccessIterator> +inline void stable_sort(RandomAccessIterator first, + RandomAccessIterator last) { + __stable_sort_aux(first, last, distance_type(first)); +} + +template <class RandomAccessIterator, class Compare> +inline void stable_sort(RandomAccessIterator first, + RandomAccessIterator last, Compare comp) { + __stable_sort_aux(first, last, 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 (*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 (*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, + Distance& fill_pointer, T*) { + if (len1 <= len2 && len1 <= buffer_size) { + BidirectionalIterator i = first; + Pointer j = buffer; + len2 = 0; + while (len2 < len1 && len2 < fill_pointer) { + *buffer++ = *first++; + ++len2; + } + raw_storage_iterator<Pointer, T> end_buffer = buffer; + while (len2++ < len1) { + *end_buffer++ = *first++; + ++fill_pointer; + } + merge(j, j + len1, middle, last, i); + } else if (len2 <= buffer_size) { + BidirectionalIterator i = middle; + Pointer j = buffer; + len1 = 0; + while (len1 < len2 && len1 < fill_pointer) { + *buffer++ = *middle++; + ++len1; + } + raw_storage_iterator<Pointer, T> end_buffer = buffer; + while (len1++ < len2) { + *end_buffer++ = *middle++; + ++fill_pointer; + } + __merge_backward(first, i, j, j + len2, 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, fill_pointer, (T*)0); + __merge_adaptive(new_middle, second_cut, last, len1 - len11, + len2 - len22, buffer, buffer_size, fill_pointer, + (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, + Distance& fill_pointer, T*, Compare comp) { + if (len1 <= len2 && len1 <= buffer_size) { + BidirectionalIterator i = first; + Pointer j = buffer; + len2 = 0; + while (len2 < len1 && len2 < fill_pointer) { + *buffer++ = *first++; + ++len2; + } + raw_storage_iterator<Pointer, T> end_buffer = buffer; + while (len2++ < len1) { + *end_buffer++ = *first++; + ++fill_pointer; + } + merge(j, j + len1, middle, last, i, comp); + } else if (len2 <= buffer_size) { + BidirectionalIterator i = middle; + Pointer j = buffer; + len1 = 0; + while (len1 < len2 && len1 < fill_pointer) { + *buffer++ = *middle++; + ++len1; + } + raw_storage_iterator<Pointer, T> end_buffer = buffer; + while (len1++ < len2) { + *end_buffer++ = *middle++; + ++fill_pointer; + } + __merge_backward(first, i, j, j + len2, 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, fill_pointer, (T*)0, comp); + __merge_adaptive(new_middle, second_cut, last, len1 - len11, + len2 - len22, buffer, buffer_size, fill_pointer, + (T*)0, comp); + } +} + +template <class BidirectionalIterator, class Distance, class Pointer> +void __inplace_merge(BidirectionalIterator first, + BidirectionalIterator middle, + BidirectionalIterator last, Distance len1, Distance len2, + pair<Pointer, Distance> p) { + if (p.first == 0) { + __merge_without_buffer(first, middle, last, len1, len2); + return; + } + Distance fill_pointer = 0; + __merge_adaptive(first, middle, last, len1, len2, p.first, p.second, + fill_pointer, value_type(first)); + destroy(p.first, p.first + fill_pointer); + return_temporary_buffer(p.first); +} + +template <class BidirectionalIterator, class Distance, class Pointer, + class Compare> +void __inplace_merge(BidirectionalIterator first, + BidirectionalIterator middle, + BidirectionalIterator last, Distance len1, Distance len2, + pair<Pointer, Distance> p, Compare comp) { + if (p.first == 0) { + __merge_without_buffer(first, middle, last, len1, len2, comp); + return; + } + Distance fill_pointer = 0; + __merge_adaptive(first, middle, last, len1, len2, p.first, p.second, + fill_pointer, value_type(first), comp); + destroy(p.first, p.first + fill_pointer); + return_temporary_buffer(p.first); +} + +template <class BidirectionalIterator, class Distance> +inline void __inplace_merge_aux(BidirectionalIterator first, + BidirectionalIterator middle, + BidirectionalIterator last, 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, value_type(first))); +} + +template <class BidirectionalIterator, class Distance, class Compare> +inline void __inplace_merge_aux(BidirectionalIterator first, + BidirectionalIterator middle, + BidirectionalIterator last, 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, value_type(first)), + comp); +} + +template <class BidirectionalIterator> +inline void inplace_merge(BidirectionalIterator first, + BidirectionalIterator middle, + BidirectionalIterator last) { + __inplace_merge_aux(first, middle, last, distance_type(first)); +} + +template <class BidirectionalIterator, class Compare> +inline void inplace_merge(BidirectionalIterator first, + BidirectionalIterator middle, + BidirectionalIterator last, Compare comp) { + __inplace_merge_aux(first, middle, last, 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 InputIterator> +InputIterator max_element(InputIterator first, InputIterator last) { + if (first == last) return first; + InputIterator result = first; + while (++first != last) + if (*result < *first) result = first; + return result; +} + +template <class InputIterator, class Compare> +InputIterator max_element(InputIterator first, InputIterator last, + Compare comp) { + if (first == last) return first; + InputIterator result = first; + while (++first != last) + if (comp(*result, *first)) result = first; + return result; +} + +template <class InputIterator> +InputIterator min_element(InputIterator first, InputIterator last) { + if (first == last) return first; + InputIterator result = first; + while (++first != last) + if (*first < *result) result = first; + return result; +} + +template <class InputIterator, class Compare> +InputIterator min_element(InputIterator first, InputIterator last, + Compare comp) { + if (first == last) return first; + InputIterator 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 (!(*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 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(*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 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++; +} + + +/* + *Added by d:\\convert.pl --begin-- + */ +} +/* + *Added by d:\\convert.pl --end-- + */ + +#endif diff --git a/STL/algobase.h b/STL/algobase.h new file mode 100644 index 00000000000..24c6f7d398f --- /dev/null +++ b/STL/algobase.h @@ -0,0 +1,250 @@ +/* + * + * 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 and Microsoft + * Corporation make 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> + + +/* + *Added by d:\\convert.pl --begin-- + */ +namespace std { +/* + *Added by d:\\convert.pl --end-- + */ + +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> +void uninitialized_fill_n(ForwardIterator first, Size n, const T& x) { + while (n--) construct(first++, x); +} + +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> +void fill_n(OutputIterator first, Size n, const T& value) { + while (n-- > 0) *first++ = value; +} + +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; +} + + +/* + *Added by d:\\convert.pl --begin-- + */ +} +/* + *Added by d:\\convert.pl --end-- + */ + +#endif diff --git a/STL/bool.h b/STL/bool.h new file mode 100644 index 00000000000..dd73435e51e --- /dev/null +++ b/STL/bool.h @@ -0,0 +1,37 @@ + +/* + *Added by d:\\convert.pl --begin-- + */ +namespace std { +/* + *Added by d:\\convert.pl --end-- + */ + +/* + * + * 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 and Microsoft + * Corporation make 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 + +/* + *Added by d:\\convert.pl --begin-- + */ +} +/* + *Added by d:\\convert.pl --end-- + */ + diff --git a/STL/bstring.h b/STL/bstring.h new file mode 100644 index 00000000000..bcab7de632c --- /dev/null +++ b/STL/bstring.h @@ -0,0 +1,2497 @@ +/** + ** Copyright (c) 1994-1995 Modena Software Inc., + ** + ** Permission to use, copy, modify, distribute and sell this software + ** and its documentation for any purpose is hereby granted without fee, + ** provided that the above copyright notice appear in all copies and + ** that both that copyright notice and this permission notice appear + ** in supporting documentation. Modena Software, Inc. makes no + ** representations about the suitability of this software for any + ** purpose. It is provided "as is" without express or implied warranty. + ** + **/ + +#ifndef __cplusplus +#error Must use C++ for BSTRING.H +#endif + +#ifndef __MBSTRING_H +#define __MBSTRING_H + +extern "C" { +#include <ctype.h> +#include <string.h> +#include <stddef.h> +#include <stdlib.h> +} + +#include <iostream.h> +#include <bool.h> + +// bc4const + +#ifdef __BC4_STL +#define __BC401_STL +#endif + +#ifdef __BC401_STL +#define __BC401_const +#else +#define __BC401_const const +#endif + +// bndchk.h +#ifdef BOUNDS_CHECK +void check_bounds + ( int index, + int container_size, + int lineno, + char *filename ); +#endif + +// mexcept.h + +#define _THROW_NONE +#define _THROW_DOMAIN +#define _THROW_INVALIDARG +#define _THROW_LENGTH +#define _THROW_OUTRANGE +#define _THROW_RANGE +#define _THROW_OVERFLOW +#define _THROW_ALLOC +#define _THROW_CAST +#define _THROW_TYPEID +#define _THROW_ALLOC_LENGTH +#define _THROW_ALLOC_OUTRANGE +#define _THROW_LENGTH_OUTRANGE +#define _THROW_ALLOC_LENGTH_OUTRANGE + +#include <vector.h> + +#ifdef __MMULTITHREAD +#include "mutex.h" +#endif + +const size_t NPOS = (size_t)(-1); + + +/* + *Added by d:\\convert.pl --begin-- + */ +namespace std { +/* + *Added by d:\\convert.pl --end-- + */ + +enum capacity { default_size, reserve }; + +template<class charT> +struct string_char_baggage { + + typedef charT char_type; + + // + // for users to acquire the basic character type + // + // constraints functions + // + static void + assign (char_type& c1, const char_type& c2) _THROW_NONE + { + c1 = c2; + } + static bool + eq (const char_type& c1, const char_type& c2) _THROW_NONE + { + return (c1 == c2); + } + static bool + ne (const char_type& c1, const char_type& c2) _THROW_NONE + { + return !(c1 == c2); + } + static bool + lt (const char_type& c1, const char_type& c2) _THROW_NONE + { + return (c1 < c2); + } + static char_type + eos () _THROW_NONE + { + return char_type(); // the null character + } + static istream& + char_in (istream& is, char_type& c) _THROW_NONE + { + return is >> c; // extractor for a char_type object + } + static ostream& + char_out (ostream& os, char_type c) _THROW_NONE + { + return os << c; // inserter for a char_type object + } + static bool + is_del (char_type c) _THROW_NONE + { + // characteristic function for delimiters of char_type + return isspace(c); + } + + // + // speed-up functions + // + static int + compare (const char_type* s1, const char_type* s2, size_t n) _THROW_NONE + { + for (size_t i = 0; i < n; ++i, ++s1, ++s2) + if (ne(*s1, *s2)) + { + return lt(*s1, *s2) ? -1 : 1; + } + return 0; + } + static size_t + length (const char_type* s) _THROW_NONE + { + size_t l = 0; + while (ne(*s++, eos())) + ++l; + return l; + } + static char_type* + copy (char_type* s1, const char_type* s2, size_t n) _THROW_NONE + { + char_type* s = s1; + for (size_t i = 0; i < n; ++i) + assign(*++s1, *++s2); + return s; + } +}; + +struct string_char_baggage<char> { + + typedef char char_type; + + // + // constraint member functions + // + static void + assign (char_type& c1, const char_type& c2) _THROW_NONE + { + c1 = c2; + } + static bool + eq (const char_type& c1, const char_type& c2) _THROW_NONE + { + return (c1 == c2); + } + static bool + ne (const char_type& c1, const char_type& c2) _THROW_NONE + { + return (c1 != c2); + } + static bool + lt (const char_type& c1, const char_type& c2) _THROW_NONE + { + return (c1 < c2); + } + static char_type + eos () _THROW_NONE + { + return 0; // the null character + } + static istream& + char_in (istream& is, char_type& c) _THROW_NONE + { + // extractor for a char_type object + // return is >> c; // this does not work + is.get(c); + return is; + } + static ostream& + char_out (ostream& os, char_type c) _THROW_NONE + { + return os << c; // inserter for a char_type object + } + static bool + is_del (char_type c) _THROW_NONE + { + // characteristic function for delimiters of char_type + return isspace(c); + } + + // + // speed-up functions + // + static int + compare (const char_type* s1, const char_type* s2, size_t n) _THROW_NONE + { + return memcmp(s1, s2, n); + } + static size_t + length (const char_type* s) _THROW_NONE + { + return strlen(s); + } + static char_type* + copy (char_type* s1, const char_type* s2, size_t n) _THROW_NONE + { + // type cast required as memcpy returns void* + return (char_type*)memcpy(s1, s2, n); + } +}; + +/* +struct string_char_baggage<wchar_t> { + + typedef wchar_t char_type; + + static void + assign (char_type& c1, const char_type& c2) _THROW_NONE + { + c1 = c2; + } + static bool + eq (const char_type& c1, const char_type& c2) _THROW_NONE + { + return (c1 == c2); + } + static bool + ne (const char_type& c1, const char_type& c2) _THROW_NONE + { + return (c1 != c2); + } + static bool + lt (const char_type& c1, const char_type& c2) _THROW_NONE + { + return (c1 < c2); + } + static char_type + eos () _THROW_NONE + { + return 0; // the null character + } + static istream& + char_in (istream& is, char_type& c) _THROW_NONE + { + return is >> c; // extractor for a char_type object + } + static ostream& + char_out (ostream& os, char_type c) _THROW_NONE + { + return os << c; // inserter for a char_type object + } + static bool + is_del (char_type c) _THROW_NONE + { + // characteristic function for delimiters of char_type + // using templatized locale::isspace function + return isspace(c); + } + + // + // speed-up functions + // + static int + compare (const char_type* s1, const char_type* s2, size_t n) _THROW_NONE + { + return wmemcmp(s1, s2, n); + } + static size_t + length (const char_type* s) _THROW_NONE + { + return wcslen(s); + // May use Koshida's overloaded MSE function strlen(s) + } + static char_type* + copy (char_type* s1, const char_type* s2, size_t n) _THROW_NONE + { + return (char_type*)wmemcpy(s1, s2, n); + } +}; +*/ + +template <class charT> +class basic_string; + +template <class charT> +class basic_string_ref { + +// +// friend class declaration +// +friend class basic_string<charT>; + +// +// typedef declarations +// +typedef string_char_baggage<charT> baggage_type; + +// +// private data members +// + charT* ptr; + size_t len; + size_t res; + +#ifdef __MMULTITHREAD + mutex_arith<size_t, mutex> count; // reference count +#else + size_t count; // reference count +#endif + +// +// private constructors and destructors +// + basic_string_ref () _THROW_NONE ; + + basic_string_ref (size_t size, capacity cap) _THROW_ALLOC_LENGTH ; + + basic_string_ref (const basic_string<charT>& str, size_t pos , size_t rlen) + _THROW_ALLOC ; + + basic_string_ref (const charT* s, size_t rlen, size_t rres) _THROW_ALLOC ; + + basic_string_ref (const charT* s, size_t n) _THROW_ALLOC_LENGTH ; + + basic_string_ref (const charT* s) _THROW_ALLOC ; + + basic_string_ref (charT c, size_t rep) _THROW_ALLOC_LENGTH ; + + basic_string_ref (const vector<charT>& vec) _THROW_ALLOC_LENGTH ; + + ~basic_string_ref () _THROW_NONE ; + + inline void + delete_ptr () _THROW_NONE ; + + inline static + charT + eos () _THROW_NONE ; + + inline static + void + throwlength () _THROW_LENGTH; + + inline static + void + throwrange () _THROW_OUTRANGE; + +}; + +template<class charT> +class basic_string { + +private: + +// +// typedef declaration +// + typedef basic_string_ref<charT> reference_class; + typedef basic_string_ref<charT>* reference_pointer; + +// +// data member +// + charT* c_str_ptr; + reference_pointer reference; + +// +// private member functions +// + inline charT* + point () _THROW_NONE ; + + inline size_t& + len () _THROW_NONE ; + + inline size_t + ref_count () const _THROW_NONE ; + + inline static + charT + eos () _THROW_NONE ; + + void + assign_str (const charT* s, size_t slen) _THROW_ALLOC_LENGTH ; + + void + append_str (const charT* s, size_t slen) _THROW_ALLOC_LENGTH ; + + void + insert_str (size_t pos, const charT* s, size_t slen) + _THROW_ALLOC_LENGTH_OUTRANGE ; + + void + replace_str (size_t xlen, size_t pos, const charT* s, size_t slen) + _THROW_ALLOC_LENGTH_OUTRANGE ; + + int + compare_str (size_t pos, const charT* str, size_t slen, size_t strlen) + const _THROW_OUTRANGE ; + + size_t + find_str (const charT* s, size_t pos, size_t len) const _THROW_NONE ; + + size_t + rfind_str (const charT* s, size_t pos, size_t len) const _THROW_NONE ; + + size_t + find_first_of_str (const charT* s, size_t pos, size_t len) const + _THROW_NONE ; + + size_t + find_last_of_str (const charT* s, size_t pos, size_t len) const + _THROW_NONE ; + + size_t + find_first_not_of_str (const charT* s, size_t pos, size_t len) const + _THROW_NONE ; + + size_t + find_last_not_of_str (const charT* s, size_t pos, size_t len) const + _THROW_NONE ; + + +protected: + + basic_string (const charT* s, size_t rlen, size_t xlen) _THROW_ALLOC_LENGTH; + + inline void + delete_ref () _THROW_NONE ; + +public: + + typedef charT char_type; + typedef string_char_baggage<charT> baggage_type; + + basic_string () _THROW_ALLOC ; + + basic_string (size_t size, capacity cap) _THROW_ALLOC_LENGTH ; + + basic_string (const basic_string<charT>& str, size_t pos = 0, size_t n = NPOS) + _THROW_ALLOC_OUTRANGE ; + + basic_string (const charT* s, size_t n) _THROW_ALLOC_LENGTH ; + + basic_string (const charT* s) _THROW_ALLOC ; + + basic_string (charT c, size_t rep = 1) _THROW_ALLOC_LENGTH ; + + basic_string (const vector<charT>& vec) _THROW_ALLOC_LENGTH ; + + ~basic_string () _THROW_NONE ; + + basic_string<charT>& + operator= (const basic_string<charT>& str) _THROW_ALLOC ; + + basic_string<charT>& + operator= (const charT* s) _THROW_ALLOC ; + + basic_string<charT>& + operator= (charT c) _THROW_ALLOC ; + + basic_string<charT>& + operator+= (const basic_string<charT>& rhs) _THROW_ALLOC_LENGTH ; + + basic_string<charT>& + operator+= (const charT* s) _THROW_ALLOC_LENGTH ; + + basic_string<charT>& + operator+= (charT c) _THROW_ALLOC_LENGTH ; + + operator vector<charT> () const _THROW_ALLOC + { + return vector<charT> (data(), data()+length()); + } + + + basic_string<charT>& + append (const basic_string<charT>& str, size_t pos = 0, size_t n = NPOS) + _THROW_ALLOC_LENGTH_OUTRANGE ; + + basic_string<charT>& + append (const charT* s, size_t n) _THROW_ALLOC_LENGTH ; + + basic_string<charT>& + append (const charT* s) _THROW_ALLOC_LENGTH ; + + basic_string<charT>& + append (charT c, size_t rep = 1) _THROW_ALLOC_LENGTH ; + + basic_string<charT>& + assign (const basic_string<charT>& str, size_t pos = 0, size_t n = NPOS) + _THROW_ALLOC_LENGTH_OUTRANGE ; + + basic_string<charT>& + assign (const charT* s, size_t n) _THROW_ALLOC_LENGTH ; + + basic_string<charT>& + assign (const charT* s) _THROW_ALLOC_LENGTH ; + + basic_string<charT>& + assign (charT c, size_t rep = 1) _THROW_ALLOC_LENGTH ; + + basic_string<charT>& + insert (size_t pos1, const basic_string<charT>& str, size_t pos2 = 0, + size_t n = NPOS) _THROW_ALLOC_LENGTH_OUTRANGE ; + + basic_string<charT>& + insert (size_t pos, const charT* s, size_t n) _THROW_ALLOC_LENGTH_OUTRANGE ; + + basic_string<charT>& + insert (size_t pos, const charT* s) _THROW_ALLOC_LENGTH_OUTRANGE ; + + basic_string<charT>& + insert (size_t pos, charT c, size_t rep = 1) _THROW_ALLOC_LENGTH_OUTRANGE ; + + basic_string<charT>& + remove (size_t pos = 0, size_t n = NPOS) _THROW_ALLOC_OUTRANGE ; + + basic_string<charT>& + replace (size_t pos1, size_t n1, const basic_string<charT>& str, size_t pos2 = 0, + size_t n2 = NPOS) _THROW_ALLOC_LENGTH_OUTRANGE ; + + basic_string<charT>& + replace (size_t pos, size_t n1, const charT* s, size_t n2) + _THROW_ALLOC_LENGTH_OUTRANGE ; + + basic_string<charT>& + replace (size_t pos, size_t n1, const charT* s) + _THROW_ALLOC_LENGTH_OUTRANGE ; + + basic_string<charT>& + replace (size_t pos, size_t n, charT c, size_t rep = 1) + _THROW_ALLOC_LENGTH_OUTRANGE ; + + inline charT + get_at (size_t pos) const _THROW_OUTRANGE ; + + void + put_at (size_t pos, charT c) _THROW_ALLOC_OUTRANGE ; + + inline charT + operator[] (size_t pos) const _THROW_NONE ; + + charT& + operator[] (size_t pos) _THROW_ALLOC_OUTRANGE ; + + const charT* + c_str () const _THROW_ALLOC ; + + inline const charT* + data () const _THROW_NONE ; + + inline size_t + length () const _THROW_NONE ; + + void + resize (size_t n, charT c) _THROW_ALLOC_LENGTH ; + + void + resize (size_t n) _THROW_ALLOC_LENGTH ; + + inline size_t + reserve () const _THROW_NONE ; + + void + reserve (size_t res_arg) _THROW_ALLOC_LENGTH ; + + size_t + copy (charT* s, size_t n, size_t pos = 0) const _THROW_OUTRANGE ; + + size_t + find (const basic_string<charT>& str, size_t pos = 0) const _THROW_NONE ; + + size_t + find (const charT* s, size_t pos, size_t n) const _THROW_NONE ; + + size_t + find (const charT* s, size_t pos = 0) const _THROW_NONE ; + + size_t + find (charT c, size_t pos = 0) const _THROW_NONE ; + + size_t + rfind (const basic_string<charT>& str, size_t pos = NPOS) const _THROW_NONE ; + + size_t + rfind (const charT* s, size_t pos, size_t n) const _THROW_NONE ; + + size_t + rfind (const charT* s, size_t pos = NPOS) const _THROW_NONE ; + + size_t + rfind (charT c, size_t pos = NPOS) const _THROW_NONE ; + + size_t + find_first_of (const basic_string<charT>& str, size_t pos = 0) const _THROW_NONE ; + + size_t + find_first_of (const charT* s, size_t pos, size_t n) const _THROW_NONE ; + + size_t + find_first_of (const charT* s, size_t pos = 0) const _THROW_NONE ; + + size_t + find_first_of (charT c, size_t pos = 0) const _THROW_NONE ; + + + size_t + find_last_of (const basic_string<charT>& str, size_t pos = NPOS) const + _THROW_NONE ; + + size_t + find_last_of (const charT* s, size_t pos, size_t n) const _THROW_NONE ; + + size_t + find_last_of (const charT* s, size_t pos = NPOS) const _THROW_NONE ; + + size_t + find_last_of (charT c, size_t pos = NPOS) const _THROW_NONE ; + + size_t + find_first_not_of (const basic_string<charT>& str, size_t pos = 0) const + _THROW_NONE ; + + size_t + find_first_not_of (const charT* s, size_t pos, size_t n) const _THROW_NONE ; + + size_t + find_first_not_of (const charT* s, size_t pos = 0) const _THROW_NONE ; + + size_t + find_first_not_of (charT c, size_t pos = 0) const _THROW_NONE ; + + size_t + find_last_not_of (const basic_string<charT>& str, size_t pos = NPOS) const + _THROW_NONE ; + + size_t + find_last_not_of (const charT* s, size_t pos, size_t n) const _THROW_NONE ; + + size_t + find_last_not_of (const charT* s, size_t pos = NPOS) const _THROW_NONE ; + + size_t + find_last_not_of (charT c, size_t pos = NPOS) const _THROW_NONE ; + + basic_string<charT> + substr (size_t pos = 0, size_t n = NPOS) const _THROW_ALLOC_OUTRANGE ; + + int + compare (const basic_string<charT>& str, size_t pos = 0, size_t n = NPOS) const + _THROW_OUTRANGE ; + + int + compare (const charT* s, size_t pos, size_t n) const + _THROW_LENGTH_OUTRANGE ; + + int + compare (const charT* s, size_t pos = 0) const _THROW_OUTRANGE ; + + int + compare (charT c, size_t pos = 0, size_t rep = 1) const + _THROW_LENGTH_OUTRANGE ; + + friend + ostream& + operator<< (ostream& o, const basic_string<charT>& s) _THROW_NONE ; + + friend + istream& + operator>> (istream& i, basic_string<charT>& s) _THROW_ALLOC_LENGTH ; + + friend + basic_string<charT> + operator+ (const basic_string<charT>& lhs, const basic_string<charT>& rhs) + _THROW_ALLOC_LENGTH ; + + friend + basic_string<charT> + operator+ (const charT* lhs, const basic_string<charT>& rhs) + _THROW_ALLOC_LENGTH ; + + friend + basic_string<charT> + operator+ (charT lhs, const basic_string<charT>& rhs) _THROW_ALLOC_LENGTH ; + + friend + basic_string<charT> + operator+ (const basic_string<charT>& lhs, const charT* rhs) + _THROW_ALLOC_LENGTH ; + + friend + basic_string<charT> + operator+ (const basic_string<charT>& lhs, charT rhs) _THROW_ALLOC_LENGTH ; + +}; + +template <class charT> +inline void +basic_string_ref<charT>::delete_ptr () _THROW_NONE +{ + if (res) + { + delete[] ptr; + res = 0; + ptr = 0; + } +} + +template <class charT> +inline void +basic_string_ref<charT>::throwlength () _THROW_LENGTH +{ +#ifdef __MEXCEPT + throw length_error("Length exception occurred"); +#else + cout << "Length exception occurred" << endl; + exit(1); +#endif +} + +template <class charT> +inline void +basic_string_ref<charT>::throwrange () _THROW_OUTRANGE +{ +#ifdef __MEXCEPT + throw out_of_range("Out of range exception occurred"); +#else + cout << "Out of range exception occurred" << endl; + exit(1); +#endif +} + +template <class charT> +inline void +basic_string<charT>::delete_ref () _THROW_NONE +{ + --(reference->count); + if (!(reference->count)) + delete reference; +} + +template <class charT> +inline size_t +basic_string<charT>::ref_count () const _THROW_NONE +{ + return reference->count; +} + +template <class charT> +inline const charT* +basic_string<charT>::data () const _THROW_NONE +{ + if (length()) + return reference->ptr; + else + return 0; +} + +template <class charT> +inline charT* +basic_string<charT>::point () _THROW_NONE +{ + return reference->ptr; +} + +template <class charT> +inline size_t& +basic_string<charT>::len () _THROW_NONE +{ + return reference->len; +} + +template <class charT> +inline size_t +basic_string<charT>::length () const _THROW_NONE +{ + return reference->len; +} + +template <class charT> +inline size_t +basic_string<charT>::reserve () const _THROW_NONE +{ + return reference->res; +} + +template <class charT> +inline charT +basic_string<charT>::get_at (size_t pos) const _THROW_OUTRANGE +{ + if (pos >= length()) + { + reference_class::throwrange(); + } + return *(data()+pos); +} + +template <class charT> +inline charT +basic_string<charT>::operator[] (size_t pos) const _THROW_NONE +{ + if (pos < length()) + return *(data()+pos); + else + return 0; +} + +template <class charT> +inline bool +operator== (const basic_string<charT>& lhs, const basic_string<charT>& rhs) + _THROW_NONE +{ + return !(lhs.compare(rhs)); +} + +template <class charT> +inline bool +operator== (const charT* lhs, const basic_string<charT>& rhs) _THROW_NONE +{ + return !(rhs.compare(lhs)); +} + +template <class charT> +inline bool +operator== (charT lhs, const basic_string<charT>& rhs) _THROW_NONE +{ + return !(rhs.compare(lhs)); +} + +template <class charT> +inline bool +operator== (const basic_string<charT>& lhs, const charT* rhs) _THROW_NONE +{ + return !(lhs.compare(rhs)); +} + +template <class charT> +inline bool +operator== (const basic_string<charT>& lhs, charT rhs) _THROW_NONE +{ + return !(lhs.compare(rhs)); +} + +#ifdef __MNONDEF +template <class charT> +inline bool +operator!= (const basic_string<charT>& lhs, const basic_string<charT>& rhs) + _THROW_NONE +{ + return lhs.compare(rhs); +} +#endif + +template <class charT> +inline bool +operator!= (const charT* lhs, const basic_string<charT>& rhs) _THROW_NONE +{ + return rhs.compare(lhs); +} + +template <class charT> +inline bool +operator!= (charT lhs, const basic_string<charT>& rhs) _THROW_NONE +{ + return rhs.compare(lhs); +} + +template <class charT> +inline bool +operator!= (const basic_string<charT>& lhs, const charT* rhs) _THROW_NONE +{ + return lhs.compare(rhs); +} + +template <class charT> +inline bool +operator!= (const basic_string<charT>& lhs, charT rhs) _THROW_NONE +{ + return lhs.compare(rhs); +} + +template <class charT> +inline bool +operator< (const basic_string<charT>& lhs, const basic_string<charT>& rhs) + _THROW_NONE +{ + if (lhs.compare(rhs) < 0) + return true; + else + return false; +} + +template <class charT> +inline bool +operator< (const charT* lhs, const basic_string<charT>& rhs) _THROW_NONE +{ + if (rhs.compare(lhs) > 0) + return true; + else + return false; +} + +template <class charT> +inline bool +operator< (charT lhs, const basic_string<charT>& rhs) _THROW_NONE +{ + if (rhs.compare(lhs) > 0) + return true; + else + return false; +} + +template <class charT> +inline bool +operator< (const basic_string<charT>& lhs, const charT* rhs) _THROW_NONE +{ + if (lhs.compare(rhs) < 0) + return true; + else + return false; +} + +template <class charT> +inline bool +operator< (const basic_string<charT>& lhs, charT rhs) _THROW_NONE +{ + if (lhs.compare(rhs) < 0) + return true; + else + return false; +} + +#ifdef __MNONDEF +template <class charT> +inline bool +operator> (const basic_string<charT>& lhs, const basic_string<charT>& rhs) + _THROW_NONE +{ + return (rhs < lhs); +} +#endif + +template <class charT> +inline bool +operator> (const charT* lhs, const basic_string<charT>& rhs) _THROW_NONE +{ + return (rhs < lhs); +} + +template <class charT> +inline bool +operator> (charT lhs, const basic_string<charT>& rhs) _THROW_NONE +{ + return (rhs < lhs); +} + +template <class charT> +inline bool +operator> (const basic_string<charT>& lhs, const charT* rhs) _THROW_NONE +{ + return (rhs < lhs); +} + +template <class charT> +inline bool +operator> (const basic_string<charT>& lhs, charT rhs) _THROW_NONE +{ + return (rhs < lhs); +} + +#ifdef __MNONDEF +template <class charT> +inline bool +operator>= (const basic_string<charT>& lhs, const basic_string<charT>& rhs) + _THROW_NONE +{ + return !(lhs < rhs); +} +#endif + +template <class charT> +inline bool +operator>= (const charT* lhs, const basic_string<charT>& rhs) _THROW_NONE +{ + return !(lhs < rhs); +} + +template <class charT> +inline bool +operator>= (charT lhs, const basic_string<charT>& rhs) _THROW_NONE +{ + return !(lhs < rhs); +} + +template <class charT> +inline bool +operator>= (const basic_string<charT>& lhs, const charT* rhs) _THROW_NONE +{ + return !(lhs < rhs); +} + +template <class charT> +inline bool +operator>= (const basic_string<charT>& lhs, charT rhs) _THROW_NONE +{ + return !(lhs < rhs); +} + +#ifdef __MNONDEF +template <class charT> +inline bool +operator<= (const basic_string<charT>& lhs, const basic_string<charT>& rhs) + _THROW_NONE +{ + return !(rhs < lhs); +} +#endif + +template <class charT> +inline bool +operator<= (const charT* lhs, const basic_string<charT>& rhs) _THROW_NONE +{ + return !(rhs < lhs); +} + +template <class charT> +inline bool +operator<= (charT lhs, const basic_string<charT>& rhs) _THROW_NONE +{ + return !(rhs < lhs); +} + +template <class charT> +inline bool +operator<= (const basic_string<charT>& lhs, const charT* rhs) _THROW_NONE +{ + return !(rhs < lhs); +} + +template <class charT> +inline bool +operator<= (const basic_string<charT>& lhs, charT rhs) _THROW_NONE +{ + return !(rhs < lhs); +} + +// definitions : can be in a .c file +// + +template <class charT> +charT +basic_string_ref<charT>::eos () _THROW_NONE +{ + return baggage_type::eos(); +} + +template <class charT> +basic_string_ref<charT>::basic_string_ref () _THROW_NONE +{ + res = len = 0; + ptr = 0; + count = 1; +} + +template <class charT> +basic_string_ref<charT>::basic_string_ref (size_t size, capacity cap) + _THROW_ALLOC_LENGTH +{ + if (cap == std::reserve) + { + len = 0; + res = size; + ptr = new charT [res]; + } + else if ((cap == std::default_size) && (size != NPOS)) + { + res = len = size; + if (res) + { + ptr = new charT [res]; + for (size_t position = 0; position < len; ++position) + baggage_type::assign (*(ptr+position), eos()); + } + else + ptr = 0; + } + else + { + throwlength(); + } + count = 1; +} + +template <class charT> +basic_string_ref<charT>::basic_string_ref (const basic_string<charT>& str, + size_t pos, size_t rlen) _THROW_ALLOC +{ + res = len = rlen; + if (res) + { + ptr = new charT [res]; + baggage_type::copy (ptr, str.data()+pos, len); + } + else + ptr = 0; + count = 1; +} + +template <class charT> +basic_string_ref<charT>::basic_string_ref (const charT* s, size_t rlen, + size_t rres) _THROW_ALLOC +{ + res = rres; + len = rlen; + if (res) + { + ptr = new charT [res]; + if (len) + baggage_type::copy (ptr, s, len); + } + else + ptr = 0; + count = 1; +} + +template <class charT> +basic_string_ref<charT>::basic_string_ref (const charT* s, size_t n) + _THROW_ALLOC_LENGTH +{ + if (n == NPOS) + { + throwlength(); + } + res = len = n; + if (res) + { + ptr = new charT [res]; + baggage_type::copy (ptr, s, len); + } + else + ptr = 0; + count = 1; +} + +template <class charT> +basic_string_ref<charT>::basic_string_ref (const charT* s) _THROW_ALLOC +{ + res = len = baggage_type::length(s); + if (res) + { + ptr = new charT [res]; + baggage_type::copy (ptr, s, len); + } + else + ptr = 0; + count = 1; +} + +template <class charT> +basic_string_ref<charT>::basic_string_ref (charT c, size_t rep) + _THROW_ALLOC_LENGTH +{ + if (rep == NPOS) + { + throwlength(); + } + res = len = rep; + if (res) + { + ptr = new charT [res]; + for (size_t position = 0; position < len; ++position) + baggage_type::assign (*(ptr+position), c); + } + else + ptr = 0; + count = 1; +} + +template <class charT> +basic_string_ref<charT>::basic_string_ref (const vector<charT>& vec) + _THROW_ALLOC_LENGTH +{ + size_t n = vec.size(); + if (n == NPOS) + { + throwlength(); + } + res = len = n; + if (res) + { + ptr = new charT [res]; + baggage_type::copy (ptr, vec.begin(), len); + } + else + ptr = 0; + count = 1; +} + +template <class charT> +basic_string_ref<charT>::~basic_string_ref () _THROW_NONE +{ + delete_ptr(); +} + +template <class charT> +charT +basic_string<charT>::eos () _THROW_NONE +{ + return baggage_type::eos(); +} + +template <class charT> +void +basic_string<charT>::assign_str (const charT* s, size_t slen) + _THROW_ALLOC_LENGTH +{ + if (slen == NPOS) + { + reference_class::throwlength(); + } + if ((ref_count() > 1) || (slen && (reserve() < slen))) + { + reference_pointer tmp; + tmp = new basic_string_ref<charT> (s, slen); + delete_ref(); + reference = tmp; + } + else if (slen) + { + baggage_type::copy (point(), s, slen); + } + reference->len = slen; +} + +template <class charT> +void +basic_string<charT>::append_str (const charT* s, size_t slen) + _THROW_ALLOC_LENGTH +{ + if (length() >= (NPOS-slen)) + { + reference_class::throwlength(); + } + if ((ref_count() > 1) || (slen > (reserve()-length()))) + { + reference_pointer tmp; + tmp = new basic_string_ref<charT> (data(), length(), length()+slen); + delete_ref(); + reference = tmp; + } + if (slen) + baggage_type::copy (point()+length(), s, slen); + reference->len += slen; +} + +template <class charT> +void +basic_string<charT>::insert_str (size_t pos, const charT* s, size_t slen) + _THROW_ALLOC_LENGTH_OUTRANGE +{ + if (pos > length()) + { + reference_class::throwrange(); + } + if (length() >= (NPOS-slen)) + { + reference_class::throwlength(); + } + if ((ref_count() > 1) || (slen > (reserve()-length()))) + { + reference_pointer tmp; + tmp = new basic_string_ref<charT> (data(), pos, length()+slen); + baggage_type::copy (tmp->ptr+pos+slen, data()+pos, length()-pos); + tmp->len = length(); + delete_ref(); + reference = tmp; + } + else + { + for (size_t count = length()-pos; count > 0; --count) + baggage_type::assign (*(point()+pos+slen+count-1), + *(data()+pos+count-1)); + } + if (slen) + baggage_type::copy (point()+pos, s, slen); + reference->len += slen; +} + +template <class charT> +void +basic_string<charT>::replace_str (size_t xlen, size_t pos, const charT* s, + size_t slen) _THROW_ALLOC_LENGTH_OUTRANGE +{ + if (pos > length()) + { + reference_class::throwrange(); + } + if ((length()-xlen) >= (NPOS-slen)) + { + reference_class::throwlength(); + } + if ((ref_count() > 1) || (reserve() < (length()+slen-xlen))) + { + reference_pointer tmp; + tmp = new basic_string_ref<charT> (data(), pos, length()+slen-xlen); + baggage_type::copy (tmp->ptr+pos+slen, data()+pos+xlen, + length()-pos-xlen); + tmp->len = length(); + delete_ref(); + reference = tmp; + } + else + { + if (slen < xlen) + baggage_type::copy (point()+pos+slen, data()+pos+xlen, + length()-pos-xlen); + else + { + for (size_t count = length()-pos-xlen; count > 0; --count) + baggage_type::assign (*(point()+pos+slen+count-1), + *(data()+pos+xlen+count-1)); + } + } + if (slen) + baggage_type::copy (point()+pos, s, slen); + reference->len += (slen-xlen); +} + +template <class charT> +int +basic_string<charT>::compare_str (size_t pos, const charT* str, size_t slen, + size_t strlen) const _THROW_OUTRANGE +{ + if (pos > length()) + { + reference_class::throwrange(); + } + size_t rlen = (slen > strlen ) ? strlen : slen; + int result; + if (!length()) + return str ? (eos()- *str) : eos(); + result = baggage_type::compare (data()+pos, str, rlen); + return result ? result : (length()-pos-strlen); +} + +template <class charT> +size_t +basic_string<charT>::find_str (const charT* s, size_t pos, size_t len) + const _THROW_NONE +{ + size_t count = pos; + size_t shift; + size_t place; + if ((length() == 0) || (len == 0)) + return NPOS; + while (len <= (length()-count)) + { + for (place = 0; place < len; ++place) + { + if (baggage_type::ne(*(s+len-1-place), *(data()+count+(len-1-place)))) + break; + } + if (place == len) + return count; + shift = find(*(s+len-1-place), count+(len-place)); + if (shift == NPOS) + return NPOS; + count = shift-(len-place-1); + } + return NPOS; +} + +template <class charT> +size_t +basic_string<charT>::rfind_str (const charT* s, size_t pos, size_t len) + const _THROW_NONE +{ + size_t count = (pos < (length()-len)) ? (pos+1) : (length()-len); + size_t shift; + size_t place; + if ((length() < len) || (len == 0)) + return NPOS; + while (count > 0) + { + for (place = 0; place < len; ++place) + { + if (baggage_type::ne(*(s+len-1-place), *(data()+count+(len-place)-2))) + break; + } + if (place == len) + return count-1; + shift = rfind(*(s+len-1-place), count+(len-place)-3); + if (shift == NPOS) + return NPOS; + count = shift+place-len+2; + } + return NPOS; + +} + +template <class charT> +size_t +basic_string<charT>::find_first_of_str (const charT* s, size_t pos, size_t len) + const _THROW_NONE +{ + size_t temp; + size_t count = pos; + size_t result = NPOS; + while (count < length()) + { + temp = 0; + while ((temp < len) && baggage_type::ne(*(data()+count), *(s+temp))) + ++temp; + if (temp != len) + break; + ++count; + } + temp = (count >= length()) ? NPOS : count; + return ((result > temp) ? temp : result); +} + +template <class charT> +size_t +basic_string<charT>::find_last_of_str (const charT* s, size_t pos, size_t len) + const _THROW_NONE +{ + size_t temp = 0; + size_t count = (pos < length()) ? (pos+1) : length(); + if (length()) + { + while (count > 0) + { + temp = 0; + --count; + while ((temp != len) && baggage_type::ne(*(data()+count), *(s+temp))) + ++temp; + if (temp != len) + break; + } + } + return ((temp != len) && length()) ? count : NPOS; +} + +template <class charT> +size_t +basic_string<charT>::find_first_not_of_str (const charT* s, size_t pos, + size_t len) const _THROW_NONE +{ + size_t count = pos; + while (count < length()) + { + size_t temp = 0; + while (temp < len) + { + if (baggage_type::eq(*(data()+count), *(s+temp))) + break; + ++temp; + } + if (temp == len) + break; + ++count; + } + return ((count >= length()) ? NPOS : count); +} + +template <class charT> +size_t +basic_string<charT>::find_last_not_of_str (const charT* s, size_t pos, + size_t len) const _THROW_NONE +{ + size_t temp = 0; + size_t count = (pos < length()) ? (pos+1) : length(); + + if (length()) + { + while (count > 0) + { + temp = 0; + while (temp != len) + { + if (baggage_type::eq(*(data()+count-1), *(s+temp))) + break; + ++temp; + } + if (temp == len) + break; + --count; + } + } + return ((temp == len) && length()) ? count-1 : NPOS; +} + +template <class charT> +basic_string<charT>::basic_string () _THROW_ALLOC +{ + reference = new basic_string_ref<charT> (); + c_str_ptr = 0; +} + +template <class charT> +basic_string<charT>::basic_string (size_t size, capacity cap) + _THROW_ALLOC_LENGTH +{ + reference = new basic_string_ref<charT> (size, cap); + c_str_ptr = 0; +} + +template <class charT> +basic_string<charT>::basic_string (const basic_string<charT>& str, + size_t pos, size_t n) _THROW_ALLOC_OUTRANGE +{ + if (pos > str.length()) + { + reference_class::throwrange(); + } + size_t rlen = (n > (str.length() - pos)) ? str.length() - pos : n; + if ((rlen == str.length()) && (str.ref_count() != NPOS)) + (reference = str.reference)->count++; + else + reference = new basic_string_ref<charT> (str, pos, rlen); + c_str_ptr = 0; +} + +template <class charT> +basic_string<charT>::basic_string (const charT* s, size_t rlen, size_t xlen) + _THROW_ALLOC_LENGTH +{ + if (rlen >= (NPOS - xlen)) + { + reference_class::throwlength(); + } + reference = new basic_string_ref<charT> (s, rlen, rlen+xlen); + c_str_ptr = 0; +} + +template <class charT> +basic_string<charT>::basic_string (const charT* s, size_t n) _THROW_ALLOC_LENGTH +{ + reference = new basic_string_ref<charT> (s, n); + c_str_ptr = 0; +} + +template <class charT> +basic_string<charT>::basic_string (const charT* s) _THROW_ALLOC +{ + reference = new basic_string_ref<charT> (s); + c_str_ptr = 0; +} + +template <class charT> +basic_string<charT>::basic_string (charT c, size_t rep) _THROW_ALLOC_LENGTH +{ + reference = new basic_string_ref<charT> (c, rep); + c_str_ptr = 0; +} + +template <class charT> +basic_string<charT>::basic_string (const vector<charT>& vec) _THROW_ALLOC_LENGTH +{ + reference = new basic_string_ref<charT> (vec); + c_str_ptr = 0; +} + +template <class charT> +basic_string<charT>::~basic_string () _THROW_NONE +{ + delete_ref(); + if (c_str_ptr) + delete[] c_str_ptr; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::operator= (const basic_string<charT>& str) _THROW_ALLOC +{ + if (this != &str) + { + delete_ref(); + if (str.ref_count() != NPOS) + (reference = str.reference)->count++; + else + reference = new basic_string_ref<charT> (str, 0, str.length()); + } + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::operator= (const charT* s) _THROW_ALLOC +{ + assign_str (s, baggage_type::length(s)); + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::operator= (charT c) _THROW_ALLOC +{ + if ((ref_count() == 1) && (reserve() >= 1)) + { + baggage_type::assign (*(point()), c); + reference->len = 1; + } + else + { + delete_ref(); + reference = new basic_string_ref<charT> (c, 1); + } + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::operator+= (const basic_string<charT>& rhs) _THROW_ALLOC_LENGTH +{ + append_str (rhs.data(), rhs.length()); + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::operator+= (const charT* s) _THROW_ALLOC_LENGTH +{ + append_str (s, baggage_type::length(s)); + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::operator+= (charT c) _THROW_ALLOC_LENGTH +{ + if (length() >= (NPOS-1)) + { + reference_class::throwlength(); + } + if (!((ref_count() == 1) && (reserve() > length()))) + { + reference_pointer tmp; + tmp = new basic_string_ref<charT> (data(), length(), length()+1); + delete_ref(); + reference = tmp; + } + baggage_type::assign (*(point()+length()), c); + reference->len++; + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::append (const basic_string<charT>& str, size_t pos, size_t n) + _THROW_ALLOC_LENGTH_OUTRANGE +{ + if (pos > str.length()) + { + reference_class::throwrange(); + } + append_str (str.data() + pos, (n>(str.length()-pos))?(str.length()-pos):n); + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::append (const charT* s, size_t n) _THROW_ALLOC_LENGTH +{ + append_str (s, n); + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::append (const charT* s) _THROW_ALLOC_LENGTH +{ + append_str (s, baggage_type::length(s)); + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::append (charT c, size_t rep) _THROW_ALLOC_LENGTH +{ + if (length() >= (NPOS-rep)) + { + reference_class::throwlength(); + } + if (rep) + { + if ((ref_count() > 1) || (reserve() < (length() + rep))) + { + reference_pointer tmp; + tmp = new basic_string_ref<charT> (data(), length(), length()+rep); + delete_ref(); + reference = tmp; + } + for (size_t count = 0; count < rep; ++count) + baggage_type::assign (*(point()+length()+count), c); + reference->len += rep; + } + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::assign (const basic_string<charT>& str, size_t pos, size_t n) + _THROW_ALLOC_LENGTH_OUTRANGE +{ + if (pos > str.length()) + { + reference_class::throwrange(); + } + size_t rlen = (n > (str.length() - pos)) ? str.length() - pos : n; + if ((rlen == str.length()) && (str.ref_count() != NPOS)) + { + delete_ref(); + (reference = str.reference)->count++; + } + else + assign_str (str.data()+pos, rlen); + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::assign (const charT* s, size_t n) _THROW_ALLOC_LENGTH +{ + assign_str (s, n); + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::assign (const charT* s) _THROW_ALLOC_LENGTH +{ + assign_str (s, baggage_type::length(s)); + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::assign (charT c, size_t rep) _THROW_ALLOC_LENGTH +{ + if (rep == NPOS) + { + reference_class::throwlength(); + } + if ((ref_count() > 1) || (rep && (reserve() < rep))) + { + reference_pointer tmp; + tmp = new basic_string_ref<charT> (c, rep); + delete_ref(); + reference = tmp; + } + else + { + for (size_t count = 0; count < rep; ++count) + baggage_type::assign (*(point()+count), c); + reference->len = rep; + } + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::insert (size_t pos1, const basic_string<charT>& str, + size_t pos2, size_t n) _THROW_ALLOC_LENGTH_OUTRANGE +{ + if (pos2 > str.length()) + { + reference_class::throwrange(); + } + size_t rlen = (n > (str.length() - pos2)) ? str.length() - pos2 : n; + insert_str (pos1, str.data()+pos2, rlen); + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::insert (size_t pos, const charT* s, size_t n) + _THROW_ALLOC_LENGTH_OUTRANGE +{ + insert_str(pos, s, n); + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::insert (size_t pos, const charT* s) + _THROW_ALLOC_LENGTH_OUTRANGE +{ + insert_str(pos, s, baggage_type::length(s)); + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::insert (size_t pos, charT c, size_t rep) + _THROW_ALLOC_LENGTH_OUTRANGE +{ + if (pos > length()) + { + reference_class::throwrange(); + } + if ((rep == NPOS) || (length() >= (NPOS - rep))) + { + reference_class::throwlength(); + } + if (rep) + { + size_t count; + if ((ref_count() > 1) || (reserve() < (length()+rep))) + { + reference_pointer tmp; + tmp = new basic_string_ref<charT> (data(), pos, length()+rep); + if (length()) + for (count = length()-pos; count > 0; --count) + baggage_type::assign (*(tmp->ptr+pos+rep+count-1), + *(data()+pos+count-1)); + tmp->len = length(); + delete_ref(); + reference = tmp; + } + else + { + for (count = length()-pos; count > 0; --count) + baggage_type::assign (*(point()+pos+rep+count-1), + *(data()+pos+count-1)); + } + for (count = 0; count < rep; ++count) + baggage_type::assign (*(point()+pos+count), c); + reference->len += rep; + } + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::remove (size_t pos, size_t n) _THROW_ALLOC_OUTRANGE +{ + if (pos > length()) + { + reference_class::throwrange(); + } + size_t xlen = (n > (length()-pos)) ? (length()-pos) : n; + if (ref_count() > 1) + { + reference_pointer tmp; + tmp = new basic_string_ref<charT> (data(), pos, length()); + baggage_type::copy (tmp->ptr+pos, data()+pos+xlen, length()-xlen-pos); + tmp->len = length()-xlen; + delete_ref(); + reference = tmp; + } + else if (xlen == length()) + reference->len = 0; + else if (xlen) + { + baggage_type::copy (point()+pos, data()+pos+xlen, length()-xlen-pos); + reference->len -= xlen; + } + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::replace (size_t pos1, size_t n1, const basic_string<charT>& str, + size_t pos2, size_t n2) _THROW_ALLOC_LENGTH_OUTRANGE +{ + if (pos2 > str.length()) + { + reference_class::throwrange(); + } + size_t xlen = (n1 > (length()-pos1)) ? (length()-pos1) : n1; + size_t rlen = (n2 > (str.length()-pos2)) ? (str.length()-pos2) : n2; + replace_str (xlen, pos1, str.data()+pos2, rlen); + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::replace (size_t pos, size_t n1, const charT* s, size_t n2) + _THROW_ALLOC_LENGTH_OUTRANGE +{ + size_t xlen = (n1 > (length()-pos)) ? (length()-pos) : n1; + replace_str (xlen, pos, s, n2); + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::replace (size_t pos, size_t n1, const charT* s) + _THROW_ALLOC_LENGTH_OUTRANGE +{ + size_t xlen = (n1 > (length()-pos)) ? (length()-pos) : n1; + replace_str (xlen, pos, s, baggage_type::length(s)); + return *this; +} + +template <class charT> +basic_string<charT>& +basic_string<charT>::replace (size_t pos, size_t n, charT c, size_t rep) + _THROW_ALLOC_LENGTH_OUTRANGE +{ + if (pos > length()) + { + reference_class::throwrange(); + } + size_t xlen = (n > (length()-pos)) ? (length()-pos) : n; + if ((length()-xlen) >= (NPOS-rep)) + { + reference_class::throwlength(); + } + if (!rep) + return remove (pos, n); + else + { + size_t count; + if ((ref_count() > 1) || (reserve() < (length()-xlen+rep))) + { + reference_pointer tmp; + tmp = new basic_string_ref<charT> (data(), pos, + length()+((xlen > rep) ? (xlen-rep) : 0)); + if (rep < xlen) + baggage_type::copy (tmp->ptr+pos+rep, data()+pos+xlen, + length()-pos-xlen); + else + { + for (count = length()-xlen-pos; count > 0; --count) + baggage_type::assign (*(tmp->ptr+pos+rep+count-1), + *(data()+pos+xlen+count-1)); + } + tmp->len = length(); + delete_ref(); + reference = tmp; + } + else + { + if (rep < xlen) + baggage_type::copy (point()+pos+rep, data()+pos+xlen, + length()-pos-xlen); + else + { + for (count = length()-xlen-pos; count > 0; --count) + baggage_type::assign (*(point()+pos+rep+count-1), + *(data()+pos+xlen+count-1)); + } + } + for (count = 0; count < rep; ++count) + baggage_type::assign (*(point()+pos+count), c); + reference->len += (rep-xlen); + } + return *this; +} + +template <class charT> +void +basic_string<charT>::put_at (size_t pos, charT c) _THROW_ALLOC_OUTRANGE +{ + if (pos > length()) + { + reference_class::throwrange(); + } + if ((ref_count() > 1) || (pos == reserve())) + { + reference_pointer tmp; + tmp = new basic_string_ref<charT> (data(), length(), + length()+((pos==length())?1:0)); + delete_ref(); + reference = tmp; + } + if (pos == length()) + ++reference->len; + baggage_type::assign (*(point()+pos), c); +} + +template <class charT> +charT& +basic_string<charT>::operator[] (size_t pos) _THROW_ALLOC_OUTRANGE +{ + if (pos >= length()) + { + reference_class::throwrange(); + } + if (ref_count() > 1) + { + reference_pointer tmp; + tmp = new basic_string_ref<charT> (data(), length(), length()); + delete_ref(); + reference = tmp; + } + return *(point()+pos); +} + +template <class charT> +const charT* +basic_string<charT>::c_str () const _THROW_ALLOC +{ + if (c_str_ptr) + delete[] ((basic_string<charT>*)this)->c_str_ptr; + ((basic_string<charT>*)this)->c_str_ptr = new charT [length()+1]; + if (length()) + baggage_type::copy (((basic_string<charT>*)this)->c_str_ptr, data(), + length()); + baggage_type::assign (*(((basic_string<charT>*)this)->c_str_ptr+length()), + eos()); + return c_str_ptr; +} + +template <class charT> +void +basic_string<charT>::resize (size_t n, charT c) _THROW_ALLOC_LENGTH +{ + if (n == NPOS) + { + reference_class::throwlength(); + } + if ((ref_count() > 1) || (n > reserve())) + { + reference_pointer tmp; + tmp = new basic_string_ref<charT> (data(), + ((n > length()) ? length() : n), n); + delete_ref(); + reference = tmp; + } + while (reference->len < n) + { + baggage_type::assign (*(reference->ptr+length()), c); + ++reference->len; + } + reference->len = n; +} + +template <class charT> +void +basic_string<charT>::resize (size_t n) _THROW_ALLOC_LENGTH +{ + resize (n, eos()); +} + +template <class charT> +void +basic_string<charT>::reserve (size_t res_arg) _THROW_ALLOC_LENGTH +{ + if (res_arg == NPOS) + { + reference_class::throwlength(); + } + if (res_arg > reserve()) + { + reference_pointer tmp; + tmp = new basic_string_ref<charT> (data(), length(), res_arg); + delete_ref(); + reference = tmp; + } +} + +template <class charT> +size_t +basic_string<charT>::copy (charT* s, size_t n, size_t pos) const _THROW_OUTRANGE +{ + if (pos > length()) + { + reference_class::throwrange(); + } + size_t rlen = (n > (length()-pos)) ? (length()-pos) : n; + if (length()) + baggage_type::copy (s, data()+pos, rlen); + return rlen; +} + +template <class charT> +size_t +basic_string<charT>::find (const basic_string<charT>& str, size_t pos) const + _THROW_NONE +{ + return find_str (str.data(), pos, str.length()); +} + +template <class charT> +size_t +basic_string<charT>::find (const charT* s, size_t pos, size_t n) const + _THROW_NONE +{ + return find_str (s, pos, n); +} + +template <class charT> +size_t +basic_string<charT>::find (const charT* s, size_t pos) const _THROW_NONE +{ + return find_str (s, pos, baggage_type::length(s)); +} + +template <class charT> +size_t +basic_string<charT>::find (charT c, size_t pos) const _THROW_NONE +{ + while ((pos < length()) && (baggage_type::ne(*(data()+pos), c))) + ++pos; + return ((pos < length()) ? pos : NPOS); +} + +template <class charT> +size_t +basic_string<charT>::rfind (const basic_string<charT>& str, size_t pos) const + _THROW_NONE +{ + return rfind_str (str.data(), pos, str.length()); +} + +template <class charT> +size_t +basic_string<charT>::rfind (const charT* s, size_t pos, size_t n) const + _THROW_NONE +{ + return rfind_str (s, pos, n); +} + +template <class charT> +size_t +basic_string<charT>::rfind (const charT* s, size_t pos) const _THROW_NONE +{ + return rfind_str (s, pos, baggage_type::length(s)); +} + +template <class charT> +size_t +basic_string<charT>::rfind (charT c, size_t pos) const _THROW_NONE +{ + size_t count = ((pos < length()) ? pos+1 : length()); + if (length() == 0) + return NPOS; + while ((baggage_type::ne(*(data()+count-1), c)) && (count > 1)) + --count; + if ((count == 1) && (baggage_type::ne(*(data()), c))) + return NPOS; + else + return count-1; +} + +template <class charT> +size_t +basic_string<charT>::find_first_of (const basic_string<charT>& str, size_t pos) const + _THROW_NONE +{ + return find_first_of_str (str.data(), pos, str.length()); +} + +template <class charT> +size_t +basic_string<charT>::find_first_of (const charT* s, size_t pos, size_t n) const + _THROW_NONE +{ + return find_first_of_str (s, pos, n); +} + +template <class charT> +size_t +basic_string<charT>::find_first_of (const charT* s, size_t pos) const + _THROW_NONE +{ + return find_first_of_str (s, pos, baggage_type::length(s)); +} + +template <class charT> +size_t +basic_string<charT>::find_first_of (charT c, size_t pos) const _THROW_NONE +{ + return find (c, pos); +} + +template <class charT> +size_t +basic_string<charT>::find_last_of (const basic_string<charT>& str, size_t pos) const + _THROW_NONE +{ + return find_last_of_str (str.data(), pos, str.length()); +} + +template <class charT> +size_t +basic_string<charT>::find_last_of (const charT* s, size_t pos, size_t n) const + _THROW_NONE +{ + return find_last_of_str (s, pos, n); +} + +template <class charT> +size_t +basic_string<charT>::find_last_of (const charT* s, size_t pos) const _THROW_NONE +{ + return find_last_of_str (s, pos, baggage_type::length(s)); +} + +template <class charT> +size_t +basic_string<charT>::find_last_of (charT c, size_t pos) const _THROW_NONE +{ + return rfind (c, pos); +} + +template <class charT> +size_t +basic_string<charT>::find_first_not_of (const basic_string<charT>& str, size_t pos) + const _THROW_NONE +{ + return find_first_not_of_str (str.data(), pos, str.length()); +} + +template <class charT> +size_t +basic_string<charT>::find_first_not_of (const charT* s, size_t pos, size_t n) + const _THROW_NONE +{ + return find_first_not_of_str (s, pos, n); +} + +template <class charT> +size_t +basic_string<charT>::find_first_not_of (const charT* s, size_t pos) const + _THROW_NONE +{ + return find_first_not_of_str (s, pos, baggage_type::length(s)); +} + +template <class charT> +size_t +basic_string<charT>::find_first_not_of (charT c, size_t pos) const _THROW_NONE +{ + while ((pos < length()) && (baggage_type::eq(*(data()+pos), c))) + ++pos; + return ((pos < length()) ? pos : NPOS); +} + +template <class charT> +size_t +basic_string<charT>::find_last_not_of (const basic_string<charT>& str, size_t pos) + const _THROW_NONE +{ + return find_last_not_of_str (str.data(), pos, str.length()); +} + +template <class charT> +size_t +basic_string<charT>::find_last_not_of (const charT* s, size_t pos, size_t n) + const _THROW_NONE +{ + return find_last_not_of_str (s, pos, n); +} + +template <class charT> +size_t +basic_string<charT>::find_last_not_of (const charT* s, size_t pos) const + _THROW_NONE +{ + return find_last_not_of_str (s, pos, baggage_type::length(s)); +} + +template <class charT> +size_t +basic_string<charT>::find_last_not_of (charT c, size_t pos) const _THROW_NONE +{ + size_t count = ((pos < length()) ? pos+1 : length()); + if (length() == 0) + return NPOS; + while ((baggage_type::eq(*(data()+count-1), c)) && (count > 1)) + --count; + if ((count == 1) && (baggage_type::eq(*(data()), c))) + return NPOS; + else + return count-1; +} + +template <class charT> +basic_string<charT> +basic_string<charT>::substr (size_t pos, size_t n) const _THROW_ALLOC_OUTRANGE +{ + if (pos > length()) + { + reference_class::throwrange(); + } + if (length()) + return basic_string<charT> (data()+pos, + (n > (length()-pos)) ? (length()-pos) : n); + else + return basic_string<charT>(); +} + +template <class charT> +int +basic_string<charT>::compare (const basic_string<charT>& str, size_t pos, + size_t n) const _THROW_OUTRANGE +{ + size_t slen = (n > (length()-pos)) ? (length()-pos) : n; + return compare_str (pos, str.data(), slen, str.length()); +} + +template <class charT> +int +basic_string<charT>::compare (const charT* s, size_t pos, size_t n) const + _THROW_LENGTH_OUTRANGE +{ + if (n == NPOS) + { + reference_class::throwlength(); + } + return compare_str (pos, s, length()-pos, n); +} + +template <class charT> +int +basic_string<charT>::compare (const charT* s, size_t pos) const _THROW_OUTRANGE +{ + return compare_str (pos, s, length()-pos, baggage_type::length(s)); +} + +template <class charT> +int +basic_string<charT>::compare (charT c, size_t pos, size_t rep) const + _THROW_LENGTH_OUTRANGE +{ + if (pos > length()) + { + reference_class::throwrange(); + } + if (rep == NPOS) + { + reference_class::throwlength(); + } + if (rep) + { + size_t count = 0; + while ((count < rep) && (count < (length()-pos)) && + baggage_type::eq (*(data()+pos+count), c)) + ++count; + if ((count == rep) || (count == (length()-pos))) + return (length()-pos-count); + else + return (*(data()+pos+count)-c); + } + else + { + return (length()-pos); + } +} + +template <class charT> +basic_string<charT> +operator+ (const basic_string<charT>& lhs, const basic_string<charT>& rhs) + _THROW_ALLOC_LENGTH +{ + typedef basic_string<charT>::baggage_type baggage_type; + basic_string<charT> tmp(lhs.data(), lhs.length(), rhs.length()); + if (rhs.length()) + baggage_type::copy (tmp.point()+lhs.length(), rhs.data(), rhs.length()); + tmp.len() += rhs.length(); + return tmp; +} + +template <class charT> +basic_string<charT> +operator+ (const charT* lhs, const basic_string<charT>& rhs) _THROW_ALLOC_LENGTH +{ + typedef basic_string<charT>::baggage_type baggage_type; + size_t slen = baggage_type::length(lhs); + basic_string<charT> tmp(lhs, slen, rhs.length()); + if (rhs.length()) + baggage_type::copy (tmp.point()+slen, rhs.data(), rhs.length()); + tmp.len() += rhs.length(); + return tmp; +} + +template <class charT> +basic_string<charT> +operator+ (charT lhs, const basic_string<charT>& rhs) _THROW_ALLOC_LENGTH +{ + typedef basic_string<charT>::baggage_type baggage_type; + basic_string<charT> tmp(&lhs, 1, rhs.length()); + if (rhs.length()) + baggage_type::copy (tmp.point()+1, rhs.data(), rhs.length()); + tmp.len() += rhs.length(); + return tmp; +} + +template <class charT> +basic_string<charT> +operator+ (const basic_string<charT>& lhs, const charT* rhs) _THROW_ALLOC_LENGTH +{ + typedef basic_string<charT>::baggage_type baggage_type; + size_t slen = baggage_type::length(rhs); + basic_string<charT> tmp(lhs.data(), lhs.length(), slen); + if (slen) + baggage_type::copy (tmp.point()+lhs.length(), rhs, slen); + tmp.len() += slen; + return tmp; +} + +template <class charT> +basic_string<charT> +operator+ (const basic_string<charT>& lhs, charT rhs) _THROW_ALLOC_LENGTH +{ + typedef basic_string<charT>::baggage_type baggage_type; + basic_string<charT> tmp(lhs.data(), lhs.length(), 1); + baggage_type::assign (*(tmp.point()+lhs.length()), rhs); + ++tmp.len(); + return tmp; +} + +template <class charT> +ostream& +operator<< (ostream& o, const basic_string<charT>& s) _THROW_NONE +{ + typedef basic_string<charT>::baggage_type baggage_type; + for (size_t count = 0; count < s.length(); ++count) + baggage_type::char_out (o, *(s.data()+count)); + return o; +} + +template <class charT> +istream& +operator>> (istream& i, basic_string<charT>& s) _THROW_ALLOC_LENGTH +{ + typedef basic_string<charT>::baggage_type baggage_type; + s.remove(); + while (true) + { + charT value; + baggage_type::char_in (i, value); + if (!i.operator void*()) + break; + if (!baggage_type::is_del (value)) + { + s.append(value); + while (true) + { + baggage_type::char_in (i, value); + if (!i.operator void*()) + break; + if (!baggage_type::is_del (value)) + { + s.append(value); + } + else + break; + } + break; + } + } + return i; +} + +template basic_string<char>; +typedef basic_string<char> cstring; +typedef basic_string<char> string; +//typedef basic_string<wchar_t> wstring; + + +/* + *Added by d:\\convert.pl --begin-- + */ +} +/* + *Added by d:\\convert.pl --end-- + */ + +#endif diff --git a/STL/bvector.h b/STL/bvector.h new file mode 100644 index 00000000000..b206a40f36d --- /dev/null +++ b/STL/bvector.h @@ -0,0 +1,438 @@ +/* + * + * 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 and Microsoft + * Corporation make 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> +#include <bool.h> + +#ifndef Allocator +#define Allocator allocator +#include <defalloc.h> +#endif + +#define __WORD_BIT (int(CHAR_BIT*sizeof(unsigned int))) + + +/* + *Added by d:\\convert.pl --begin-- + */ +namespace std { +/* + *Added by d:\\convert.pl --end-- + */ + +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) { + std::swap(start, x.start); + std::swap(finish, x.finish); + std::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 + + +/* + *Added by d:\\convert.pl --begin-- + */ +} +/* + *Added by d:\\convert.pl --end-- + */ + +#endif + + diff --git a/STL/defalloc.h b/STL/defalloc.h new file mode 100644 index 00000000000..56c5e692e96 --- /dev/null +++ b/STL/defalloc.h @@ -0,0 +1,198 @@ +/* + * + * 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 and Microsoft + * Corporation make 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> + +#if 0 +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; +} +*/ + +/* + * Begin change by Terris + */ +namespace std { +/* + * End change by Terris + */ + +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; + + /* + * Begin change by Terris + * + * This removes compile-time warnings about signed/unsigned mismatch + * and negating unsigned values. + * typedef size_t size_type; + */ + typedef long size_type; + /* + * End change by Terris + */ + + typedef ptrdiff_t difference_type; + pointer allocate(size_type n) { + return std::allocate((difference_type)n, (pointer)0); + } + void deallocate(pointer p) { std::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))); + } + */ + size_type init_page_size() { + return size_type(4096/sizeof(T)); + } + size_type max_size() const { + return size_type(UINT_MAX/sizeof(T)); + } +}; + +class allocator<void> { +public: + typedef void* pointer; +}; + + + + +/* + *Added by d:\\convert.pl --begin-- + */ +} +/* + *Added by d:\\convert.pl --end-- + */ + +#endif diff --git a/STL/deque.h b/STL/deque.h new file mode 100644 index 00000000000..2f273e76c44 --- /dev/null +++ b/STL/deque.h @@ -0,0 +1,586 @@ +/* + * + * 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 and Microsoft + * Corporation make 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> +#include <bool.h> + +#ifndef Allocator +#define Allocator allocator +#include <defalloc.h> +#endif + +#ifndef deque +#define deque deque +#endif + + +/* + *Added by d:\Terris\convert.pl --begin-- + */ +namespace std { +/* + *Added by d:\Terris\convert.pl --end-- + */ + +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; + static size_type buffer_size; + 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 + 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(buffer_size * (node - x.node - 1) + + (current - first) + (x.last - x.current)); + } + iterator& operator++() { + if (++current == last) { + first = *(++node); + current = first; + last = first + buffer_size; + } + return *this; + } + iterator operator++(int) { + iterator tmp = *this; + ++*this; + return tmp; + } + iterator& operator--() { + if (current == first) { + first = *(--node); + last = first + 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 / buffer_size + : -((-offset + buffer_size - 1) / buffer_size); + if (num_node_to_jump == 0) + current += n; + else { + node = node + num_node_to_jump; + first = *node; + last = first + buffer_size; + current = first + (offset - num_node_to_jump * 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 + 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(buffer_size * (node - x.node - 1) + + (current - first) + (x.last - x.current)); + } + const_iterator& operator++() { + if (++current == last) { + first = *(++node); + current = first; + last = first + 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 + 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 / buffer_size + : -((-offset + buffer_size - 1) / buffer_size); + if (num_node_to_jump == 0) + current += n; + else { + node = node + num_node_to_jump; + first = *node; + last = first + buffer_size; + current = first + (offset - num_node_to_jump * 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) { +/* + * Changed by Terris + */ + /*buffer_size = data_allocator.init_page_size();*/ + } + 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; + } + void push_back(const T& x) { + if (empty() || end().current == end().last) + allocate_at_end(); + construct(finish.current, x); + ++finish.current; + ++length; + } + void pop_front() { + destroy(start.current); + ++start.current; + --length; + if (empty() || begin().current == begin().last) + deallocate_at_begin(); + } + void pop_back() { + --finish.current; + destroy(finish.current); + --length; + if (empty() || end().current == end().first) + deallocate_at_end(); + } + void swap(deque<T>& x) { + std::swap(start, x.start); + std::swap(finish, x.finish); + std::swap(length, x.length); + std::swap(map, x.map); + std::swap(map_size, x.map_size); + } + 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); + deque(size_type n, const T& value = T()) + : start(), finish(), length(0), map(0), map_size(0) { +/* + * Changed by Terris + */ + /*buffer_size = data_allocator.init_page_size();*/ + 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) { +/* + * Changed by Terris + */ + /*buffer_size = data_allocator.init_page_size();*/ + copy(first, last, back_inserter(*this)); + } + deque(const deque<T>& x) + : start(), finish(), length(0), map(0), map_size(0) { +/* + * Changed by Terris + */ + /*buffer_size = data_allocator.init_page_size();*/ + 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(); +}; + +template <class T> +deque<T>::data_allocator_type deque<T>::data_allocator; + +template <class T> +deque<T>::map_allocator_type deque<T>::map_allocator; + +/* + * Changed by Terris + */ +#if 0 +template <class T> +deque<T>::size_type deque<T>::buffer_size = 0; +// should be data_allocator.init_page_size(); // Borland bug +#endif + +/* + * Added by Terris + */ +template <class T> +deque<T>::size_type deque<T>::buffer_size = data_allocator.init_page_size(); + +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(buffer_size); + if (!empty()) { + if (start.node == map) { + difference_type i = finish.node - start.node; + map_size = (i + 1) * 2; + map_pointer tmp = map_allocator.allocate(map_size); + copy(start.node, finish.node + 1, tmp + map_size / 4 + 1); + map_allocator.deallocate(map); + map = tmp; + map[map_size / 4] = p; + start = iterator(p + buffer_size, map + map_size / 4); + finish = iterator(finish.current, map + map_size / 4 + i + 1); + } else { + *--start.node = p; + start = iterator(p + buffer_size, start.node); + } + } else { + map_size = map_allocator.init_page_size(); + map = map_allocator.allocate(map_size); + map[map_size / 2] = p; + start = iterator(p + buffer_size / 2 + 1, map + map_size / 2); + finish = start; + } +} + +template <class T> +void deque<T>::allocate_at_end() { + pointer p = data_allocator.allocate(buffer_size); + if (!empty()) { + if (finish.node == map + map_size - 1) { + difference_type i = finish.node - start.node; + map_size = (i + 1) * 2; + map_pointer tmp = map_allocator.allocate(map_size); + copy(start.node, finish.node + 1, tmp + map_size / 4); + map_allocator.deallocate(map); + 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 { + map_size = map_allocator.init_page_size(); + map = map_allocator.allocate(map_size); + map[map_size / 2] = p; + start = iterator(p + 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()) { + start = iterator(); + finish = start; + map_allocator.deallocate(map); + } 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; + map_allocator.deallocate(map); + } else + finish = iterator(*finish.node + buffer_size, finish.node); +} + +template <class T> +deque<T>::iterator deque<T>::insert(iterator position, const T& x) { + if (position == begin()) { + push_front(x); + return begin(); + } else if (position == end()) { + push_back(x); + return end() - 1; + } else if (end() - position > position - begin()) { + push_front(*begin()); + copy(begin() + 2, position, begin() + 1); + *(position - 1) = x; + return position - 1; + } else { + push_back(*(end() - 1)); + copy_backward(position, end() - 2, end() - 1); + *position = x; + return position; + } +} + +template <class T> +void deque<T>::insert(iterator position, size_type n, const T& x) { + if (end() - position > position - begin()) { + iterator old_begin = begin(); + if (n > position - old_begin) { + size_type m = n - (position - old_begin); + while (m-- > 0) push_front(x); + iterator i = position; + while (i != old_begin) push_front(*--i); + fill(old_begin, position, x); + } else { + iterator i = old_begin + n; + while (i != old_begin) push_front(*--i); + copy(old_begin + n, position, old_begin); + fill(position - n, position, x); + } + } else { + iterator old_end = end(); + if (n > old_end - position) { + size_type m = n - (old_end - position); + while (m-- > 0) push_back(x); + iterator i = position; + while (i != old_end) push_back(*i++); + fill(position, old_end, x); + } else { + iterator i = old_end - n; + while (i != old_end) push_back(*i++); + copy_backward(position, old_end - n, old_end); + fill(position, position + n, x); + } + } +} + +template <class T> +void deque<T>::insert(iterator position, const T* first, const T* last) { + size_type n = 0; + distance(first, last, n); + if (end() - position > position - begin()) { + iterator old_begin = begin(); + if (n > position - old_begin) { + const T* m = last - (position - old_begin); + while (m != first) push_front(*--m); + iterator i = position; + while (i != old_begin) push_front(*--i); + copy(last - (position - old_begin), last, old_begin); + } else { + iterator i = old_begin + n; + while (i != old_begin) push_front(*--i); + copy(old_begin + n, position, old_begin); + copy(first, last, position - n); + } + } else { + iterator old_end = end(); + if (n > old_end - position) { + const T* m = first + (old_end - position); + while (m != last) push_back(*m++); + iterator i = position; + while (i != old_end) push_back(*i++); + copy(first, first + (old_end - position), position); + } else { + iterator i = old_end - n; + while (i != old_end) push_back(*i++); + copy_backward(position, old_end - n, old_end); + copy(first, last, position); + } + } +} + +template <class T> +void deque<T>::erase(iterator position) { + if (end() - position > position - begin()) { + copy_backward(begin(), position, position + 1); + pop_front(); + } else { + copy(position + 1, end(), position); + pop_back(); + } +} + +template <class T> +void deque<T>::erase(iterator first, iterator last) { + difference_type n = last - first; + 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 + + +/* + *Added by d:\Terris\convert.pl --begin-- + */ +} +/* + *Added by d:\Terris\convert.pl --end-- + */ + +#endif diff --git a/STL/function.h b/STL/function.h new file mode 100644 index 00000000000..b6f87a69706 --- /dev/null +++ b/STL/function.h @@ -0,0 +1,287 @@ +/* + * + * 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 and Microsoft + * Corporation make 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 + +#include <bool.h> + + +/* + *Added by d:\\convert.pl --begin-- + */ +namespace std { +/* + *Added by d:\\convert.pl --end-- + */ + +template <class T> +inline bool operator!=(const T& x, const T& y) { + return !(x == y); +} + +template <class T> +inline bool operator>(const T& x, const T& y) { + return y < x; +} + +template <class T> +inline bool operator<=(const T& x, const T& y) { + return !(y < x); +} + +template <class T> +inline bool operator>=(const T& x, const T& 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> +struct modulus : binary_function<T, T, T> { + T operator()(const T& x, const T& y) const { return x % y; } +}; + +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(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(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); +} + +/* + *Added by d:\\convert.pl --begin-- + */ +} +/* + *Added by d:\\convert.pl --end-- + */ + +#endif diff --git a/STL/heap.h b/STL/heap.h new file mode 100644 index 00000000000..75e1796beea --- /dev/null +++ b/STL/heap.h @@ -0,0 +1,212 @@ +/* + * + * 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 and Microsoft + * Corporation make 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 + + +/* + *Added by d:\\convert.pl --begin-- + */ +namespace std { +/* + *Added by d:\\convert.pl --end-- + */ + +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); +} + + +/* + *Added by d:\\convert.pl --begin-- + */ +} +/* + *Added by d:\\convert.pl --end-- + */ + +#endif diff --git a/STL/iterator.h b/STL/iterator.h new file mode 100644 index 00000000000..bf29871192d --- /dev/null +++ b/STL/iterator.h @@ -0,0 +1,414 @@ +/* + * + * 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 and Microsoft + * Corporation make 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> +#include <bool.h> +#include <function.h> + +struct input_iterator_tag {}; +struct output_iterator_tag {}; +struct forward_iterator_tag {}; +struct bidirectional_iterator_tag {}; +struct random_access_iterator_tag {}; + + +/* + *Added by d:\\convert.pl --begin-- + */ +namespace std { +/* + *Added by d:\\convert.pl --end-- + */ + +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> +// Reference = T& +// Distance = ptrdiff_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> +// Reference = T& +// Distance = ptrdiff_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> // 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; } +}; + + +/* + *Added by d:\\convert.pl --begin-- + */ +} +/* + *Added by d:\\convert.pl --end-- + */ + +#endif diff --git a/STL/list.h b/STL/list.h new file mode 100644 index 00000000000..095962f6c51 --- /dev/null +++ b/STL/list.h @@ -0,0 +1,510 @@ +/* + * + * 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 and Microsoft + * Corporation make 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> +#include <bool.h> + +#ifndef Allocator +#define Allocator allocator +#include <defalloc.h> +#endif + +#ifndef list +#define list list +#endif + + +/* + *Added by d:\Terris\convert.pl --begin-- + */ +namespace std { +/* + *Added by d:\Terris\convert.pl --end-- + */ + +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; + }; + static Allocator<list_node> list_node_allocator; + static Allocator<T> value_allocator; +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: + 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; +/* + * Changed by Terris + */ + /*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(); + } +/* + * Changed by Terris + */ + /*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; + } + +protected: + 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; +/* + * Changed by Terris + */ + list() : length(0), free_list(0), buffer_list(0), next_avail(0), last(0), number_of_lists(0) { + ++number_of_lists; + 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; } + size_type max_size() const { return list_node_allocator.max_size(); } + 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) { + std::swap(node, x.node); + std::swap(length, x.length); + } + iterator insert(iterator position, const T& x) { + link_type tmp = get_node(); + construct(value_allocator.address((*tmp).data), x); + (*tmp).next = position.node; + (*tmp).prev = (*position.node).prev; + (*(link_type((*position.node).prev))).next = tmp; + (*position.node).prev = tmp; + ++length; + return tmp; + } + 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); + 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; + destroy(value_allocator.address((*position.node).data)); + put_node(position.node); + --length; + } + void erase(iterator first, iterator last); + void pop_front() { erase(begin()); } + void pop_back() { + iterator tmp = end(); + erase(--tmp); + } +/* + * Changed by Terris + */ + list(size_type n, const T& value = T()) : length(0), free_list(0), buffer_list(0), next_avail(0), last(0), number_of_lists(0) { + ++number_of_lists; + node = get_node(); + (*node).next = node; + (*node).prev = node; + insert(begin(), n, value); + } +/* + * Changed by Terris + */ + list(const T* first, const T* last) : length(0), free_list(0), buffer_list(0), next_avail(0), last(0), number_of_lists(0) { + ++number_of_lists; + node = get_node(); + (*node).next = node; + (*node).prev = node; + insert(begin(), first, last); + } +/* + * Changed by Terris + */ + list(const list<T>& x) : length(0), free_list(0), buffer_list(0), next_avail(0), last(0), number_of_lists(0) { + ++number_of_lists; + node = get_node(); + (*node).next = node; + (*node).prev = node; + insert(begin(), x.begin(), x.end()); + } + ~list() { + erase(begin(), end()); + put_node(node); + if (--number_of_lists == 0) deallocate_buffers(); + } + 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(); +}; + +/* + * Added by Terris + */ +#if 0 +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; +/* + * Added by Terris + */ +#endif + +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; + +/* + * 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()); +} + +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; +} + +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++); +} + +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; + } + while(fill--) merge(counter[fill]); +} + +#undef Allocator +#undef list + + +/* + *Added by d:\Terris\convert.pl --begin-- + */ +} +/* + *Added by d:\Terris\convert.pl --end-- + */ + +#endif diff --git a/STL/map.h b/STL/map.h new file mode 100644 index 00000000000..2cf7e543269 --- /dev/null +++ b/STL/map.h @@ -0,0 +1,167 @@ +/* + * + * 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 and Microsoft + * Corporation make 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> + + +/* + *Added by d:\\convert.pl --begin-- + */ +namespace std { +/* + *Added by d:\\convert.pl --end-- + */ + +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(); } + size_type max_size() const { return t.max_size(); } + 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 + + +/* + *Added by d:\\convert.pl --begin-- + */ +} +/* + *Added by d:\\convert.pl --end-- + */ + +#endif diff --git a/STL/multimap.h b/STL/multimap.h new file mode 100644 index 00000000000..570aa521999 --- /dev/null +++ b/STL/multimap.h @@ -0,0 +1,161 @@ +/* + * + * 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 and Microsoft + * Corporation make 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> + + +/* + *Added by d:\\convert.pl --begin-- + */ +namespace std { +/* + *Added by d:\\convert.pl --end-- + */ + +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 + + +/* + *Added by d:\\convert.pl --begin-- + */ +} +/* + *Added by d:\\convert.pl --end-- + */ + +#endif diff --git a/STL/multiset.h b/STL/multiset.h new file mode 100644 index 00000000000..6c96e7504c3 --- /dev/null +++ b/STL/multiset.h @@ -0,0 +1,148 @@ +/* + * + * 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 and Microsoft + * Corporation make 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> + + +/* + *Added by d:\\convert.pl --begin-- + */ +namespace std { +/* + *Added by d:\\convert.pl --end-- + */ + +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 + + +/* + *Added by d:\\convert.pl --begin-- + */ +} +/* + *Added by d:\\convert.pl --end-- + */ + +#endif diff --git a/STL/pair.h b/STL/pair.h new file mode 100644 index 00000000000..acb45a2f7f1 --- /dev/null +++ b/STL/pair.h @@ -0,0 +1,62 @@ +/* + * + * 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 and Microsoft + * Corporation make 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 + +#include <bool.h> + + +/* + *Added by d:\\convert.pl --begin-- + */ +namespace std { +/* + *Added by d:\\convert.pl --end-- + */ + +template <class T1, class T2> +struct pair { + T1 first; + T2 second; + 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); +} + + +/* + *Added by d:\\convert.pl --begin-- + */ +} +/* + *Added by d:\\convert.pl --end-- + */ + +#endif diff --git a/STL/projectn.h b/STL/projectn.h new file mode 100644 index 00000000000..eae35dd8e6d --- /dev/null +++ b/STL/projectn.h @@ -0,0 +1,50 @@ +/* + * + * 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 and Microsoft + * Corporation make 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> + + +/* + *Added by d:\\convert.pl --begin-- + */ +namespace std { +/* + *Added by d:\\convert.pl --end-- + */ + +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; } +}; + + +/* + *Added by d:\\convert.pl --begin-- + */ +} +/* + *Added by d:\\convert.pl --end-- + */ + +#endif diff --git a/STL/ptr.h b/STL/ptr.h new file mode 100644 index 00000000000..ad0fe736795 --- /dev/null +++ b/STL/ptr.h @@ -0,0 +1,338 @@ +//***************************************************************************** +// +// Class Ptr +// +// Ptr is a proxy for a pointer to an object. This class provides automatic +// deletion of objects allocated on the heap. Objects are viewed via the +// ->, *, and (itemClass *) operators. Since these operators are inline, there +// is no performance penalty for using this proxy instead of a real pointer. +// +// You can assign multiple pointers to one Ptr object. If you +// do, the old object will be destroyed automatically. +// +// Use suggestions: +// 1. To clean up pointers returned by functions or methods that +// return pointers and expect the caller to delete the pointer. +// 2. To make sure an object gets deleted. Using Ptr saves you +// the hassle of writing an exception handler for this purpose. +// 3. Part of a composite object (assembly-part). +// This class is a useful substitute when pointers are needed, +// because object clean-up is fully encapsulated. +// The following are cases where pointers would normally be used. +// +// For declaring class data members that may or +// may not be instantiated (1 to 0-or-1 relationship). +// +// To instantiate a data member only when it is really needed, +// reducing average memory consumption during execution. +// +// MFC and thread-local storage -- some MFC objects can only be +// accessed by the thread that created them. MFC sub-component +// objects cannot be instantiated along with its container object +// if the container object is created in one thread and the MFC +// object is accessed in another. +// +// When a 'part' class does not have a default constructor. +// There are two solutions provided by C++ for this situation. +// The designer could use a pointer to the object instead, +// or the designer could alter the assembly class's constructor +// to accept parameters that are passed on to the 'part' class's +// constructor. +// +// See Design Patterns - Proxy pattern, and the Iterator pattern (pg 266). +// +// Template Parameters: +// itemClass: The class of the underlying object (the 'pointed to' object). +// +//***************************************************************************** + +template <class itemClass> +class Ptr +{ + public: + + // Construction + Ptr( itemClass *pItem = NULL ); + Ptr( const Ptr& ); + + // Destruction + ~Ptr(); + + // Access to 'real' object + inline itemClass * operator -> () const; + inline operator itemClass * () const; + inline itemClass& operator * () const; + + // Assignment + Ptr& operator = ( const Ptr& ); + Ptr& operator = ( itemClass *pItem ); + itemClass *& GetPtrRef(); + + // Other + void Disown(); + + private: + + itemClass *m_pObject; +}; + +//***************************************************************************** +// +// Ptr default constructor +// +// DESCRIPTION: +// +// Constructor. +// +// INPUT PARAMETERS: +// pItem - Pointer to the object to point to. pItem is deleted +// when 'this' is deleted. +// +//***************************************************************************** + +template <class itemClass> +Ptr<itemClass>::Ptr<itemClass>( itemClass *pItem ) + : m_pObject( pItem ) +{ +} + +//***************************************************************************** +// +// Ptr::Ptr (Ptr&) +// +// DESCRIPTION: +// +// Copy constructor. To avoid deleting 'rCopy's object +// twice, 'rCopy' will not point to any object after this method completes. +// rCopy is not really const, but it is declared 'const' since +// this allows putting Ptr's in STL containers. +// +// INPUT PARAMETERS: +// rCopy - A reference to the Ptr to copy. +// +// OUTPUT PARAMETERS: +// rCopy - No longer points to anything. +// +//***************************************************************************** + +template <class itemClass> +Ptr<itemClass>::Ptr<itemClass>( const Ptr<itemClass>& rCopy ) +{ + m_pObject = rCopy.m_pObject; + + // rCopy no longer owns the object. + const_cast< Ptr<itemClass>& >(rCopy).m_pObject = NULL; +} + +//***************************************************************************** +// +// Ptr::~Ptr +// +// DESCRIPTION: +// +// Destroys the object that is being pointed to (if any). +// +//***************************************************************************** + +template <class itemClass> +Ptr<itemClass>::~Ptr<itemClass>() +{ + delete m_pObject; // delete NULL OK +} + +//***************************************************************************** +// +// Ptr::GetPtrRef +// +// DESCRIPTION: +// +// Returns a reference to an internal pointer. This allows these +// objects to be sent to functions that accept pointers to pointers +// or references to pointers as output arguments. Typically, this +// is how functions return multiple objects. +// +// This is not const because this method is ultimately intended +// for changing the object's value. +// +// RETURNS: +// A reference to the 'pointer' data member of this object. +// +//***************************************************************************** + +template <class itemClass> +itemClass *& Ptr<itemClass>::GetPtrRef() +{ + return m_pObject; +} + +//***************************************************************************** +// +// Ptr::operator -> +// +// DESCRIPTION: +// +// Provides access to the interface of the underlying object. +// +// RETURNS: +// Nothing callers can really use - only the compiler can use it. +// This method is part of the pointer to member operator (-> *). +// +//***************************************************************************** + +template <class itemClass> +itemClass * Ptr<itemClass>::operator -> () const +{ + return m_pObject; +} + +//***************************************************************************** +// +// Ptr::operator itemClass * +// +// DESCRIPTION: +// +// Provides access to the underlying object. +// +// RETURNS: +// Pointer to the object that is being pointed to. +// +//***************************************************************************** + +template <class itemClass> +Ptr<itemClass>::operator itemClass * () const +{ + return m_pObject; +} + +//***************************************************************************** +// +// Ptr::operator * +// +// DESCRIPTION: +// +// Provides access to the underlying object. +// +// RETURNS: +// Reference to the object that is being pointed to. +// +//***************************************************************************** + +template <class itemClass> +itemClass& Ptr<itemClass>::operator * () const +{ + return *m_pObject; +} + +//***************************************************************************** +// +// Ptr::operator = (Ptr&) +// +// DESCRIPTION: +// +// For assigning one Ptr to another. Deletes the object that 'this' +// is pointing to and makes 'this' point to the object that 'rCopy' +// is pointing to. To avoid deleting 'rCopy's object twice, 'rCopy' +// will not point to any object after this method completes. +// +// Although the parameter rCopy can be arugably not "const", it +// must be "const" since the compiler will complain in certain +// cases with warning C4270. +// +// INPUT PARAMETERS: +// rCopy - A reference to the Ptr to copy. +// +// OUTPUT PARAMETERS: +// rCopy - No longer points to anything. +// +// RETURNS: +// A reference to 'this'. +// +//***************************************************************************** + +template <class itemClass> +Ptr<itemClass>& +Ptr<itemClass>::operator = ( const Ptr<itemClass>& rCopy ) +{ + // Check for A = A + if ( &rCopy == this ) + { + return *this; + } + + // Save current pointer so we can delete it after + // doing everything else + itemClass *pOldObject = m_pObject; + + // Get the pointer out of rCopy + m_pObject = rCopy.m_pObject; + + // rCopy no longer owns the object. + const_cast< Ptr<itemClass>& >(rCopy).m_pObject = NULL; + + // This might generate an exception. But, we won't + // introduce a memory leak because 'this' now + // owns rCopy's pointer. + delete pOldObject; // delete NULL OK + + return *this; +} + +//***************************************************************************** +// +// Ptr::operator = +// +// DESCRIPTION: +// +// Changes the underlying object. If the proxy currently has an +// underlying object, then it is deleted. +// +// INPUT PARAMETERS: +// pItem - Reference to the new object. Can be NULL. +// +// RETURNS: +// Reference to 'this'. +// +//***************************************************************************** + +template <class itemClass> +Ptr<itemClass>& Ptr<itemClass>::operator = ( itemClass *pItem ) +{ + if ( m_pObject == pItem ) + { + return *this; + } + + // Save current pointer so we can delete it after + // doing everything else + itemClass *pOldObject = m_pObject; + + m_pObject = pItem; + + // This might generate an exception. But, we won't + // introduce a memory leak because 'this' now + // owns pItem. + delete pOldObject; // delete NULL OK + + return *this; +} + +//***************************************************************************** +// +// Ptr::Disown +// +// DESCRIPTION: +// +// Ptr objects delete their pointed-to objects when they go out +// of scope. Calling Disown() causes the Ptr object to 'forget' +// that it is currently pointing to an object. +// +// RETURNS: +// Doesn't return anything because returning a value such as a pointer +// to the item encourages misuse leading to memory leaks. +// +//***************************************************************************** +template <class itemClass> +void Ptr<itemClass>::Disown() +{ + m_pObject = NULL; +} diff --git a/STL/random.cpp b/STL/random.cpp new file mode 100644 index 00000000000..57ef645ae64 --- /dev/null +++ b/STL/random.cpp @@ -0,0 +1,58 @@ +/* + * + * 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 and Microsoft + * Corporation make 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 (i = 0; i < 55; i++) + table[i] = table[i] - table[(1 + i + 30) % 55]; + } + index1 = 0; + index2 = 31; +} + +__random_generator rd(__SEED); + +unsigned long __long_random(unsigned long limit) { + return rd(limit); +} diff --git a/STL/set.h b/STL/set.h new file mode 100644 index 00000000000..95ce5e1279d --- /dev/null +++ b/STL/set.h @@ -0,0 +1,151 @@ +/* + * + * 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 and Microsoft + * Corporation make 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> + + +/* + *Added by d:\\convert.pl --begin-- + */ +namespace std { +/* + *Added by d:\\convert.pl --end-- + */ + +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 + + +/* + *Added by d:\\convert.pl --begin-- + */ +} +/* + *Added by d:\\convert.pl --end-- + */ + +#endif diff --git a/STL/stack.h b/STL/stack.h new file mode 100644 index 00000000000..fbbfcff7541 --- /dev/null +++ b/STL/stack.h @@ -0,0 +1,137 @@ +/* + * + * 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 and Microsoft + * Corporation make 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 + +#include <bool.h> +#include <heap.h> + + +/* + *Added by d:\\convert.pl --begin-- + */ +namespace std { +/* + *Added by d:\\convert.pl --end-- + */ + +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 + + +/* + *Added by d:\\convert.pl --begin-- + */ +} +/* + *Added by d:\\convert.pl --end-- + */ + +#endif diff --git a/STL/stl.h b/STL/stl.h new file mode 100644 index 00000000000..2d75e19ba5a --- /dev/null +++ b/STL/stl.h @@ -0,0 +1,206 @@ +#ifndef __STL_H +#define __STL_H +#endif + +#include <bool.h> + +// Assumes MFC is included too. + +//***************************************************************************** +// +// SequenceDelete +// +// DESCRIPTION: +// +// Deletes items in an STL sequence container. All items in the +// container must be pointers to objects. +// +// INPUT PARAMETERS: +// first - An iterator. Should point to the first item to delete. +// last - An iterator. Should point AFTER the last item you wish +// to delete. +// +//***************************************************************************** + +template <class ForwardIteratorClass> +void +SequenceDelete(ForwardIteratorClass first, const ForwardIteratorClass &last) +{ + using namespace std; + + while ( first != last ) + { + delete *first++; + } +} + +//***************************************************************************** +// +// MapDelete +// +// DESCRIPTION: +// +// Deletes items in an STL map container. All items in the container +// must be pointers to objects. +// +// INPUT PARAMETERS: +// first - An iterator. Should point to the first item to delete. +// last - An iterator. Should point AFTER the last item you wish +// to delete. +// +//***************************************************************************** + +template <class ForwardIteratorClass> +void +MapDelete(ForwardIteratorClass first, const ForwardIteratorClass &last) +{ + using namespace std; + + while ( first != last ) + { + delete (*first++).second; + } +} + +//***************************************************************************** +// +// Comparison operators +// +// STL cannot find comparison operators at the global level. Is this a +// compier bug?? +// +// These functions cannot be templates because they will cause ambiguity +// errors within the STL code. +// +//***************************************************************************** + +//***************************************************************************** +// STL_ROUTE_ALL_GLOBALS(T1, T2) (macro) +// +// DESCRIPTION: +// +// This macro routes all of the comparison operators for a class whose +// operators happen to be defined at the global level. +// +// INPUT PARAMETERS: +// T1 - The name of the left-hand-side class. +// T2 - The name of the right-hand-side class. +// +//***************************************************************************** + +#define STL_ROUTE_ALL_GLOBALS(T1, T2) \ +namespace std \ +{ \ + inline bool operator == ( const T1 &s1, const T2 &s2 ) \ + { \ + return ::operator == (s1, s2); \ + } \ + inline bool operator != ( const T1 &s1, const T2 &s2 ) \ + { \ + return ::operator != (s1, s2); \ + } \ + inline bool operator > ( const T1 &s1, const T2 &s2 ) \ + { \ + return ::operator > (s1, s2); \ + } \ + inline bool operator < ( const T1 &s1, const T2 &s2 ) \ + { \ + return ::operator < (s1, s2); \ + } \ + inline bool operator >= ( const T1 &s1, const T2 &s2 ) \ + { \ + return ::operator >= (s1, s2); \ + } \ + inline bool operator <= ( const T1 &s1, const T2 &s2 ) \ + { \ + return ::operator <= (s1, s2); \ + } \ +} + +//***************************************************************************** +// STL_DECLARE_GLOBAL_NE(T1, T2) (macro) / Inequality +// STL_DECLARE_GLOBAL_GT(T1, T2) (macro) / Greater than +// STL_DECLARE_GLOBAL_GE(T1, T2) (macro) / Greater than or equal to +// STL_DECLARE_GLOBAL_LE(T1, T2) (macro) / Less than or equal to +// +// DESCRIPTION: +// +// These macros duplicate the behavior in the STL's function.h file. +// This behavior provides default implementations of certain comparison +// operators: !=, >, >=, and <=. +// +// STL is designed to instantiate these operators automatically if +// they are missing. This convenient feature of the STL has wreaked havoc +// on MFC and as a result Microsoft punted and said "use the std namespace." +// However, this introduced a new problem -- the STL can no longer +// automatically derive !=, <, >=, and <= from the objects' existing +// operators, because the operators are not accessible from the std +// namespace (they are in the global namespace). In fact, STL cannot +// even find the default global operators (such as == between two +// classes). This seems like a bug in Microsoft's compiler. +// +// If you are storing a new class of objects in an STL container and +// want to use find() on the container, then you must declare a global +// equality operator on the object. Then you can either create your +// own != operator, or derive one using STL_DECLARE_GLOBAL_NE. +// +// e.g., bool operator == ( const X&, const X& ) +// STL_DECLARE_GLOBAL_NE( X, X ) +// +// It's not a bad idea to declare: +// bool operator < ( const X&, const X& ) too. +// +// These macros should be used with classes that implement their +// comparison operators as global functions. +// +// INPUT PARAMETERS: +// T1 - The name of the left-hand-side class. +// T2 - The name of the right-hand-side class. +// +//***************************************************************************** + +// Retuires == (T1, T2) +#define STL_DECLARE_GLOBAL_NE(T1, T2) \ +namespace std \ +{ \ + inline bool operator != ( const T1 &s1, const T2 &s2 ) \ + { \ + return !( ::operator == (s1, s2) ); \ + } \ +} + +// Requires < ( T2, T1 ) +#define STL_DECLARE_GLOBAL_GT(T1, T2) \ +namespace std \ +{ \ + inline bool operator > ( const T1 &s1, const T2 &s2 ) \ + { \ + return ::operator < (s2, s1); \ + } \ +} + +// Requires < ( T1, T2 ) +#define STL_DECLARE_GLOBAL_GE(T1, T2) \ +namespace std \ +{ \ + inline bool operator >= ( const T1 &s1, const T2 &s2 ) \ + { \ + return !( ::operator < (s1, s2) ); \ + } \ +} + +// Requires < ( T2, T1 ) +#define STL_DECLARE_GLOBAL_LE(T1, T2) \ +namespace std \ +{ \ + inline bool operator <= ( const T1 &s1, const T2 &s2 ) \ + { \ + return !( ::operator < (s2, s1) ); \ + } \ +} + +//***************************************************************************** +// Route CString's comparison operators. +//***************************************************************************** + +STL_ROUTE_ALL_GLOBALS(CString, CString) diff --git a/STL/tempbuf.cpp b/STL/tempbuf.cpp new file mode 100644 index 00000000000..90760dc5326 --- /dev/null +++ b/STL/tempbuf.cpp @@ -0,0 +1,19 @@ +/* + * + * 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 and Microsoft + * Corporation make 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/STL/tempbuf.h b/STL/tempbuf.h new file mode 100644 index 00000000000..84c9f4b2306 --- /dev/null +++ b/STL/tempbuf.h @@ -0,0 +1,74 @@ +/* + * + * 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 and Microsoft + * Corporation make 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 + + +/* + *Added by d:\\convert.pl --begin-- + */ +namespace std { +/* + *Added by d:\\convert.pl --end-- + */ + +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)); +} + + +/* + *Added by d:\\convert.pl --begin-- + */ +} +/* + *Added by d:\\convert.pl --end-- + */ + +#endif diff --git a/STL/tree.h b/STL/tree.h new file mode 100644 index 00000000000..71568ec7807 --- /dev/null +++ b/STL/tree.h @@ -0,0 +1,1068 @@ +/* + * + * 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 and Microsoft + * Corporation make 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> +#include <bool.h> +#include <projectn.h> + +#ifndef rb_tree +#define rb_tree rb_tree +#endif + +/* + *Added by d:\Terris\convert.pl --begin-- + */ +namespace std { +/* + *Added by d:\Terris\convert.pl --end-- + */ + +template <class Key, class Value, class KeyOfValue, class Compare> +class rb_tree { +protected: + enum color_type {red, black}; + typedef Allocator<void>::pointer void_pointer; + struct rb_tree_node; + friend rb_tree_node; + struct rb_tree_node { + color_type color_field; + void_pointer parent_link; + void_pointer left_link; + void_pointer right_link; + Value value_field; + }; + static Allocator<rb_tree_node> rb_tree_node_allocator; + static Allocator<Value> value_allocator; +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: + size_type buffer_size() { + return rb_tree_node_allocator.init_page_size(); + } + 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: + static Allocator<rb_tree_node_buffer> buffer_allocator; +/* + * Changed by Terris + */ + /*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 = 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(); + } +/* + * Changed by Terris + */ + /*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; + } +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; +/* + * Changed by Terris + */ + /*static*/ link_type NIL; + + 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; } +/* + * Changed by Terris + * Doesn't need to take "NIL" parameter because everyone who calls this + * uses links only from "this" + */ + /*static*/ link_type minimum(link_type x) { + while (left(x) != NIL) + x = left(x); + return x; + } +/* + * Changed by Terris + */ + /*static*/ link_type maximum(link_type x) { + while (right(x) != NIL) + x = right(x); + return x; + } +public: + class iterator; + friend iterator; + class const_iterator; + friend const_iterator; +/* + * Terris comment: Here is where the iterator class starts. + */ + class iterator : public bidirectional_iterator<Value, difference_type> { + friend class rb_tree<Key, Value, KeyOfValue, Compare>; + friend class const_iterator; +/* + * Added by Terris + */ + link_type NIL; + +/* + friend bool operator==(const iterator& x, const iterator& y) { + return x.node == y.node; + } +*/ + protected: + link_type node; + iterator(link_type x, link_type NIL) : node(x), NIL(NIL) {} + public: + iterator() {} + bool operator==(const iterator& y) const { return node == y.node; } + reference operator*() const { return value(node); } + iterator& operator++() { + if (right(node) != NIL) { + node = right(node); + while (left(node) != 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) != NIL) { + link_type y = left(node); + while (right(y) != 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; + } + }; +/* + * Terris comment: Iterator class ends here + * Terris comment: Const Iterator class starts here + */ + 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; + } +*/ +/* + * Added by Terris + */ + link_type NIL; + + protected: + link_type node; + const_iterator(link_type x, link_type NIL) : node(x), NIL(NIL) {} + 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) != NIL) { + node = right(node); + while (left(node) != 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) != NIL) { + link_type y = left(node); + while (right(y) != 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; + } + }; +/* + * Terris comment: const_iterator ends here + */ + 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: + iterator __insert(link_type x, link_type y, const value_type& v); +/* + * Changed by Terris + */ + link_type __copy(link_type x, link_type p, link_type nil); + void __erase(link_type x); + void init() { + ++number_of_trees; + if ( NIL == 0 ) { + NIL = get_node(); + color(NIL) = black; + parent(NIL) = 0; + left(NIL) = 0; + right(NIL) = 0; + } + header = get_node(); + color(header) = red; // used to distinguish header from root, + // in iterator.operator++ + root() = NIL; + leftmost() = header; + rightmost() = header; + } +public: + +// allocation/deallocation + +/* + * Changed by Terris + */ + rb_tree(const Compare& comp = Compare(), bool always = true) + : node_count(0), key_compare(comp), insert_always(always), free_list(0), buffer_list(0), next_avail(0), + last(0), number_of_trees(0), NIL(0) { + init(); + } +/* + * Changed by Terris + */ + rb_tree(const value_type* first, const value_type* last, + const Compare& comp = Compare(), bool always = true) + : node_count(0), key_compare(comp), insert_always(always), free_list(0), + buffer_list(0), next_avail(0), last(0), number_of_trees(0), NIL(0) { + init(); + insert(first, last); + } +/* + * Changed by Terris + */ + rb_tree(const rb_tree<Key, Value, KeyOfValue, Compare>& x, + bool always = true) : node_count(x.node_count), + key_compare(x.key_compare), insert_always(always), free_list(0), + buffer_list(0), next_avail(0), last(0), number_of_trees(0), + NIL( 0 ) { +/* + * Added by Terris + */ + init(); +/* + * Changed by Terris + */ + // ++number_of_trees; + // header = get_node(); + // color(header) = red; +/* + * Changed by Terris + */ + root() = __copy(x.root(), header, x.NIL); + if (root() == NIL) { + leftmost() = header; + rightmost() = header; + } else { + leftmost() = minimum(root()); + rightmost() = maximum(root()); + } + } + ~rb_tree() { + erase(begin(), end()); + put_node(header); + if (--number_of_trees == 0) { + put_node(NIL); + NIL = 0; + deallocate_buffers(); + free_list = 0; + next_avail = 0; + last = 0; + } + } + rb_tree<Key, Value, KeyOfValue, Compare>& + operator=(const rb_tree<Key, Value, KeyOfValue, Compare>& x); + +// accessors: + + Compare key_comp() const { return key_compare; } +/* + * Changed by Terris + */ + iterator begin() { return iterator(leftmost(), NIL); } +/* + * Changed by Terris + */ + const_iterator begin() const { return const_iterator(leftmost(), NIL); } +/* + * Changed by Terris + */ + iterator end() { return iterator(header, NIL); } +/* + * Changed by Terris + */ + const_iterator end() const { return const_iterator(header, NIL); } + 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; } + size_type max_size() const { + return rb_tree_node_allocator.max_size(); + } + void swap(rb_tree<Key, Value, KeyOfValue, Compare>& t) { + std::swap(header, t.header); + std::swap(node_count, t.node_count); + std::swap(insert_always, t.insert_always); + std::swap(key_compare, t.key_compare); + } + +// insert/erase + + typedef pair<iterator, bool> pair_iterator_bool; + // typedef done to get around compiler bug + 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); + void erase(const key_type* first, const key_type* last); + +// set operations: + + 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); +}; + +/* + * Added by Terris + */ +#if 0 +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; +/* + * Added by Terris + */ +#endif + +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; + +/* Added by Terris + */ +#if 0 +template <class Key, class Value, class KeyOfValue, class Compare> +rb_tree<Key, Value, KeyOfValue, Compare>::link_type + rb_tree<Key, Value, KeyOfValue, Compare>::NIL = 0; +#endif + +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); + } +} + +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()); +/* + * Changed by Terris + */ + root() = __copy(x.root(), header, x.NIL); + if (root() == 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> +rb_tree<Key, Value, KeyOfValue, Compare>::iterator +rb_tree<Key, Value, KeyOfValue, Compare>:: +__insert(link_type x, link_type y, const Value& v) { + ++node_count; + link_type z = get_node(); + construct(value_allocator.address(value(z)), v); + if (y == header || x != 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; + left(z) = NIL; + right(z) = 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, NIL); +} + +template <class Key, class Value, class KeyOfValue, class Compare> +rb_tree<Key, Value, KeyOfValue, Compare>::pair_iterator_bool +rb_tree<Key, Value, KeyOfValue, Compare>::insert(const Value& v) { + link_type y = header; + link_type x = root(); + bool comp = true; + while (x != 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, NIL); + 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> +rb_tree<Key, Value, KeyOfValue, Compare>::iterator +rb_tree<Key, Value, KeyOfValue, Compare>::insert(iterator position, + const Value& v) { + 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-NIL + else + return insert(v).first; + else if (position == iterator(end())) + if (key_compare(key(rightmost()), KeyOfValue()(v))) + return __insert(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) == NIL) + return __insert(NIL, before.node, v); + else + return __insert(position.node, position.node, v); + // first argument just needs to be non-NIL + else + return insert(v).first; + } +} + +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++); +} + +template <class Key, class Value, class KeyOfValue, class Compare> +void rb_tree<Key, Value, KeyOfValue, Compare>::erase(iterator position) { + link_type z = position.node; + link_type y = z; + link_type x; + if (left(y) == NIL) + x = right(y); + else + if (right(y) == NIL) + x = left(y); + else { + y = right(y); + while (left(y) != 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 == 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 == 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); + std::swap(color(y), color(z)); + std::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 == 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) == NIL) // left(z) must be NIL also + leftmost() = parent(z); + // makes leftmost() == header if z == root() + else + leftmost() = minimum(x); + if (rightmost() == z) + if (left(z) == NIL) // right(z) must be 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; + } + destroy(value_allocator.address(value(y))); + put_node(y); + --node_count; +} + +template <class Key, class Value, class KeyOfValue, class Compare> +rb_tree<Key, Value, KeyOfValue, Compare>::size_type +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> +rb_tree<Key, Value, KeyOfValue, Compare>::link_type +/* + * Changed by Terris + */ +rb_tree<Key, Value, KeyOfValue, Compare>::__copy(link_type x, link_type p, link_type xNIL) { + // structural copy + link_type r = x; + while (x != xNIL) { + link_type y = get_node(); + if (r == x) r = y; // save for return value + construct(value_allocator.address(value(y)), value(x)); + left(p) = y; + parent(y) = p; + color(y) = color(x); +/* + * Changed by Terris + */ + right(y) = __copy(right(x), y, xNIL); + p = y; + x = left(x); + } + left(p) = NIL; +/* + * Changed by Terris + */ + return r == xNIL ? NIL : r; +} + +template <class Key, class Value, class KeyOfValue, class Compare> +void rb_tree<Key, Value, KeyOfValue, Compare>::__erase(link_type x) { + // erase without rebalancing + while (x != NIL) { + __erase(right(x)); + link_type y = left(x); + destroy(value_allocator.address(value(x))); + put_node(x); + x = y; + } +} + +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++); +} + +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> +rb_tree<Key, Value, KeyOfValue, Compare>::iterator +rb_tree<Key, Value, KeyOfValue, Compare>::find(const Key& k) { + link_type y = header; + link_type x = root(); + bool comp = false; + while (x != NIL) { + y = x; + comp = key_compare(key(x), k); + x = comp ? right(x) : left(x); + } + iterator j = iterator(y, NIL); + if (comp) ++j; + return (j == end() || key_compare(k, key(j.node))) ? end() : j; +} + +template <class Key, class Value, class KeyOfValue, class Compare> +rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator +rb_tree<Key, Value, KeyOfValue, Compare>::find(const Key& k) const { + link_type y = header; + link_type x = root(); + bool comp = false; + while (x != NIL) { + y = x; + comp = key_compare(key(x), k); + x = comp ? right(x) : left(x); + } + const_iterator j = const_iterator(y, NIL); + if (comp) ++j; + return (j == end() || key_compare(k, key(j.node))) ? end() : j; +} + +template <class Key, class Value, class KeyOfValue, class Compare> +rb_tree<Key, Value, KeyOfValue, Compare>::size_type +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> +rb_tree<Key, Value, KeyOfValue, Compare>::iterator +rb_tree<Key, Value, KeyOfValue, Compare>::lower_bound(const Key& k) { + link_type y = header; + link_type x = root(); + bool comp = false; + while (x != NIL) { + y = x; + comp = key_compare(key(x), k); + x = comp ? right(x) : left(x); + } + iterator j = iterator(y, NIL); + return comp ? ++j : j; +} + +template <class Key, class Value, class KeyOfValue, class Compare> +rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator +rb_tree<Key, Value, KeyOfValue, Compare>::lower_bound(const Key& k) const { + link_type y = header; + link_type x = root(); + bool comp = false; + while (x != NIL) { + y = x; + comp = key_compare(key(x), k); + x = comp ? right(x) : left(x); + } + const_iterator j = const_iterator(y, NIL); + return comp ? ++j : j; +} + +template <class Key, class Value, class KeyOfValue, class Compare> +rb_tree<Key, Value, KeyOfValue, Compare>::iterator +rb_tree<Key, Value, KeyOfValue, Compare>::upper_bound(const Key& k) { + link_type y = header; + link_type x = root(); + bool comp = true; + while (x != NIL) { + y = x; + comp = key_compare(k, key(x)); + x = comp ? left(x) : right(x); + } + iterator j = iterator(y, NIL); + return comp ? j : ++j; +} + +template <class Key, class Value, class KeyOfValue, class Compare> +rb_tree<Key, Value, KeyOfValue, Compare>::const_iterator +rb_tree<Key, Value, KeyOfValue, Compare>::upper_bound(const Key& k) const { + link_type y = header; + link_type x = root(); + bool comp = true; + while (x != NIL) { + y = x; + comp = key_compare(k, key(x)); + x = comp ? left(x) : right(x); + } + const_iterator j = const_iterator(y, NIL); + return comp ? j : ++j; +} + + +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) != 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) != 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; +} + + +/* + *Added by d:\Terris\convert.pl --begin-- + */ +} +/* + *Added by d:\Terris\convert.pl --end-- + */ + +#endif diff --git a/STL/vector.h b/STL/vector.h new file mode 100644 index 00000000000..c1da703e508 --- /dev/null +++ b/STL/vector.h @@ -0,0 +1,302 @@ +/* + * + * 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 and Microsoft + * Corporation make 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> +#include <bool.h> + +#ifndef Allocator +#define Allocator allocator +#include <defalloc.h> +#endif + +#ifndef vector +#define vector vector +#endif + + +/* + *Added by d:\\convert.pl --begin-- + */ +namespace std { +/* + *Added by d:\\convert.pl --end-- + */ + +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; + void insert_aux(iterator position, const T& x); +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) { + std::swap(start, x.start); + std::swap(finish, x.finish); + std::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; + } + void insert (iterator position, const_iterator first, + const_iterator last); + void insert (iterator position, size_type n, const T& x); + 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); + } +}; + +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()); +} + + +template <class T> +vector<T>::vector_allocator vector<T>::static_allocator; + + +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> +void vector<T>::insert_aux(iterator position, const T& x) { + 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> +void vector<T>::insert(iterator position, size_type n, const T& x) { + if (n == 0) return; + if (end_of_storage - finish >= n) { + if (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> +void vector<T>::insert(iterator position, + const_iterator first, + const_iterator last) { + if (first == last) return; + size_type n = 0; + distance(first, last, n); + if (end_of_storage - finish >= n) { + if (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 + + +/* + *Added by d:\\convert.pl --begin-- + */ +} +/* + *Added by d:\\convert.pl --end-- + */ + +#endif + + |