Import from my private repository. Snapshot after version 5.16, immediately
[external/ragel.git] / aapl / mergesort.h
1 /*
2  *  Copyright 2001, 2002 Adrian Thurston <thurston@cs.queensu.ca>
3  */
4
5 /*  This file is part of Aapl.
6  *
7  *  Aapl is free software; you can redistribute it and/or modify it under the
8  *  terms of the GNU Lesser General Public License as published by the Free
9  *  Software Foundation; either version 2.1 of the License, or (at your option)
10  *  any later version.
11  *
12  *  Aapl is distributed in the hope that it will be useful, but WITHOUT ANY
13  *  WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
14  *  FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for
15  *  more details.
16  *
17  *  You should have received a copy of the GNU Lesser General Public License
18  *  along with Aapl; if not, write to the Free Software Foundation, Inc., 59
19  *  Temple Place, Suite 330, Boston, MA 02111-1307 USA
20  */
21
22 #ifndef _AAPL_MERGESORT_H
23 #define _AAPL_MERGESORT_H
24
25 #include "bubblesort.h"
26
27 #ifdef AAPL_NAMESPACE
28 namespace Aapl {
29 #endif
30
31 /**
32  * \addtogroup sort 
33  * @{
34  */
35
36 /** 
37  * \class MergeSort
38  * \brief Merge sort an array of data.
39  *
40  * MergeSort can be used to sort any array of objects of type T provided a
41  * compare class is given. MergeSort is not in-place, it requires temporary
42  * storage equal to the size of the array. The temporary storage is allocated
43  * on the heap.
44  *
45  * Objects are not made aware that they are being moved around in memory.
46  * Assignment operators, constructors and destructors are never invoked by the
47  * sort. 
48  *
49  * MergeSort runs in worst case O(n*log(n)) time. In most cases it is slower
50  * than QuickSort because more copying is neccessary. But on the other hand,
51  * it is a stable sort, meaning that objects with the same key have their
52  * relative ordering preserved. Also, its worst case is better. MergeSort
53  * switches to a BubbleSort when the size of the array being sorted is small.
54  * This happens when directly sorting a small array or when MergeSort calls
55  * itself recursively on a small portion of a larger array.
56  */
57
58 /*@}*/
59
60
61 /* MergeSort. */
62 template <class T, class Compare> class MergeSort 
63                 : public BubbleSort<T, Compare>
64 {
65 public:
66         /* Sorting interface routine. */
67         void sort(T *data, long len);
68
69 private:
70         /* Recursive worker. */
71         void doSort(T *tmpStor, T *data, long len);
72 };
73
74 #define _MS_BUBBLE_THRESH 16
75
76 /* Recursive mergesort worker. Split data, make recursive calls, merge
77  * results. */
78 template< class T, class Compare> void MergeSort<T,Compare>::
79                 doSort(T *tmpStor, T *data, long len)
80 {
81         if ( len <= 1 )
82                 return;
83
84         if ( len <= _MS_BUBBLE_THRESH ) {
85                 BubbleSort<T, Compare>::sort( data, len );
86                 return;
87         }
88
89         long mid = len / 2;
90
91         doSort( tmpStor, data, mid );
92         doSort( tmpStor + mid, data + mid, len - mid );
93         
94         /* Merge the data. */
95         T *endLower = data + mid, *lower = data;
96         T *endUpper = data + len, *upper = data + mid;
97         T *dest = tmpStor;
98         while ( true ) {
99                 if ( lower == endLower ) {
100                         /* Possibly upper left. */
101                         if ( upper != endUpper )
102                                 memcpy( dest, upper, (endUpper - upper) * sizeof(T) );
103                         break;
104                 }
105                 else if ( upper == endUpper ) {
106                         /* Only lower left. */
107                         if ( lower != endLower )
108                                 memcpy( dest, lower, (endLower - lower) * sizeof(T) );
109                         break;
110                 }
111                 else {
112                         /* Both upper and lower left. */
113                         if ( compare(*lower, *upper) <= 0 )
114                                 memcpy( dest++, lower++, sizeof(T) );
115                         else
116                                 memcpy( dest++, upper++, sizeof(T) );
117                 }
118         }
119
120         /* Copy back from the tmpStor array. */
121         memcpy( data, tmpStor, sizeof( T ) * len );
122 }
123
124 /**
125  * \brief Merge sort an array of data.
126  */
127 template< class T, class Compare> 
128         void MergeSort<T,Compare>::sort(T *data, long len)
129 {
130         /* Allocate the tmp space needed by merge sort, sort and free. */
131         T *tmpStor = (T*) new char[sizeof(T) * len];
132         doSort( tmpStor, data, len );
133         delete[] (char*) tmpStor;
134 }
135
136 #ifdef AAPL_NAMESPACE
137 }
138 #endif
139
140 #endif /* _AAPL_MERGESORT_H */