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