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     */
020    package org.apache.directory.shared.ldap.util.tree;
021    
022    
023    import java.util.HashMap;
024    import java.util.List;
025    import java.util.Map;
026    
027    import org.apache.directory.shared.i18n.I18n;
028    import org.apache.directory.shared.ldap.exception.LdapException;
029    import org.apache.directory.shared.ldap.exception.LdapUnwillingToPerformException;
030    import org.apache.directory.shared.ldap.message.ResultCodeEnum;
031    import org.apache.directory.shared.ldap.name.DN;
032    import org.apache.directory.shared.ldap.name.RDN;
033    import org.slf4j.Logger;
034    import org.slf4j.LoggerFactory;
035    
036    
037    /**
038     * 
039     * The Hierarchical Container holds elements ordered by their DN. 
040     * <br/>
041     * We can see them as directories, where the leaves are the files.
042     * <br/>
043     * This class is *not* thread safe
044     *
045     * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
046     */
047    public class DnBranchNode<N> implements DnNode<N>
048    {
049        /** The logger for this class */
050        private static final Logger LOG = LoggerFactory.getLogger( DnBranchNode.class );
051    
052        /** Stores the list of all the descendant */
053        private Map<String, DnNode<N>> children;
054        
055        /** Stores the number of descendents */
056        private int size;
057        
058        /**
059         * Creates a new instance of a DnBranchNode.
060         */
061        public DnBranchNode()
062        {
063            children = new HashMap<String, DnNode<N>>(3);
064            size = 0;
065        }
066    
067        
068        /**
069         * @see DnNode#isLeaf()
070         */
071        public boolean isLeaf()
072        {
073            return false;
074        }
075        
076        
077        /**
078         * Recursively adds new nodes to the element lookup tree data structure.  
079         * When called it will add an element to the tree in the appropriate leaf 
080         * node position based on the DN passed in as an argument.
081         *
082         * @param current The current node having an element added to it
083         * @param dn The DN associated with the added element
084         * @param index The index of the current RDN being processed 
085         * @param element The associated element to add as a tree node
086         * @return The modified tree structure.
087         */
088        private DnNode<N> recursivelyAddElement( DnBranchNode<N> current, DN dn, int index, N element ) throws LdapException
089        {
090            String rdnAtIndex = dn.getRdn( index ).getNormName();
091            
092            if ( index == dn.size() - 1 )
093            {
094                if ( !current.contains( rdnAtIndex ) )
095                {
096                    return current.addNode( rdnAtIndex, new DnLeafNode<N>( element ) );
097                }
098                else
099                {
100                    return null;
101                }
102            }
103            else
104            {
105                DnNode<N> newNode = ((DnBranchNode<N>)current).getChild( rdnAtIndex );
106                
107                if ( newNode instanceof DnLeafNode )
108                {
109                    String message = I18n.err( I18n.ERR_04334 );
110                    LOG.error( message );
111                    throw new LdapUnwillingToPerformException( ResultCodeEnum.UNWILLING_TO_PERFORM, message );
112                }
113            
114                if ( newNode == null )
115                {
116                    newNode = new DnBranchNode<N>();
117                }
118    
119                DnNode<N> child = recursivelyAddElement( (DnBranchNode<N>)newNode, dn, index + 1, element );
120                
121                if ( child != null )
122                {
123                    return current.addNode( rdnAtIndex, child );
124                }
125                else
126                {
127                    return null;
128                }
129            }
130        }
131        
132        
133        /**
134         * Directly adds a new child DnNode to the current DnBranchNode.
135         *
136         * @param rdn The rdn of the child node to add 
137         * @param child The child node to add
138         * @return The modified branch node after the insertion
139         */
140        public DnNode<N> addNode( String rdn, DnNode<N> child )
141        {
142            children.put( rdn, child );
143            size++;
144            return this;
145        }
146        
147        
148        /**
149         * Tells if the current DnBranchNode contains another node associated 
150         * with an rdn.
151         *
152         * @param rdn The name we are looking for
153         * @return <code>true</code> if the tree instance contains this name
154         */
155        public boolean contains( String rdn )
156        {
157            return children.containsKey( rdn );
158        }
159    
160        
161        /**
162         * Get's a child using an rdn string.
163         * 
164         * @param rdn the rdn to use as the node key
165         * @return the child node corresponding to the rdn.
166         */
167        public DnNode<N> getChild( String rdn )
168        {
169            if ( children.containsKey( rdn ) )
170            {
171                return children.get( rdn );
172            }
173    
174            return null;
175        }
176        
177        
178        /**
179         * Get the parent of a given DN, if present in the tree. This parent should be a 
180         * subset of the given dn.<br>
181         * For instance, if we have stored dc=acme, dc=org into the tree, 
182         * the DN: ou=example, dc=acme, dc=org will have a parent, and 
183         * dc=acme, dc=org will be returned.
184         * <br>For the DN ou=apache, dc=org, there is no parent, so null will be returned.
185         *  
186         *
187         * @param dn the normalized distinguished name to resolve to a parent
188         * @return the parent associated with the normalized dn
189         */
190        public N getParentElement( DN dn )
191        {
192            List<RDN> rdns = dn.getRdns();
193            
194            // This is synchronized so that we can't read the
195            // partitionList when it is modified.
196            synchronized ( this )
197            {
198                DnNode<N> currentNode = this;
199    
200                // Iterate through all the RDN until we find the associated partition
201                for ( int i = rdns.size() - 1; i >= 0; i-- )
202                {
203                    String rdnStr = rdns.get( i ).getNormName();
204    
205                    if ( currentNode == null )
206                    {
207                        break;
208                    }
209    
210                    if ( currentNode instanceof DnLeafNode )
211                    {
212                        return ( ( DnLeafNode<N> ) currentNode ).getElement();
213                    }
214    
215                    DnBranchNode<N> currentBranch = ( DnBranchNode<N> ) currentNode;
216                    
217                    if ( currentBranch.contains( rdnStr ) )
218                    {
219                        currentNode = currentBranch.getChild( rdnStr );
220                        
221                        if ( currentNode instanceof DnLeafNode )
222                        {
223                            return ( ( DnLeafNode<N> ) currentNode ).getElement();
224                        }
225                    }
226                }
227            }
228            
229            return null;
230        }
231    
232        
233        /**
234         * Tells if the DN contains a parent in the tree. This parent should be a 
235         * subset of the given dn.<br>
236         * For instance, if we have stored dc=acme, dc=org into the tree, 
237         * the DN: ou=example, dc=acme, dc=org will have a parent. 
238         *
239         * @param dn the normalized distinguished name to resolve to a parent
240         * @return the parent associated with the normalized dn
241         */
242        public boolean hasParentElement( DN dn )
243        {
244            List<RDN> rdns = dn.getRdns();
245            
246            // This is synchronized so that we can't read the
247            // partitionList when it is modified.
248            synchronized ( this )
249            {
250                DnNode<N> currentNode = this;
251    
252                // Iterate through all the RDN until we find the associated partition
253                for ( int i = rdns.size() - 1; i >= 0; i-- )
254                {
255                    String rdnStr = rdns.get( i ).getNormName();
256    
257                    if ( currentNode == null )
258                    {
259                        return false;
260                    }
261    
262                    if ( currentNode instanceof DnLeafNode )
263                    {
264                        return true;
265                    }
266    
267                    DnBranchNode<N> currentBranch = ( DnBranchNode<N> ) currentNode;
268                    
269                    if ( currentBranch.contains( rdnStr ) )
270                    {
271                        currentNode = currentBranch.getChild( rdnStr );
272                        
273                        if ( currentNode instanceof DnLeafNode )
274                        {
275                            return true;
276                        }
277                    }
278                }
279            }
280            
281            return false;
282        }
283        
284        
285        /**
286         * Tells if a branchNode has some children or not
287         *
288         * @return <code>true</code> if the node has some children
289         */
290        public boolean hasChildren()
291        {
292            return children.size() != 0;
293        }
294        
295        
296        /**
297         * Removes an element from the tree.
298         *
299         * @param element The element to remove
300         */
301        private boolean recursivelyRemoveElement( DnBranchNode<N> currentNode, N element )
302        {
303            // It might be a leaf
304            for ( String key: currentNode.children.keySet() )
305            {
306                DnNode<N> child = currentNode.children.get( key );
307                
308                if ( child instanceof DnLeafNode )
309                {
310                    if ( ((DnLeafNode<N>)child).getElement().equals( element ) )
311                    {
312                        // found ! Remove it from the children
313                        currentNode.children.remove( key );
314                        currentNode.size--;
315                        return true;
316                    }
317                }
318                else
319                {
320                    if ( recursivelyRemoveElement( (DnBranchNode<N>)child, element ) )
321                    {
322                        if ( ((DnBranchNode<N>)child).children.size() == 0 )
323                        {
324                            // If there are no more children, we can remove the node
325                            currentNode.children.remove( key );
326                            currentNode.size--;
327                        }
328                        else
329                        {
330                            currentNode.size--;
331                        }
332    
333                        return true;
334                    }
335                }
336            }
337            
338            
339            return false;
340        }
341    
342        
343        /**
344         * 
345         * TODO add.
346         *
347         * @param dn
348         * @param element
349         * @throws NamingException
350         */
351        public void add( DN dn, N element ) throws LdapException
352        {
353            recursivelyAddElement( this, dn, 0, element );
354        }
355        
356        
357        /**
358         * Removes an element from the tree.
359         *
360         * @param element The element to remove
361         */
362        public void remove( N element )
363        {
364            DnBranchNode<N> currentNode = this;
365            
366            if ( currentNode.hasChildren() )
367            {
368                recursivelyRemoveElement( currentNode, element );
369            }
370        }
371        
372        
373        /**
374         * {@inheritDoc}
375         */
376        public int size()
377        {
378            return size;
379        }
380    
381    
382        /**
383         * @see Object#toString()
384         */
385        public String toString()
386        {
387            StringBuilder sb = new StringBuilder();
388            sb.append( "{" );
389            boolean isFirst = true;
390            
391            for ( String key:children.keySet() )
392            {
393                if ( isFirst )
394                {
395                    isFirst = false;
396                }
397                else
398                {
399                    sb.append(  ", " );
400                }
401    
402                DnNode<N> child = children.get( key );
403                
404                if ( child instanceof DnBranchNode )
405                {
406                    sb.append( "Branch[" ).append( key ).append( "]: ").append( child );
407                }
408                else
409                {
410                    sb.append( "Leaf: " ).append( "'" ).append( child ).append( "'" );
411                }
412            }
413    
414            sb.append( "}" );
415            return sb.toString();
416        }
417    }