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.util.Strings; 033 034 035/** 036 * Various utility methods for sorting schema objects. 037 * 038 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 039 */ 040public final class SchemaObjectSorter 041{ 042 private SchemaObjectSorter() 043 { 044 } 045 046 047 /** 048 * Gets an hierarchical ordered {@link Iterable} of the given {@link AttributeType}s. 049 * In other words parent {@link AttributeType}s are returned before child {@link AttributeType}s. 050 * @param attributeTypes list of attribute types to order 051 * @return the hierarchical ordered attribute types 052 */ 053 public static Iterable<AttributeType> hierarchicalOrdered( List<AttributeType> attributeTypes ) 054 { 055 return new SchemaObjectIterable<>( attributeTypes, new ReferenceCallback<AttributeType>() 056 { 057 @Override 058 public Collection<String> getSuperiorOids( AttributeType at ) 059 { 060 return Collections.singleton( at.getSuperiorOid() ); 061 } 062 } ); 063 } 064 065 066 /** 067 * Gets an hierarchical ordered {@link Iterable} of the given {@link ObjectClass}es. 068 * In other words parent {@link ObjectClass}es are returned before child {@link ObjectClass}es. 069 * @param objectClasses list of object classes to order 070 * @return the hierarchical ordered object classes 071 */ 072 public static Iterable<ObjectClass> sortObjectClasses( List<ObjectClass> objectClasses ) 073 { 074 return new SchemaObjectIterable<>( objectClasses, new ReferenceCallback<ObjectClass>() 075 { 076 @Override 077 public Collection<String> getSuperiorOids( ObjectClass oc ) 078 { 079 return oc.getSuperiorOids(); 080 } 081 } ); 082 } 083 084 private interface ReferenceCallback<T extends SchemaObject> 085 { 086 087 Collection<String> getSuperiorOids( T schemaObject ); 088 089 } 090 091 private static final class SchemaObjectIterable<T extends SchemaObject> implements Iterable<T> 092 { 093 094 private final List<T> schemaObjects; 095 private final ReferenceCallback<T> callback; 096 097 098 private SchemaObjectIterable( List<T> schemaObjects, ReferenceCallback<T> callback ) 099 { 100 this.schemaObjects = schemaObjects; 101 this.callback = callback; 102 } 103 104 105 @Override 106 public Iterator<T> iterator() 107 { 108 return new SchemaObjectIterator<>( schemaObjects, callback ); 109 } 110 111 } 112 113 private static final class SchemaObjectIterator<T extends SchemaObject> implements Iterator<T> 114 { 115 private final List<T> schemaObjects; 116 private final ReferenceCallback<T> callback; 117 118 private final Map<String, String> oid2numericOid; 119 private final Map<String, T> numericOid2schemaObject; 120 121 private int loopCount; 122 private Iterator<Entry<String, T>> schemaObjectIterator; 123 124 125 private SchemaObjectIterator( List<T> schemaObjects, ReferenceCallback<T> callback ) 126 { 127 this.schemaObjects = schemaObjects; 128 this.callback = callback; 129 130 this.oid2numericOid = new HashMap<>(); 131 this.numericOid2schemaObject = new TreeMap<>(); 132 this.loopCount = 0; 133 134 for ( T schemaObject : schemaObjects ) 135 { 136 String oid = Strings.toLowerCaseAscii( schemaObject.getOid() ); 137 oid2numericOid.put( oid, oid ); 138 139 for ( String name : schemaObject.getNames() ) 140 { 141 oid2numericOid.put( Strings.toLowerCaseAscii( name ), oid ); 142 } 143 144 numericOid2schemaObject.put( oid, schemaObject ); 145 } 146 } 147 148 149 @Override 150 public boolean hasNext() 151 { 152 return !numericOid2schemaObject.isEmpty(); 153 } 154 155 156 @Override 157 public T next() 158 { 159 while ( !maxLoopCountReached() ) 160 { 161 Iterator<Entry<String, T>> iterator = getIterator(); 162 163 while ( iterator.hasNext() ) 164 { 165 Entry<String, T> entry = iterator.next(); 166 T schemaObject = entry.getValue(); 167 168 Collection<String> superiorOids = callback.getSuperiorOids( schemaObject ); 169 170 // schema object has no superior 171 if ( superiorOids == null ) 172 { 173 iterator.remove(); 174 return schemaObject; 175 } 176 177 boolean allSuperiorsProcessed = true; 178 179 for ( String superiorOid : superiorOids ) 180 { 181 if ( superiorOid == null ) 182 { 183 continue; 184 } 185 186 String superiorNumeridOid = oid2numericOid.get( Strings.toLowerCaseAscii( superiorOid ) ); 187 188 // AT's superior is not within the processed AT list 189 if ( superiorNumeridOid == null ) 190 { 191 continue; 192 } 193 194 T superiorSchemaObject = numericOid2schemaObject.get( Strings.toLowerCaseAscii( superiorNumeridOid ) ); 195 196 // AT's superior was already removed 197 if ( superiorSchemaObject == null ) 198 { 199 continue; 200 } 201 202 allSuperiorsProcessed = false; 203 break; 204 } 205 206 if ( allSuperiorsProcessed ) 207 { 208 iterator.remove(); 209 return schemaObject; 210 } 211 } 212 } 213 throw new IllegalStateException( "Loop detected: " + numericOid2schemaObject.values() ); 214 } 215 216 217 private Iterator<Entry<String, T>> getIterator() 218 { 219 if ( schemaObjectIterator != null && schemaObjectIterator.hasNext() ) 220 { 221 return schemaObjectIterator; 222 } 223 224 if ( !maxLoopCountReached() ) 225 { 226 schemaObjectIterator = numericOid2schemaObject.entrySet().iterator(); 227 loopCount++; 228 return schemaObjectIterator; 229 } 230 231 throw new IllegalStateException( "Loop detected: " + numericOid2schemaObject.values() ); 232 } 233 234 235 private boolean maxLoopCountReached() 236 { 237 return loopCount > schemaObjects.size(); 238 } 239 240 241 @Override 242 public void remove() 243 { 244 throw new UnsupportedOperationException(); 245 } 246 247 } 248 249}