Functions_Arrays.cxx
1 // Copyright (C) 2003-2011 Marc Duruflé
2 // Copyright (C) 2001-2011 Vivien Mallet
3 //
4 // This file is part of the linear-algebra library Seldon,
5 // http://seldon.sourceforge.net/.
6 //
7 // Seldon 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 // Seldon 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 Seldon. If not, see http://www.gnu.org/licenses/.
19 
20 
21 #ifndef SELDON_FILE_FUNCTIONS_ARRAYS_CXX
22 
23 /*
24  Functions defined in this file
25 
26  QuickSort(m, n, X);
27  QuickSort(m, n, X, Y);
28  QuickSort(m, n, X, Y, Z);
29 
30  MergeSort(m, n, X);
31  MergeSort(m, n, X, Y);
32  MergeSort(m, n, X, Y, Z);
33 
34  Sort(m, n, X);
35  Sort(m, n, X, Y);
36  Sort(m, n, X, Y, Z);
37  Sort(m, X);
38  Sort(m, X, Y);
39  Sort(m, X, Y, Z);
40  Sort(X);
41  Sort(X, Y);
42  Sort(X, Y, Z);
43 
44  Assemble(m, X);
45  Assemble(m, X, Y);
46 
47  RemoveDuplicate(m, X);
48  RemoveDuplicate(m, X, Y);
49  RemoveDuplicate(X);
50  RemoveDuplicate(X, Y);
51 
52  HasElement(X, a);
53 */
54 
55 namespace Seldon
56 {
57 
58 
60  // SORT //
61 
62 
64  template<class T, class Storage, class Allocator>
65  long PartitionQuickSort(long m, long n,
66  Vector<T, Storage, Allocator>& t)
67  {
68  T temp, v;
69  v = t(m);
70  long i = m - 1;
71  long j = n + 1;
72 
73  while (true)
74  {
75  do
76  {
77  j--;
78  }
79  while (t(j) > v);
80 
81  do
82  {
83  i++;
84  }
85  while (t(i) < v);
86 
87  if (i < j)
88  {
89  temp = t(i);
90  t(i) = t(j);
91  t(j) = temp;
92  }
93  else
94  {
95  return j;
96  }
97  }
98  }
99 
100 
102 
105  template<class T, class Storage, class Allocator>
106  void QuickSort(long m, long n,
107  Vector<T, Storage, Allocator>& t)
108  {
109  if (m < n)
110  {
111  long p = PartitionQuickSort(m, n, t);
112  QuickSort(m, p, t);
113  QuickSort(p+1, n, t);
114  }
115  }
116 
117 
119  template<class T1, class Storage1, class Allocator1,
120  class T2, class Storage2, class Allocator2>
121  long PartitionQuickSort(long m, long n,
122  Vector<T1, Storage1, Allocator1>& t1,
123  Vector<T2, Storage2, Allocator2>& t2)
124  {
125  T1 temp1, v;
126  T2 temp2;
127  v = t1(m);
128  long i = m - 1;
129  long j = n + 1;
130 
131  while (true)
132  {
133  do
134  {
135  j--;
136  }
137  while (t1(j) > v);
138  do
139  {
140  i++;
141  }
142  while (t1(i) < v);
143 
144  if (i < j)
145  {
146  temp1 = t1(i);
147  t1(i) = t1(j);
148  t1(j) = temp1;
149  temp2 = t2(i);
150  t2(i) = t2(j);
151  t2(j) = temp2;
152  }
153  else
154  {
155  return j;
156  }
157  }
158  }
159 
160 
162 
165  template<class T1, class Storage1, class Allocator1,
166  class T2, class Storage2, class Allocator2>
167  void QuickSort(long m, long n,
168  Vector<T1, Storage1, Allocator1>& t1,
169  Vector<T2, Storage2, Allocator2>& t2)
170  {
171  if (m < n)
172  {
173  long p = PartitionQuickSort(m, n, t1, t2);
174  QuickSort(m, p, t1, t2);
175  QuickSort(p+1, n, t1, t2);
176  }
177  }
178 
179 
181  template<class T1, class Storage1, class Allocator1,
182  class T2, class Storage2, class Allocator2,
183  class T3, class Storage3, class Allocator3>
184  long PartitionQuickSort(long m, long n,
185  Vector<T1, Storage1, Allocator1>& t1,
186  Vector<T2, Storage2, Allocator2>& t2,
187  Vector<T3, Storage3, Allocator3>& t3)
188  {
189  T1 temp1, v;
190  T2 temp2;
191  T3 temp3;
192  v = t1(m);
193  long i = m - 1;
194  long j = n + 1;
195 
196  while (true)
197  {
198  do
199  {
200  j--;
201  }
202  while (t1(j) > v);
203 
204  do
205  {
206  i++;
207  }
208  while (t1(i) < v);
209 
210  if (i < j)
211  {
212  temp1 = t1(i);
213  t1(i) = t1(j);
214  t1(j) = temp1;
215  temp2 = t2(i);
216  t2(i) = t2(j);
217  t2(j) = temp2;
218  temp3 = t3(i);
219  t3(i) = t3(j);
220  t3(j) = temp3;
221  }
222  else
223  {
224  return j;
225  }
226  }
227  }
228 
229 
231 
234  template<class T1, class Storage1, class Allocator1,
235  class T2, class Storage2, class Allocator2,
236  class T3, class Storage3, class Allocator3>
237  void QuickSort(long m, long n,
238  Vector<T1, Storage1, Allocator1>& t1,
239  Vector<T2, Storage2, Allocator2>& t2,
240  Vector<T3, Storage3, Allocator3>& t3)
241  {
242  if (m < n)
243  {
244  long p = PartitionQuickSort(m, n, t1, t2, t3);
245  QuickSort(m, p, t1, t2, t3);
246  QuickSort(p+1, n, t1, t2, t3);
247  }
248  }
249 
250 
252 
255  template<class T, class Storage, class Allocator>
256  void MergeSort(long m, long n, Vector<T, Storage, Allocator>& tab1)
257  {
258  if (m >= n)
259  return;
260 
261  bool array_sorted = true;
262  for (long k = m; k < n; k++)
263  if (tab1(k+1) < tab1(k))
264  array_sorted = false;
265 
266  if (array_sorted)
267  return;
268 
269  long inc = 1, ind = 0, current, i, j, sup;
270  Vector<T, Storage, Allocator> tab1t(n - m + 1);
271  // Performs a merge sort with a recurrence.
272  // inc = 1, 2, 4, 8, ...
273  while (inc < (n - m + 1) )
274  {
275  // 'i' is the first index of the sub array of size 2*inc.
276  // A loop is performed on these sub-arrays.
277  // Each sub array is divided in two sub-arrays of size 'inc'.
278  // These two sub-arrays are then merged.
279  for (i = m; i <= n - inc; i += 2 * inc)
280  {
281  ind = i;
282  current = i + inc; // Index of the second sub-array.
283  sup = i + 2 * inc; // End of the merged array.
284  if (sup >= n + 1)
285  sup = n + 1;
286 
287  j = i;
288  // Loop on values of the first sub-array.
289  while (j < i + inc)
290  {
291  // If the second sub-array has still unsorted elements.
292  if (current < sup)
293  {
294  // Insert the elements of the second sub-array in the
295  // merged array until tab1(j) < tab1(current).
296  while (current < sup && tab1(j) > tab1(current))
297  {
298  tab1t(ind-m) = tab1(current);
299  current++;
300  ind++;
301  }
302 
303  // Inserts the element of the first sub-array now.
304  tab1t(ind - m) = tab1(j);
305  ind++;
306  j++;
307 
308  // If the first sub-array is sorted, all remaining
309  // elements of the second sub-array are inserted.
310  if (j == i + inc)
311  {
312  for (j = current; j < sup; j++)
313  {
314  tab1t(ind - m) = tab1(j);
315  ind++;
316  }
317  }
318  }
319  else
320  {
321  // If the second sub-array is sorted, all remaining
322  // elements of the first sub-array are inserted.
323  for (current = j; current < i + inc; current++)
324  {
325  tab1t(ind - m) = tab1(current);
326  ind++;
327  }
328  j = current + 1;
329  }
330  }
331  }
332 
333  for (i = m; i < ind; i++)
334  tab1(i) = tab1t(i - m);
335 
336  inc = 2 * inc;
337  }
338  }
339 
340 
342 
345  template<class T1, class Storage1, class Allocator1,
346  class T2, class Storage2, class Allocator2>
347  void MergeSort(long m, long n, Vector<T1, Storage1, Allocator1>& tab1,
348  Vector<T2, Storage2, Allocator2>& tab2)
349  {
350  if (m >= n)
351  return;
352 
353  bool array_sorted = true;
354  for (long k = m; k < n; k++)
355  if (tab1(k+1) < tab1(k))
356  array_sorted = false;
357 
358  if (array_sorted)
359  return;
360 
361  long inc = 1, ind = 0, current, i, j, sup;
362  Vector<T1, Storage1, Allocator1> tab1t(n - m + 1);
363  Vector<T2, Storage2, Allocator2> tab2t(n - m + 1);
364 
365  while (inc < n - m + 1)
366  {
367  for (i = m; i <= n - inc; i += 2 * inc)
368  {
369  ind = i;
370  current = i + inc;
371  sup = i + 2 * inc;
372  if (sup >= n+1)
373  sup = n+1;
374 
375  j = i;
376  while (j < i + inc)
377  {
378  if (current < sup)
379  {
380  while (current < sup && tab1(j) > tab1(current))
381  {
382  tab1t(ind - m) = tab1(current);
383  tab2t(ind - m) = tab2(current);
384  current++;
385  ind++;
386  }
387  tab1t(ind - m) = tab1(j);
388  tab2t(ind - m) = tab2(j);
389  ind++;
390  j++;
391  if (j == i + inc)
392  {
393  for (j = current; j < sup; j++)
394  {
395  tab1t(ind - m) = tab1(j);
396  tab2t(ind - m) = tab2(j);
397  ind++;
398  }
399  }
400  }
401  else
402  {
403  for (current = j; current < i + inc; current++)
404  {
405  tab1t(ind - m) = tab1(current);
406  tab2t(ind - m) = tab2(current);
407  ind++;
408  }
409  j = current + 1;
410  }
411  }
412  }
413  for (i = m; i < ind; i++)
414  {
415  tab1(i) = tab1t(i - m);
416  tab2(i) = tab2t(i - m);
417  }
418  inc = 2 * inc;
419  }
420  }
421 
422 
424 
427  template<class T1, class Storage1, class Allocator1,
428  class T2, class Storage2, class Allocator2,
429  class T3, class Storage3, class Allocator3>
430  void MergeSort(long m, long n, Vector<T1, Storage1, Allocator1>& tab1,
431  Vector<T2, Storage2, Allocator2>& tab2,
432  Vector<T3, Storage3, Allocator3>& tab3)
433  {
434  if (m >= n)
435  return;
436 
437  bool array_sorted = true;
438  for (long k = m; k < n; k++)
439  if (tab1(k+1) < tab1(k))
440  array_sorted = false;
441 
442  if (array_sorted)
443  return;
444 
445  long inc = 1, ind = 0, current, i, j, sup;
446  Vector<T1, Storage1, Allocator1> tab1t(n - m + 1);
447  Vector<T2, Storage2, Allocator2> tab2t(n - m + 1);
448  Vector<T3, Storage3, Allocator3> tab3t(n - m + 1);
449 
450  while (inc < n - m + 1)
451  {
452  for (i = m; i <= n - inc; i += 2 * inc)
453  {
454  ind = i;
455  current = i + inc;
456  sup = i + 2 * inc;
457  if (sup >= n+1)
458  sup = n+1;
459 
460  j = i;
461  while (j < i + inc)
462  {
463  if (current < sup)
464  {
465  while (current < sup && tab1(j) > tab1(current))
466  {
467  tab1t(ind - m) = tab1(current);
468  tab2t(ind - m) = tab2(current);
469  tab3t(ind - m) = tab3(current);
470  current++;
471  ind++;
472  }
473  tab1t(ind - m) = tab1(j);
474  tab2t(ind - m) = tab2(j);
475  tab3t(ind - m) = tab3(j);
476  ind++;
477  j++;
478  if (j == i + inc)
479  {
480  for (j = current; j < sup; j++)
481  {
482  tab1t(ind - m) = tab1(j);
483  tab2t(ind - m) = tab2(j);
484  tab3t(ind - m) = tab3(j);
485  ind++;
486  }
487  }
488  }
489  else
490  {
491  for (current = j; current < i + inc; current++)
492  {
493  tab1t(ind - m) = tab1(current);
494  tab2t(ind - m) = tab2(current);
495  tab3t(ind - m) = tab3(current);
496  ind++;
497  }
498  j = current+1;
499  }
500  }
501  }
502  for (i = m; i < ind; i++)
503  {
504  tab1(i) = tab1t(i - m);
505  tab2(i) = tab2t(i - m);
506  tab3(i) = tab3t(i - m);
507  }
508  inc = 2 * inc;
509  }
510  }
511 
512 
514 
526  template<class Storage1, class Allocator1,
527  class T2, class Storage2, class Allocator2 >
528  void Assemble(long& n, Vector<int, Storage1, Allocator1>& Node,
529  Vector<T2, Storage2, Allocator2>& Vect)
530  {
531  if (n <= 1)
532  return;
533 
534  Sort(n, Node, Vect);
535  int prec = Node(0);
536  long nb = 0;
537  for (long i = 1; i < n; i++)
538  if (Node(i) == prec)
539  {
540  Vect(nb) += Vect(i);
541  }
542  else
543  {
544  nb++;
545  Node(nb) = Node(i);
546  Vect(nb) = Vect(i);
547  prec = Node(nb);
548  }
549  n = nb + 1;
550  }
551 
552 
554 
560  template<class T, class Storage1, class Allocator1>
561  void Assemble(long& n, Vector<T, Storage1, Allocator1>& Node)
562  {
563  if (n <= 1)
564  return;
565 
566  Sort(n, Node);
567  T prec = Node(0);
568  long nb = 1;
569  for (long i = 1; i < n; i++)
570  if (Node(i) != prec)
571  {
572  Node(nb) = Node(i);
573  prec = Node(nb);
574  nb++;
575  }
576  n = nb;
577  }
578 
579 
581  template<class T, class Storage1, class Allocator1>
582  void Assemble(Vector<T, Storage1, Allocator1>& Node)
583  {
584  long nb = Node.GetM();
585  Assemble(nb, Node);
586  Node.Resize(nb);
587  }
588 
589 
591 
594  template<class T, class Storage1, class Allocator1,
595  class T2, class Storage2, class Allocator2>
596  void RemoveDuplicate(long& n, Vector<T, Storage1, Allocator1>& Node,
597  Vector<T2, Storage2, Allocator2>& Node2)
598  {
599  if (n <= 1)
600  return;
601 
602  Sort(n, Node, Node2);
603  T prec = Node(0);
604  long nb = 1;
605  for (long i = 1; i < n; i++)
606  if (Node(i) != prec)
607  {
608  Node(nb) = Node(i);
609  Node2(nb) = Node2(i);
610  prec = Node(nb);
611  nb++;
612  }
613  n = nb;
614  }
615 
616 
618  template<class T, class Storage1, class Allocator1>
619  void RemoveDuplicate(long& n, Vector<T, Storage1, Allocator1>& Node)
620  {
621  Assemble(n, Node);
622  }
623 
624 
626 
629  template<class T, class Storage1, class Allocator1,
630  class T2, class Storage2, class Allocator2>
631  void RemoveDuplicate(Vector<T, Storage1, Allocator1>& Node,
632  Vector<T2, Storage2, Allocator2>& Node2)
633  {
634  long n = Node.GetM();
635  if (n <= 1)
636  return;
637 
638  RemoveDuplicate(n, Node, Node2);
639  Node.Resize(n);
640  Node2.Resize(n);
641  }
642 
643 
645  template<class T, class Storage1, class Allocator1>
646  void RemoveDuplicate(Vector<T, Storage1, Allocator1>& Node)
647  {
648  long n = Node.GetM();
649  if (n <= 1)
650  return;
651 
652  Assemble(n, Node);
653  Node.Resize(n);
654  }
655 
656 
658  template<class T, class Storage, class Allocator>
659  void Sort(long m, long n, Vector<T, Storage, Allocator>& V)
660  {
661  MergeSort(m, n, V);
662  }
663 
664 
666 
669  template<class T1, class Storage1, class Allocator1,
670  class T2, class Storage2, class Allocator2>
671  void Sort(long m, long n, Vector<T1, Storage1, Allocator1>& V,
672  Vector<T2, Storage2, Allocator2>& V2)
673  {
674  MergeSort(m, n, V, V2);
675  }
676 
677 
679 
682  template<class T1, class Storage1, class Allocator1,
683  class T2, class Storage2, class Allocator2,
684  class T3, class Storage3, class Allocator3>
685  void Sort(long m, long n, Vector<T1, Storage1, Allocator1>& V,
686  Vector<T2, Storage2, Allocator2>& V2,
687  Vector<T3, Storage3, Allocator3>& V3)
688  {
689  MergeSort(m, n, V, V2, V3);
690  }
691 
692 
694  template<class T, class Storage, class Allocator>
695  void Sort(long n, Vector<T, Storage, Allocator>& V)
696  {
697  Sort(0, n - 1, V);
698  }
699 
700 
702 
705  template<class T1, class Storage1, class Allocator1,
706  class T2, class Storage2, class Allocator2>
707  void Sort(long n, Vector<T1, Storage1, Allocator1>& V,
708  Vector<T2, Storage2, Allocator2>& V2)
709  {
710  Sort(0, n - 1, V, V2);
711  }
712 
713 
715 
718  template<class T1, class Storage1, class Allocator1,
719  class T2, class Storage2, class Allocator2,
720  class T3, class Storage3, class Allocator3>
721  void Sort(long n, Vector<T1, Storage1, Allocator1>& V,
722  Vector<T2, Storage2, Allocator2>& V2,
723  Vector<T3, Storage3, Allocator3>& V3)
724  {
725  Sort(0, n - 1, V, V2, V3);
726  }
727 
728 
730  template<class T, class Storage, class Allocator>
731  void Sort(Vector<T, Storage, Allocator>& V)
732  {
733  Sort(0, V.GetM() - 1, V);
734  }
735 
736 
738 
741  template<class T1, class Storage1, class Allocator1,
742  class T2, class Storage2, class Allocator2>
743  void Sort(Vector<T1, Storage1, Allocator1>& V,
744  Vector<T2, Storage2, Allocator2>& V2)
745  {
746  Sort(0, V.GetM() - 1, V, V2);
747  }
748 
749 
751 
754  template<class T1, class Storage1, class Allocator1,
755  class T2, class Storage2, class Allocator2,
756  class T3, class Storage3, class Allocator3>
757  void Sort(Vector<T1, Storage1, Allocator1>& V,
758  Vector<T2, Storage2, Allocator2>& V2,
759  Vector<T3, Storage3, Allocator3>& V3)
760  {
761  Sort(0, V.GetM() - 1, V, V2, V3);
762  }
763 
764 
765  // SORT //
767 
768 
770  template<class T, class Storage, class Allocator>
771  bool HasElement(const Vector<T, Storage, Allocator>& X, const T& a)
772  {
773  for (long i = 0; i < X.GetM(); i++)
774  if (a == X(i))
775  return true;
776 
777  return false;
778  }
779 
780 
781 } // namespace Seldon
782 
783 #define SELDON_FILE_FUNCTIONS_ARRAYS_CXX
784 #endif
Seldon::Vector
Definition: SeldonHeader.hxx:207
Seldon::PartitionQuickSort
long PartitionQuickSort(long m, long n, Vector< T, Storage, Allocator > &t)
Intermediary function used for quick sort algorithm.
Definition: Functions_Arrays.cxx:65
Seldon
Seldon namespace.
Definition: Array.cxx:24