Author: tfmorris Date: 2008-04-24 10:32:36-0700 New Revision: 14454 Added: trunk/src/argouml-app/tests/org/argouml/uml/util/TestPathComparator.java (contents, props changed) Modified: trunk/src/argouml-app/src/org/argouml/uml/util/PathComparator.java
Log: Make comparison stable and more efficient. Add tests. Modified: trunk/src/argouml-app/src/org/argouml/uml/util/PathComparator.java Url: http://argouml.tigris.org/source/browse/argouml/trunk/src/argouml-app/src/org/argouml/uml/util/PathComparator.java?view=diff&rev=14454&p1=trunk/src/argouml-app/src/org/argouml/uml/util/PathComparator.java&p2=trunk/src/argouml-app/src/org/argouml/uml/util/PathComparator.java&r1=14453&r2=14454 ============================================================================== --- trunk/src/argouml-app/src/org/argouml/uml/util/PathComparator.java (original) +++ trunk/src/argouml-app/src/org/argouml/uml/util/PathComparator.java 2008-04-24 10:32:36-0700 @@ -1,5 +1,5 @@ // $Id$ -// Copyright (c) 2007 The Regents of the University of California. All +// Copyright (c) 2008 The Regents of the University of California. All // Rights Reserved. Permission to use, copy, modify, and distribute this // software and its documentation without fee, and without a written // agreement is hereby granted, provided that the above copyright notice @@ -41,6 +41,16 @@ */ public class PathComparator implements Comparator { + private Collator collator; + + /** + * Construct a PathComparator. + */ + public PathComparator() { + collator = Collator.getInstance(); + collator.setStrength(Collator.PRIMARY); + } + /** * Compare two UML elements names, ignoring case, using names from the path * as tie breakers. @@ -54,28 +64,44 @@ if (o1.equals(o2)) { return 0; } - // Elements are collated first by name and then by - // their enclosing path to distinguish them - List<String> path1 = Model.getModelManagementHelper().getPathList(o1); - Collections.reverse(path1); - List<String> path2 = Model.getModelManagementHelper().getPathList(o2); - Collections.reverse(path2); - return compareStringLists(path1, path2); + // Elements are collated first by name hoping for a quick solution + String name1, name2; + try { + name1 = Model.getFacade().getName(o1); + name2 = Model.getFacade().getName(o2); + } catch (IllegalArgumentException e) { + throw new ClassCastException("Model element required"); + } + int comparison = collator.compare(name1, name2); + if (comparison != 0) { + return comparison; + } else { + // and then by their enclosing path to fully distinguish them + return comparePaths(o1, o2); + } + } /* - * Compare two lists of strings using a primary strength text collator. + * Compare path of two elements in reverse order (inner to outer) + * using a primary strength text collator. * This will collate e, E, é, É together, but not eliminate non-identical * strings which collate in the same place. * * @return equivalent of list1.compareTo(list2) */ - private int compareStringLists(List<String> list1, List<String> list2) { - Collator collator = Collator.getInstance(); - collator.setStrength(Collator.PRIMARY); - Iterator<String> i2 = list2.iterator(); - Iterator<String> i1 = list1.iterator(); - boolean caseDiffers = false; + private int comparePaths(Object o1, Object o2) { + + List<String> path1 = + Model.getModelManagementHelper().getPathList(o1); + Collections.reverse(path1); + List<String> path2 = + Model.getModelManagementHelper().getPathList(o2); + Collections.reverse(path2); + + Iterator<String> i2 = path2.iterator(); + Iterator<String> i1 = path1.iterator(); + int caseSensitiveComparison = 0; while (i2.hasNext()) { String name2 = i2.next(); if (!i1.hasNext()) { @@ -89,23 +115,28 @@ if (comparison != 0) { return comparison; } - caseDiffers = caseDiffers | !(name1.equals(name2)); + // Keep track of first non-equal comparison to use in case the + // case-insensitive comparisons all end up equal + if (caseSensitiveComparison == 0) { + caseSensitiveComparison = name1.compareTo(name2); + } } if (i2.hasNext()) { return 1; } // If the strings differed only in non-primary characteristics at - // some point (case, accent, etc) pick an arbitrary collating order. - // We don't call them equal to keep them from being merged in the list. - if (caseDiffers) { - return 1; + // some point (case, accent, etc) pick an arbitrary, but stable, + // collating order. + if (caseSensitiveComparison != 0) { + return caseSensitiveComparison; } // It's illegal in UML to have multiple elements in a namespace with // the same name, but if it happens, keep them distinct so the user - // has a chance of catching the error. Pick an arbitrary collating - // order. - // Note: this may make the collating order unstable. - return 1; + // has a chance of catching the error. Pick an arbitrary, but stable, + // collating order. + // We don't call them equal because otherwise one will get eliminated + // from the TreeSet where this comparator is used. + return o1.toString().compareTo(o2.toString()); } } Added: trunk/src/argouml-app/tests/org/argouml/uml/util/TestPathComparator.java Url: http://argouml.tigris.org/source/browse/argouml/trunk/src/argouml-app/tests/org/argouml/uml/util/TestPathComparator.java?view=auto&rev=14454 ============================================================================== --- (empty file) +++ trunk/src/argouml-app/tests/org/argouml/uml/util/TestPathComparator.java 2008-04-24 10:32:36-0700 @@ -0,0 +1,106 @@ +// $Id$ +// Copyright (c) 2008 The Regents of the University of California. All +// Rights Reserved. Permission to use, copy, modify, and distribute this +// software and its documentation without fee, and without a written +// agreement is hereby granted, provided that the above copyright notice +// and this paragraph appear in all copies. This software program and +// documentation are copyrighted by The Regents of the University of +// California. The software program and documentation are supplied "AS +// IS", without any accompanying services from The Regents. The Regents +// does not warrant that the operation of the program will be +// uninterrupted or error-free. The end-user understands that the program +// was developed for research purposes and is advised not to rely +// exclusively on the program for any reason. IN NO EVENT SHALL THE +// UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, +// SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS, +// ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF +// THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF +// SUCH DAMAGE. THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY +// WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF +// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE +// PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF +// CALIFORNIA HAS NO OBLIGATIONS TO PROVIDE MAINTENANCE, SUPPORT, +// UPDATES, ENHANCEMENTS, OR MODIFICATIONS. + +package org.argouml.uml.util; + +import java.util.Comparator; + +import junit.framework.TestCase; + +import org.argouml.model.InitializeModel; +import org.argouml.model.Model; + +/** + * Testing the PathComparator class. + * + * @author Tom Morris <[EMAIL PROTECTED]> + */ +public class TestPathComparator extends TestCase { + + + @Override + protected void setUp() throws Exception { + super.setUp(); + InitializeModel.initializeDefault(); + } + + /** + * Test the PathComparator to make sure that it returns expected results + * as well as conforms to the contract for Comparator. + */ + public void testComparator() { + Comparator comp = new PathComparator(); + Object root = Model.getModelManagementFactory().createModel(); + setName(root, "rootModel"); + Object unnamed1 = Model.getCoreFactory().buildClass(root); + Object unnamed2 = Model.getCoreFactory().buildClass(root); + Object a = Model.getCoreFactory().buildClass("a", root); + Object a1 = Model.getCoreFactory().buildClass("a", root); + Object b = Model.getCoreFactory().buildClass("b", root); + Object b1 = Model.getCoreFactory().buildClass("B", root); + Object c = Model.getCoreFactory().buildClass("c", root); + + Object ba = Model.getCoreFactory().buildClass("b", a); + Object bc = Model.getCoreFactory().buildClass("b", c); + + assertFalse("Two different unnamed elements should not be equal", + comp.compare(unnamed1, unnamed2) == 0); + assertEquals("Unnamed elements should collate before named", -1, + comp.compare(unnamed1, a)); + assertEquals("Unnamed elements should collate before named", 1, + comp.compare(a, unnamed1)); + + assertFalse("Two different elements with same name should not be equal", + comp.compare(a, a1) == 0); + + assertEquals("Comparison not stable for elements with same name", + comp.compare(a, a1), -1 * comp.compare(a1, a)); + + assertEquals("Shorter paths should collate before longer paths", 1, + comp.compare(b, ba)); + assertEquals("Shorter paths should collate before longer paths", -1, + comp.compare(ba, b)); + + assertEquals("Comparison failed on container", -1, + comp.compare(ba, bc)); + assertEquals("Comparison failed on container", 1, + comp.compare(bc, ba)); + + assertEquals("Comparator results should match String.compareTo", + comp.compare(b, b1), + Model.getFacade().getName(b).compareTo( + Model.getFacade().getName(b1))); + assertEquals("Comparator results should match String.compareTo", + comp.compare(b1, b), + Model.getFacade().getName(b1).compareTo( + Model.getFacade().getName(b))); + Model.getUmlFactory().delete(root); + } + + + private void setName(Object elem, String name) { + Model.getCoreHelper().setName(elem, name); + } + +} --------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
