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