Coverage Report

Coverage Report - org.melati.poem.util.SortUtils

Classes in this File

Line Coverage

Branch Coverage

Complexity

SortUtils

97%

48/49

96%

25/26

2.625

 /*
  * $Source$
  * $Revision$
  *
  * Copyright (C) 2000 William Chesters
  *
  * Part of Melati (http://melati.org), a framework for the rapid
  * development of clean, maintainable web applications.
  *
  * Melati is free software; Permission is granted to copy, distribute
  * and/or modify this software under the terms either:
  *
  * a) the GNU General Public License as published by the Free Software
  *    Foundation; either version 2 of the License, or (at your option)
  *    any later version,
  *
  *    or
  *
  * b) any version of the Melati Software License, as published
  *    at http://melati.org
  *
  * You should have received a copy of the GNU General Public License and
  * the Melati Software License along with this program;
  * if not, write to the Free Software Foundation, Inc.,
  * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA to obtain the
  * GNU General Public License and visit http://melati.org to obtain the
  * Melati Software License.
  *
  * Feel free to contact the Developers of Melati (http://melati.org),
  * if you would like to work out a different arrangement than the options
  * outlined here.  It is our intention to allow Melati to be used by as
  * wide an audience as possible.
  *
  * This program is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * Contact details for copyright holder:
  *
  *     William Chesters <williamc At paneris.org>
  *     http://paneris.org/~williamc
  *     Obrechtstraat 114, 2517VX Den Haag, The Netherlands
  */
 
 package org.melati.poem.util;
 
 import java.util.Vector;
 import java.util.Enumeration;
 
 /**
  * An assortment of useful sorting operations.
  */
 public final class SortUtils {
 
   private SortUtils() {}
 
   /**
    * Swap two elements of an Array.
    * @param arr the Array
    * @param i will become j
    * @param j will become i
    */
   public static void swap(Object[] arr, int i, int j) {
     Object t = arr[i];
     arr[i] = arr[j];
     arr[j] = t;
   }
 
   /**
    * Sort an Array by a supplied ordering.
    * @param cmp an ordering
    * @param arr the Array to sort
    */
   public static void insertionSort(Order cmp, Object[] arr) {
     for (int i = 1; i < arr.length; ++i) {
       Object val_i = arr[i];
       if (!cmp.lessOrEqual(arr[i-1], val_i)) {
         int j = i - 1;
         arr[i] = arr[j];
         while (j >= 1 && !cmp.lessOrEqual(arr[j-1], val_i)) {
           arr[j] = arr[j-1];
           --j;
         }
         arr[j] = val_i;
       }
     }
   }
 
   /**
    * This is nicked from ocaml 2.03's Sort.array, in turn derived from
    * Sedgewick.  ocaml is a superb object/functional language from INRIA: 
    * see http://caml.inria.fr/ .
    */
   private static void partlyQSort(Order cmp, Object[] arr, int lo, int hi) {
     if (hi - lo >= 6) {
       int mid = (lo + hi) >> 1;
       
       /* Select median value from among LO, MID, and HI. Rearrange
          LO and HI so the three values are sorted. This lowers the
          probability of picking a pathological pivot.  It also
          avoids extra comparisons on i and j in the two tight "while"
          loops below. */
 
       if (cmp.lessOrEqual(arr[mid], arr[lo]))
         swap(arr, mid, lo);
       if (cmp.lessOrEqual(arr[hi], arr[mid])) {
         swap(arr, mid, hi);
         if (cmp.lessOrEqual(arr[mid], arr[lo]))
           swap(arr, mid, lo);
       }
 
       Object pivot = arr[mid];
       int i = lo + 1;
       int j = hi - 1;
       while (i < j) {
         while (!cmp.lessOrEqual(pivot, arr[i])) ++i;
         while (!cmp.lessOrEqual(arr[j], pivot)) --j;
         if (i < j)
           swap(arr, i, j);
         ++i;
         --j;
       }
 
       /* Recursion on smaller half, tail-call on larger half */
 
       if (j - lo <= hi - i) {
         partlyQSort(cmp, arr, lo, j);
         partlyQSort(cmp, arr, i, hi);
       }
       else {
         partlyQSort(cmp, arr, i, hi);
         partlyQSort(cmp, arr, lo, j);
       }
     }
   }
 
   /**
    * Quick sort an array.
    * @param cmp ordering to use
    * @param arr Array to sort 
    */
   public static void qsort(Order cmp, Object[] arr) {
     partlyQSort(cmp, arr, 0, arr.length - 1);
     /* Finish sorting by insertion sort */
     insertionSort(cmp, arr);
   }
 
   /**
    * Return a new sorted Array.
    * @param cmp the ordering
    * @param arr the Array to sort
    * @return the sorted Array
    */
   public static Object[] sorted(Order cmp, Object[] arr) {
     Object[] arr2 = (Object[])arr.clone();
     qsort(cmp, arr2);
     return arr2;
   }
 
   /**
    * Sort a Vector into a new Array.
    * @param cmp the ordering
    * @param v Vector to sort
    * @return an Array of the sorted Vector's Elements 
    */
   public static <O> O[] sorted(Order cmp, Vector<O> v) {
     O[] arr = ArrayUtils.arrayOf(v);
     qsort(cmp, arr);
     return arr;
   }
 
   /**
    * Sort an Enumeration into an Array.
    * @param cmp the ordering
    * @param e the Enumeration to sort
    * @return an Array of the sorted Enumeration's Elements 
    */
   public static <O> O[] sorted(Order cmp, Enumeration<O> e) {
     return sorted(cmp, EnumUtils.vectorOf(e));
   }
 
 }

