001/* Copyright (C) 2013 TU Dortmund 002 * This file is part of AutomataLib, http://www.automatalib.net/. 003 * 004 * AutomataLib is free software; you can redistribute it and/or 005 * modify it under the terms of the GNU Lesser General Public 006 * License version 3.0 as published by the Free Software Foundation. 007 * 008 * AutomataLib is distributed in the hope that it will be useful, 009 * but WITHOUT ANY WARRANTY; without even the implied warranty of 010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 011 * Lesser General Public License for more details. 012 * 013 * You should have received a copy of the GNU Lesser General Public 014 * License along with AutomataLib; if not, see 015 * http://www.gnu.de/documents/lgpl.en.html. 016 */ 017package net.automatalib.commons.util.comparison; 018 019import java.util.Comparator; 020import java.util.Iterator; 021 022/** 023 * Various methods for dealing with the comparison of objects. 024 * 025 * @author Malte Isberner <malte.isberner@gmail.com> 026 * 027 */ 028public abstract class CmpUtil { 029 030 /** 031 * Enum for controlling which rank is assigned to a <code>null</code> 032 * element when using a safe comparator 033 * ({@link CmpUtil#safeComparator(Comparator, NullOrdering)}). 034 * 035 * @author Malte Isberner <malte.isberner@cs.uni-dortmund.de> 036 * 037 */ 038 public static enum NullOrdering { 039 /** 040 * <code>null</code> elements are smaller than all regular elements. 041 */ 042 MIN(-1), 043 /** 044 * <code>null</code> elements are bigger than all regular elements. 045 */ 046 MAX(1); 047 048 /** 049 * Value that determines the result of the comparison, when 050 * only the first value is a <code>null</code> value. 051 */ 052 public final int firstNullResult; 053 054 private NullOrdering(int firstNullResult) { 055 this.firstNullResult = firstNullResult; 056 } 057 } 058 059 060 /* 061 * Prevent inheritance. 062 */ 063 private CmpUtil() { 064 } 065 066 067 /** 068 * Lexicographically compares two {@link Iterable}s. Comparison of the 069 * elements is done using the specified comparator. 070 * 071 * @param o1 the first iterable. 072 * @param o2 the second iterable. 073 * @param elemComparator the comparator. 074 * @return <code>< 0</code> iff o1 is lexicographically smaller, 075 * <code>0</code> if o1 equals o2 and <code>> 0</code> otherwise. 076 */ 077 public static <U> int lexCompare(Iterable<? extends U> o1, Iterable<? extends U> o2, Comparator<U> elemComparator) { 078 Iterator<? extends U> it1 = o1.iterator(), it2 = o2.iterator(); 079 080 while(it1.hasNext() && it2.hasNext()) { 081 int cmp = elemComparator.compare(it1.next(), it2.next()); 082 if(cmp != 0) 083 return cmp; 084 } 085 086 if(it1.hasNext()) 087 return 1; 088 else if(it2.hasNext()) 089 return -1; 090 return 0; 091 } 092 093 /** 094 * Lexicographically compares two {@link Iterable}s, whose element types 095 * are comparable. 096 * @param o1 097 * @param o2 098 * @return 099 */ 100 public static <U extends Comparable<? super U>> int lexCompare(Iterable<? extends U> o1, Iterable<? extends U> o2) { 101 Iterator<? extends U> it1 = o1.iterator(), it2 = o2.iterator(); 102 103 while(it1.hasNext() && it2.hasNext()) { 104 int cmp = it1.next().compareTo(it2.next()); 105 if(cmp != 0) 106 return cmp; 107 } 108 109 if(it1.hasNext()) 110 return 1; 111 else if(it2.hasNext()) 112 return -1; 113 return 0; 114 } 115 116 /** 117 * Retrieves a lexicographical comparator for the given type. 118 * @param elemComp the comparator to use for comparing the elements. 119 * @return a comparator for comparing objects of type <code>T</code>. 120 */ 121 public static <T extends Iterable<U>,U> Comparator<T> lexComparator(Comparator<U> elemComp) { 122 return new LexComparator<T,U>(elemComp); 123 } 124 125 /** 126 * Retrieves a lexicographical comparator for the given type, which has 127 * to be an {@link Iterable} of {@link Comparable} types. 128 * @return the lexicographical comparator. 129 */ 130 public static <U extends Comparable<U>,T extends Iterable<U>> Comparator<T> lexComparator() { 131 return NaturalLexComparator.<T,U>getInstance(); 132 } 133 134 /** 135 * Retrieves a <i>safe</i> comparator, which can handle <code>null</code> 136 * element values. 137 * Whether <code>null</code> values are smaller or bigger than regular 138 * values is controlled by the {@link NullOrdering} parameter. 139 * @param <T> original element class. 140 * @param baseComp the basic comparator. 141 * @param nullOrd the ordering policy for <code>null</code> values. 142 * @return a safe comparator using the specified underlying comparator. 143 */ 144 public static <T> Comparator<T> safeComparator(Comparator<T> baseComp, NullOrdering nullOrd) { 145 return new SafeComparator<T>(baseComp, nullOrd); 146 } 147 148 149 150 /** 151 * Retrieves a {@link Comparator} that compares elements according to their 152 * natural ordering (i.e., they have to implement the {@link Comparable} 153 * interface. 154 * 155 * If this comparator is used on elements that don't implement this 156 * interface, this may result in a {@link ClassCastException}. 157 * 158 * @param <T> element class. 159 * @return the natural ordering comparator. 160 */ 161 public static <T extends Comparable<T>> Comparator<T> naturalOrderingComparator() { 162 return NaturalOrderingComparator.getInstance(); 163 } 164}