001/* 002 * Copyright 2009-2018 Ping Identity Corporation 003 * All Rights Reserved. 004 */ 005/* 006 * Copyright (C) 2015-2018 Ping Identity Corporation 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.unboundidds.examples; 022 023 024 025import java.io.Serializable; 026import java.util.Arrays; 027import java.util.Comparator; 028import java.util.Iterator; 029import java.util.TreeSet; 030 031import com.unboundid.ldap.sdk.Filter; 032import com.unboundid.util.NotMutable; 033import com.unboundid.util.StaticUtils; 034import com.unboundid.util.ThreadSafety; 035import com.unboundid.util.ThreadSafetyLevel; 036import com.unboundid.util.Validator; 037 038 039 040/** 041 * This class provides a comparator that may be used to define a relative order 042 * for search filters. The filter order will be based first on the filter type 043 * (in the following order: AND, OR, NOT, equality, substring, 044 * greater-or-equal, less-or-equal, presence, approximate match, extensible 045 * match), then based on the attribute name, and then by the assertion value. 046 * For AND and OR filters, with all other things equal, a filter with fewer 047 * components will be ordered before one with more components. For a substring 048 * filter with all other things equal, then a filter missing a substring element 049 * will be ordered before one with that element, and one with fewer subAny 050 * elements will be ordered before one with more subAny elements. For an 051 * extensible match filter with all other things being equal, a filter without 052 * an element will be ordered before one with that element. 053 * <BR> 054 * <BLOCKQUOTE> 055 * <B>NOTE:</B> This class, and other classes within the 056 * {@code com.unboundid.ldap.sdk.unboundidds} package structure, are only 057 * supported for use against Ping Identity, UnboundID, and 058 * Nokia/Alcatel-Lucent 8661 server products. These classes provide support 059 * for proprietary functionality or for external specifications that are not 060 * considered stable or mature enough to be guaranteed to work in an 061 * interoperable way with other types of LDAP servers. 062 * </BLOCKQUOTE> 063 */ 064@NotMutable() 065@ThreadSafety(level=ThreadSafetyLevel.COMPLETELY_THREADSAFE) 066public final class FilterComparator 067 implements Comparator<Filter>, Serializable 068{ 069 /** 070 * The singleton instance of this comparator. 071 */ 072 private static final FilterComparator INSTANCE = new FilterComparator(); 073 074 075 076 /** 077 * The serial version UID for this serializable class. 078 */ 079 private static final long serialVersionUID = 7637416445464620770L; 080 081 082 083 /** 084 * Creates a new instance of this filter comparator. 085 */ 086 private FilterComparator() 087 { 088 // No implementation is required. 089 } 090 091 092 093 /** 094 * Retrieves the singleton instance of this filter comparator. 095 * 096 * @return The singleton instance of this filter comparator. 097 */ 098 public static FilterComparator getInstance() 099 { 100 return INSTANCE; 101 } 102 103 104 105 /** 106 * Determines a relative order for the provided filter objects. 107 * 108 * @param f1 The first filter for which to make the determination. 109 * It must not be {@code null} 110 * @param f2 The second filter for which to make the determination. 111 * It must not be {@code null} 112 * 113 * @return A negative value if the first filter should be ordered before the 114 * second, a positive value if the first filter should be ordered 115 * after the second, or zero if there is no difference in their 116 * relative orders. 117 */ 118 @Override() 119 public int compare(final Filter f1, final Filter f2) 120 { 121 if (f1 == f2) 122 { 123 return 0; 124 } 125 126 Validator.ensureNotNull(f1, f2); 127 128 final byte type1 = f1.getFilterType(); 129 final byte type2 = f2.getFilterType(); 130 131 if (type1 != type2) 132 { 133 return ((type1 & 0x1F) - (type2 & 0x1F)); 134 } 135 136 final String name1 = StaticUtils.toLowerCase(f1.getAttributeName()); 137 final String name2 = StaticUtils.toLowerCase(f2.getAttributeName()); 138 if ((name1 != null) && (name2 != null)) 139 { 140 final int cmpValue = name1.compareTo(name2); 141 if (cmpValue != 0) 142 { 143 return cmpValue; 144 } 145 } 146 147 final byte[] value1 = f1.getAssertionValueBytes(); 148 if (value1 != null) 149 { 150 final byte[] value2 = f2.getAssertionValueBytes(); 151 final int cmpValue = compare(value1, value2); 152 if (cmpValue != 0) 153 { 154 return cmpValue; 155 } 156 } 157 158 switch (type1) 159 { 160 case Filter.FILTER_TYPE_AND: 161 case Filter.FILTER_TYPE_OR: 162 return compareANDOrOR(f1, f2); 163 164 case Filter.FILTER_TYPE_NOT: 165 return compare(f1.getNOTComponent(), f2.getNOTComponent()); 166 167 case Filter.FILTER_TYPE_PRESENCE: 168 case Filter.FILTER_TYPE_EQUALITY: 169 case Filter.FILTER_TYPE_GREATER_OR_EQUAL: 170 case Filter.FILTER_TYPE_LESS_OR_EQUAL: 171 case Filter.FILTER_TYPE_APPROXIMATE_MATCH: 172 // The necessary processing for these types has already been done. 173 return 0; 174 175 case Filter.FILTER_TYPE_SUBSTRING: 176 return compareSubstring(f1, f2); 177 178 case Filter.FILTER_TYPE_EXTENSIBLE_MATCH: 179 return compareExtensible(f1, f2); 180 181 default: 182 // This should never happen. 183 return 0; 184 } 185 } 186 187 188 189 /** 190 * Performs a comparison of the contents of AND or OR filters. 191 * 192 * @param f1 The first filter for which to make the determination. 193 * @param f2 The second filter for which to make the determination. 194 * 195 * @return A negative value if the first filter should be ordered before the 196 * second, a positive value if the first filter should be ordered 197 * after the second, or zero if there is no difference in their 198 * relative orders. 199 */ 200 private static int compareANDOrOR(final Filter f1, final Filter f2) 201 { 202 final TreeSet<Filter> set1 = new TreeSet<>(INSTANCE); 203 final TreeSet<Filter> set2 = new TreeSet<>(INSTANCE); 204 205 set1.addAll(Arrays.asList(f1.getComponents())); 206 set2.addAll(Arrays.asList(f2.getComponents())); 207 208 final Iterator<Filter> iterator1 = set1.iterator(); 209 final Iterator<Filter> iterator2 = set2.iterator(); 210 while (true) 211 { 212 final Filter comp1; 213 if (iterator1.hasNext()) 214 { 215 comp1 = iterator1.next(); 216 } 217 else if (iterator2.hasNext()) 218 { 219 return -1; 220 } 221 else 222 { 223 return 0; 224 } 225 226 final Filter comp2; 227 if (iterator2.hasNext()) 228 { 229 comp2 = iterator2.next(); 230 } 231 else 232 { 233 return 1; 234 } 235 236 final int compValue = INSTANCE.compare(comp1, comp2); 237 if (compValue != 0) 238 { 239 return compValue; 240 } 241 } 242 } 243 244 245 246 /** 247 * Performs a comparison of the contents of substring filters. 248 * 249 * @param f1 The first filter for which to make the determination. 250 * @param f2 The second filter for which to make the determination. 251 * 252 * @return A negative value if the first filter should be ordered before the 253 * second, a positive value if the first filter should be ordered 254 * after the second, or zero if there is no difference in their 255 * relative orders. 256 */ 257 private static int compareSubstring(final Filter f1, final Filter f2) 258 { 259 final byte[] sI1 = f1.getSubInitialBytes(); 260 final byte[] sI2 = f2.getSubInitialBytes(); 261 if (sI1 == null) 262 { 263 if (sI2 != null) 264 { 265 return -1; 266 } 267 } 268 else if (sI2 == null) 269 { 270 return 1; 271 } 272 else 273 { 274 final int cmpValue = compare(sI1, sI2); 275 if (cmpValue != 0) 276 { 277 return cmpValue; 278 } 279 } 280 281 final byte[][] sA1 = f1.getSubAnyBytes(); 282 final byte[][] sA2 = f2.getSubAnyBytes(); 283 if (sA1.length == 0) 284 { 285 if (sA2.length > 0) 286 { 287 return -1; 288 } 289 } 290 else if (sA2.length == 0) 291 { 292 return 1; 293 } 294 else 295 { 296 final int minLength = Math.min(sA1.length, sA2.length); 297 for (int i=0; i < minLength; i++) 298 { 299 final int cmpValue = compare(sA1[i], sA2[i]); 300 if (cmpValue != 0) 301 { 302 return cmpValue; 303 } 304 } 305 306 if (sA1.length < sA2.length) 307 { 308 return -1; 309 } 310 else if (sA2.length < sA1.length) 311 { 312 return 1; 313 } 314 } 315 316 final byte[] sF1 = f1.getSubFinalBytes(); 317 final byte[] sF2 = f2.getSubFinalBytes(); 318 if (sF1 == null) 319 { 320 if (sF2 != null) 321 { 322 return -1; 323 } 324 else 325 { 326 return 0; 327 } 328 } 329 else if (sF2 == null) 330 { 331 return 1; 332 } 333 else 334 { 335 return compare(sF1, sF2); 336 } 337 } 338 339 340 341 /** 342 * Performs a comparison of the contents of substring filters. 343 * 344 * @param f1 The first filter for which to make the determination. 345 * @param f2 The second filter for which to make the determination. 346 * 347 * @return A negative value if the first filter should be ordered before the 348 * second, a positive value if the first filter should be ordered 349 * after the second, or zero if there is no difference in their 350 * relative orders. 351 */ 352 private static int compareExtensible(final Filter f1, final Filter f2) 353 { 354 final String name1 = f1.getAttributeName(); 355 final String name2 = f2.getAttributeName(); 356 if (name1 == null) 357 { 358 if (name2 != null) 359 { 360 return -1; 361 } 362 } 363 else if (name2 == null) 364 { 365 return 1; 366 } 367 368 final String mr1 = f1.getMatchingRuleID(); 369 final String mr2 = f2.getMatchingRuleID(); 370 if (mr1 == null) 371 { 372 if (mr2 != null) 373 { 374 return -1; 375 } 376 } 377 else if (mr2 == null) 378 { 379 return 1; 380 } 381 else 382 { 383 final int cmpValue = mr1.compareTo(mr2); 384 if (cmpValue != 0) 385 { 386 return cmpValue; 387 } 388 } 389 390 if (f1.getDNAttributes()) 391 { 392 if (f2.getDNAttributes()) 393 { 394 return 0; 395 } 396 else 397 { 398 return 1; 399 } 400 } 401 else if (f2.getDNAttributes()) 402 { 403 return -1; 404 } 405 else 406 { 407 return 0; 408 } 409 } 410 411 412 413 /** 414 * Performs a comparison of the contents of the provided byte arrays. 415 * 416 * @param a1 The first array to be compared. 417 * @param a2 The second array to be compared. 418 * 419 * @return An integer value denoting the comparison value. 420 */ 421 private static int compare(final byte[] a1, final byte[] a2) 422 { 423 final int length = Math.min(a1.length, a2.length); 424 425 for (int i=0; i < length; i++) 426 { 427 final int b1 = 0xFF & a1[i]; 428 final int b2 = 0xFF & a2[i]; 429 if (b1 != b2) 430 { 431 return b1 - b2; 432 } 433 } 434 435 return (a1.length - a2.length); 436 } 437 438 439 440 /** 441 * Retrieves a hash code for this filter comparator. 442 * 443 * @return A hash code for this filter comparator. 444 */ 445 @Override() 446 public int hashCode() 447 { 448 return 0; 449 } 450 451 452 453 /** 454 * Indicates whether the provided object is equal to this filter comparator. 455 * 456 * @param o The object for which to make the determination. 457 * 458 * @return {@code true} if the provided object is equal to this filter 459 * comparator, or {@code false} if not. 460 */ 461 @Override() 462 public boolean equals(final Object o) 463 { 464 return ((o != null) && (o instanceof FilterComparator)); 465 } 466}