001/* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 * 019 */ 020package org.apache.directory.api.ldap.model.schema; 021 022 023import java.util.Collection; 024import java.util.Collections; 025import java.util.HashMap; 026import java.util.Iterator; 027import java.util.List; 028import java.util.Map; 029import java.util.Map.Entry; 030import java.util.TreeMap; 031 032import org.apache.directory.api.ldap.model.schema.AttributeType; 033import org.apache.directory.api.ldap.model.schema.ObjectClass; 034import org.apache.directory.api.ldap.model.schema.SchemaObject; 035 036 037/** 038 * Various utility methods for sorting schema objects. 039 * 040 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 041 */ 042public class SchemaObjectSorter 043{ 044 045 /** 046 * Gets an hierarchical ordered {@link Iterable} of the given {@link AttributeType}s. 047 * In other words parent {@link AttributeType}s are returned before child {@link AttributeType}s. 048 * @param attributeTypes list of attribute types to order 049 * @return the hierarchical ordered attribute types 050 */ 051 public static Iterable<AttributeType> hierarchicalOrdered( List<AttributeType> attributeTypes ) 052 { 053 return new SchemaObjectIterable<AttributeType>( attributeTypes, new ReferenceCallback<AttributeType>() 054 { 055 @Override 056 public Collection<String> getSuperiorOids( AttributeType at ) 057 { 058 return Collections.singleton( at.getSuperiorOid() ); 059 } 060 } ); 061 } 062 063 064 /** 065 * Gets an hierarchical ordered {@link Iterable} of the given {@link ObjectClass}es. 066 * In other words parent {@link ObjectClass}es are returned before child {@link ObjectClass}es. 067 * @param objectClasses list of object classes to order 068 * @return the hierarchical ordered object classes 069 */ 070 public static Iterable<ObjectClass> sortObjectClasses( List<ObjectClass> objectClasses ) 071 { 072 return new SchemaObjectIterable<ObjectClass>( objectClasses, new ReferenceCallback<ObjectClass>() 073 { 074 @Override 075 public Collection<String> getSuperiorOids( ObjectClass oc ) 076 { 077 return oc.getSuperiorOids(); 078 } 079 } ); 080 } 081 082 private static interface ReferenceCallback<T extends SchemaObject> 083 { 084 085 Collection<String> getSuperiorOids( T schemaObject ); 086 087 } 088 089 private static class SchemaObjectIterable<T extends SchemaObject> implements Iterable<T> 090 { 091 092 private final List<T> schemaObjects; 093 private final ReferenceCallback<T> callback; 094 095 096 private SchemaObjectIterable( List<T> schemaObjects, ReferenceCallback<T> callback ) 097 { 098 this.schemaObjects = schemaObjects; 099 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}