Lucene.Net  3.0.3
Lucene.Net is a port of the Lucene search engine library, written in C# and targeted at .NET runtime users.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Properties Pages
SorterTemplate.cs
Go to the documentation of this file.
1 /*
2  * Licensed to the Apache Software Foundation (ASF) under one or more
3  * contributor license agreements. See the NOTICE file distributed with
4  * this work for additional information regarding copyright ownership.
5  * The ASF licenses this file to You under the Apache License, Version 2.0
6  * (the "License"); you may not use this file except in compliance with
7  * the License. You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17 
18 using System;
19 
20 namespace Lucene.Net.Util
21 {
22 
23  /// <summary> Borrowed from Cglib. Allows custom swap so that two arrays can be sorted
24  /// at the same time.
25  /// </summary>
26  public abstract class SorterTemplate
27  {
28  private const int MERGESORT_THRESHOLD = 12;
29  private const int QUICKSORT_THRESHOLD = 7;
30 
31  abstract protected internal void Swap(int i, int j);
32  abstract protected internal int Compare(int i, int j);
33 
34  public virtual void QuickSort(int lo, int hi)
35  {
36  QuickSortHelper(lo, hi);
37  InsertionSort(lo, hi);
38  }
39 
40  private void QuickSortHelper(int lo, int hi)
41  {
42  for (; ; )
43  {
44  int diff = hi - lo;
45  if (diff <= QUICKSORT_THRESHOLD)
46  {
47  break;
48  }
49  int i = (hi + lo) / 2;
50  if (Compare(lo, i) > 0)
51  {
52  Swap(lo, i);
53  }
54  if (Compare(lo, hi) > 0)
55  {
56  Swap(lo, hi);
57  }
58  if (Compare(i, hi) > 0)
59  {
60  Swap(i, hi);
61  }
62  int j = hi - 1;
63  Swap(i, j);
64  i = lo;
65  int v = j;
66  for (; ; )
67  {
68  while (Compare(++i, v) < 0)
69  {
70  /* nothing */ ;
71  }
72  while (Compare(--j, v) > 0)
73  {
74  /* nothing */ ;
75  }
76  if (j < i)
77  {
78  break;
79  }
80  Swap(i, j);
81  }
82  Swap(i, hi - 1);
83  if (j - lo <= hi - i + 1)
84  {
85  QuickSortHelper(lo, j);
86  lo = i + 1;
87  }
88  else
89  {
90  QuickSortHelper(i + 1, hi);
91  hi = j;
92  }
93  }
94  }
95 
96  private void InsertionSort(int lo, int hi)
97  {
98  for (int i = lo + 1; i <= hi; i++)
99  {
100  for (int j = i; j > lo; j--)
101  {
102  if (Compare(j - 1, j) > 0)
103  {
104  Swap(j - 1, j);
105  }
106  else
107  {
108  break;
109  }
110  }
111  }
112  }
113 
114  protected internal virtual void MergeSort(int lo, int hi)
115  {
116  int diff = hi - lo;
117  if (diff <= MERGESORT_THRESHOLD)
118  {
119  InsertionSort(lo, hi);
120  return ;
121  }
122  int mid = lo + diff / 2;
123  MergeSort(lo, mid);
124  MergeSort(mid, hi);
125  Merge(lo, mid, hi, mid - lo, hi - mid);
126  }
127 
128  private void Merge(int lo, int pivot, int hi, int len1, int len2)
129  {
130  if (len1 == 0 || len2 == 0)
131  {
132  return ;
133  }
134  if (len1 + len2 == 2)
135  {
136  if (Compare(pivot, lo) < 0)
137  {
138  Swap(pivot, lo);
139  }
140  return ;
141  }
142  int first_cut, second_cut;
143  int len11, len22;
144  if (len1 > len2)
145  {
146  len11 = len1 / 2;
147  first_cut = lo + len11;
148  second_cut = Lower(pivot, hi, first_cut);
149  len22 = second_cut - pivot;
150  }
151  else
152  {
153  len22 = len2 / 2;
154  second_cut = pivot + len22;
155  first_cut = Upper(lo, pivot, second_cut);
156  len11 = first_cut - lo;
157  }
158  Rotate(first_cut, pivot, second_cut);
159  int new_mid = first_cut + len22;
160  Merge(lo, first_cut, new_mid, len11, len22);
161  Merge(new_mid, second_cut, hi, len1 - len11, len2 - len22);
162  }
163 
164  private void Rotate(int lo, int mid, int hi)
165  {
166  int lot = lo;
167  int hit = mid - 1;
168  while (lot < hit)
169  {
170  Swap(lot++, hit--);
171  }
172  lot = mid; hit = hi - 1;
173  while (lot < hit)
174  {
175  Swap(lot++, hit--);
176  }
177  lot = lo; hit = hi - 1;
178  while (lot < hit)
179  {
180  Swap(lot++, hit--);
181  }
182  }
183 
184  private int Lower(int lo, int hi, int val)
185  {
186  int len = hi - lo;
187  while (len > 0)
188  {
189  int half = len / 2;
190  int mid = lo + half;
191  if (Compare(mid, val) < 0)
192  {
193  lo = mid + 1;
194  len = len - half - 1;
195  }
196  else
197  {
198  len = half;
199  }
200  }
201  return lo;
202  }
203 
204  private int Upper(int lo, int hi, int val)
205  {
206  int len = hi - lo;
207  while (len > 0)
208  {
209  int half = len / 2;
210  int mid = lo + half;
211  if (Compare(val, mid) < 0)
212  {
213  len = half;
214  }
215  else
216  {
217  lo = mid + 1;
218  len = len - half - 1;
219  }
220  }
221  return lo;
222  }
223  }
224 }