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