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>&lt; 0</code> iff o1 is lexicographically smaller,
075         * <code>0</code> if o1 equals o2 and <code>&gt; 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}