001/* 002 * Copyright 2007-2017 UnboundID Corp. 003 * All Rights Reserved. 004 */ 005/* 006 * Copyright (C) 2008-2017 UnboundID Corp. 007 * 008 * This program is free software; you can redistribute it and/or modify 009 * it under the terms of the GNU General Public License (GPLv2 only) 010 * or the terms of the GNU Lesser General Public License (LGPLv2.1 only) 011 * as published by the Free Software Foundation. 012 * 013 * This program is distributed in the hope that it will be useful, 014 * but WITHOUT ANY WARRANTY; without even the implied warranty of 015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 016 * GNU General Public License for more details. 017 * 018 * You should have received a copy of the GNU General Public License 019 * along with this program; if not, see <http://www.gnu.org/licenses>. 020 */ 021package com.unboundid.ldap.sdk; 022 023 024 025import java.io.Serializable; 026import java.util.ArrayList; 027import java.util.Arrays; 028import java.util.Collection; 029import java.util.Collections; 030import java.util.Comparator; 031import java.util.Iterator; 032import java.util.List; 033import java.util.SortedSet; 034import java.util.TreeSet; 035 036import com.unboundid.asn1.ASN1OctetString; 037import com.unboundid.ldap.matchingrules.MatchingRule; 038import com.unboundid.ldap.sdk.controls.SortKey; 039import com.unboundid.ldap.sdk.schema.Schema; 040import com.unboundid.util.ThreadSafety; 041import com.unboundid.util.ThreadSafetyLevel; 042 043import static com.unboundid.util.Debug.*; 044import static com.unboundid.util.StaticUtils.*; 045 046 047 048/** 049 * This class provides a mechanism for client-side entry sorting. Sorting may 050 * be based on attributes contained in the entry, and may also be based on the 051 * hierarchical location of the entry in the DIT. The sorting may be applied 052 * to any collection of entries, including the entries included in a 053 * {@link SearchResult} object. 054 * <BR><BR> 055 * This class provides a client-side alternative to the use of the 056 * {@link com.unboundid.ldap.sdk.controls.ServerSideSortRequestControl}. 057 * Client-side sorting is most appropriate for small result sets, as it requires 058 * all entries to be held in memory at the same time. It is a good alternative 059 * to server-side sorting when the overhead of sorting should be distributed 060 * across client systems rather than on the server, and in cases in which the 061 * target directory server does not support the use of the server-side sort 062 * request control. 063 * <BR><BR> 064 * For best results, a {@link Schema} object may be used to provide an 065 * indication as to which matching rules should be used to perform the ordering. 066 * If no {@code Schema} object is provided, then all ordering will be performed 067 * using case-ignore string matching. 068 * <BR><BR> 069 * <H2>Example</H2> 070 * The following example may be used to obtain a sorted set of search result 071 * entries, ordered first by sn and then by givenName, without consideration for 072 * hierarchy: 073 * <PRE> 074 * SearchResult searchResult = connection.search("dc=example,dc=com", 075 * SearchScope.SUB, Filter.createEqualityFilter("sn", "Smith")); 076 * 077 * EntrySorter entrySorter = new EntrySorter(false, 078 * new SortKey("sn"), new SortKey("givenName")); 079 * SortedSet<Entry> sortedEntries = 080 * entrySorter.sort(searchResult.getSearchEntries()); 081 * </PRE> 082 */ 083@ThreadSafety(level=ThreadSafetyLevel.COMPLETELY_THREADSAFE) 084public final class EntrySorter 085 implements Comparator<Entry>, Serializable 086{ 087 /** 088 * The serial version UID for this serializable class. 089 */ 090 private static final long serialVersionUID = 7606107105238612142L; 091 092 093 094 // Indicates whether entries should be sorted based on hierarchy. 095 private final boolean sortByHierarchy; 096 097 // The set of sort keys for attribute-level sorting. 098 private final List<SortKey> sortKeys; 099 100 // The schema to use to make the comparison, if available. 101 private final Schema schema; 102 103 104 105 /** 106 * Creates a new entry sorter that will sort entries based only on hierarchy. 107 * Superior entries (that is, entries closer to the root of the DIT) will be 108 * ordered before subordinate entries. Entries below the same parent will be 109 * sorted lexicographically based on their normalized DNs. 110 */ 111 public EntrySorter() 112 { 113 this(true, null, Collections.<SortKey>emptyList()); 114 } 115 116 117 118 /** 119 * Creates a new entry sorter with the provided information. 120 * 121 * @param sortByHierarchy Indicates whether entries should be sorted 122 * hierarchically, such that superior entries will 123 * be ordered before subordinate entries. 124 * @param sortKeys A list of sort keys that define the order in which 125 * attributes should be compared. It may be empty 126 * (but never {@code null}) if sorting should be done 127 * only based on hierarchy. 128 */ 129 public EntrySorter(final boolean sortByHierarchy, final SortKey... sortKeys) 130 { 131 this(sortByHierarchy, null, Arrays.asList(sortKeys)); 132 } 133 134 135 136 /** 137 * Creates a new entry sorter with the provided information. 138 * 139 * @param sortByHierarchy Indicates whether entries should be sorted 140 * hierarchically, such that superior entries will 141 * be ordered before subordinate entries. 142 * @param schema The schema to use to make the determination. It 143 * may be {@code null} if no schema is available. 144 * @param sortKeys A list of sort keys that define the order in which 145 * attributes should be compared. It may be empty 146 * (but never {@code null}) if sorting should be done 147 * only based on hierarchy. 148 */ 149 public EntrySorter(final boolean sortByHierarchy, final Schema schema, 150 final SortKey... sortKeys) 151 { 152 this(sortByHierarchy, schema, Arrays.asList(sortKeys)); 153 } 154 155 156 157 /** 158 * Creates a new entry sorter with the provided information. 159 * 160 * @param sortByHierarchy Indicates whether entries should be sorted 161 * hierarchically, such that superior entries will 162 * be ordered before subordinate entries. 163 * @param sortKeys A list of sort keys that define the order in which 164 * attributes should be compared. It may be empty or 165 * {@code null} if sorting should be done only based 166 * on hierarchy. 167 */ 168 public EntrySorter(final boolean sortByHierarchy, 169 final List<SortKey> sortKeys) 170 { 171 this(sortByHierarchy, null, sortKeys); 172 } 173 174 175 176 /** 177 * Creates a new entry sorter with the provided information. 178 * 179 * @param sortByHierarchy Indicates whether entries should be sorted 180 * hierarchically, such that superior entries will 181 * be ordered before subordinate entries. 182 * @param schema The schema to use to make the determination. It 183 * may be {@code null} if no schema is available. 184 * @param sortKeys A list of sort keys that define the order in which 185 * attributes should be compared. It may be empty or 186 * {@code null} if sorting should be done only based 187 * on hierarchy. 188 */ 189 public EntrySorter(final boolean sortByHierarchy, final Schema schema, 190 final List<SortKey> sortKeys) 191 { 192 this.sortByHierarchy = sortByHierarchy; 193 this.schema = schema; 194 195 if (sortKeys == null) 196 { 197 this.sortKeys = Collections.emptyList(); 198 } 199 else 200 { 201 this.sortKeys = 202 Collections.unmodifiableList(new ArrayList<SortKey>(sortKeys)); 203 } 204 } 205 206 207 208 /** 209 * Sorts the provided collection of entries according to the criteria defined 210 * in this entry sorter. 211 * 212 * @param entries The collection of entries to be sorted. 213 * 214 * @return A sorted set, ordered in accordance with this entry sorter. 215 */ 216 public SortedSet<Entry> sort(final Collection<? extends Entry> entries) 217 { 218 final TreeSet<Entry> entrySet = new TreeSet<Entry>(this); 219 entrySet.addAll(entries); 220 return entrySet; 221 } 222 223 224 225 /** 226 * Compares the provided entries to determine the order in which they should 227 * be placed in a sorted list. 228 * 229 * @param e1 The first entry to be compared. 230 * @param e2 The second entry to be compared. 231 * 232 * @return A negative value if the first entry should be ordered before the 233 * second, a positive value if the first entry should be ordered 234 * after the second, or zero if the entries should have an equivalent 235 * order. 236 */ 237 public int compare(final Entry e1, final Entry e2) 238 { 239 DN parsedDN1 = null; 240 DN parsedDN2 = null; 241 242 if (sortByHierarchy) 243 { 244 try 245 { 246 parsedDN1 = e1.getParsedDN(); 247 parsedDN2 = e2.getParsedDN(); 248 249 if (parsedDN1.isAncestorOf(parsedDN2, false)) 250 { 251 return -1; 252 } 253 else if (parsedDN2.isAncestorOf(parsedDN1, false)) 254 { 255 return 1; 256 } 257 } 258 catch (LDAPException le) 259 { 260 debugException(le); 261 } 262 } 263 264 for (final SortKey k : sortKeys) 265 { 266 final String attrName = k.getAttributeName(); 267 final Attribute a1 = e1.getAttribute(attrName); 268 final Attribute a2 = e2.getAttribute(attrName); 269 270 if ((a1 == null) || (! a1.hasValue())) 271 { 272 if ((a2 == null) || (! a2.hasValue())) 273 { 274 // Neither entry has the attribute. Continue on with the next 275 // attribute. 276 continue; 277 } 278 else 279 { 280 // The first entry does not have the attribute but the second does. 281 // The first entry should be ordered after the second. 282 return 1; 283 } 284 } 285 else 286 { 287 if ((a2 == null) || (! a2.hasValue())) 288 { 289 // The first entry has the attribute but the second does not. The 290 // first entry should be ordered before the second. 291 return -1; 292 } 293 } 294 295 296 final MatchingRule matchingRule = MatchingRule.selectOrderingMatchingRule( 297 attrName, k.getMatchingRuleID(), schema); 298 if (k.reverseOrder()) 299 { 300 // Find the largest value for each attribute, and pick the larger of the 301 // two. 302 ASN1OctetString v1 = null; 303 for (final ASN1OctetString s : a1.getRawValues()) 304 { 305 if (v1 == null) 306 { 307 v1 = s; 308 } 309 else 310 { 311 try 312 { 313 if (matchingRule.compareValues(s, v1) > 0) 314 { 315 v1 = s; 316 } 317 } 318 catch (LDAPException le) 319 { 320 debugException(le); 321 } 322 } 323 } 324 325 ASN1OctetString v2 = null; 326 for (final ASN1OctetString s : a2.getRawValues()) 327 { 328 if (v2 == null) 329 { 330 v2 = s; 331 } 332 else 333 { 334 try 335 { 336 if (matchingRule.compareValues(s, v2) > 0) 337 { 338 v2 = s; 339 } 340 } 341 catch (LDAPException le) 342 { 343 debugException(le); 344 } 345 } 346 } 347 348 try 349 { 350 final int value = matchingRule.compareValues(v2, v1); 351 if (value != 0) 352 { 353 return value; 354 } 355 } 356 catch (LDAPException le) 357 { 358 debugException(le); 359 } 360 } 361 else 362 { 363 // Find the smallest value for each attribute, and pick the larger of 364 // the two. 365 ASN1OctetString v1 = null; 366 for (final ASN1OctetString s : a1.getRawValues()) 367 { 368 if (v1 == null) 369 { 370 v1 = s; 371 } 372 else 373 { 374 try 375 { 376 if (matchingRule.compareValues(s, v1) < 0) 377 { 378 v1 = s; 379 } 380 } 381 catch (LDAPException le) 382 { 383 debugException(le); 384 } 385 } 386 } 387 388 ASN1OctetString v2 = null; 389 for (final ASN1OctetString s : a2.getRawValues()) 390 { 391 if (v2 == null) 392 { 393 v2 = s; 394 } 395 else 396 { 397 try 398 { 399 if (matchingRule.compareValues(s, v2) < 0) 400 { 401 v2 = s; 402 } 403 } 404 catch (LDAPException le) 405 { 406 debugException(le); 407 } 408 } 409 } 410 411 try 412 { 413 final int value = matchingRule.compareValues(v1, v2); 414 if (value != 0) 415 { 416 return value; 417 } 418 } 419 catch (LDAPException le) 420 { 421 debugException(le); 422 } 423 } 424 } 425 426 427 // If we've gotten here, then there is no difference in hierarchy or 428 // sort attributes. Compare the DNs as a last resort. 429 try 430 { 431 if (parsedDN1 == null) 432 { 433 parsedDN1 = e1.getParsedDN(); 434 } 435 436 if (parsedDN2 == null) 437 { 438 parsedDN2 = e2.getParsedDN(); 439 } 440 441 return parsedDN1.compareTo(parsedDN2); 442 } 443 catch (LDAPException le) 444 { 445 debugException(le); 446 final String lowerDN1 = toLowerCase(e1.getDN()); 447 final String lowerDN2 = toLowerCase(e2.getDN()); 448 return lowerDN1.compareTo(lowerDN2); 449 } 450 } 451 452 453 454 /** 455 * Retrieves a hash code for this entry sorter. 456 * 457 * @return A hash code for this entry sorter. 458 */ 459 @Override() 460 public int hashCode() 461 { 462 int hashCode = 0; 463 464 if (sortByHierarchy) 465 { 466 hashCode++; 467 } 468 469 for (final SortKey k : sortKeys) 470 { 471 if (k.reverseOrder()) 472 { 473 hashCode *= -31; 474 } 475 else 476 { 477 hashCode *= 31; 478 } 479 480 hashCode += toLowerCase(k.getAttributeName()).hashCode(); 481 } 482 483 return hashCode; 484 } 485 486 487 488 /** 489 * Indicates whether the provided object is equal to this entry sorter. 490 * 491 * @param o The object for which to make the determination. 492 * 493 * @return {@code true} if the provided object is equal to this entry sorter, 494 * or {@code false} if not. 495 */ 496 @Override() 497 public boolean equals(final Object o) 498 { 499 if (o == null) 500 { 501 return false; 502 } 503 504 if (o == this) 505 { 506 return true; 507 } 508 509 if (! (o instanceof EntrySorter)) 510 { 511 return false; 512 } 513 514 final EntrySorter s = (EntrySorter) o; 515 if (sortByHierarchy != s.sortByHierarchy) 516 { 517 return false; 518 } 519 520 return sortKeys.equals(s.sortKeys); 521 } 522 523 524 525 /** 526 * Retrieves a string representation of this entry sorter. 527 * 528 * @return A string representation of this entry sorter. 529 */ 530 @Override() 531 public String toString() 532 { 533 final StringBuilder buffer = new StringBuilder(); 534 toString(buffer); 535 return buffer.toString(); 536 } 537 538 539 540 /** 541 * Appends a string representation of this entry sorter to the provided 542 * buffer. 543 * 544 * @param buffer The buffer to which the string representation should be 545 * appended. 546 */ 547 public void toString(final StringBuilder buffer) 548 { 549 buffer.append("EntrySorter(sortByHierarchy="); 550 buffer.append(sortByHierarchy); 551 buffer.append(", sortKeys={"); 552 553 final Iterator<SortKey> iterator = sortKeys.iterator(); 554 while (iterator.hasNext()) 555 { 556 iterator.next().toString(buffer); 557 if (iterator.hasNext()) 558 { 559 buffer.append(", "); 560 } 561 } 562 563 buffer.append("})"); 564 } 565}