001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 package org.apache.commons.collections.comparators; 018 019 import java.io.Serializable; 020 import java.util.ArrayList; 021 import java.util.BitSet; 022 import java.util.Comparator; 023 import java.util.Iterator; 024 import java.util.List; 025 026 /** 027 * <p>A ComparatorChain is a Comparator that wraps one or 028 * more Comparators in sequence. The ComparatorChain 029 * calls each Comparator in sequence until either 1) 030 * any single Comparator returns a non-zero result 031 * (and that result is then returned), 032 * or 2) the ComparatorChain is exhausted (and zero is 033 * returned). This type of sorting is very similar 034 * to multi-column sorting in SQL, and this class 035 * allows Java classes to emulate that kind of behaviour 036 * when sorting a List.</p> 037 * 038 * <p>To further facilitate SQL-like sorting, the order of 039 * any single Comparator in the list can be reversed.</p> 040 * 041 * <p>Calling a method that adds new Comparators or 042 * changes the ascend/descend sort <i>after compare(Object, 043 * Object) has been called</i> will result in an 044 * UnsupportedOperationException. However, <i>take care</i> 045 * to not alter the underlying List of Comparators 046 * or the BitSet that defines the sort order.</p> 047 * 048 * <p>Instances of ComparatorChain are not synchronized. 049 * The class is not thread-safe at construction time, but 050 * it <i>is</i> thread-safe to perform multiple comparisons 051 * after all the setup operations are complete.</p> 052 * 053 * @since Commons Collections 2.0 054 * @author Morgan Delagrange 055 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $ 056 */ 057 public class ComparatorChain implements Comparator, Serializable { 058 059 /** Serialization version from Collections 2.0. */ 060 private static final long serialVersionUID = -721644942746081630L; 061 062 /** The list of comparators in the chain. */ 063 protected List comparatorChain = null; 064 /** Order - false (clear) = ascend; true (set) = descend. */ 065 protected BitSet orderingBits = null; 066 /** Whether the chain has been "locked". */ 067 protected boolean isLocked = false; 068 069 //----------------------------------------------------------------------- 070 /** 071 * Construct a ComparatorChain with no Comparators. 072 * You must add at least one Comparator before calling 073 * the compare(Object,Object) method, or an 074 * UnsupportedOperationException is thrown 075 */ 076 public ComparatorChain() { 077 this(new ArrayList(),new BitSet()); 078 } 079 080 /** 081 * Construct a ComparatorChain with a single Comparator, 082 * sorting in the forward order 083 * 084 * @param comparator First comparator in the Comparator chain 085 */ 086 public ComparatorChain(Comparator comparator) { 087 this(comparator,false); 088 } 089 090 /** 091 * Construct a Comparator chain with a single Comparator, 092 * sorting in the given order 093 * 094 * @param comparator First Comparator in the ComparatorChain 095 * @param reverse false = forward sort; true = reverse sort 096 */ 097 public ComparatorChain(Comparator comparator, boolean reverse) { 098 comparatorChain = new ArrayList(); 099 comparatorChain.add(comparator); 100 orderingBits = new BitSet(1); 101 if (reverse == true) { 102 orderingBits.set(0); 103 } 104 } 105 106 /** 107 * Construct a ComparatorChain from the Comparators in the 108 * List. All Comparators will default to the forward 109 * sort order. 110 * 111 * @param list List of Comparators 112 * @see #ComparatorChain(List,BitSet) 113 */ 114 public ComparatorChain(List list) { 115 this(list,new BitSet(list.size())); 116 } 117 118 /** 119 * Construct a ComparatorChain from the Comparators in the 120 * given List. The sort order of each column will be 121 * drawn from the given BitSet. When determining the sort 122 * order for Comparator at index <i>i</i> in the List, 123 * the ComparatorChain will call BitSet.get(<i>i</i>). 124 * If that method returns <i>false</i>, the forward 125 * sort order is used; a return value of <i>true</i> 126 * indicates reverse sort order. 127 * 128 * @param list List of Comparators. NOTE: This constructor does not perform a 129 * defensive copy of the list 130 * @param bits Sort order for each Comparator. Extra bits are ignored, 131 * unless extra Comparators are added by another method. 132 */ 133 public ComparatorChain(List list, BitSet bits) { 134 comparatorChain = list; 135 orderingBits = bits; 136 } 137 138 //----------------------------------------------------------------------- 139 /** 140 * Add a Comparator to the end of the chain using the 141 * forward sort order 142 * 143 * @param comparator Comparator with the forward sort order 144 */ 145 public void addComparator(Comparator comparator) { 146 addComparator(comparator,false); 147 } 148 149 /** 150 * Add a Comparator to the end of the chain using the 151 * given sort order 152 * 153 * @param comparator Comparator to add to the end of the chain 154 * @param reverse false = forward sort order; true = reverse sort order 155 */ 156 public void addComparator(Comparator comparator, boolean reverse) { 157 checkLocked(); 158 159 comparatorChain.add(comparator); 160 if (reverse == true) { 161 orderingBits.set(comparatorChain.size() - 1); 162 } 163 } 164 165 /** 166 * Replace the Comparator at the given index, maintaining 167 * the existing sort order. 168 * 169 * @param index index of the Comparator to replace 170 * @param comparator Comparator to place at the given index 171 * @exception IndexOutOfBoundsException 172 * if index < 0 or index >= size() 173 */ 174 public void setComparator(int index, Comparator comparator) 175 throws IndexOutOfBoundsException { 176 setComparator(index,comparator,false); 177 } 178 179 /** 180 * Replace the Comparator at the given index in the 181 * ComparatorChain, using the given sort order 182 * 183 * @param index index of the Comparator to replace 184 * @param comparator Comparator to set 185 * @param reverse false = forward sort order; true = reverse sort order 186 */ 187 public void setComparator(int index, Comparator comparator, boolean reverse) { 188 checkLocked(); 189 190 comparatorChain.set(index,comparator); 191 if (reverse == true) { 192 orderingBits.set(index); 193 } else { 194 orderingBits.clear(index); 195 } 196 } 197 198 199 /** 200 * Change the sort order at the given index in the 201 * ComparatorChain to a forward sort. 202 * 203 * @param index Index of the ComparatorChain 204 */ 205 public void setForwardSort(int index) { 206 checkLocked(); 207 orderingBits.clear(index); 208 } 209 210 /** 211 * Change the sort order at the given index in the 212 * ComparatorChain to a reverse sort. 213 * 214 * @param index Index of the ComparatorChain 215 */ 216 public void setReverseSort(int index) { 217 checkLocked(); 218 orderingBits.set(index); 219 } 220 221 /** 222 * Number of Comparators in the current ComparatorChain. 223 * 224 * @return Comparator count 225 */ 226 public int size() { 227 return comparatorChain.size(); 228 } 229 230 /** 231 * Determine if modifications can still be made to the 232 * ComparatorChain. ComparatorChains cannot be modified 233 * once they have performed a comparison. 234 * 235 * @return true = ComparatorChain cannot be modified; false = 236 * ComparatorChain can still be modified. 237 */ 238 public boolean isLocked() { 239 return isLocked; 240 } 241 242 // throw an exception if the ComparatorChain is locked 243 private void checkLocked() { 244 if (isLocked == true) { 245 throw new UnsupportedOperationException("Comparator ordering cannot be changed after the first comparison is performed"); 246 } 247 } 248 249 private void checkChainIntegrity() { 250 if (comparatorChain.size() == 0) { 251 throw new UnsupportedOperationException("ComparatorChains must contain at least one Comparator"); 252 } 253 } 254 255 //----------------------------------------------------------------------- 256 /** 257 * Perform comparisons on the Objects as per 258 * Comparator.compare(o1,o2). 259 * 260 * @param o1 the first object to compare 261 * @param o2 the second object to compare 262 * @return -1, 0, or 1 263 * @exception UnsupportedOperationException 264 * if the ComparatorChain does not contain at least one 265 * Comparator 266 */ 267 public int compare(Object o1, Object o2) throws UnsupportedOperationException { 268 if (isLocked == false) { 269 checkChainIntegrity(); 270 isLocked = true; 271 } 272 273 // iterate over all comparators in the chain 274 Iterator comparators = comparatorChain.iterator(); 275 for (int comparatorIndex = 0; comparators.hasNext(); ++comparatorIndex) { 276 277 Comparator comparator = (Comparator) comparators.next(); 278 int retval = comparator.compare(o1,o2); 279 if (retval != 0) { 280 // invert the order if it is a reverse sort 281 if (orderingBits.get(comparatorIndex) == true) { 282 if(Integer.MIN_VALUE == retval) { 283 retval = Integer.MAX_VALUE; 284 } else { 285 retval *= -1; 286 } 287 } 288 289 return retval; 290 } 291 292 } 293 294 // if comparators are exhausted, return 0 295 return 0; 296 } 297 298 //----------------------------------------------------------------------- 299 /** 300 * Implement a hash code for this comparator that is consistent with 301 * {@link #equals(Object) equals}. 302 * 303 * @return a suitable hash code 304 * @since Commons Collections 3.0 305 */ 306 public int hashCode() { 307 int hash = 0; 308 if(null != comparatorChain) { 309 hash ^= comparatorChain.hashCode(); 310 } 311 if(null != orderingBits) { 312 hash ^= orderingBits.hashCode(); 313 } 314 return hash; 315 } 316 317 /** 318 * Returns <code>true</code> iff <i>that</i> Object is 319 * is a {@link Comparator} whose ordering is known to be 320 * equivalent to mine. 321 * <p> 322 * This implementation returns <code>true</code> 323 * iff <code><i>object</i>.{@link Object#getClass() getClass()}</code> 324 * equals <code>this.getClass()</code>, and the underlying 325 * comparators and order bits are equal. 326 * Subclasses may want to override this behavior to remain consistent 327 * with the {@link Comparator#equals(Object)} contract. 328 * 329 * @param object the object to compare with 330 * @return true if equal 331 * @since Commons Collections 3.0 332 */ 333 public boolean equals(Object object) { 334 if(this == object) { 335 return true; 336 } else if(null == object) { 337 return false; 338 } else if(object.getClass().equals(this.getClass())) { 339 ComparatorChain chain = (ComparatorChain)object; 340 return ( (null == orderingBits ? null == chain.orderingBits : orderingBits.equals(chain.orderingBits)) 341 && (null == comparatorChain ? null == chain.comparatorChain : comparatorChain.equals(chain.comparatorChain)) ); 342 } else { 343 return false; 344 } 345 } 346 347 }