directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From seelm...@apache.org
Subject 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
Date Tue, 03 Dec 2013 21:01:38 GMT
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();
+    }
+
+}



Mime
View raw message