← Back to branch summary

~ubuntu-branches/ubuntu/lucid/igraph/lucid

« back to all changes in this revision

Viewing changes to src/gengraph_qsort.h

  • Committer: Bazaar Package Importer
  • Author(s): Mathieu Malaterre
  • Date: 2009-11-16 18:12:42 UTC
  • Revision ID: james.westby@ubuntu.com-20091116181242-mzv9p5fz9uj57xd1
Tags: upstream-0.5.3
Import upstream version 0.5.3

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/gengraph_qsort.h
 
1
#ifndef QSORT_H
 
2
#define QSORT_H
 
3
 
 
4
#include <assert.h>
 
5
#include <stdio.h>
 
6
 
 
7
namespace gengraph {
 
8
 
 
9
//___________________________________________________________________________
 
10
// check if every element is zero
 
11
inline bool check_zero(int *mem, int n) {
 
12
  for(int *v = mem+n; v!=mem; ) if(*(--v)!=0) return false;
 
13
  return true;
 
14
}
 
15
 
 
16
//___________________________________________________________________________
 
17
//  Sort simple integer arrays in ASCENDING order
 
18
//___________________________________________________________________________
 
19
inline int med3(int a, int b, int c) {
 
20
  if(a<b) {
 
21
    if(c<b) return (a<c) ? c : a;
 
22
    else return b;
 
23
  }
 
24
  else {
 
25
    if(c<a) return (b<c) ? c : b;
 
26
    else return a;
 
27
  }
 
28
}
 
29
 
 
30
inline void isort(int *v, int t) {
 
31
  if(t<2) return;
 
32
  for(int i=1; i<t; i++) {
 
33
    register int *w = v+i;
 
34
    int tmp = *w;
 
35
    while(w!=v && *(w-1)>tmp) { *w = *(w-1); w--; }
 
36
    *w = tmp;
 
37
  }
 
38
}
 
39
 
 
40
inline int partitionne(int *v, int t, int p) {
 
41
  int i=0;
 
42
  int j=t-1;
 
43
  while(i<j) {
 
44
    while(i<=j && v[i]<p) i++;
 
45
    while(i<=j && v[j]>p) j--;
 
46
    if(i<j) {
 
47
      int tmp=v[i];
 
48
      v[i++]=v[j];
 
49
      v[j--]=tmp;
 
50
    }
 
51
  }
 
52
  if(i==j && v[i]<p) i++;
 
53
  assert(i!=0 && i!=t);
 
54
  return i;
 
55
}
 
56
  
 
57
inline void qsort(int *v, int t) {
 
58
  if(t<15) isort(v,t);
 
59
  else {
 
60
    int x = partitionne(v, t, med3(v[t>>1], v[(t>>2)+2], v[t-(t>>1)-2]));
 
61
    qsort(v,x);
 
62
    qsort(v+x,t-x);
 
63
  }
 
64
}
 
65
 
 
66
inline int qsort_median(int *v, int t, int pos) {
 
67
  if(t<10) { isort(v,t); return v[pos]; }
 
68
  int x = partitionne(v, t, med3(v[t>>1], v[(t>>2)+2], v[t-(t>>1)-2]));
 
69
  if(pos<x) return qsort_median(v, x, pos);
 
70
  else return qsort_median(v+x, t-x, pos-x);
 
71
} 
 
72
  
 
73
inline int qsort_median(int *v, int t) { return qsort_median(v,t,t/2); }
 
74
 
 
75
//___________________________________________________________________________
 
76
//  Sort simple double arrays in ASCENDING order
 
77
//___________________________________________________________________________
 
78
inline double med3(double a, double b, double c) {
 
79
  if(a<b) {
 
80
    if(c<b) return (a<c) ? c : a;
 
81
    else return b;
 
82
  }
 
83
  else {
 
84
    if(c<a) return (b<c) ? c : b;
 
85
    else return a;
 
86
  }
 
87
}
 
88
 
 
89
inline void isort(double *v, int t) {
 
90
  if(t<2) return;
 
91
  for(int i=1; i<t; i++) {
 
92
    register double *w = v+i;
 
93
    double tmp = *w;
 
94
    while(w!=v && *(w-1)>tmp) { *w = *(w-1); w--; }
 
95
    *w = tmp;
 
96
  }
 
97
}
 
98
 
 
99
inline int partitionne(double *v, int t, double p) {
 
100
  int i=0;
 
101
  int j=t-1;
 
102
  while(i<j) {
 
103
    while(i<=j && v[i]<p) i++;
 
104
    while(i<=j && v[j]>p) j--;
 
105
    if(i<j) {
 
106
      double tmp=v[i];
 
107
      v[i++]=v[j];
 
108
      v[j--]=tmp;
 
109
    }
 
110
  }
 
111
  if(i==j && v[i]<p) i++;
 
112
  assert(i!=0 && i!=t);
 
113
  return i;
 
114
}
 
115
  
 
116
inline void qsort(double *v, int t) {
 
117
  if(t<15) isort(v,t);
 
118
  else {
 
119
    int x = partitionne(v, t, med3(v[t>>1], v[(t>>2)+2], v[t-(t>>1)-2]));
 
120
    qsort(v,x);
 
121
    qsort(v+x,t-x);
 
122
  }
 
123
}
 
124
 
 
125
inline double qsort_median(double *v, int t, int pos) {
 
126
  if(t<10) { isort(v,t); return v[pos]; }
 
127
  int x = partitionne(v, t, med3(v[t>>1], v[(t>>2)+2], v[t-(t>>1)-2]));
 
128
  if(pos<x) return qsort_median(v, x, pos);
 
129
  else return qsort_median(v+x, t-x, pos-x);
 
130
} 
 
131
 
 
132
inline double qsort_median(double *v, int t) { return qsort_median(v,t,t/2); }
 
133
 
 
134
//___________________________________________________________________________
 
135
// Sort integer arrays according to value stored in mem[], in ASCENDING order
 
136
inline void isort(int *mem, int *v, int t) {
 
137
  if(t<2) return;
 
138
  for(int i=1; i<t; i++) {
 
139
    int vtmp = v[i];
 
140
    int tmp = mem[vtmp];
 
141
    int j;
 
142
    for(j=i; j>0 && tmp<mem[v[j-1]]; j--) v[j]=v[j-1];
 
143
    v[j] = vtmp;
 
144
  }
 
145
}
 
146
 
 
147
inline void qsort(int *mem, int *v, int t) {
 
148
  if(t<15) isort(mem,v,t);
 
149
  else {
 
150
    int p = med3(mem[v[t>>1]], mem[v[(t>>2)+3]], mem[v[t-(t>>1)-3]]);
 
151
    int i=0;
 
152
    int j=t-1;
 
153
    while(i<j) {
 
154
      while(i<=j && mem[v[i]]<p)  i++;
 
155
      while(i<=j && mem[v[j]]>p) j--;
 
156
      if(i<j) {
 
157
        int tmp=v[i];
 
158
        v[i++]=v[j];
 
159
        v[j--]=tmp;
 
160
      }
 
161
    }
 
162
    if(i==j && mem[v[i]]<p) i++;
 
163
    assert(i!=0 && i!=t);
 
164
    qsort(mem,v,i);
 
165
    qsort(mem,v+i,t-i);
 
166
  }
 
167
}
 
168
 
 
169
//Box-Sort 1..n according to value stored in mem[], in DESCENDING order.
 
170
inline int *pre_boxsort(int *mem, int n, int &offset) {
 
171
  int *yo;
 
172
  // maximum and minimum
 
173
  int mx = mem[0];
 
174
  int mn = mem[0];
 
175
  for(yo=mem+n-1; yo!=mem; yo--) {
 
176
    register int x = *yo;
 
177
    if(x>mx) mx=x;
 
178
    if(x<mn) mn=x;
 
179
  }
 
180
  // box
 
181
  int c = mx-mn+1;
 
182
  int *box = new int[c];
 
183
  for(yo=box+c; yo!=box; *(--yo)=0);
 
184
  for(yo=mem+n; yo!=mem; box[*(--yo)-mn]++);
 
185
  // cumul sum
 
186
  int sum=0;
 
187
  for(yo=box+c; yo!=box; ) {
 
188
    sum += *(--yo);
 
189
    *yo = sum;
 
190
  }
 
191
  offset = mn;
 
192
  return box;
 
193
}
 
194
 
 
195
inline int *boxsort(int *mem, int n, int *buff=NULL) {
 
196
  int i;
 
197
  if(n<=0) return buff;
 
198
  int offset=0;
 
199
  int *box = pre_boxsort(mem,n,offset);
 
200
  // sort
 
201
  if(buff==NULL) buff=new int[n];
 
202
  for(i=0; i<n; i++) buff[--box[mem[i]-offset]]=i;
 
203
  // clean
 
204
  delete[] box;
 
205
  return buff;
 
206
}
 
207
 
 
208
// merge two sorted arays in their intersection. Store the result in first array, and return length
 
209
inline int intersect(int *a, int a_len, int *b, int b_len) {
 
210
  if(a_len==0 || b_len==0) return 0;
 
211
  int *asup = a+a_len;
 
212
  int *bsup = b+b_len;
 
213
  int len=0;
 
214
  int *p = a;
 
215
  do {
 
216
    if (*a == *b) p[len++] = *a;
 
217
    do if(++a == asup) return len; while(*a<*b);
 
218
    if (*a == *b) p[len++] = *a;
 
219
    do if(++b == bsup) return len; while(*b<*a);
 
220
  } while(true);
 
221
}
 
222
 
 
223
// merge two sorted arays in their union, store result in m
 
224
inline int unify(int *m, int *a, int a_len, int *b, int b_len) {
 
225
  int *asup = a+a_len;
 
226
  int *bsup = b+b_len;
 
227
  int len=0;
 
228
  while(a!=asup && b!=bsup) {
 
229
    if(*a < *b) m[len++] = *(a++);
 
230
    else {
 
231
      if (*a == *b) a++;
 
232
      m[len++] = *(b++);
 
233
    }
 
234
  }
 
235
  while(a!=asup) m[len++]=*(a++);
 
236
  while(b!=asup) m[len++]=*(b++);
 
237
  return len;
 
238
}
 
239
 
 
240
// lexicographic compare
 
241
inline int lex_comp(int *v1, int *v2, int n) {
 
242
  int *stop = v1+n;
 
243
  while(v1!=stop && *v1==*v2) { v1++; v2++; };
 
244
  if(v1==stop) return 0; else if(*v1<*v2) return -1; else return 1;
 
245
}
 
246
// lexicographic median of three
 
247
inline int *lex_med3(int *a, int *b, int *c, int s) {
 
248
  int ab = lex_comp(a,b,s);
 
249
  if(ab==0) return a;
 
250
  else {
 
251
    int cb = lex_comp(c,b,s);
 
252
    if(cb==0) return b;
 
253
    int ca = lex_comp(c,a,s);
 
254
    if(ab<0) { if(cb>0) return b; else return (ca>0) ? c : a; }
 
255
    else     { if(cb<0) return b; else return (ca<0) ? c : a; }
 
256
  }
 
257
}
 
258
 
 
259
// Lexicographic sort
 
260
inline void lex_isort(int **l, int *v, int t, int s) {
 
261
  if(t<2) return;
 
262
  for(int i=1; i<t; i++) {
 
263
    register int *w = v+i;
 
264
    int tmp = *w;
 
265
    while(w!=v && lex_comp(l[tmp],l[*(w-1)],s)<0) { *w = *(w-1); w--; }
 
266
    *w = tmp;
 
267
  }
 
268
}
 
269
 
 
270
#ifdef _STABLE_SORT_ONLY
 
271
#define _CRITICAL_SIZE_QSORT 0x7FFFFFFF
 
272
#warning "lex_qsort will be replaced by lex_isort"
 
273
#else
 
274
#define _CRITICAL_SIZE_QSORT 15
 
275
#endif
 
276
 
 
277
inline void lex_qsort(int **l, int *v, int t, int s) {
 
278
 
 
279
  if(t<_CRITICAL_SIZE_QSORT) lex_isort(l,v,t,s);
 
280
  else {
 
281
    int *p = lex_med3(l[v[t>>1]], l[v[(t>>2)+2]], l[v[t-(t>>1)-2]], s);
 
282
    int i=0;
 
283
    int j=t-1;
 
284
//    printf("pivot = %d\n",p);
 
285
    while(i<j) {
 
286
//      for(int k=0; k<t; k++) printf("%d ",v[k]);
 
287
      while(i<=j && lex_comp(l[v[i]],p,s)<0) i++;
 
288
      while(i<=j && lex_comp(l[v[j]],p,s)>0) j--;
 
289
      if(i<j) {
 
290
//        printf("  swap %d[%d] with %d[%d]\n",i,v[i],j,v[j]);
 
291
        int tmp=v[i];
 
292
        v[i++]=v[j];
 
293
        v[j--]=tmp;
 
294
      }
 
295
    }
 
296
    if(i==j && lex_comp(l[v[i]],p,s)<0) i++;
 
297
    assert(i!=0 && i!=t);
 
298
    lex_qsort(l,v,i,s);
 
299
    lex_qsort(l,v+i,t-i,s);
 
300
  }
 
301
}
 
302
 
 
303
// lexicographic indirect compare
 
304
inline int lex_comp_indirect(int *key, int *v1, int *v2, int n) {
 
305
  int *stop = v1+n;
 
306
  while(v1!=stop && key[*v1]==key[*v2]) { v1++; v2++; };
 
307
  if(v1==stop) return 0; else if(key[*v1]<key[*v2]) return -1; else return 1;
 
308
}
 
309
 
 
310
inline int qsort_min(const int a, const int b) { return a<=b ? a : b; }
 
311
 
 
312
// mix indirect compare
 
313
inline int mix_comp_indirect(int *key, int a, int b, int **neigh, int *degs)
 
314
{
 
315
  if(key[a]<key[b]) return -1;
 
316
  else if(key[a]>key[b]) return 1;
 
317
  else {
 
318
    int cmp=lex_comp_indirect(key,neigh[a],neigh[b],qsort_min(degs[a],degs[b]));
 
319
    if(cmp==0) {
 
320
      if(degs[a]>degs[b]) return -1;
 
321
      if(degs[a]<degs[b]) return 1;
 
322
    }
 
323
    return cmp;
 
324
  }
 
325
}
 
326
// lexicographic indirect median of three
 
327
inline int mix_med3_indirect(int *key, int a, int b, int c, int **neigh, int *degs) {
 
328
  int ab = mix_comp_indirect(key,a,b,neigh,degs);
 
329
  if(ab==0) return a;
 
330
  else {
 
331
    int cb = mix_comp_indirect(key,c,b,neigh,degs);
 
332
    if(cb==0) return b;
 
333
    int ca = mix_comp_indirect(key,c,a,neigh,degs);
 
334
    if(ab<0) { if(cb>0) return b; else return (ca>0) ? c : a; }
 
335
    else     { if(cb<0) return b; else return (ca<0) ? c : a; }
 
336
  }
 
337
}
 
338
 
 
339
// Sort integer arrays in ASCENDING order
 
340
inline void mix_isort_indirect(int *key, int *v, int t, int **neigh, int *degs)
 
341
{
 
342
  if(t<2) return;
 
343
  for(int i=1; i<t; i++) {
 
344
    register int *w = v+i;
 
345
    int tmp = *w;
 
346
    while(w!=v && mix_comp_indirect(key,tmp,*(w-1),neigh,degs)<0) {
 
347
      *w = *(w-1);
 
348
      w--;
 
349
    }
 
350
    *w = tmp;
 
351
  }
 
352
}
 
353
 
 
354
inline void mix_qsort_indirect(int *key, int *v, int t, int **neigh, int *degs)
 
355
{
 
356
  if(t<15) mix_isort_indirect(key,v,t,neigh,degs);
 
357
  else {
 
358
    int p = mix_med3_indirect(key, v[t>>1], v[(t>>2)+2], v[t-(t>>1)-2], neigh, degs);
 
359
    int i=0;
 
360
    int j=t-1;
 
361
//    printf("pivot = %d\n",p);
 
362
    while(i<j) {
 
363
//      for(int k=0; k<t; k++) printf("%d ",v[k]);
 
364
      while(i<=j && mix_comp_indirect(key,v[i],p,neigh,degs)<0) i++;
 
365
      while(i<=j && mix_comp_indirect(key,v[j],p,neigh,degs)>0) j--;
 
366
      if(i<j) {
 
367
//        printf("  swap %d[%d] with %d[%d]\n",i,v[i],j,v[j]);
 
368
        int tmp=v[i];
 
369
        v[i++]=v[j];
 
370
        v[j--]=tmp;
 
371
      }
 
372
    }
 
373
    if(i==j && mix_comp_indirect(key,v[i],p,neigh,degs)<0) i++;
 
374
    assert(i!=0 && i!=t);
 
375
    mix_qsort_indirect(key,v,i,neigh,degs);
 
376
    mix_qsort_indirect(key,v+i,t-i,neigh,degs);
 
377
  }
 
378
}
 
379
 
 
380
} // namespace gengraph
 
381
 
 
382
#endif //QSORT_H