patch to fix occasional arrayoutofbounds exception when working with hidden columns...
[jalview.git] / src / jalview / util / QuickSort.java
1 /*
2  * Jalview - A Sequence Alignment Editor and Viewer (Version 2.4)
3  * Copyright (C) 2008 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
62   public static void sort(double[] arr, int p, int r, Object[] s)
63   {
64     int q;
65
66     if (p < r)
67     {
68       q = partition(arr, p, r, s);
69       sort(arr, p, q, s);
70       sort(arr, q + 1, r, s);
71     }
72   }
73
74   private static int partition(float[] arr, int p, int r, Object[] s)
75   {
76     float x = arr[p];
77     int i = p - 1;
78     int j = r + 1;
79
80     while (true)
81     {
82       do
83       {
84         j = j - 1;
85       } while (arr[j] > x);
86
87       do
88       {
89         i = i + 1;
90       } while (arr[i] < x);
91
92       if (i < j)
93       {
94         float tmp = arr[i];
95         arr[i] = arr[j];
96         arr[j] = tmp;
97
98         Object tmp2 = s[i];
99         s[i] = s[j];
100         s[j] = tmp2;
101       }
102       else
103       {
104         return j;
105       }
106     }
107   }
108
109   private static int partition(double[] arr, int p, int r, Object[] s)
110   {
111     double x = arr[p];
112     int i = p - 1;
113     int j = r + 1;
114
115     while (true)
116     {
117       do
118       {
119         j = j - 1;
120       } while (arr[j] > x);
121
122       do
123       {
124         i = i + 1;
125       } while (arr[i] < x);
126
127       if (i < j)
128       {
129         double tmp = arr[i];
130         arr[i] = arr[j];
131         arr[j] = tmp;
132
133         Object tmp2 = s[i];
134         s[i] = s[j];
135         s[j] = tmp2;
136       }
137       else
138       {
139         return j;
140       }
141     }
142   }
143
144   private static int stringPartition(String[] arr, int p, int r, Object[] s)
145   {
146     String x = arr[p];
147     int i = p - 1;
148     int j = r + 1;
149
150     while (true)
151     {
152       do
153       {
154         j = j - 1;
155       } while (arr[j].compareTo(x) < 0);
156
157       do
158       {
159         i = i + 1;
160       } while (arr[i].compareTo(x) > 0);
161
162       if (i < j)
163       {
164         String tmp = arr[i];
165         arr[i] = arr[j];
166         arr[j] = tmp;
167
168         Object tmp2 = s[i];
169         s[i] = s[j];
170         s[j] = tmp2;
171       }
172       else
173       {
174         return j;
175       }
176     }
177   }
178 }