View Javadoc
1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *  
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *  
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License. 
18   *  
19   */
20  package org.apache.directory.api.ldap.model.schema;
21  
22  
23  import java.util.Collection;
24  import java.util.Collections;
25  import java.util.HashMap;
26  import java.util.Iterator;
27  import java.util.List;
28  import java.util.Map;
29  import java.util.Map.Entry;
30  import java.util.TreeMap;
31  
32  import org.apache.directory.api.ldap.model.schema.AttributeType;
33  import org.apache.directory.api.ldap.model.schema.ObjectClass;
34  import org.apache.directory.api.ldap.model.schema.SchemaObject;
35  
36  
37  /**
38   * Various utility methods for sorting schema objects.
39   * 
40   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
41   */
42  public class SchemaObjectSorter
43  {
44  
45      /**
46       * Gets an hierarchical ordered {@link Iterable} of the given {@link AttributeType}s. 
47       * In other words parent {@link AttributeType}s are returned before child {@link AttributeType}s.
48       * @param attributeTypes list of attribute types to order
49       * @return the hierarchical ordered attribute types
50       */
51      public static Iterable<AttributeType> hierarchicalOrdered( List<AttributeType> attributeTypes )
52      {
53          return new SchemaObjectIterable<AttributeType>( attributeTypes, new ReferenceCallback<AttributeType>()
54          {
55              @Override
56              public Collection<String> getSuperiorOids( AttributeType at )
57              {
58                  return Collections.singleton( at.getSuperiorOid() );
59              }
60          } );
61      }
62  
63  
64      /**
65       * Gets an hierarchical ordered {@link Iterable} of the given {@link ObjectClass}es. 
66       * In other words parent {@link ObjectClass}es are returned before child {@link ObjectClass}es.
67       * @param objectClasses list of object classes to order
68       * @return the hierarchical ordered object classes
69       */
70      public static Iterable<ObjectClass> sortObjectClasses( List<ObjectClass> objectClasses )
71      {
72          return new SchemaObjectIterable<ObjectClass>( objectClasses, new ReferenceCallback<ObjectClass>()
73          {
74              @Override
75              public Collection<String> getSuperiorOids( ObjectClass oc )
76              {
77                  return oc.getSuperiorOids();
78              }
79          } );
80      }
81  
82      private static interface ReferenceCallback<T extends SchemaObject>
83      {
84  
85          Collection<String> getSuperiorOids( T schemaObject );
86  
87      }
88  
89      private static class SchemaObjectIterable<T extends SchemaObject> implements Iterable<T>
90      {
91  
92          private final List<T> schemaObjects;
93          private final ReferenceCallback<T> callback;
94  
95  
96          private SchemaObjectIterable( List<T> schemaObjects, ReferenceCallback<T> callback )
97          {
98              this.schemaObjects = schemaObjects;
99              this.callback = callback;
100         }
101 
102 
103         @Override
104         public Iterator<T> iterator()
105         {
106             return new SchemaObjectIterator<T>( schemaObjects, callback );
107         }
108 
109     }
110 
111     private static class SchemaObjectIterator<T extends SchemaObject> implements Iterator<T>
112     {
113         private final List<T> schemaObjects;
114         private final ReferenceCallback<T> callback;
115 
116         private final Map<String, String> oid2numericOid;
117         private final Map<String, T> numericOid2schemaObject;
118 
119         private int loopCount;
120         private Iterator<Entry<String, T>> schemaObjectIterator;
121 
122 
123         private SchemaObjectIterator( List<T> schemaObjects, ReferenceCallback<T> callback )
124         {
125             this.schemaObjects = schemaObjects;
126             this.callback = callback;
127 
128             this.oid2numericOid = new HashMap<String, String>();
129             this.numericOid2schemaObject = new TreeMap<String, T>();
130             this.loopCount = 0;
131 
132             for ( T schemaObject : schemaObjects )
133             {
134                 String oid = schemaObject.getOid().toLowerCase();
135                 oid2numericOid.put( oid, oid );
136                 for ( String name : schemaObject.getNames() )
137                 {
138                     oid2numericOid.put( name.toLowerCase(), oid );
139                 }
140                 numericOid2schemaObject.put( oid, schemaObject );
141             }
142         }
143 
144 
145         @Override
146         public boolean hasNext()
147         {
148             return !numericOid2schemaObject.isEmpty();
149         }
150 
151 
152         @Override
153         public T next()
154         {
155             while ( !maxLoopCountReached() )
156             {
157                 Iterator<Entry<String, T>> iterator = getIterator();
158 
159                 while ( iterator.hasNext() )
160                 {
161                     Entry<String, T> entry = iterator.next();
162                     T schemaObject = entry.getValue();
163 
164                     Collection<String> superiorOids = callback.getSuperiorOids( schemaObject );
165 
166                     // schema object has no superior
167                     if ( superiorOids == null )
168                     {
169                         iterator.remove();
170                         return schemaObject;
171                     }
172 
173                     boolean allSuperiorsProcessed = true;
174 
175                     for ( String superiorOid : superiorOids )
176                     {
177                         if ( superiorOid == null )
178                         {
179                             continue;
180                         }
181 
182                         String superiorNumeridOid = oid2numericOid.get( superiorOid.toLowerCase() );
183 
184                         // AT's superior is not within the processed AT list
185                         if ( superiorNumeridOid == null )
186                         {
187                             continue;
188                         }
189 
190                         T superiorSchemaObject = numericOid2schemaObject.get( superiorNumeridOid.toLowerCase() );
191 
192                         // AT's superior was already removed
193                         if ( superiorSchemaObject == null )
194                         {
195                             continue;
196                         }
197 
198                         allSuperiorsProcessed = false;
199                         break;
200                     }
201 
202                     if ( allSuperiorsProcessed )
203                     {
204                         iterator.remove();
205                         return schemaObject;
206                     }
207                 }
208             }
209             throw new IllegalStateException( "Loop detected: " + numericOid2schemaObject.values() );
210         }
211 
212 
213         private Iterator<Entry<String, T>> getIterator()
214         {
215             if ( schemaObjectIterator != null && schemaObjectIterator.hasNext() )
216             {
217                 return schemaObjectIterator;
218             }
219 
220             if ( !maxLoopCountReached() )
221             {
222                 schemaObjectIterator = numericOid2schemaObject.entrySet().iterator();
223                 loopCount++;
224                 return schemaObjectIterator;
225             }
226 
227             throw new IllegalStateException( "Loop detected: " + numericOid2schemaObject.values() );
228         }
229 
230 
231         private boolean maxLoopCountReached()
232         {
233             return loopCount > schemaObjects.size();
234         }
235 
236 
237         @Override
238         public void remove()
239         {
240             throw new UnsupportedOperationException();
241         }
242 
243     }
244 
245 }