1. /*
  2. * Copyright 1999-2004 The Apache Software Foundation
  3. *
  4. * Licensed under the Apache License, Version 2.0 (the "License");
  5. * you may not use this file except in compliance with the License.
  6. * You may obtain a copy of the License at
  7. *
  8. * http://www.apache.org/licenses/LICENSE-2.0
  9. *
  10. * Unless required by applicable law or agreed to in writing, software
  11. * distributed under the License is distributed on an "AS IS" BASIS,
  12. * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13. * See the License for the specific language governing permissions and
  14. * limitations under the License.
  15. */
  16. package org.apache.commons.collections.comparators;
  17. import java.io.Serializable;
  18. import java.util.ArrayList;
  19. import java.util.BitSet;
  20. import java.util.Comparator;
  21. import java.util.Iterator;
  22. import java.util.List;
  23. /**
  24. * <p>A ComparatorChain is a Comparator that wraps one or
  25. * more Comparators in sequence. The ComparatorChain
  26. * calls each Comparator in sequence until either 1)
  27. * any single Comparator returns a non-zero result
  28. * (and that result is then returned),
  29. * or 2) the ComparatorChain is exhausted (and zero is
  30. * returned). This type of sorting is very similar
  31. * to multi-column sorting in SQL, and this class
  32. * allows Java classes to emulate that kind of behaviour
  33. * when sorting a List.</p>
  34. *
  35. * <p>To further facilitate SQL-like sorting, the order of
  36. * any single Comparator in the list can be reversed.</p>
  37. *
  38. * <p>Calling a method that adds new Comparators or
  39. * changes the ascend/descend sort <i>after compare(Object,
  40. * Object) has been called</i> will result in an
  41. * UnsupportedOperationException. However, <i>take care</i>
  42. * to not alter the underlying List of Comparators
  43. * or the BitSet that defines the sort order.</p>
  44. *
  45. * <p>Instances of ComparatorChain are not synchronized.
  46. * The class is not thread-safe at construction time, but
  47. * it <i>is</i> thread-safe to perform multiple comparisons
  48. * after all the setup operations are complete.</p>
  49. *
  50. * @since Commons Collections 2.0
  51. * @author Morgan Delagrange
  52. * @version $Revision: 1.18 $ $Date: 2004/05/16 11:48:49 $
  53. */
  54. public class ComparatorChain implements Comparator, Serializable {
  55. /** Serialization version from Collections 2.0. */
  56. private static final long serialVersionUID = -721644942746081630L;
  57. /** The list of comparators in the chain. */
  58. protected List comparatorChain = null;
  59. /** Order - false (clear) = ascend; true (set) = descend. */
  60. protected BitSet orderingBits = null;
  61. /** Whether the chain has been "locked". */
  62. protected boolean isLocked = false;
  63. //-----------------------------------------------------------------------
  64. /**
  65. * Construct a ComparatorChain with no Comparators.
  66. * You must add at least one Comparator before calling
  67. * the compare(Object,Object) method, or an
  68. * UnsupportedOperationException is thrown
  69. */
  70. public ComparatorChain() {
  71. this(new ArrayList(),new BitSet());
  72. }
  73. /**
  74. * Construct a ComparatorChain with a single Comparator,
  75. * sorting in the forward order
  76. *
  77. * @param comparator First comparator in the Comparator chain
  78. */
  79. public ComparatorChain(Comparator comparator) {
  80. this(comparator,false);
  81. }
  82. /**
  83. * Construct a Comparator chain with a single Comparator,
  84. * sorting in the given order
  85. *
  86. * @param comparator First Comparator in the ComparatorChain
  87. * @param reverse false = forward sort; true = reverse sort
  88. */
  89. public ComparatorChain(Comparator comparator, boolean reverse) {
  90. comparatorChain = new ArrayList();
  91. comparatorChain.add(comparator);
  92. orderingBits = new BitSet(1);
  93. if (reverse == true) {
  94. orderingBits.set(0);
  95. }
  96. }
  97. /**
  98. * Construct a ComparatorChain from the Comparators in the
  99. * List. All Comparators will default to the forward
  100. * sort order.
  101. *
  102. * @param list List of Comparators
  103. * @see #ComparatorChain(List,BitSet)
  104. */
  105. public ComparatorChain(List list) {
  106. this(list,new BitSet(list.size()));
  107. }
  108. /**
  109. * Construct a ComparatorChain from the Comparators in the
  110. * given List. The sort order of each column will be
  111. * drawn from the given BitSet. When determining the sort
  112. * order for Comparator at index <i>i</i> in the List,
  113. * the ComparatorChain will call BitSet.get(<i>i</i>).
  114. * If that method returns <i>false</i>, the forward
  115. * sort order is used; a return value of <i>true</i>
  116. * indicates reverse sort order.
  117. *
  118. * @param list List of Comparators. NOTE: This constructor does not perform a
  119. * defensive copy of the list
  120. * @param bits Sort order for each Comparator. Extra bits are ignored,
  121. * unless extra Comparators are added by another method.
  122. */
  123. public ComparatorChain(List list, BitSet bits) {
  124. comparatorChain = list;
  125. orderingBits = bits;
  126. }
  127. //-----------------------------------------------------------------------
  128. /**
  129. * Add a Comparator to the end of the chain using the
  130. * forward sort order
  131. *
  132. * @param comparator Comparator with the forward sort order
  133. */
  134. public void addComparator(Comparator comparator) {
  135. addComparator(comparator,false);
  136. }
  137. /**
  138. * Add a Comparator to the end of the chain using the
  139. * given sort order
  140. *
  141. * @param comparator Comparator to add to the end of the chain
  142. * @param reverse false = forward sort order; true = reverse sort order
  143. */
  144. public void addComparator(Comparator comparator, boolean reverse) {
  145. checkLocked();
  146. comparatorChain.add(comparator);
  147. if (reverse == true) {
  148. orderingBits.set(comparatorChain.size() - 1);
  149. }
  150. }
  151. /**
  152. * Replace the Comparator at the given index, maintaining
  153. * the existing sort order.
  154. *
  155. * @param index index of the Comparator to replace
  156. * @param comparator Comparator to place at the given index
  157. * @exception IndexOutOfBoundsException
  158. * if index < 0 or index >= size()
  159. */
  160. public void setComparator(int index, Comparator comparator)
  161. throws IndexOutOfBoundsException {
  162. setComparator(index,comparator,false);
  163. }
  164. /**
  165. * Replace the Comparator at the given index in the
  166. * ComparatorChain, using the given sort order
  167. *
  168. * @param index index of the Comparator to replace
  169. * @param comparator Comparator to set
  170. * @param reverse false = forward sort order; true = reverse sort order
  171. */
  172. public void setComparator(int index, Comparator comparator, boolean reverse) {
  173. checkLocked();
  174. comparatorChain.set(index,comparator);
  175. if (reverse == true) {
  176. orderingBits.set(index);
  177. } else {
  178. orderingBits.clear(index);
  179. }
  180. }
  181. /**
  182. * Change the sort order at the given index in the
  183. * ComparatorChain to a forward sort.
  184. *
  185. * @param index Index of the ComparatorChain
  186. */
  187. public void setForwardSort(int index) {
  188. checkLocked();
  189. orderingBits.clear(index);
  190. }
  191. /**
  192. * Change the sort order at the given index in the
  193. * ComparatorChain to a reverse sort.
  194. *
  195. * @param index Index of the ComparatorChain
  196. */
  197. public void setReverseSort(int index) {
  198. checkLocked();
  199. orderingBits.set(index);
  200. }
  201. /**
  202. * Number of Comparators in the current ComparatorChain.
  203. *
  204. * @return Comparator count
  205. */
  206. public int size() {
  207. return comparatorChain.size();
  208. }
  209. /**
  210. * Determine if modifications can still be made to the
  211. * ComparatorChain. ComparatorChains cannot be modified
  212. * once they have performed a comparison.
  213. *
  214. * @return true = ComparatorChain cannot be modified; false =
  215. * ComparatorChain can still be modified.
  216. */
  217. public boolean isLocked() {
  218. return isLocked;
  219. }
  220. // throw an exception if the ComparatorChain is locked
  221. private void checkLocked() {
  222. if (isLocked == true) {
  223. throw new UnsupportedOperationException("Comparator ordering cannot be changed after the first comparison is performed");
  224. }
  225. }
  226. private void checkChainIntegrity() {
  227. if (comparatorChain.size() == 0) {
  228. throw new UnsupportedOperationException("ComparatorChains must contain at least one Comparator");
  229. }
  230. }
  231. //-----------------------------------------------------------------------
  232. /**
  233. * Perform comparisons on the Objects as per
  234. * Comparator.compare(o1,o2).
  235. *
  236. * @param o1 the first object to compare
  237. * @param o2 the second object to compare
  238. * @return -1, 0, or 1
  239. * @exception UnsupportedOperationException
  240. * if the ComparatorChain does not contain at least one
  241. * Comparator
  242. */
  243. public int compare(Object o1, Object o2) throws UnsupportedOperationException {
  244. if (isLocked == false) {
  245. checkChainIntegrity();
  246. isLocked = true;
  247. }
  248. // iterate over all comparators in the chain
  249. Iterator comparators = comparatorChain.iterator();
  250. for (int comparatorIndex = 0; comparators.hasNext(); ++comparatorIndex) {
  251. Comparator comparator = (Comparator) comparators.next();
  252. int retval = comparator.compare(o1,o2);
  253. if (retval != 0) {
  254. // invert the order if it is a reverse sort
  255. if (orderingBits.get(comparatorIndex) == true) {
  256. if(Integer.MIN_VALUE == retval) {
  257. retval = Integer.MAX_VALUE;
  258. } else {
  259. retval *= -1;
  260. }
  261. }
  262. return retval;
  263. }
  264. }
  265. // if comparators are exhausted, return 0
  266. return 0;
  267. }
  268. //-----------------------------------------------------------------------
  269. /**
  270. * Implement a hash code for this comparator that is consistent with
  271. * {@link #equals(Object) equals}.
  272. *
  273. * @return a suitable hash code
  274. * @since Commons Collections 3.0
  275. */
  276. public int hashCode() {
  277. int hash = 0;
  278. if(null != comparatorChain) {
  279. hash ^= comparatorChain.hashCode();
  280. }
  281. if(null != orderingBits) {
  282. hash ^= orderingBits.hashCode();
  283. }
  284. return hash;
  285. }
  286. /**
  287. * Returns <code>true</code> iff <i>that</i> Object is
  288. * is a {@link Comparator} whose ordering is known to be
  289. * equivalent to mine.
  290. * <p>
  291. * This implementation returns <code>true</code>
  292. * iff <code><i>object</i>.{@link Object#getClass() getClass()}</code>
  293. * equals <code>this.getClass()</code>, and the underlying
  294. * comparators and order bits are equal.
  295. * Subclasses may want to override this behavior to remain consistent
  296. * with the {@link Comparator#equals(Object)} contract.
  297. *
  298. * @param object the object to compare with
  299. * @return true if equal
  300. * @since Commons Collections 3.0
  301. */
  302. public boolean equals(Object object) {
  303. if(this == object) {
  304. return true;
  305. } else if(null == object) {
  306. return false;
  307. } else if(object.getClass().equals(this.getClass())) {
  308. ComparatorChain chain = (ComparatorChain)object;
  309. return ( (null == orderingBits ? null == chain.orderingBits : orderingBits.equals(chain.orderingBits))
  310. && (null == comparatorChain ? null == chain.comparatorChain : comparatorChain.equals(chain.comparatorChain)) );
  311. } else {
  312. return false;
  313. }
  314. }
  315. }