You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by se...@apache.org on 2013/12/03 22:01:38 UTC
svn commit: r1547587 - in /directory/shared/trunk/ldap/model/src:
main/java/org/apache/directory/api/ldap/model/schema/SchemaObjectSorter.java
test/java/org/apache/directory/api/ldap/model/schema/SchemaObjectSorterTest.java
Author: seelmann
Date: Tue Dec 3 21:01:38 2013
New Revision: 1547587
URL: http://svn.apache.org/r1547587
Log:
Add functions to hierarchically order attribute types and object classes (needed for DIRSTUDIO-958)
Added:
directory/shared/trunk/ldap/model/src/main/java/org/apache/directory/api/ldap/model/schema/SchemaObjectSorter.java
directory/shared/trunk/ldap/model/src/test/java/org/apache/directory/api/ldap/model/schema/SchemaObjectSorterTest.java
Added: directory/shared/trunk/ldap/model/src/main/java/org/apache/directory/api/ldap/model/schema/SchemaObjectSorter.java
URL: http://svn.apache.org/viewvc/directory/shared/trunk/ldap/model/src/main/java/org/apache/directory/api/ldap/model/schema/SchemaObjectSorter.java?rev=1547587&view=auto
==============================================================================
--- directory/shared/trunk/ldap/model/src/main/java/org/apache/directory/api/ldap/model/schema/SchemaObjectSorter.java (added)
+++ directory/shared/trunk/ldap/model/src/main/java/org/apache/directory/api/ldap/model/schema/SchemaObjectSorter.java Tue Dec 3 21:01:38 2013
@@ -0,0 +1,240 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.api.ldap.model.schema;
+
+
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.TreeMap;
+
+import org.apache.directory.api.ldap.model.schema.AttributeType;
+import org.apache.directory.api.ldap.model.schema.ObjectClass;
+import org.apache.directory.api.ldap.model.schema.SchemaObject;
+
+
+/**
+ * Various utility methods for sorting schema objects.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class SchemaObjectSorter
+{
+
+ /**
+ * Gets an hierarchical ordered {@link Iterable} of the given {@link AttributeType}s.
+ * In other words parent {@link AttributeType}s are returned before child {@link AttributeType}s.
+ * @param attributeTypes list of attribute types to order
+ * @return the hierarchical ordered attribute types
+ */
+ public static Iterable<AttributeType> hierarchicalOrdered( List<AttributeType> attributeTypes )
+ {
+ return new SchemaObjectIterable<AttributeType>( attributeTypes, new ReferenceCallback<AttributeType>()
+ {
+ @Override
+ public Collection<String> getSuperiorOids( AttributeType at )
+ {
+ return Collections.singleton( at.getSuperiorOid() );
+ }
+ } );
+ }
+
+
+ /**
+ * Gets an hierarchical ordered {@link Iterable} of the given {@link ObjectClass}es.
+ * In other words parent {@link ObjectClass}es are returned before child {@link ObjectClass}es.
+ * @param objectClasses list of object classes to order
+ * @return the hierarchical ordered object classes
+ */
+ public static Iterable<ObjectClass> sortObjectClasses( List<ObjectClass> objectClasses )
+ {
+ return new SchemaObjectIterable<ObjectClass>( objectClasses, new ReferenceCallback<ObjectClass>()
+ {
+ @Override
+ public Collection<String> getSuperiorOids( ObjectClass oc )
+ {
+ return oc.getSuperiorOids();
+ }
+ } );
+ }
+
+ private static interface ReferenceCallback<T extends SchemaObject>
+ {
+
+ Collection<String> getSuperiorOids( T schemaObject );
+
+ }
+
+ private static class SchemaObjectIterable<T extends SchemaObject> implements Iterable<T>
+ {
+
+ private final List<T> schemaObjects;
+ private final ReferenceCallback<T> callback;
+
+
+ private SchemaObjectIterable( List<T> schemaObjects, ReferenceCallback<T> callback )
+ {
+ this.schemaObjects = schemaObjects;
+ this.callback = callback;
+ }
+
+
+ @Override
+ public Iterator<T> iterator()
+ {
+ return new SchemaObjectIterator<T>( schemaObjects, callback );
+ }
+
+ }
+
+ private static class SchemaObjectIterator<T extends SchemaObject> implements Iterator<T>
+ {
+ private final List<T> schemaObjects;
+ private final ReferenceCallback<T> callback;
+
+ private final Map<String, String> oid2numericOid;
+ private final Map<String, T> numericOid2schemaObject;
+
+ private int loopCount;
+ private Iterator<Entry<String, T>> schemaObjectIterator;
+
+
+ private SchemaObjectIterator( List<T> schemaObjects, ReferenceCallback<T> callback )
+ {
+ this.schemaObjects = schemaObjects;
+ this.callback = callback;
+
+ this.oid2numericOid = new HashMap<String, String>();
+ this.numericOid2schemaObject = new TreeMap<String, T>();
+ this.loopCount = 0;
+
+ for ( T schemaObject : schemaObjects )
+ {
+ String oid = schemaObject.getOid();
+ oid2numericOid.put( oid.toLowerCase(), oid );
+ for ( String name : schemaObject.getNames() )
+ {
+ oid2numericOid.put( name.toLowerCase(), oid );
+ }
+ numericOid2schemaObject.put( oid, schemaObject );
+ }
+ }
+
+
+ @Override
+ public boolean hasNext()
+ {
+ return !numericOid2schemaObject.isEmpty();
+ }
+
+
+ @Override
+ public T next()
+ {
+ while ( !maxLoopCountReached() )
+ {
+ Iterator<Entry<String, T>> iterator = getIterator();
+
+ while ( iterator.hasNext() )
+ {
+ Entry<String, T> entry = iterator.next();
+ T schemaObject = entry.getValue();
+
+ Collection<String> superiorOids = callback.getSuperiorOids( schemaObject );
+
+ // schema object has no superior
+ if ( superiorOids == null )
+ {
+ iterator.remove();
+ return schemaObject;
+ }
+
+ boolean allSuperiorsProcessed = true;
+
+ for ( String superiorOid : superiorOids )
+ {
+ String superiorNumeridOid = oid2numericOid.get( superiorOid );
+
+ // AT's superior is not within the processed AT list
+ if ( superiorNumeridOid == null )
+ {
+ continue;
+ }
+
+ T superiorSchemaObject = numericOid2schemaObject.get( superiorNumeridOid );
+
+ // AT's superior was already removed
+ if ( superiorSchemaObject == null )
+ {
+ continue;
+ }
+
+ allSuperiorsProcessed = false;
+ break;
+ }
+
+ if ( allSuperiorsProcessed )
+ {
+ iterator.remove();
+ return schemaObject;
+ }
+ }
+ }
+ throw new IllegalStateException( "Loop detected: " + numericOid2schemaObject.values() );
+ }
+
+
+ private Iterator<Entry<String, T>> getIterator()
+ {
+ if ( schemaObjectIterator != null && schemaObjectIterator.hasNext() )
+ {
+ return schemaObjectIterator;
+ }
+
+ if ( !maxLoopCountReached() )
+ {
+ schemaObjectIterator = numericOid2schemaObject.entrySet().iterator();
+ loopCount++;
+ return schemaObjectIterator;
+ }
+
+ throw new IllegalStateException( "Loop detected: " + numericOid2schemaObject.values() );
+ }
+
+
+ private boolean maxLoopCountReached()
+ {
+ return loopCount > schemaObjects.size();
+ }
+
+
+ @Override
+ public void remove()
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ }
+
+}
Added: directory/shared/trunk/ldap/model/src/test/java/org/apache/directory/api/ldap/model/schema/SchemaObjectSorterTest.java
URL: http://svn.apache.org/viewvc/directory/shared/trunk/ldap/model/src/test/java/org/apache/directory/api/ldap/model/schema/SchemaObjectSorterTest.java?rev=1547587&view=auto
==============================================================================
--- directory/shared/trunk/ldap/model/src/test/java/org/apache/directory/api/ldap/model/schema/SchemaObjectSorterTest.java (added)
+++ directory/shared/trunk/ldap/model/src/test/java/org/apache/directory/api/ldap/model/schema/SchemaObjectSorterTest.java Tue Dec 3 21:01:38 2013
@@ -0,0 +1,234 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.api.ldap.model.schema;
+
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+
+import org.junit.Test;
+
+
+/**
+ * Tests for SchemaObjectSorter.
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ */
+public class SchemaObjectSorterTest
+{
+
+ private void addAttributeType( List<AttributeType> attributeTypes, String oid, String name, String superiorOid )
+ {
+ MutableAttributeType at = new MutableAttributeType( oid );
+ at.setNames( name );
+ at.setSuperiorOid( superiorOid );
+ attributeTypes.add( at );
+ }
+
+
+ @Test
+ public void testSortAttributeTypesAlreadySorted()
+ {
+ List<AttributeType> attributeTypes = new ArrayList<AttributeType>();
+ addAttributeType( attributeTypes, "1.1.1", "att1", null );
+ addAttributeType( attributeTypes, "1.1.2", "att2", "att1" );
+ addAttributeType( attributeTypes, "1.1.3", "att3", "att2" );
+ addAttributeType( attributeTypes, "1.1.4", "att4", "att3" );
+ addAttributeType( attributeTypes, "1.1.5", "att5", "att1" );
+ addAttributeType( attributeTypes, "1.1.6", "att6", null );
+ addAttributeType( attributeTypes, "1.1.7", "att7", "other" );
+
+ Iterable<AttributeType> sorted = SchemaObjectSorter.hierarchicalOrdered( attributeTypes );
+ assertHierarchicalOrderAT( sorted );
+ }
+
+
+ @Test
+ public void testSortAttributeTypesShuffled()
+ {
+ List<String> oids = Arrays.asList( "1.1.1", "1.1.2", "1.1.3", "1.1.4", "1.1.5", "1.1.6", "1.1.7" );
+ for ( int i = 0; i < 1000; i++ )
+ {
+ Collections.shuffle( oids );
+ Iterator<String> oidIterator = oids.iterator();
+
+ List<AttributeType> attributeTypes = new ArrayList<AttributeType>();
+ addAttributeType( attributeTypes, oidIterator.next(), "att1", null );
+ addAttributeType( attributeTypes, oidIterator.next(), "att2", "att1" );
+ addAttributeType( attributeTypes, oidIterator.next(), "att3", "att2" );
+ addAttributeType( attributeTypes, oidIterator.next(), "att4", "att3" );
+ addAttributeType( attributeTypes, oidIterator.next(), "att5", "att1" );
+ addAttributeType( attributeTypes, oidIterator.next(), "att6", null );
+ addAttributeType( attributeTypes, oidIterator.next(), "att7", "other" );
+
+ Iterable<AttributeType> sorted = SchemaObjectSorter.hierarchicalOrdered( attributeTypes );
+ assertHierarchicalOrderAT( sorted );
+ }
+ }
+
+
+ private void assertHierarchicalOrderAT( Iterable<AttributeType> ordered )
+ {
+ Iterator<AttributeType> iterator = ordered.iterator();
+
+ String name1 = assertNextSuperiorAT( iterator, null, "other" );
+ String name2 = assertNextSuperiorAT( iterator, null, "other", name1 );
+ String name3 = assertNextSuperiorAT( iterator, null, "other", name1, name2 );
+ String name4 = assertNextSuperiorAT( iterator, null, "other", name1, name2, name3 );
+ String name5 = assertNextSuperiorAT( iterator, null, "other", name1, name2, name3, name4 );
+ String name6 = assertNextSuperiorAT( iterator, null, "other", name1, name2, name3, name4, name5 );
+ assertNextSuperiorAT( iterator, null, "other", name1, name2, name3, name4, name5, name6 );
+
+ assertFalse( iterator.hasNext() );
+ }
+
+
+ private String assertNextSuperiorAT( Iterator<AttributeType> iterator, String... expected )
+ {
+ assertTrue( iterator.hasNext() );
+
+ AttributeType next = iterator.next();
+ String superiorOid = next.getSuperiorOid();
+
+ if ( !Arrays.asList( expected ).contains( superiorOid ) )
+ {
+ fail( "Expected that " + Arrays.asList( expected ) + " contains " + superiorOid );
+ }
+
+ return next.getName();
+ }
+
+
+ @Test(expected = IllegalStateException.class)
+ public void testSortAttributeTypesLoop()
+ {
+ List<AttributeType> attributeTypes = new ArrayList<AttributeType>();
+ addAttributeType( attributeTypes, "1.1.1", "att1", "att4" );
+ addAttributeType( attributeTypes, "1.1.2", "att2", "att1" );
+ addAttributeType( attributeTypes, "1.1.3", "att3", "att2" );
+ addAttributeType( attributeTypes, "1.1.4", "att4", "att3" );
+
+ Iterable<AttributeType> sorted = SchemaObjectSorter.hierarchicalOrdered( attributeTypes );
+ sorted.iterator().next();
+ }
+
+
+ private void addObjectClass( List<ObjectClass> objectClasses, String oid, String name, String... superiorOid )
+ {
+ MutableObjectClass oc = new MutableObjectClass( oid );
+ oc.setNames( name );
+ if ( superiorOid != null )
+ {
+ oc.setSuperiorOids( Arrays.asList( superiorOid ) );
+ }
+ objectClasses.add( oc );
+ }
+
+
+ @Test
+ public void testSortObjectClassesAlreadySorted()
+ {
+ List<ObjectClass> objectClasses = new ArrayList<ObjectClass>();
+ addObjectClass( objectClasses, "1.2.1", "oc1" );
+ addObjectClass( objectClasses, "1.2.2", "oc2", "oc1" );
+ addObjectClass( objectClasses, "1.2.3", "oc3", "oc2" );
+ addObjectClass( objectClasses, "1.2.4", "oc4" );
+ addObjectClass( objectClasses, "1.2.5", "oc5", "oc2", "oc4" );
+ addObjectClass( objectClasses, "1.2.6", "oc6", "other" );
+
+ Iterable<ObjectClass> sorted = SchemaObjectSorter.sortObjectClasses( objectClasses );
+ assertHierarchicalOrderOC( sorted );
+ }
+
+
+ @Test
+ public void testSortObjectClassesShuffled()
+ {
+ List<String> oids = Arrays.asList( "1.1.1", "1.1.2", "1.1.3", "1.1.4", "1.1.5", "1.1.6" );
+ for ( int i = 0; i < 1000; i++ )
+ {
+ Collections.shuffle( oids );
+ Iterator<String> oidIterator = oids.iterator();
+
+ List<ObjectClass> objectClasses = new ArrayList<ObjectClass>();
+ addObjectClass( objectClasses, oidIterator.next(), "oc1" );
+ addObjectClass( objectClasses, oidIterator.next(), "oc2", "oc1" );
+ addObjectClass( objectClasses, oidIterator.next(), "oc3", "oc2" );
+ addObjectClass( objectClasses, oidIterator.next(), "oc4" );
+ addObjectClass( objectClasses, oidIterator.next(), "oc5", "oc2", "oc4" );
+ addObjectClass( objectClasses, oidIterator.next(), "oc6", "other" );
+
+ Iterable<ObjectClass> sorted = SchemaObjectSorter.sortObjectClasses( objectClasses );
+ assertHierarchicalOrderOC( sorted );
+ }
+ }
+
+
+ private void assertHierarchicalOrderOC( Iterable<ObjectClass> ordered )
+ {
+ Iterator<ObjectClass> iterator = ordered.iterator();
+
+ String name1 = assertNextSuperiorOC( iterator, null, "other" );
+ String name2 = assertNextSuperiorOC( iterator, null, "other", name1 );
+ String name3 = assertNextSuperiorOC( iterator, null, "other", name1, name2 );
+ String name4 = assertNextSuperiorOC( iterator, null, "other", name1, name2, name3 );
+ String name5 = assertNextSuperiorOC( iterator, null, "other", name1, name2, name3, name4 );
+ assertNextSuperiorOC( iterator, null, "other", name1, name2, name3, name4, name5 );
+
+ assertFalse( iterator.hasNext() );
+ }
+
+
+ private String assertNextSuperiorOC( Iterator<ObjectClass> iterator, String... expected )
+ {
+ assertTrue( iterator.hasNext() );
+
+ ObjectClass next = iterator.next();
+ List<String> superiorOids = next.getSuperiorOids();
+
+ if ( !Arrays.asList( expected ).containsAll( superiorOids ) )
+ {
+ fail( "Expected that " + Arrays.asList( expected ) + " contains all " + superiorOids );
+ }
+
+ return next.getName();
+ }
+
+
+ @Test(expected = IllegalStateException.class)
+ public void testSortObjectClassesLoop()
+ {
+ List<ObjectClass> objectClasses = new ArrayList<ObjectClass>();
+ addObjectClass( objectClasses, "1.2.1", "oc1", "oc3" );
+ addObjectClass( objectClasses, "1.2.2", "oc2", "oc1" );
+ addObjectClass( objectClasses, "1.2.3", "oc3", "oc2" );
+
+ Iterable<ObjectClass> sorted = SchemaObjectSorter.sortObjectClasses( objectClasses );
+ sorted.iterator().next();
+ }
+
+}