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.server.core.partition.avl;
021    
022    
023    import java.util.Comparator;
024    
025    import org.apache.directory.server.core.avltree.AvlSingletonOrOrderedSetCursor;
026    import org.apache.directory.server.core.avltree.AvlTree;
027    import org.apache.directory.server.core.avltree.AvlTreeCursor;
028    import org.apache.directory.server.core.avltree.AvlTreeMap;
029    import org.apache.directory.server.core.avltree.AvlTreeMapImpl;
030    import org.apache.directory.server.core.avltree.AvlTreeMapNoDupsWrapperCursor;
031    import org.apache.directory.server.core.avltree.KeyTupleAvlCursor;
032    import org.apache.directory.server.core.avltree.LinkedAvlMapNode;
033    import org.apache.directory.server.core.avltree.SingletonOrOrderedSet;
034    import org.apache.directory.server.xdbm.Table;
035    import org.apache.directory.server.xdbm.Tuple;
036    import org.apache.directory.shared.ldap.cursor.Cursor;
037    import org.apache.directory.shared.ldap.cursor.EmptyCursor;
038    import org.apache.directory.shared.ldap.cursor.SingletonCursor;
039    
040    
041    /**
042     * A Table implementation backed by in memory AVL tree.
043     *
044     * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
045     * @version $Rev$, $Date$
046     */
047    public class AvlTable<K, V> implements Table<K, V>
048    {
049        private final AvlTreeMap<K, V> avl;
050        private final String name;
051        private final Comparator<K> keyComparator;
052        private final Comparator<V> valComparator;
053        private final Comparator<Tuple<K,V>> keyOnlytupleComparator;
054        private int count;
055        
056        
057        public AvlTable( String name, final Comparator<K> keyComparator, final Comparator<V> valComparator, boolean dupsEnabled )
058        {
059            this.name = name;
060            this.keyComparator = keyComparator;
061            this.valComparator = valComparator;
062            this.avl = new AvlTreeMapImpl<K, V>( keyComparator, valComparator, dupsEnabled );
063            this.keyOnlytupleComparator = new Comparator<Tuple<K, V>>()
064            {
065                public int compare( Tuple<K, V> t0, Tuple<K, V> t1 )
066                {
067                    return keyComparator.compare( t0.getKey(), t1.getKey() );
068                }
069            };
070        }
071        
072    
073        /**
074         * Does nothing.
075         * 
076         * {@inheritDoc}
077         */
078        public void close() throws Exception
079        {
080        }
081    
082        
083        /**
084         * {@inheritDoc}
085         */
086        public int count() throws Exception
087        {
088            return count;
089        }
090    
091        
092        /**
093         * {@inheritDoc}
094         */
095        public int count( K key ) throws Exception
096        {
097            if ( key == null )
098            {
099                return 0;
100            }
101            
102            LinkedAvlMapNode<K, V> node = avl.find( key );
103            if ( node == null )
104            {
105                return 0;
106            }
107            
108            SingletonOrOrderedSet<V> val = node.getValue();
109            if ( val.isOrderedSet() )
110            {
111                return val.getOrderedSet().getSize();
112            }
113            
114            return 1;
115        }
116    
117       
118        /**
119         * {@inheritDoc}
120         */
121        public V get( K key ) throws Exception
122        {
123            if ( key == null )
124            {
125                return null;
126            }
127            
128            LinkedAvlMapNode<K, V> node = avl.find( key );
129            if ( node == null )
130            {
131                return null;
132            }
133            
134            SingletonOrOrderedSet<V> val = node.getValue();
135            if ( val.isOrderedSet() )
136            {
137                return val.getOrderedSet().getFirst().getKey();
138            }
139            
140            return val.getSingleton();
141        }
142    
143        
144        /**
145         * {@inheritDoc}
146         */
147        public Comparator<K> getKeyComparator()
148        {
149            return keyComparator;
150        }
151    
152        
153        /**
154         * {@inheritDoc}
155         */
156        public Comparator<V> getValueComparator()
157        {
158            return valComparator;
159        }
160    
161        
162        /**
163         * {@inheritDoc}
164         */
165        public String getName()
166        {
167            return name;
168        }
169        
170    
171        /**
172         * {@inheritDoc}
173         */
174        public int greaterThanCount( K key ) throws Exception
175        {
176            return avl.getSize();
177        }
178    
179        
180        /**
181         * {@inheritDoc}
182         */
183        public boolean has( K key ) throws Exception
184        {
185            if ( key == null )
186            {
187                return false;
188            }
189            
190            return avl.find( key ) != null;
191        }
192    
193        
194        /**
195         * {@inheritDoc}
196         */
197        public boolean has( K key, V value ) throws Exception
198        {
199            if ( key == null )
200            {
201                return false;
202            }
203            
204            return avl.find( key, value ) != null;
205        }
206    
207        
208        /**
209         * {@inheritDoc}
210         */
211        public boolean hasGreaterOrEqual( K key ) throws Exception
212        {
213            if ( key == null )
214            {
215                return false;
216            }
217            
218            return avl.findGreaterOrEqual( key ) != null;
219        }
220    
221        
222        /**
223         * {@inheritDoc}
224         */
225        public boolean hasGreaterOrEqual( K key, V val ) throws Exception
226        {
227            if ( key == null )
228            {
229                return false;
230            }
231            
232            LinkedAvlMapNode<K, V> node = avl.findGreaterOrEqual( key );
233            if ( node == null )
234            {
235                return false;
236            }
237            
238            if ( node.getValue().isOrderedSet() )
239            {
240                AvlTree<V> values = node.getValue().getOrderedSet();
241                return values.findGreaterOrEqual( val ) != null;
242            }
243            
244            return valComparator.compare( node.getValue().getSingleton(), val ) >= 0;
245        }
246    
247        
248        /**
249         * {@inheritDoc}
250         */
251        public boolean hasLessOrEqual( K key ) throws Exception
252        {
253            if ( key == null )
254            {
255                return false;
256            }
257            
258            return avl.findLessOrEqual( key ) != null;
259        }
260    
261        
262        /**
263         * {@inheritDoc}
264         */
265        public boolean hasLessOrEqual( K key, V val ) throws Exception
266        {
267            if ( key == null )
268            {
269                return false;
270            }
271            
272            LinkedAvlMapNode<K, V> node = avl.findLessOrEqual( key );
273            if ( node == null )
274            {
275                return false;
276            }
277            
278            if ( node.getValue().isOrderedSet() )
279            {
280                AvlTree<V> values = node.getValue().getOrderedSet();
281                return values.findLessOrEqual( val ) != null;
282            }
283            
284            return valComparator.compare( node.getValue().getSingleton(), val ) <= 0;
285        }
286    
287    
288        /**
289         * {@inheritDoc}
290         */
291        public boolean isCountExact()
292        {
293            return false;
294        }
295    
296        
297        /**
298         * {@inheritDoc}
299         */
300        public boolean isDupsEnabled()
301        {
302            return avl.isDupsAllowed();
303        }
304        
305    
306        /**
307         * {@inheritDoc}
308         */
309        public int lessThanCount( K key ) throws Exception
310        {
311            return count;
312        }
313        
314    
315        /**
316         * {@inheritDoc}
317         */
318        public void put( K key, V value ) throws Exception
319        {
320            if ( key == null || value == null )
321            {
322                return;
323            }
324            
325            if ( avl.insert( key, value ) == null )
326            {
327                count++;
328            }
329        }
330    
331        
332        /**
333         * {@inheritDoc}
334         */
335        public void remove( K key ) throws Exception
336        {
337            if ( key == null )
338            {
339                return;
340            }
341            
342            SingletonOrOrderedSet<V> value = avl.remove( key );
343            if ( value == null )
344            {
345                return;
346            }
347    
348            if ( value.isOrderedSet() )
349            {
350                count -= value.getOrderedSet().getSize();
351            }
352            else
353            {
354                count --;
355            }
356        }
357    
358        
359        /**
360         * {@inheritDoc}
361         */
362        public void remove( K key, V value ) throws Exception
363        {
364            if ( avl.remove( key, value ) != null )
365            {
366                count--;
367            }
368        }
369        
370        
371        /**
372         * {@inheritDoc}
373         */
374        public Cursor<Tuple<K, V>> cursor() throws Exception
375        {
376            if ( ! avl.isDupsAllowed() )
377            {
378                return new AvlTreeMapNoDupsWrapperCursor<K, V>( new AvlSingletonOrOrderedSetCursor<K,V>( avl ) );
379            }
380    
381            return new AvlTableDupsCursor<K, V>( this );
382        }
383    
384        
385        /**
386         * {@inheritDoc}
387         */
388        public Cursor<Tuple<K, V>> cursor( K key ) throws Exception
389        {
390            if ( key == null )
391            {
392                return new EmptyCursor<Tuple<K,V>>();
393            }
394            
395            LinkedAvlMapNode<K, V> node = avl.find( key );
396            if ( node == null )
397            {
398                return new EmptyCursor<Tuple<K,V>>();
399            }
400            
401            if ( node.getValue().isOrderedSet() )
402            {
403                return new KeyTupleAvlCursor<K,V>( node.getValue().getOrderedSet(), key );
404            }
405            
406            return new SingletonCursor<Tuple<K,V>>( new Tuple<K,V>( key, node.getValue().getSingleton() ), 
407                    keyOnlytupleComparator );
408        }
409    
410        
411        /**
412         * {@inheritDoc}
413         */
414        public Cursor<V> valueCursor( K key ) throws Exception
415        {
416            if ( key == null )
417            {
418                return new EmptyCursor<V>();
419            }
420            
421            LinkedAvlMapNode<K, V> node = avl.find( key );
422            if ( node == null )
423            {
424                return new EmptyCursor<V>();
425            }
426            
427            if ( node.getValue().isOrderedSet() )
428            {
429                return new AvlTreeCursor<V>( node.getValue().getOrderedSet() );
430            }
431            
432            return new SingletonCursor<V>( node.getValue().getSingleton(), valComparator );
433        }
434    
435    
436        /**
437         * Returns the internal AvlTreeMap so other classes like Cursors
438         * in the same package can access it.
439         *
440         * @return AvlTreeMap used to store Tuples
441         */
442        AvlTreeMap<K, V> getAvlTreeMap()
443        {
444            return avl;
445        }
446    }