apparent bug in JpredFile parser where annotation was not being removed from alignmen...
[jalview.git] / src / jalview / util / QuickSort.java
1 /*
2  * Jalview - A Sequence Alignment Editor and Viewer
3  * Copyright (C) 2007 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License
7  * as published by the Free Software Foundation; either version 2
8  * of the License, or (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software
17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
18  */
19 package jalview.util;
20
21 public class QuickSort
22 {
23   public static void sort(float[] arr, Object[] s)
24   {
25     sort(arr, 0, arr.length - 1, s);
26   }
27   
28   public static void sort(double[] arr, Object[] s)
29   {
30     sort(arr, 0, arr.length - 1, s);
31   }
32
33   public static void sort(String[] arr, Object[] s)
34   {
35     stringSort(arr, 0, arr.length - 1, s);
36   }
37
38   public static void stringSort(String[] arr, int p, int r, Object[] s)
39   {
40     int q;
41
42     if (p < r)
43     {
44       q = stringPartition(arr, p, r, s);
45       stringSort(arr, p, q, s);
46       stringSort(arr, q + 1, r, s);
47     }
48   }
49
50   public static void sort(float[] arr, int p, int r, Object[] s)
51   {
52     int q;
53
54     if (p < r)
55     {
56       q = partition(arr, p, r, s);
57       sort(arr, p, q, s);
58       sort(arr, q + 1, r, s);
59     }
60   }
61   public static void sort(double[] arr, int p, int r, Object[] s)
62   {
63     int q;
64
65     if (p < r)
66     {
67       q = partition(arr, p, r, s);
68       sort(arr, p, q, s);
69       sort(arr, q + 1, r, s);
70     }
71   }
72
73   private static int partition(float[] arr, int p, int r, Object[] s)
74   {
75     float x = arr[p];
76     int i = p - 1;
77     int j = r + 1;
78
79     while (true)
80     {
81       do
82       {
83         j = j - 1;
84       }
85       while (arr[j] > x);
86
87       do
88       {
89         i = i + 1;
90       }
91       while (arr[i] < x);
92
93       if (i < j)
94       {
95         float tmp = arr[i];
96         arr[i] = arr[j];
97         arr[j] = tmp;
98
99         Object tmp2 = s[i];
100         s[i] = s[j];
101         s[j] = tmp2;
102       }
103       else
104       {
105         return j;
106       }
107     }
108   }
109
110   private static int partition(double[] arr, int p, int r, Object[] s)
111   {
112     double x = arr[p];
113     int i = p - 1;
114     int j = r + 1;
115
116     while (true)
117     {
118       do
119       {
120         j = j - 1;
121       }
122       while (arr[j] > x);
123
124       do
125       {
126         i = i + 1;
127       }
128       while (arr[i] < x);
129
130       if (i < j)
131       {
132         double tmp = arr[i];
133         arr[i] = arr[j];
134         arr[j] = tmp;
135
136         Object tmp2 = s[i];
137         s[i] = s[j];
138         s[j] = tmp2;
139       }
140       else
141       {
142         return j;
143       }
144     }
145   }
146
147   private static int stringPartition(String[] arr, int p, int r, Object[] s)
148   {
149     String x = arr[p];
150     int i = p - 1;
151     int j = r + 1;
152
153     while (true)
154     {
155       do
156       {
157         j = j - 1;
158       }
159       while (arr[j].compareTo(x) < 0);
160
161       do
162       {
163         i = i + 1;
164       }
165       while (arr[i].compareTo(x) > 0);
166
167       if (i < j)
168       {
169         String tmp = arr[i];
170         arr[i] = arr[j];
171         arr[j] = tmp;
172
173         Object tmp2 = s[i];
174         s[i] = s[j];
175         s[j] = tmp2;
176       }
177       else
178       {
179         return j;
180       }
181     }
182   }
183 }