1		/*
2		* $Source$
3		* $Revision$
4		*
5		* Copyright (C) 2000 William Chesters
6		*
7		* Part of Melati (http://melati.org), a framework for the rapid
8		* development of clean, maintainable web applications.
9		*
10		* Melati is free software; Permission is granted to copy, distribute
11		* and/or modify this software under the terms either:
12		*
13		* a) the GNU General Public License as published by the Free Software
14		* Foundation; either version 2 of the License, or (at your option)
15		* any later version,
16		*
17		* or
18		*
19		* b) any version of the Melati Software License, as published
20		* at http://melati.org
21		*
22		* You should have received a copy of the GNU General Public License and
23		* the Melati Software License along with this program;
24		* if not, write to the Free Software Foundation, Inc.,
25		* 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA to obtain the
26		* GNU General Public License and visit http://melati.org to obtain the
27		* Melati Software License.
28		*
29		* Feel free to contact the Developers of Melati (http://melati.org),
30		* if you would like to work out a different arrangement than the options
31		* outlined here. It is our intention to allow Melati to be used by as
32		* wide an audience as possible.
33		*
34		* This program is distributed in the hope that it will be useful,
35		* but WITHOUT ANY WARRANTY; without even the implied warranty of
36		* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
37		* GNU General Public License for more details.
38		*
39		* Contact details for copyright holder:
40		*
41		* William Chesters <williamc At paneris.org>
42		* http://paneris.org/~williamc
43		* Obrechtstraat 114, 2517VX Den Haag, The Netherlands
44		*/
45
46		package org.melati.poem.util;
47
48		import java.util.Vector;
49		import java.util.Enumeration;
50
51		/**
52		* An assortment of useful sorting operations.
53		*/
54		public final class SortUtils {
55
56	0	private SortUtils() {}
57
58		/**
59		* Swap two elements of an Array.
60		* @param arr the Array
61		* @param i will become j
62		* @param j will become i
63		*/
64		public static void swap(Object[] arr, int i, int j) {
65	12	Object t = arr[i];
66	12	arr[i] = arr[j];
67	12	arr[j] = t;
68	12	}
69
70		/**
71		* Sort an Array by a supplied ordering.
72		* @param cmp an ordering
73		* @param arr the Array to sort
74		*/
75		public static void insertionSort(Order cmp, Object[] arr) {
76	475	for (int i = 1; i < arr.length; ++i) {
77	59	Object val_i = arr[i];
78	59	if (!cmp.lessOrEqual(arr[i-1], val_i)) {
79	19	int j = i - 1;
80	19	arr[i] = arr[j];
81	20	while (j >= 1 && !cmp.lessOrEqual(arr[j-1], val_i)) {
82	1	arr[j] = arr[j-1];
83	1	--j;
84		}
85	19	arr[j] = val_i;
86		}
87		}
88	416	}
89
90		/**
91		* This is nicked from ocaml 2.03's Sort.array, in turn derived from
92		* Sedgewick. ocaml is a superb object/functional language from INRIA:
93		* see http://caml.inria.fr/ .
94		*/
95		private static void partlyQSort(Order cmp, Object[] arr, int lo, int hi) {
96	426	if (hi - lo >= 6) {
97	5	int mid = (lo + hi) >> 1;
98
99		/* Select median value from among LO, MID, and HI. Rearrange
100		LO and HI so the three values are sorted. This lowers the
101		probability of picking a pathological pivot. It also
102		avoids extra comparisons on i and j in the two tight "while"
103		loops below. */
104
105	5	if (cmp.lessOrEqual(arr[mid], arr[lo]))
106	3	swap(arr, mid, lo);
107	5	if (cmp.lessOrEqual(arr[hi], arr[mid])) {
108	2	swap(arr, mid, hi);
109	2	if (cmp.lessOrEqual(arr[mid], arr[lo]))
110	2	swap(arr, mid, lo);
111		}
112
113	5	Object pivot = arr[mid];
114	5	int i = lo + 1;
115	5	int j = hi - 1;
116	13	while (i < j) {
117	16	while (!cmp.lessOrEqual(pivot, arr[i])) ++i;
118	12	while (!cmp.lessOrEqual(arr[j], pivot)) --j;
119	8	if (i < j)
120	5	swap(arr, i, j);
121	8	++i;
122	8	--j;
123		}
124
125		/* Recursion on smaller half, tail-call on larger half */
126
127	5	if (j - lo <= hi - i) {
128	4	partlyQSort(cmp, arr, lo, j);
129	4	partlyQSort(cmp, arr, i, hi);
130		}
131		else {
132	1	partlyQSort(cmp, arr, i, hi);
133	1	partlyQSort(cmp, arr, lo, j);
134		}
135		}
136	426	}
137
138		/**
139		* Quick sort an array.
140		* @param cmp ordering to use
141		* @param arr Array to sort
142		*/
143		public static void qsort(Order cmp, Object[] arr) {
144	416	partlyQSort(cmp, arr, 0, arr.length - 1);
145		/* Finish sorting by insertion sort */
146	416	insertionSort(cmp, arr);
147	416	}
148
149		/**
150		* Return a new sorted Array.
151		* @param cmp the ordering
152		* @param arr the Array to sort
153		* @return the sorted Array
154		*/
155		public static Object[] sorted(Order cmp, Object[] arr) {
156	2	Object[] arr2 = (Object[])arr.clone();
157	2	qsort(cmp, arr2);
158	2	return arr2;
159		}
160
161		/**
162		* Sort a Vector into a new Array.
163		* @param cmp the ordering
164		* @param v Vector to sort
165		* @return an Array of the sorted Vector's Elements
166		*/
167		public static <O> O[] sorted(Order cmp, Vector<O> v) {
168	411	O[] arr = ArrayUtils.arrayOf(v);
169	411	qsort(cmp, arr);
170	411	return arr;
171		}
172
173		/**
174		* Sort an Enumeration into an Array.
175		* @param cmp the ordering
176		* @param e the Enumeration to sort
177		* @return an Array of the sorted Enumeration's Elements
178		*/
179		public static <O> O[] sorted(Order cmp, Enumeration<O> e) {
180	411	return sorted(cmp, EnumUtils.vectorOf(e));
181		}
182
183		}