# This is a shell archive. Remove anything before this line, # then unpack it by saving it in a file and typing "sh file". # # Wrapped by Meng Lee on Mon Oct 30 14:51:54 1995 # # This archive contains: # algo.h algobase.h bool.h bvector.h # defalloc.h deque.h doc.mif doc.ps # docbar.ps faralloc.h fdeque.h files.dif # flist.h fmap.h fmultmap.h fmultset.h # fset.h function.h hdeque.h heap.h # hlist.h hmap.h hmultmap.h hmultset.h # hset.h hugalloc.h hvector.h iterator.h # lbvector.h ldeque.h list.h llist.h # lmap.h lmultmap.h lmultset.h lngalloc.h # lset.h map.h multimap.h multiset.h # neralloc.h nmap.h nmultmap.h nmultset.h # nset.h pair.h projectn.h random.cpp # read.me readme.old set.h stack.h # tempbuf.cpp tempbuf.h tree.h vector.h # LANG=""; export LANG PATH=/bin:/usr/bin:$PATH; export PATH echo x - algo.h cat >algo.h <<'@EOF' /* * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * */ #ifndef ALGO_H #define ALGO_H #include #include #include #include #include #include #include template inline const T& __median(const T& a, const T& b, const T& c) { if (a < b) if (b < c) return b; else if (a < c) return c; else return a; else if (a < c) return a; else if (b < c) return c; else return b; } template inline const T& __median(const T& a, const T& b, const T& c, Compare comp) { if (comp(a, b)) if (comp(b, c)) return b; else if (comp(a, c)) return c; else return a; else if (comp(a, c)) return a; else if (comp(b, c)) return c; else return b; } template Function for_each(InputIterator first, InputIterator last, Function f) { while (first != last) f(*first++); return f; } template InputIterator find(InputIterator first, InputIterator last, const T& value) { while (first != last && *first != value) ++first; return first; } template InputIterator find_if(InputIterator first, InputIterator last, Predicate pred) { while (first != last && !pred(*first)) ++first; return first; } template ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last) { if (first == last) return last; ForwardIterator next = first; while(++next != last) { if (*first == *next) return first; first = next; } return last; } template ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred) { if (first == last) return last; ForwardIterator next = first; while(++next != last) { if (binary_pred(*first, *next)) return first; first = next; } return last; } template void count(InputIterator first, InputIterator last, const T& value, Size& n) { while (first != last) if (*first++ == value) ++n; } template void count_if(InputIterator first, InputIterator last, Predicate pred, Size& n) { while (first != last) if (pred(*first++)) ++n; } template ForwardIterator1 __search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, Distance1*, Distance2*) { Distance1 d1 = 0; distance(first1, last1, d1); Distance2 d2 = 0; distance(first2, last2, d2); if (d1 < d2) return last1; ForwardIterator1 current1 = first1; ForwardIterator2 current2 = first2; while (current2 != last2) if (*current1++ != *current2++) if (d1-- == d2) return last1; else { current1 = ++first1; current2 = first2; } return (current2 == last2) ? first1 : last1; } template inline ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2) { return __search(first1, last1, first2, last2, distance_type(first1), distance_type(first2)); } template ForwardIterator1 __search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred, Distance1*, Distance2*) { Distance1 d1 = 0; distance(first1, last1, d1); Distance2 d2 = 0; distance(first2, last2, d2); if (d1 < d2) return last1; ForwardIterator1 current1 = first1; ForwardIterator2 current2 = first2; while (current2 != last2) if (!binary_pred(*current1++, *current2++)) if (d1-- == d2) return last1; else { current1 = ++first1; current2 = first2; } return (current2 == last2) ? first1 : last1; } template inline ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred) { return __search(first1, last1, first2, last2, binary_pred, distance_type(first1), distance_type(first2)); } template ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2) { while (first1 != last1) iter_swap(first1++, first2++); return first2; } template OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op) { while (first != last) *result++ = op(*first++); return result; } template OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binary_op) { while (first1 != last1) *result++ = binary_op(*first1++, *first2++); return result; } template 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 void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value) { while (first != last) { if (pred(*first)) *first = new_value; ++first; } } template 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 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 void generate(ForwardIterator first, ForwardIterator last, Generator gen) { while (first != last) *first++ = gen(); } template OutputIterator generate_n(OutputIterator first, Size n, Generator gen) { while (n-- > 0) *first++ = gen(); return first; } template OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value) { while (first != last) { if (*first != value) *result++ = *first; ++first; } return result; } template OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred) { while (first != last) { if (!pred(*first)) *result++ = *first; ++first; } return result; } template 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 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 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 inline BidirectionalIterator __unique_copy(InputIterator first, InputIterator last, BidirectionalIterator result, bidirectional_iterator_tag) { return __unique_copy(first, last, result, forward_iterator_tag()); } template inline RandomAccessIterator __unique_copy(InputIterator first, InputIterator last, RandomAccessIterator result, random_access_iterator_tag) { return __unique_copy(first, last, result, forward_iterator_tag()); } template 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 inline OutputIterator __unique_copy(InputIterator first, InputIterator last, OutputIterator result, output_iterator_tag) { return __unique_copy(first, last, result, value_type(first)); } template 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 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 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 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 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 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 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 ForwardIterator unique(ForwardIterator first, ForwardIterator last) { first = adjacent_find(first, last); return unique_copy(first, last, first); } template 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 void __reverse(BidirectionalIterator first, BidirectionalIterator last, bidirectional_iterator_tag) { while (true) if (first == last || first == --last) return; else iter_swap(first++, last); } template void __reverse(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) { while (first < last) iter_swap(first++, --last); } template inline void reverse(BidirectionalIterator first, BidirectionalIterator last) { __reverse(first, last, iterator_category(first)); } template OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result) { while (first != last) *result++ = *--last; return result; } template 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 void __rotate(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Distance*, bidirectional_iterator_tag) { reverse(first, middle); reverse(middle, last); reverse(first, last); } template EuclideanRingElement __gcd(EuclideanRingElement m, EuclideanRingElement n) { while (n != 0) { EuclideanRingElement t = m % n; m = n; n = t; } return m; } template 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 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 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 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 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 inline void random_shuffle(RandomAccessIterator first, RandomAccessIterator last) { __random_shuffle(first, last, distance_type(first)); } template 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 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 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 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 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 ForwardIterator __stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred, Distance len, pair 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 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 inline ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred) { return __stable_partition_aux(first, last, pred, distance_type(first)); } template 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 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 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 inline void __quick_sort_loop(RandomAccessIterator first, RandomAccessIterator last) { __quick_sort_loop_aux(first, last, value_type(first)); } template 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 inline void __quick_sort_loop(RandomAccessIterator first, RandomAccessIterator last, Compare comp) { __quick_sort_loop_aux(first, last, value_type(first), comp); } template void __unguarded_linear_insert(RandomAccessIterator last, T value) { RandomAccessIterator next = last; --next; while (value < *next) { *last = *next; last = next--; } *last = value; } template 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 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 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 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 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 void __unguarded_insertion_sort_aux(RandomAccessIterator first, RandomAccessIterator last, T*) { for (RandomAccessIterator i = first; i != last; ++i) __unguarded_linear_insert(i, T(*i)); } template inline void __unguarded_insertion_sort(RandomAccessIterator first, RandomAccessIterator last) { __unguarded_insertion_sort_aux(first, last, value_type(first)); } template 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 inline void __unguarded_insertion_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp) { __unguarded_insertion_sort_aux(first, last, value_type(first), comp); } template 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 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 void sort(RandomAccessIterator first, RandomAccessIterator last) { __quick_sort_loop(first, last); __final_insertion_sort(first, last); } template void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp) { __quick_sort_loop(first, last, comp); __final_insertion_sort(first, last, comp); } template 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 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 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 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 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 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 void __merge_sort_with_buffer(RandomAccessIterator first, RandomAccessIterator last, Pointer buffer, Distance*, T*) { Distance len = last - first; Pointer buffer_last = buffer + len; Distance step_size = __stl_chunk_size; __chunk_insertion_sort(first, last, step_size); while (step_size < len) { __merge_sort_loop(first, last, buffer, step_size); step_size *= 2; __merge_sort_loop(buffer, buffer_last, first, step_size); step_size *= 2; } } template void __merge_sort_with_buffer(RandomAccessIterator first, RandomAccessIterator last, Pointer buffer, Distance*, T*, Compare comp) { Distance len = last - first; Pointer buffer_last = buffer + len; Distance step_size = __stl_chunk_size; __chunk_insertion_sort(first, last, step_size, comp); while (step_size < len) { __merge_sort_loop(first, last, buffer, step_size, comp); step_size *= 2; __merge_sort_loop(buffer, buffer_last, first, step_size, comp); step_size *= 2; } } template void __stable_sort_adaptive(RandomAccessIterator first, RandomAccessIterator last, Pointer buffer, Distance buffer_size, T*) { Distance len = (last - first + 1) / 2; RandomAccessIterator middle = first + len; if (len > buffer_size) { __stable_sort_adaptive(first, middle, buffer, buffer_size, (T*)0); __stable_sort_adaptive(middle, last, buffer, buffer_size, (T*)0); } else { __merge_sort_with_buffer(first, middle, buffer, (Distance*)0, (T*)0); __merge_sort_with_buffer(middle, last, buffer, (Distance*)0, (T*)0); } __merge_adaptive(first, middle, last, Distance(middle - first), Distance(last - middle), buffer, buffer_size, (T*)0); } template void __stable_sort_adaptive(RandomAccessIterator first, RandomAccessIterator last, Pointer buffer, Distance buffer_size, T*, Compare comp) { Distance len = (last - first + 1) / 2; RandomAccessIterator middle = first + len; if (len > buffer_size) { __stable_sort_adaptive(first, middle, buffer, buffer_size, (T*)0, comp); __stable_sort_adaptive(middle, last, buffer, buffer_size, (T*)0, comp); } else { __merge_sort_with_buffer(first, middle, buffer, (Distance*)0, (T*)0, comp); __merge_sort_with_buffer(middle, last, buffer, (Distance*)0, (T*)0, comp); } __merge_adaptive(first, middle, last, Distance(middle - first), Distance(last - middle), buffer, buffer_size, (T*)0, comp); } template inline void __stable_sort(RandomAccessIterator first, RandomAccessIterator last, pair p, T*) { if (p.first == 0) { __inplace_stable_sort(first, last); return; } Distance len = min(p.second, last - first); copy(first, first + len, raw_storage_iterator(p.first)); __stable_sort_adaptive(first, last, p.first, p.second, (T*)0); destroy(p.first, p.first + len); return_temporary_buffer(p.first); } template inline void __stable_sort(RandomAccessIterator first, RandomAccessIterator last, pair p, T*, Compare comp) { if (p.first == 0) { __inplace_stable_sort(first, last, comp); return; } Distance len = min(p.second, last - first); copy(first, first + len, raw_storage_iterator(p.first)); __stable_sort_adaptive(first, last, p.first, p.second, (T*)0, comp); destroy(p.first, p.first + len); return_temporary_buffer(p.first); } template inline void __stable_sort_aux(RandomAccessIterator first, RandomAccessIterator last, T*, Distance*) { __stable_sort(first, last, get_temporary_buffer(Distance(last - first), (T*)0), (T*)0); } template inline void __stable_sort_aux(RandomAccessIterator first, RandomAccessIterator last, T*, Distance*, Compare comp) { __stable_sort(first, last, get_temporary_buffer(Distance(last - first), (T*)0), (T*)0, comp); } template inline void stable_sort(RandomAccessIterator first, RandomAccessIterator last) { __stable_sort_aux(first, last, value_type(first), distance_type(first)); } template inline void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp) { __stable_sort_aux(first, last, value_type(first), distance_type(first), comp); } template 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 inline void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last) { __partial_sort(first, middle, last, value_type(first)); } template void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, T*, Compare comp) { make_heap(first, middle, comp); for (RandomAccessIterator i = middle; i < last; ++i) if (comp(*i, *first)) __pop_heap(first, middle, i, T(*i), comp, distance_type(first)); sort_heap(first, middle, comp); } template inline void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp) { __partial_sort(first, middle, last, value_type(first), comp); } template 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 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 RandomAccessIterator __partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp, Distance*, T*) { if (result_first == result_last) return result_last; RandomAccessIterator result_real_last = result_first; while(first != last && result_real_last != result_last) *result_real_last++ = *first++; make_heap(result_first, result_real_last, comp); while (first != last) { if (comp(*first, *result_first)) __adjust_heap(result_first, Distance(0), Distance(result_real_last - result_first), T(*first), comp); ++first; } sort_heap(result_first, result_real_last, comp); return result_real_last; } template 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 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 inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last) { __nth_element(first, nth, last, value_type(first)); } template 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 inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp) { __nth_element(first, nth, last, value_type(first), comp); } template 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 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 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 inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value) { return __lower_bound(first, last, value, distance_type(first), iterator_category(first)); } template 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 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 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 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 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 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 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 inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value) { return __upper_bound(first, last, value, distance_type(first), iterator_category(first)); } template 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 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 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 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 pair __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(left, right); } } return pair(first, first); } template inline pair __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 pair __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(left, right); } } return pair(first, first); } template inline pair equal_range(ForwardIterator first, ForwardIterator last, const T& value) { return __equal_range(first, last, value, distance_type(first), iterator_category(first)); } template pair __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(left, right); } } return pair(first, first); } template inline pair __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 pair __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(left, right); } } return pair(first, first); } template inline pair 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 bool binary_search(ForwardIterator first, ForwardIterator last, const T& value) { ForwardIterator i = lower_bound(first, last, value); return i != last && !(value < *i); } template 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 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 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 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 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 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 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 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 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 void __merge_adaptive(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Distance len1, Distance len2, Pointer buffer, Distance buffer_size, T*) { if (len1 <= len2 && len1 <= buffer_size) { Pointer end_buffer = copy(first, middle, buffer); merge(buffer, end_buffer, middle, last, first); } else if (len2 <= buffer_size) { Pointer end_buffer = copy(middle, last, buffer); __merge_backward(first, middle, buffer, end_buffer, last); } else { BidirectionalIterator first_cut = first; BidirectionalIterator second_cut = middle; Distance len11 = 0; Distance len22 = 0; if (len1 > len2) { len11 = len1 / 2; advance(first_cut, len11); second_cut = lower_bound(middle, last, *first_cut); distance(middle, second_cut, len22); } else { len22 = len2 / 2; advance(second_cut, len22); first_cut = upper_bound(first, middle, *second_cut); distance(first, first_cut, len11); } BidirectionalIterator new_middle = __rotate_adaptive(first_cut, middle, second_cut, len1 - len11, len22, buffer, buffer_size); __merge_adaptive(first, first_cut, new_middle, len11, len22, buffer, buffer_size, (T*)0); __merge_adaptive(new_middle, second_cut, last, len1 - len11, len2 - len22, buffer, buffer_size, (T*)0); } } template void __merge_adaptive(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Distance len1, Distance len2, Pointer buffer, Distance buffer_size, T*, Compare comp) { if (len1 <= len2 && len1 <= buffer_size) { Pointer end_buffer = copy(first, middle, buffer); merge(buffer, end_buffer, middle, last, first, comp); } else if (len2 <= buffer_size) { Pointer end_buffer = copy(middle, last, buffer); __merge_backward(first, middle, buffer, end_buffer, last, comp); } else { BidirectionalIterator first_cut = first; BidirectionalIterator second_cut = middle; Distance len11 = 0; Distance len22 = 0; if (len1 > len2) { len11 = len1 / 2; advance(first_cut, len11); second_cut = lower_bound(middle, last, *first_cut, comp); distance(middle, second_cut, len22); } else { len22 = len2 / 2; advance(second_cut, len22); first_cut = upper_bound(first, middle, *second_cut, comp); distance(first, first_cut, len11); } BidirectionalIterator new_middle = __rotate_adaptive(first_cut, middle, second_cut, len1 - len11, len22, buffer, buffer_size); __merge_adaptive(first, first_cut, new_middle, len11, len22, buffer, buffer_size, (T*)0, comp); __merge_adaptive(new_middle, second_cut, last, len1 - len11, len2 - len22, buffer, buffer_size, (T*)0, comp); } } template void __inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Distance len1, Distance len2, pair p, T*) { if (p.first == 0) { __merge_without_buffer(first, middle, last, len1, len2); return; } Distance len = min(p.second, len1 + len2); fill_n(raw_storage_iterator(p.first), len, *first); __merge_adaptive(first, middle, last, len1, len2, p.first, p.second, (T*)0); destroy(p.first, p.first + len); return_temporary_buffer(p.first); } template void __inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Distance len1, Distance len2, pair p, T*, Compare comp) { if (p.first == 0) { __merge_without_buffer(first, middle, last, len1, len2, comp); return; } Distance len = min(p.second, len1 + len2); fill_n(raw_storage_iterator(p.first), len, *first); __merge_adaptive(first, middle, last, len1, len2, p.first, p.second, (T*)0, comp); destroy(p.first, p.first + len); return_temporary_buffer(p.first); } template inline void __inplace_merge_aux(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, T*, Distance*) { Distance len1 = 0; distance(first, middle, len1); Distance len2 = 0; distance(middle, last, len2); __inplace_merge(first, middle, last, len1, len2, get_temporary_buffer(len1 + len2, (T*)0), (T*)0); } template inline void __inplace_merge_aux(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, T*, Distance*, Compare comp) { Distance len1 = 0; distance(first, middle, len1); Distance len2 = 0; distance(middle, last, len2); __inplace_merge(first, middle, last, len1, len2, get_temporary_buffer(len1 + len2, (T*)0), (T*)0, comp); } template inline void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last) { if (first == middle || middle == last) return; __inplace_merge_aux(first, middle, last, value_type(first), distance_type(first)); } template inline void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp) { if (first == middle || middle == last) return; __inplace_merge_aux(first, middle, last, value_type(first), distance_type(first), comp); } template 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 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 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 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 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 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 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 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 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 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 ForwardIterator max_element(ForwardIterator first, ForwardIterator last) { if (first == last) return first; ForwardIterator result = first; while (++first != last) if (*result < *first) result = first; return result; } template ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp) { if (first == last) return first; ForwardIterator result = first; while (++first != last) if (comp(*result, *first)) result = first; return result; } template ForwardIterator min_element(ForwardIterator first, ForwardIterator last) { if (first == last) return first; ForwardIterator result = first; while (++first != last) if (*first < *result) result = first; return result; } template ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp) { if (first == last) return first; ForwardIterator result = first; while (++first != last) if (comp(*first, *result)) result = first; return result; } template 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 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 bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last) { if (first == last) return false; BidirectionalIterator i = first; ++i; if (i == last) return false; i = last; --i; for(;;) { BidirectionalIterator ii = i--; if (*ii < *i) { BidirectionalIterator j = last; while (!(*--j < *i)); iter_swap(i, j); reverse(ii, last); return true; } if (i == first) { reverse(first, last); return false; } } } template bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp) { if (first == last) return false; BidirectionalIterator i = first; ++i; if (i == last) return false; i = last; --i; for(;;) { BidirectionalIterator ii = i--; if (comp(*ii, *i)) { BidirectionalIterator j = last; while (!comp(*--j, *i)); iter_swap(i, j); reverse(ii, last); return true; } if (i == first) { reverse(first, last); return false; } } } template T accumulate(InputIterator first, InputIterator last, T init) { while (first != last) init = init + *first++; return init; } template T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op) { while (first != last) init = binary_op(init, *first++); return init; } template T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init) { while (first1 != last1) init = init + (*first1++ * *first2++); return init; } template 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 OutputIterator __partial_sum(InputIterator first, InputIterator last, OutputIterator result, T*) { T value = *first; while (++first != last) { value = value + *first; *++result = value; } return ++result; } template 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 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 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 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 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 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 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 void iota(ForwardIterator first, ForwardIterator last, T value) { while (first != last) *first++ = value++; } #endif @EOF chmod 664 algo.h echo x - algobase.h cat >algobase.h <<'@EOF' /* * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * */ #ifndef ALGOBASE_H #define ALGOBASE_H #include #include template inline void __iter_swap(ForwardIterator1 a, ForwardIterator2 b, T*) { T tmp = *a; *a = *b; *b = tmp; } template inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b) { __iter_swap(a, b, value_type(a)); } template inline void swap(T& a, T& b) { T tmp = a; a = b; b = tmp; } template inline const T& min(const T& a, const T& b) { return b < a ? b : a; } template inline const T& min(const T& a, const T& b, Compare comp) { return comp(b, a) ? b : a; } template inline const T& max(const T& a, const T& b) { return a < b ? b : a; } template inline const T& max(const T& a, const T& b, Compare comp) { return comp(a, b) ? b : a; } template void __distance(InputIterator first, InputIterator last, Distance& n, input_iterator_tag) { while (first != last) { ++first; ++n; } } template void __distance(ForwardIterator first, ForwardIterator last, Distance& n, forward_iterator_tag) { while (first != last) { ++first; ++n; } } template void __distance(BidirectionalIterator first, BidirectionalIterator last, Distance& n, bidirectional_iterator_tag) { while (first != last) { ++first; ++n; } } template inline void __distance(RandomAccessIterator first, RandomAccessIterator last, Distance& n, random_access_iterator_tag) { n += last - first; } template inline void distance(InputIterator first, InputIterator last, Distance& n) { __distance(first, last, n, iterator_category(first)); } template void __advance(InputIterator& i, Distance n, input_iterator_tag) { while (n--) ++i; } template void __advance(ForwardIterator& i, Distance n, forward_iterator_tag) { while (n--) ++i; } template void __advance(BidirectionalIterator& i, Distance n, bidirectional_iterator_tag) { if (n >= 0) while (n--) ++i; else while (n++) --i; } template inline void __advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag) { i += n; } template inline void advance(InputIterator& i, Distance n) { __advance(i, n, iterator_category(i)); } template void destroy(ForwardIterator first, ForwardIterator last) { while (first != last) { /* Borland bug */ destroy(&*first); ++first; //destroy(&*first++); } } template ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result) { while (first != last) construct(&*result++, *first++); return result; } template void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x) { while (first != last) construct(&*first++, x); } template ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n, const T& x) { while (n--) construct(&*first++, x); return first; } template OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result) { while (first != last) *result++ = *first++; return result; } template BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result) { while (first != last) *--result = *--last; return result; } template void fill(ForwardIterator first, ForwardIterator last, const T& value) { while (first != last) *first++ = value; } template OutputIterator fill_n(OutputIterator first, Size n, const T& value) { while (n-- > 0) *first++ = value; return first; } template pair mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2) { while (first1 != last1 && *first1 == *first2) { ++first1; ++first2; } return pair(first1, first2); } template pair mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred) { while (first1 != last1 && binary_pred(*first1, *first2)) { ++first1; ++first2; } return pair(first1, first2); } template inline bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2) { return mismatch(first1, last1, first2).first == last1; } template inline bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred) { return mismatch(first1, last1, first2, binary_pred).first == last1; } template 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 bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp) { while (first1 != last1 && first2 != last2) { if (comp(*first1, *first2)) return true; if (comp(*first2++, *first1++)) return false; } return first1 == last1 && first2 != last2; } #endif @EOF chmod 644 algobase.h echo x - bool.h cat >bool.h <<'@EOF' /* * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * */ #define bool int #define true 1 #define false 0 @EOF chmod 644 bool.h echo x - bvector.h cat >bvector.h <<'@EOF' /* * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * */ // vector is replaced by bit_vector at present because bool is not // implemented. #ifndef BVECTOR_H #define BVECTOR_H #include #include #include #include #ifndef Allocator #define Allocator allocator #include #endif #define __WORD_BIT (int(CHAR_BIT*sizeof(unsigned int))) class bit_vector { public: typedef Allocator 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 { 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 { 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_reverse_iterator; typedef reverse_iterator reverse_iterator; protected: static Allocator static_allocator; iterator start; iterator finish; unsigned int* end_of_storage; unsigned int* bit_alloc(size_type n) { return static_allocator.allocate((n + __WORD_BIT - 1)/__WORD_BIT); } void initialize(size_type n) { unsigned int* q = bit_alloc(n); end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT; start = iterator(q, 0); finish = start + n; } void insert_aux(iterator position, bool x); typedef bit_vector self; public: iterator begin() { return start; } const_iterator begin() const { return start; } iterator end() { return finish; } const_iterator end() const { return finish; } reverse_iterator rbegin() { return reverse_iterator(end()); } const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } size_type size() const { return size_type(end() - begin()); } size_type max_size() const { return static_allocator.max_size(); } size_type capacity() const { return size_type(const_iterator(end_of_storage, 0) - begin()); } bool empty() const { return begin() == end(); } reference operator[](size_type n) { return *(begin() + n); } const_reference operator[](size_type n) const { return *(begin() + n); } bit_vector() : start(iterator()), finish(iterator()), end_of_storage(0) {} bit_vector(size_type n, bool value = bool()) { initialize(n); fill(start.p, end_of_storage, value ? ~0 : 0); } bit_vector(const self& x) { initialize(x.size()); copy(x.begin(), x.end(), start); } bit_vector(const_iterator first, const_iterator last) { size_type n = 0; distance(first, last, n); initialize(n); copy(first, last, start); } ~bit_vector() { static_allocator.deallocate(start.p); } self& operator=(const self& x) { if (&x == this) return *this; if (x.size() > capacity()) { static_allocator.deallocate(start.p); initialize(x.size()); } copy(x.begin(), x.end(), begin()); finish = begin() + x.size(); return *this; } void reserve(size_type n) { if (capacity() < n) { unsigned int* q = bit_alloc(n); finish = copy(begin(), end(), iterator(q, 0)); static_allocator.deallocate(start.p); start = iterator(q, 0); end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT; } } reference front() { return *begin(); } const_reference front() const { return *begin(); } reference back() { return *(end() - 1); } const_reference back() const { return *(end() - 1); } void push_back(bool x) { if (finish.p != end_of_storage) *finish++ = x; else insert_aux(end(), x); } void swap(bit_vector& x) { ::swap(start, x.start); ::swap(finish, x.finish); ::swap(end_of_storage, x.end_of_storage); } iterator insert(iterator position, bool x) { size_type n = position - begin(); if (finish.p != end_of_storage && position == end()) *finish++ = x; else insert_aux(position, x); return begin() + n; } void insert(iterator position, const_iterator first, const_iterator last); void insert(iterator position, size_type n, bool x); void pop_back() { --finish; } void erase(iterator position) { if (position + 1 != end()) copy(position + 1, end(), position); --finish; } void erase(iterator first, iterator last) { finish = copy(last, end(), first); } }; Allocator bit_vector::static_allocator; inline bool operator==(const bit_vector& x, const bit_vector& y) { return x.size() == y.size() && equal(x.begin(), x.end(), y.begin()); } inline bool operator<(const bit_vector& x, const bit_vector& y) { return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } void swap(bit_vector::reference x, bit_vector::reference y) { bool tmp = x; x = y; y = tmp; } void bit_vector::insert_aux(iterator position, bool x) { if (finish.p != end_of_storage) { copy_backward(position, finish - 1, finish); *position = x; ++finish; } else { size_type len = size() ? 2 * size() : __WORD_BIT; unsigned int* q = bit_alloc(len); iterator i = copy(begin(), position, iterator(q, 0)); *i++ = x; finish = copy(position, end(), i); static_allocator.deallocate(start.p); end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT; start = iterator(q, 0); } } void bit_vector::insert(iterator position, size_type n, bool x) { if (n == 0) return; if (capacity() - size() >= n) { copy_backward(position, end(), finish + n); fill(position, position + n, x); finish += n; } else { size_type len = size() + max(size(), n); unsigned int* q = bit_alloc(len); iterator i = copy(begin(), position, iterator(q, 0)); fill_n(i, n, x); finish = copy(position, end(), i + n); static_allocator.deallocate(start.p); end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT; start = iterator(q, 0); } } void bit_vector::insert(iterator position, const_iterator first, const_iterator last) { if (first == last) return; size_type n = 0; distance(first, last, n); if (capacity() - size() >= n) { copy_backward(position, end(), finish + n); copy(first, last, position); finish += n; } else { size_type len = size() + max(size(), n); unsigned int* q = bit_alloc(len); iterator i = copy(begin(), position, iterator(q, 0)); i = copy(first, last, i); finish = copy(position, end(), i); static_allocator.deallocate(start.p); end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT; start = iterator(q, 0); } } #undef Allocator #undef __WORD_BIT #endif @EOF chmod 644 bvector.h echo x - defalloc.h cat >defalloc.h <<'@EOF' /* * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * */ #ifndef DEFALLOC_H #define DEFALLOC_H #include #include #include #include #include #include inline void* operator new(size_t, void* p) {return p;} /* * 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 inline T* allocate(ptrdiff_t size, T*) { set_new_handler(0); T* tmp = (T*)(::operator new((size_t)(size * sizeof(T)))); if (tmp == 0) { cerr << "out of memory" << endl; exit(1); } return tmp; } */ template 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 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 inline void deallocate(T* buffer) { ::operator delete(buffer); } template 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 inline void construct(T1* p, const T2& value) { new (p) T1(value); } template class allocator { public: typedef T value_type; typedef T* pointer; typedef const T* const_pointer; typedef T& reference; typedef const T& const_reference; typedef size_t size_type; typedef ptrdiff_t difference_type; pointer allocate(size_type n) { return ::allocate((difference_type)n, (pointer)0); } void deallocate(pointer p) { ::deallocate(p); } pointer address(reference x) { return (pointer)&x; } const_pointer const_address(const_reference x) { return (const_pointer)&x; } size_type init_page_size() { return max(size_type(1), size_type(4096/sizeof(T))); } size_type max_size() const { return max(size_type(1), size_type(UINT_MAX/sizeof(T))); } }; class allocator { public: typedef void* pointer; }; #endif @EOF chmod 644 defalloc.h echo x - deque.h cat >deque.h <<'@EOF' /* * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * */ #ifndef DEQUE_H #define DEQUE_H #include #include #include #include #ifndef Allocator #define Allocator allocator #include #endif #ifndef deque #define deque deque #endif template class deque { public: class iterator; class const_iterator; friend class iterator; friend class const_iterator; public: typedef T value_type; typedef Allocator data_allocator_type; typedef Allocator::pointer pointer; typedef Allocator::reference reference; typedef Allocator::const_reference const_reference; typedef Allocator::size_type size_type; typedef Allocator::difference_type difference_type; typedef Allocator map_allocator_type; protected: static data_allocator_type data_allocator; static size_type buffer_size; static map_allocator_type map_allocator; typedef Allocator::pointer map_pointer; public: class iterator : public random_access_iterator { friend class deque; 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 { friend class deque; 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_reverse_iterator; typedef reverse_iterator 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) { 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; if (end().current == end().last) allocate_at_end(); } void push_back(const T& x) { if (empty()) allocate_at_end(); construct(finish.current, x); ++finish.current; ++length; if (end().current == end().last) allocate_at_end(); } void pop_front() { destroy(start.current); ++start.current; --length; if (empty() || begin().current == begin().last) deallocate_at_begin(); } void pop_back() { if (end().current == end().first) deallocate_at_end(); --finish.current; destroy(finish.current); --length; if (empty()) deallocate_at_end(); } void swap(deque& x) { ::swap(start, x.start); ::swap(finish, x.finish); ::swap(length, x.length); ::swap(map, x.map); ::swap(map_size, x.map_size); } iterator insert(iterator position, const T& x); void insert(iterator position, size_type n, const T& x); // template 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) { buffer_size = data_allocator.init_page_size(); insert(begin(), n, value); } // template deque(Iterator first, Iterator last); deque(const T* first, const T* last) : start(), finish(), length(0), map(0), map_size(0) { buffer_size = data_allocator.init_page_size(); copy(first, last, back_inserter(*this)); } deque(const deque& x) : start(), finish(), length(0), map(0), map_size(0) { buffer_size = data_allocator.init_page_size(); copy(x.begin(), x.end(), back_inserter(*this)); } deque& operator=(const deque& 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 deque::data_allocator_type deque::data_allocator; template deque::map_allocator_type deque::map_allocator; template deque::size_type deque::buffer_size = 0; // should be data_allocator.init_page_size(); // Borland bug template bool operator==(const deque& x, const deque& y) { return x.size() == y.size() && equal(x.begin(), x.end(), y.begin()); } template bool operator<(const deque& x, const deque& y) { return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } template deque::~deque() { while (!empty()) pop_front(); } template void deque::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 void deque::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 void deque::deallocate_at_begin() { data_allocator.deallocate(*start.node++); if (empty()) { if (finish.current == finish.first) data_allocator.deallocate(*start.node); start = iterator(); finish = start; map_allocator.deallocate(map); } else start = iterator(*start.node, start.node); } template void deque::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 deque::iterator deque::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 { difference_type index = position - begin(); if (index < length) { push_front(*begin()); copy(begin() + 2, begin() + index + 1, begin() + 1); } else { push_back(*(end() - 1)); copy_backward(begin() + index, end() - 2, end() - 1); } *(begin() + index) = x; return begin() + index; } } template void deque::insert(iterator position, size_type n, const T& x) { difference_type index = position - begin(); difference_type remainder = length - index; if (remainder > index) { if (n > index) { difference_type m = n - index; while (m-- > 0) push_front(x); difference_type i = index; while (i--) push_front(*(begin() + n - 1)); fill(begin() + n, begin() + n + index, x); } else { difference_type i = n; while (i--) push_front(*(begin() + n - 1)); copy(begin() + n + n, begin() + n + index, begin() + n); fill(begin() + index, begin() + n + index, x); } } else { difference_type orig_len = index + remainder; if (n > remainder) { difference_type m = n - remainder; while (m-- > 0) push_back(x); difference_type i = 0; while (i < remainder) push_back(*(begin() + index + i++)); fill(begin() + index, begin() + orig_len, x); } else { difference_type i = 0; while (i < n) push_back(*(begin() + orig_len - n + i++)); copy_backward(begin() + index, begin() + orig_len - n, begin() + orig_len); fill(begin() + index, begin() + index + n, x); } } } template void deque::insert(iterator position, const T* first, const T* last) { difference_type index = position - begin(); difference_type remainder = length - index; size_type n = 0; distance(first, last, n); if (remainder > index) { if (n > index) { const T* m = last - index; while (m != first) push_front(*--m); difference_type i = index; while (i--) push_front(*(begin() + n - 1)); copy(last - index, last, begin() + n); } else { difference_type i = n; while (i--) push_front(*(begin() + n - 1)); copy(begin() + n + n, begin() + n + index, begin() + n); copy(first, last, begin() + index); } } else { difference_type orig_len = index + remainder; if (n > remainder) { const T* m = first + remainder; while (m != last) push_back(*m++); difference_type i = 0; while (i < remainder) push_back(*(begin() + index + i++)); copy(first, first + remainder, begin() + index); } else { difference_type i = 0; while (i < n) push_back(*(begin() + orig_len - n + i++)); copy_backward(begin() + index, begin() + orig_len - n, begin() + orig_len); copy(first, last, begin() + index); } } } template void deque::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 void deque::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 #endif @EOF chmod 644 deque.h echo x - doc.mif cat >doc.mif <<'@EOF' # Generated by FrameMaker xm4.0.1P1m # Options: # Paragraph Text # Paragraph Tags # Paragraph Formats # Font Information # Markers # Anchored Frames # Tables # Graphics and TextRect Layout # Master Page Items # Condition Catalog # Table Catalogs # Font Catalog # Paragraph Catalog # Document Template # Document Dictionary # Variables # Element Definitions # Elements # > # end of Color > # end of Color > # end of Color > # end of Color > # end of Color > # end of Color > # end of Color > # end of Color > # end of ColorCatalog > # end of Condition > # end of ConditionCatalog > # end of PgfFont > # end of Pgf > # end of PgfFont > # end of Pgf > # end of PgfFont > # end of Pgf > # end of PgfFont > # end of TabStop > # end of Pgf > # end of PgfFont > # end of TabStop > # end of Pgf > # end of PgfFont > # end of Pgf > # end of PgfFont > # end of Pgf > # end of PgfFont > # end of Pgf > # end of PgfFont > # end of Pgf > # end of PgfFont > # end of Pgf > # end of PgfFont \\t'> > # end of TabStop > # end of TabStop > # end of Pgf > # end of PgfFont > # end of Pgf > # end of PgfFont > # end of TabStop > # end of Pgf > # end of PgfFont > # end of TabStop > # end of Pgf > # end of PgfFont .\\t'> > # end of TabStop > # end of TabStop > # end of Pgf > # end of PgfFont .\\t'> > # end of TabStop > # end of TabStop > # end of Pgf > # end of PgfFont > # end of Pgf > # end of PgfFont > # end of TabStop > # end of TabStop > # end of TabStop > # end of TabStop > # end of TabStop > # end of TabStop > # end of TabStop > # end of TabStop > # end of TabStop > # end of TabStop > # end of TabStop > # end of Pgf > # end of PgfFont > # end of Pgf > # end of PgfFont '> > # end of TabStop > # end of Pgf > # end of PgfFont > # end of TabStop > # end of Pgf > # end of PgfFont > # end of Pgf > # end of PgfFont .<+\> '> > # end of Pgf > # end of PgfFont > # end of TabStop > # end of Pgf > # end of PgfFont > # end of Pgf > # end of PgfFont .<#\>.<+\> '> > # end of Pgf > # end of PgfFont > # end of TabStop > # end of Pgf > # end of PgfFont > # end of TabStop > # end of Pgf > # end of PgfFont > # end of TabStop > # end of Pgf > # end of PgfCatalog # end of ElementDefCatalog > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > # end of FontCatalog > # end of Ruling > # end of Ruling > # end of Ruling > # end of Ruling > # end of Ruling > # end of RulingCatalog > # end of PgfFont > # end of Pgf > # end of TblColumnH > # end of TblColumnBody > # end of PgfFont > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of TblColumnBody > # end of PgfFont > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of TblColumnBody > # end of PgfFont > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of TblColumnBody > # end of PgfFont > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of TblColumnBody > # end of PgfFont > # end of Pgf > # end of TblColumnF > # end of TblColumn > # end of PgfFont : '> > # end of Pgf > # end of TblTitlePgf1 > # end of TblFormat > # end of PgfFont > # end of Pgf > # end of TblColumnH > # end of TblColumnBody > # end of PgfFont > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of TblColumnBody > # end of PgfFont > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of TblColumnBody > # end of PgfFont > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of TblColumnBody > # end of PgfFont > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of TblColumnBody > # end of PgfFont > # end of Pgf > # end of TblColumnF > # end of TblColumn > # end of PgfFont : '> > # end of Pgf > # end of TblTitlePgf1 > # end of TblFormat > # end of TblCatalog > # end of View > # end of View > # end of View > # end of View > # end of View > # end of View > # end of Views <$daynum\>, <$year\>'> > # end of VariableFormat '> > # end of VariableFormat '> > # end of VariableFormat '> > # end of VariableFormat '> > # end of VariableFormat <$daynum\>, <$year\>'> > # end of VariableFormat <$daynum\>, <$year\> <$hour\>:<$minute00\> <$ampm\>'> > # end of VariableFormat /<$daynum\>/<$shortyear\>'> > # end of VariableFormat <$daynum\>, <$year\>'> > # end of VariableFormat /<$daynum\>/<$shortyear\>'> > # end of VariableFormat '> > # end of VariableFormat '> > # end of VariableFormat '> > # end of VariableFormat '> > # end of VariableFormat > # end of VariableFormat of <$tblsheetcount\>)'> > # end of VariableFormat > # end of VariableFormats (<$paratext\>)'> > # end of XRefFormat '> > # end of XRefFormat on page <$pagenum\>'> > # end of XRefFormat on page <$pagenum\>'> > # end of XRefFormat '> > # end of XRefFormat > # end of XRefFormats > # end of Document tmpLOT.doc'> > # end of BookComponent tmpLOF.doc'> > # end of BookComponent tmpTOC.doc'> > # end of BookComponent # end of InitialAutoNums '> (i'> > # end of Dictionary > # end of DashedPattern > # end of TextRect > # end of Frame > # end of DashedPattern > # end of TextRect > # end of ArrowStyle > # end of PolyLine > # end of PolyLine > # end of PolyLine > # end of PolyLine > # end of Group > # end of Frame > # end of DashedPattern > # end of Rectangle > # end of TextRect > # end of Frame > # end of AFrames > # end of PgfFont > # end of Pgf > # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn > # end of TblFormat # end of Notes > # end of PgfFont : '> > # end of Pgf > # end of Font > > # end of Para > # end of TblTitleContent # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > > # end of Para > # end of CellContent > # end of Cell > # end of Row > # end of TblH # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > # end of Font > # end of Font > > # end of Para > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > > # end of Para > # end of Font > # end of Font > > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > > # end of Para > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > > # end of Para > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Para > # end of CellContent > # end of Cell > # end of Row > # end of TblBody > # end of Tbl > # end of PgfFont > # end of Pgf > # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn > # end of TblFormat # end of Notes > # end of PgfFont : '> > # end of Pgf > > # end of Para > # end of TblTitleContent # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > > # end of Para > # end of CellContent > # end of Cell > # end of Row > # end of TblH # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > # end of Font > # end of Font > > # end of Para > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Para > # end of CellContent > # end of Cell > # end of Row > # end of TblBody > # end of Tbl > # end of PgfFont > # end of Pgf > # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn > # end of TblFormat # end of Notes > # end of PgfFont : '> > # end of Pgf > > # end of Para > # end of TblTitleContent # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > > # end of Para > # end of CellContent > # end of Cell > # end of Row > # end of TblH # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > # end of Font > # end of Font > > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > > # end of Font > # end of Font > # end of Font > > # end of Para > # end of Font > # end of Font > > # end of Font > > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > # end of Font > # end of Font > > # end of Font > # end of Font > > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Font > # end of Font > > # end of Font > # end of Font > # end of Font > # end of Font > > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > > # end of Para > # end of CellContent > # end of Cell > # end of Row > # end of TblBody > # end of Tbl > # end of PgfFont > # end of Pgf > # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn > # end of TblFormat # end of Notes > # end of PgfFont : '> > # end of Pgf > > # end of Para > # end of TblTitleContent # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > > # end of Para > # end of CellContent > # end of Cell > # end of Row > # end of TblH # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > # end of Font > > # end of Para > # end of Font > # end of Font > > # end of Para > # end of Font > # end of Font > > # end of Para > # end of Font > # end of Font > # end of Font > # end of Font > > # end of Para > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of PgfFont > # end of Pgf > > # end of Para > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Para > # end of CellContent > # end of Cell > # end of Row > # end of TblBody > # end of Tbl > # end of PgfFont > # end of Pgf > # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn > # end of TblFormat # end of Notes > # end of PgfFont : '> > # end of Pgf > > # end of Para > # end of TblTitleContent # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > > # end of Para > # end of CellContent > # end of Cell > # end of Row > # end of TblH # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of PgfFont > # end of Pgf > # end of Font = 0)'> > > # end of Para > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of PgfFont > # end of Pgf > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > # end of Font > # end of Font > > # end of Font > # end of Font > > # end of Para > # end of PgfFont > # end of Pgf > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf 0'> > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf b'> > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font '> > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf = b'> > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf b)'> > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Para > # end of CellContent > # end of Cell > # end of Row > # end of TblBody > # end of Tbl > # end of PgfFont > # end of Pgf > # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn > # end of TblFormat # end of Notes > # end of PgfFont : '> > # end of Pgf > > # end of Para > # end of TblTitleContent # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > # end of CellContent > # end of Cell # end of Notes > > # end of Para > # end of CellContent > # end of Cell > # end of Row > # end of TblH # end of Notes > # end of PgfFont > # end of Pgf > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of Font > # end of Font > > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes > # end of Font > # end of Font > # end of Font > # end of Font > # end of Font > > # end of Para > # end of CellContent > # end of Cell > # end of Row # end of Notes > # end of PgfFont > # end of Pgf > # end of Font > > # end of Para > # end of CellContent > # end of Cell # end of Notes ã7> ãFColor `Black'> > # end of Pgf # end of Notes gfFont # end of CellContent > # endt # end of Pgf ng `a.erase(egin()) end of Cell 39403> > ng ` > # end # end of CellContent > # end of Cell > .0"> 40Font # end of Para f Cell # end of Notes > # end of PgfFont > # end of Pgf ng ` > > # end f Cell Underlining FNoUnderlining > > ã end of PgfFont > # end of Pgf # end of Notes > # end of Font # end of Font > # end of Para > # end of CellContent > # enend of Row # end of Notes > #ine # end of Cell > end of PgfFont > # end of Pgf > > # end of Para ine # end of Font > > # end of CellContent > # enl Script No > > #end of Pgf # end of Row > # end of TblBody > # end of Tbl > # end of PgfFont > # end of Pgf > # end of TblColumnH '> > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH < > > > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH < > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end > # end of TblColumnF > # end of TblColumn # end of TblColumnH < > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end f Pgf > # end of TblColumnF > # end of TblColumn > # end of TblFormat # end of Notes r'> > # end of PgfFont : '> > # end of Pgf > > # end of Para > # end of TblTitleContent # end of Notes r'> ubleUnderline No > ãFColor `Black'> > end of PgfFont ParaLine > > # end Para l > > # end Para > # ent > # end of Cell end of Notes 5315> > ent > # end of Cell > # end of TblH ourier'> o > > # end of PgfFont > # end of Pgf > > # end of Para f Cell ara # end of Pgf > # end of Para l l '> > > > # end of Para f Cell > # end of Row geBar No > > > end of PgfFont > # end of Pgf end of Notes > # end of Para # end of CellContent > # enl Notes > # end of Notes > # end of Para # end of CellContent > > # end of Para # end of CellContent > # enf Cell > # end of Row t 0.44444"> # end of Notes ourier'> > < > # end of PgfFont > # endtring `X::const_refe'> > f Cell ine > > # end of Para # # end of Notes rline No > FPosition FNormal > > # end of PgfFont > # endn Para > # ent > # end of Cell nd of Notes 5350> > # end of Cell > # end of Roow Font ãFf PgfFont > # end of Pgf > > # end of Para #ent > # end of Cell ta > Tg `program'> > # end Para > # ent > # end of Cell > # end of Para # end of CellContent ># end of Cell > > > # end of Para ## end of Cell # end of Notes > # ent > # end of Cell > # end of Row # end of Conditional ourier'> > end of PgfFont > # end of Pgf > > # end # end of CellContent ># end of Cell # end of Notes > # end # end of CellContent > # enf Cell nd of Notes > > > # end of Para > # end of CellContent ># end of Cell # end of Notes > # end of Row # end of Notes Font FCase FAsType > <DX 0.0 pt> atlor `Black'> > end of PgfFont > # end of Pgf > > # end of Notes '> > # end of Para > # end of CellContent > # enf Cell nd of Notes 5368ine `tor category except output itera'> > # end of Notes > # enend of Row # end of Notes g on FNormal > > e`X:'> > '> <pt> # end of Pgf > # end of Para #ent > # end of Cell ine > > # end of Font ParaLine # enf Cell > ow FFSupScript No > n> > #earaLine ubleUnderline No > < ãFf PgfFont > # end of Notes ine > > # end Para f Cell Notes > # end of Notes ourier'> No > > > # end of PgfFont > # endf Pgf > # end of Para #ent > # end of Cell nd of Notes > ng ` can represent any '> > > # end of Notes ParaLine > # end Para > # enf Cell > # end of Row t 0.27778"> Notes > # end of Notes No > > e > # end of Pgf > # end of CellContent ># end of Cell # end of Notes > # end Para > # end of CellContent ># end of Cell # end of Notes f Cell t end of Notes > > # end of Para > # ent Notes > # end of Notes # end of Row t 0.2 Notes > # end of Notes F Script No > ãFlor `Black'> > eng `X( > # end of Para f Cell Notes > # end of Notes g`'> > #ed of Pgf ## end of Cell # end of Notes of CellCf Cell l nd of Notes 5431> # end of Row # end of Notes '> ãFlor `Black'> > eParaLine > e > # end of Pgf > # end of Para #ent > # end of Cell > # end of Para > # eent > # end of Cell Notes > # end of Notes Fo FSupScript No > < > # e > # end of Pgf # end of Cell l '> ow >o Tg `program > > # end of Para gFont icUnderline No Fse FAsTyped > ãFf PgfFont ># end of Pgf # end of Font > # end of Para # end of CellContent > # enf Cell < nd of Notes > end of PgfFont > # end of Font nd of Notes > > # end of Para > # end of CellContent ># end of Cell '> # end of Notes ght `Regular'> FCase FAsType > FNormal > <bScript No > > eParaLine '> > > # end of Para > ## end of Cell # end of Notes '> <bScript No > > end of PgfFont > # end of Pgf of CellCof Cell l nd of Notes '> tring `post: `program'> > # end of ngsize() == 0 entring `.'> > > # end of Para ine > > > > # end ## end of Cell # end of Notes ine end of Ro ãFlor `Black'> > e > # end of Pgf nd of Notes < > tring `const_iterator FTag `'> > # end of Font ng `constant > # end of Font > end of PgfFont ># end of Pgf # end of CellContent ># end of Cell # end of Notes #ent tent ine # end of Cell > # end of Row < Fse FAsTyped > <DX > eod of Pgf > ng `const_iterator ` `nt FTag `programn # end of Cell l '> ãFlor `Black'> > end of PgfFont > # end of Pgf #ent > # end of Cell # end of Notes 54 > # end of Para #ent # end of Notes > > # end of Para # end of CellContent > # enf Cell > # end of Row # end of Notes 550CellBody'> > e > # end of Pgf # end of Font # end of Notes # end of Font Para > # end of CellContent > # end of Cell ãFf PgfFont > # end of Pgf > `b.size() && '> > > ParaLine > # end of Notes < > > # end > > > # end Para # end of CellContent > # enf Cell Notes > # end of Notes '> ng `linearof CellCent > # end of Cell > ow Notes > # end of Notes '> > #ed # end of Font # end of Notes 5520>ine # end of Cell Notes > # end of Notes Fosition FNormal > > eof Pgf > # end of Font # end of Para > ## end of Cell # end of Notes > # end of Para # end of CellContent ># endl Notes > # end of Notes ine inearof CellCent > # end of Cell > ow # end of Notes 5528> F FPosition FNormal > pt> > end of PgfFont >#ine # end of Notes Para > # end of CellContent > # end l # end of Notes '> pt> > # e > # end of Pgf # end of Font Fse FAsTyped > < ãFlor `Black'> > ef PgfFont > # end of Pgf X::~X(;'> > > # end of Para Fo Normal > > # e > # end of Pgf '> bScript No > > # end of PgfFont > # end of Pgf > > # end Para > # ent > # end of Cell <l # end of CellContent > # endof Cell > # end of Row Notes > # end of Notes FSupScript No > <DX pt> > e > # end of Pgf # end of Notes > > e > # end of Pgf # end of Notes 5545> '> ourier'> Fse FAsTyped > < > # e > # end of Pgf <`'> '> Fse FAsTyped > <DX 0.0 pt> > # end of PgfFont >#end of Pgf gtline No > FSupScript No > < > end of PgfFont > > ParaLine > > # end of Para '> FSupScript No > > ef PgfFont > # end of Pgf > # end of Para #ent > # end of Cell <l Notes > # end of Notes end of Roow Notes > # end of Notes 5551> <gfFont r'> ub ãFlor `Black'> > ef PgfFont > # end of Pgf > ef PgfFont ># end of Pgf # end of Notes '> FSubS.0pt> > # e > > > # end of Para > #ent ine > end of Font > `ontainer.'> > > # end Para > # ent > # end of Cell t > > # end of Para > # ent > # end of Cell > ow t Notes > # end of Notes '> > ãFlor `Black'> > e > # end of Pgf # end of Font # end of Para > # ent # end of Cell # end of Notes '> Para f Cell l '> <pt> > # end of PgfFont > # end of Pgf > # end of Font > # end of Para # end of CellContent ># endl # end of Notes '> end of Roow <g`'> FUnderline No > > ef PgfFont > # end of Pgf > # end of Font '> Fosition FNormal > FSuScript No > ãFlor `Black'> > e > # end of Pgf > # end of Font # end of Font > > # end Para > # end of CellContent > # endl Notes > # end of Notes # end of Font > > > > > # end of Font > ng ` is defined for values of '> > # end of Font <raLine > # end of Font > > ParaLine ng `linear Para f Cell > # end of Row t .27778"> ubleUnderline No > > # eo b'of CellCent # end of Cell # end of Notes <bScript No > > ef PgfFont >#ine `program'> > # end ofString `bool'> > > # end Para > # ent > # end of Cell Notes > # end of Notes # end of Font > > # end of Para ## endl # end of Notes > # end of Para #ent > # end of Cell t nd of Notes > # end Para > # end of CellContent > # end f Cell > xHeight 1wHeight 0.27778"> ub line No > > ef PgfFont >#ine # enf Cell '> Fosition FNormal > > # e > # end of Pgf > # end of Font # endf Cell l # end of Notes > # end of Font b > # end of Para > # end of CellContent ># endf Cell l Notes > # end of Notes > # end of Para > # ent > # end of Notes > # end Para > # end of CellContent > # endof Cell > end of Ro '> FosiFSuScript No > ãFlor `Black'> > e > # end of Pgf # end of Font = b'> > > # end of Para > ## endl # end of Notes > # end of g `bool'> > > # end Para > # ent > # end of Cell l # end of Notes '> FUnderline No > > eoPara # end of Para > # eent > # end of Cell > # end of Para #ent > # end of Cell l # end of Notes ng `linear endf Cell > end of Row # end of Notes <bScript No > > eo > # end of Pgf # end of Para > #ent # end of Cell <DX 0.0 pt> > ef PgfFont > # end of Pgf > # end Para > # enof CellCf Cell l # end of Notes No > > ef PgfFont > # end of Pgf Para ## endf Cell l Notes > # end of Notes > # end of Para #of CellCf Cell l Notes > # end of Notes <raLine end of Row > # end of TblBody > # end of Tbl < > > > # end of PgfFont > # end of Pgf > # end of TblColumnH <SubScript No > > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH '> > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH a'> > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn > # end of TblFormat # end of Notes '> < > # end of PgfFont : '> > # end of Pgf > > # end of Para > # end of TblTitleContent # end of Notes r'> No > < > # end of PgfFont > # end of Pgf > #ent # end of Notes Para > > # end of Para > #ent >end of Ro> # end of TblH '> > e ># end of Pgf # end of Para icUnderline No > ãFlor `Black'> > e > # end of Pgf <pt> ãFlor `Black'> > # ef PgfFont > # end of Pgf > # end of Para #of CellCent > # end of Cell t Notes > # end of Notes > # end ofng`size() == n' FTg ` Para # end of Font > # end of Font Tg `program'> > # end of nt > # end of Font # end of Row > # ef PgfFont > # end of Para FUUnderline No > o FNormal > bS.0pt> > # ef PgfFont >#end of Pgf > > # end of Para > # ent teaa 503> gtlineNo > <DX0 ptatn> > ef PgfFont ># end of Pgf > # end of Para > # ent # end of Font # end of Font `program'> > # end ofString `j enng`.'> > > # end Para <506> > # end of Font xHeight 1.0"> FUUnderline No > > # eo > # end of Pgf > ef PgfFont >#ine `program'> > # end of Font # end of Font # end of Font ine > > # end Para > # end of CellContent > # end of Cell > ow ght 14.0"> # end of Notes <f FUnderline No > ãFlor `Black'> > # ef PgfFont > insert(p, n, > > # end Para f Cell l Notes > # end of Notes tring `result is not used'of CellCent # end of Cell # end of Notes > # end of Font > # end of Font # end of Font `n <pt> > # end of PgfFont ># end of Pgf > # end of ng `[i, j)'> > # end of Font > # end ofng`p'>Tg ` end of Row Notes > # end of Notes > # e > # end of Para > # end of CellContent ># endf Cell l Notes > # end of Notes '> ng `q enng `.'> > > # end Para > # end of CellContent > # endof Cell > # end of Row FSubSipt No > > eo > # end of Pgf ng `result is not used endf Cell l end of Font end of Row > # end of TblBody > # end of Tbl # end of Notes '> <oUnderlining > > # end of PgfFont : '> > # end of Pgf > > # end of Para > # end of TblTitleContent # end of Notes '> > # end of Pgf tring `Random access endf Cell l Notes > # end of Pgf > # end Para > # end of Pgf > # end of Para #of CellCoent > # end of Cell '> raLine > # end of Pgf > # end Para > # end of Pgf of CellCf Cell l > Notes a > # end of Pgf > # end of Para ># end of Pgf > # end of Para > ## endf Cell l # end of Notes > # end of Pgf '> > > > # end of Para > # end of Pgf end of Row > # end of TblBody > # end of Tbl <Outline No > FCase FAsType >Normal > <SubScript No > > # end of PgfFont > # end of Pgf > # end of TblColumnH '> <Outline No > > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH <SubScript No > > # e > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH r'> <Outline No > > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end f Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH <Outline No > F <SubScript No > > # end of PgfFont > # end > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn # end of TblColumnH <Outline No > > # end of PgfFont > # end of Pgf > # end of TblColumnBody > # end of Pgf > # end of TblColumnF > # end of TblColumn > # end of TblFormat # end of Notes <Outline No > Normal > < > # end of PgfFont : '> > # end of Pgf > > # end of Para > # end of TblTitleContent 10.0 pt> > <bScript No > ãFlor `Black'> > # e Paraine > of CellContent ># end of Cell Para #ent > end of Cell > > # end Para > > # end of Para #ent # end of Cell > end of Ro> # end of TblH '> FSupScript No > <bScript No > > ef PgfFont ># end of Pgf > # end of Para #ent > end of Cell of CellContent ># end of Cell end of Font > end of Font > > # end of Para end of Ro gFont '> bSipt No > ãFlor `Black'> > # end of PgfFont > # endf Pgf > # end of Font # end of Notes FSupScript No > <bSpt> > # ef PgfFont >#end of Pgf > # end of Para #of CellCf Cell l # end of Notes > # end of Para > #ent > end of Cell # end of Notes end of Font # end of Font > > # end Para > # end of CellContent > # end f Cell > # end of Row # end of Notes No > > # ef PgfFont >#end of Pgf # end of Font Para #ent # end of Cell Font nderlining > > # ef PgfFont >#earaLine > of CellContent > # end of Cell > # end of Para ## endf Cell l Notes a FUnderline No > o FSuScript No > > # ef PgfFont > # end of Font > > # end Para f Cell > # end of Row Notes > # end of Notes FUUnderline No > gtlineNo FSupScript No > <pt> > # ef PgfFont >#ear > # end of Font r'> FSupScript No > > ef PgfFont >#ed of Pgf nd of Notes # end of Cell <f > # e > # end of Font > > # end Para > # end of CellContent > # endof Cell > ow # end of Notes <bS.0pt> > ef PgfFont >#ear > > # end of Para > ## endf Cell <l Notes Tg `program'> > # end ofg `bool'> > > # end #ent # end of Cell # end of Notes <oline No > Normal > > #ed > # end of Para #of CellContent ># end of Cell ` > # end of Font ow # end of Notes No > <bScript No > > # eo > # end of Pgf > > # end of Para #of CellCoent > # end of Cell l Notes > # end of Notes > # end of Fong `bool'> > > # end # end of CellContent ># endf Cell <l > # ef Pgfend of Pgf # end of Font # end #ent > end of Cell of CellContent > # enend of Ro gtlineNo Nern No > FSupScript No > <bScript No > > # ef PgfFont >#ineTg `program'> > # end ofg `r = a'> > > # end of Para #ent # endl # end of Notes <bSipt No > > end of PgfFont >#earine > #ent # end of Font end of Row > # end of PgfFont > # endf Pgf # end of Font #of CellCent > # end of Cell > #edf Pgf > # end of Para #of CellCent > # end of Cell nd of Notes # end of Font > > # end of Para > # end ofnt > > # end Para f Cell > ow '> > FSupScript No > > # ef PgfFont >#ed of Pgf # end of Font # end of Notes