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 org.apache.directory.server.core.avltree.AvlSingletonOrOrderedSetCursor;
024    import org.apache.directory.server.core.avltree.AvlTree;
025    import org.apache.directory.server.core.avltree.AvlTreeCursor;
026    import org.apache.directory.server.core.avltree.SingletonOrOrderedSet;
027    import org.apache.directory.server.xdbm.AbstractTupleCursor;
028    import org.apache.directory.server.xdbm.Tuple;
029    import org.apache.directory.shared.ldap.cursor.Cursor;
030    import org.apache.directory.shared.ldap.cursor.InvalidCursorPositionException;
031    import org.apache.directory.shared.ldap.cursor.SingletonCursor;
032    import org.slf4j.Logger;
033    import org.slf4j.LoggerFactory;
034    
035    
036    /**
037     * A Cursor which walks and advance over AvlTables that may contain duplicate
038     * keys with values stored in an AvlTree.  All duplicate keys are traversed 
039     * returning the key and the value in a Tuple.
040     *
041     * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
042     * @version $Rev$, $Date$
043     */
044    public class AvlTableDupsCursor<K,V> extends AbstractTupleCursor<K, V>
045    {
046        private static final Logger LOG = LoggerFactory.getLogger( AvlTableDupsCursor.class.getSimpleName() );
047        
048        /** The AVL backed table this Cursor traverses over. */
049        private final AvlTable<K,V> table;
050        
051        /**
052         * The underlying wrapped cursor which returns Tuples whose values are
053         * either V objects or AvlTree objects.
054         */
055        private final AvlSingletonOrOrderedSetCursor<K, V> wrappedCursor;
056        
057        /**
058         * A Cursor over a set of value objects for the current key held in the
059         * containerTuple.  A new Cursor will be set for each new key as we
060         * traverse.  The Cursor traverses over either a AvlTree object full
061         * of values in a multi-valued key or it traverses over a BTree which
062         * contains the values in the key field of it's Tuples.
063         */
064        private Cursor<V> dupsCursor;
065    
066        /** The current Tuple returned from the wrapped cursor. */
067        private final Tuple<K,SingletonOrOrderedSet<V>> wrappedTuple = new Tuple<K, SingletonOrOrderedSet<V>>();
068    
069        /**
070         * The Tuple that is used to return values via the get() method. This
071         * same Tuple instance will be returned every time.  At different
072         * positions it may return different values for the same key.
073         */
074        private final Tuple<K,V> returnedTuple = new Tuple<K,V>();
075    
076        /** Whether or not a value is available when get() is called. */
077        private boolean valueAvailable;
078    
079        
080        /**
081         * Creates a new instance of AvlTableDupsCursor.
082         *
083         * @param table the AvlTable to build a Cursor on.
084         */
085        public AvlTableDupsCursor( AvlTable<K,V> table )
086        {
087            this.table = table;
088            this.wrappedCursor = new AvlSingletonOrOrderedSetCursor<K, V>( table.getAvlTreeMap() );
089            LOG.debug( "Created on table {}", table.getName() );
090        }
091    
092    
093        /**
094         * {@inheritDoc}
095         */
096        public boolean available()
097        {
098            return valueAvailable;
099        }
100    
101    
102        /**
103         * {@inheritDoc}
104         */
105        public void beforeKey( K key ) throws Exception
106        {
107            beforeValue( key, null );
108        }
109    
110    
111        /**
112         * {@inheritDoc}
113         */
114        public void beforeValue( K key, V value ) throws Exception
115        {
116            checkNotClosed( "beforeValue()" );
117            wrappedCursor.beforeKey( key );
118            
119            if ( wrappedCursor.next() )
120            {
121                wrappedTuple.setBoth( wrappedCursor.get() );
122                
123                if ( wrappedTuple.getValue().isOrderedSet() )
124                {
125                    AvlTree<V> avlTree = wrappedTuple.getValue().getOrderedSet();
126                    dupsCursor = new AvlTreeCursor<V>( avlTree );
127                }
128                else
129                {
130                    dupsCursor = new SingletonCursor<V>( 
131                        wrappedTuple.getValue().getSingleton(), wrappedCursor.getValuComparator() );
132                }
133                
134                if ( value == null )
135                {
136                    clearValue();
137                    return;
138                }
139        
140                /* 
141                 * The cursor over the values is only advanced if we're on the 
142                 * same key as the primary cursor.  This is because we want this
143                 * method to really position us within a set of duplicate key 
144                 * entries at the proper value.
145                 */
146                if ( table.getKeyComparator().compare( wrappedTuple.getKey(), key ) == 0 )
147                {
148                    dupsCursor.before( value );
149                }
150                
151                clearValue();
152                return;
153            }
154            
155            clearValue();
156            wrappedTuple.setKey( null );
157            wrappedTuple.setValue( null );
158        }
159        
160    
161        /**
162         * {@inheritDoc}
163         */
164        public void afterKey( K key ) throws Exception
165        {
166            afterValue( key, null );
167        }
168    
169        
170        /**
171         * {@inheritDoc}
172         */
173        public void afterValue( K key, V value ) throws Exception
174        {
175            checkNotClosed( "afterValue()" );
176            /*
177             * There is a subtle difference between after and before handling
178             * with dupicate key values.  Say we have the following tuples:
179             *
180             * (0, 0)
181             * (1, 1)
182             * (1, 2)
183             * (1, 3)
184             * (2, 2)
185             *
186             * If we request an after cursor on (1, 2).  We must make sure that
187             * the container cursor does not advance after the entry with key 1
188             * since this would result in us skip returning (1. 3) on the call to
189             * next which will incorrectly return (2, 2) instead.
190             *
191             * So if the value is null in the element then we don't care about
192             * this obviously since we just want to advance past the duplicate key
193             * values all together.  But when it is not null, then we want to
194             * go right before this key instead of after it.
195             */
196    
197            if ( value == null )
198            {
199                wrappedCursor.afterKey( key );
200            }
201            else
202            {
203                wrappedCursor.beforeKey( key );
204            }
205    
206            if ( wrappedCursor.next() )
207            {
208                wrappedTuple.setBoth( wrappedCursor.get() );
209                SingletonOrOrderedSet<V> values = wrappedTuple.getValue();
210    
211                if ( values.isOrderedSet() )
212                {
213                    AvlTree<V> set = values.getOrderedSet();
214                    dupsCursor = new AvlTreeCursor<V>( set );
215                }
216                else
217                {
218                    dupsCursor = new SingletonCursor<V>( values.getSingleton(), wrappedCursor.getValuComparator() );
219                }
220    
221                if ( value == null )
222                {
223                    clearValue();
224                    return;
225                }
226    
227                // only advance the dupsCursor if we're on same key
228                if ( table.getKeyComparator().compare( wrappedTuple.getKey(), key ) == 0 )
229                {
230                    dupsCursor.after( value );
231                }
232    
233                clearValue();
234                return;
235            }
236    
237            clearValue();
238            wrappedTuple.setKey( null );
239            wrappedTuple.setValue( null );
240        }
241    
242        
243        /**
244         * {@inheritDoc}
245         */
246        public void after( Tuple<K, V> element ) throws Exception
247        {
248            afterValue( element.getKey(), element.getValue() );
249        }
250    
251        
252        /**
253         * {@inheritDoc}
254         */
255        public void afterLast() throws Exception
256        {
257            checkNotClosed( "afterLast()" );
258            clearValue();
259            wrappedCursor.afterLast();
260            wrappedTuple.setKey( null );
261            wrappedTuple.setValue( null );
262            dupsCursor = null;
263        }
264    
265    
266        /**
267         * {@inheritDoc}
268         */
269        public void before( Tuple<K, V> element ) throws Exception
270        {
271            beforeValue( element.getKey(), element.getValue() );
272        }
273    
274        
275        /**
276         * {@inheritDoc}
277         */
278        public void beforeFirst() throws Exception
279        {
280            checkNotClosed( "beforeFirst()" );
281            clearValue();
282            wrappedCursor.beforeFirst();
283            wrappedTuple.setKey( null );
284            wrappedTuple.setValue( null );
285            dupsCursor = null;
286        }
287    
288        
289        /**
290         * {@inheritDoc}
291         */
292        public boolean first() throws Exception
293        {
294            checkNotClosed( "first()" );
295            clearValue();
296            dupsCursor = null;
297    
298            if ( wrappedCursor.first() )
299            {
300                wrappedTuple.setBoth( wrappedCursor.get() );
301                SingletonOrOrderedSet<V> values = wrappedTuple.getValue();
302    
303                if ( values.isOrderedSet() )
304                {
305                    dupsCursor = new AvlTreeCursor<V>( values.getOrderedSet() );
306                }
307                else
308                {
309                    dupsCursor = new SingletonCursor<V>( values.getSingleton(), wrappedCursor.getValuComparator() );
310                }
311    
312                /*
313                 * Since only tables with duplicate keys enabled use this
314                 * cursor, entries must have at least one value, and therefore
315                 * call to last() will always return true.
316                 */
317                dupsCursor.first();
318                valueAvailable =  true;
319                returnedTuple.setKey( wrappedTuple.getKey() );
320                returnedTuple.setValue( dupsCursor.get() );
321                return true;
322            }
323    
324            return false;
325        }
326    
327        
328        /**
329         * {@inheritDoc}
330         */
331        public Tuple<K, V> get() throws Exception
332        {
333            checkNotClosed( "get()" );
334    
335            if ( ! valueAvailable )
336            {
337                throw new InvalidCursorPositionException();
338            }
339    
340            return returnedTuple;
341        }
342    
343        
344        /**
345         * {@inheritDoc}
346         */
347        public boolean isElementReused()
348        {
349            return true;
350        }
351        
352    
353        /**
354         * {@inheritDoc}
355         */
356        public boolean last() throws Exception
357        {
358            checkNotClosed( "last()" );
359            clearValue();
360            dupsCursor = null;
361    
362            if ( wrappedCursor.last() )
363            {
364                wrappedTuple.setBoth( wrappedCursor.get() );
365                SingletonOrOrderedSet<V> values = wrappedTuple.getValue();
366    
367                if ( values.isOrderedSet() )
368                {
369                    dupsCursor = new AvlTreeCursor<V>( values.getOrderedSet() );
370                }
371                else
372                {
373                    dupsCursor = new SingletonCursor<V>( values.getSingleton(), wrappedCursor.getValuComparator() );
374                }
375    
376                /*
377                 * Since only tables with duplicate keys enabled use this
378                 * cursor, entries must have at least one value, and therefore
379                 * call to last() will always return true.
380                 */
381                dupsCursor.last();
382                valueAvailable = true;
383                returnedTuple.setKey( wrappedTuple.getKey() );
384                returnedTuple.setValue( dupsCursor.get() );
385                return true;
386            }
387    
388            return false;
389        }
390    
391        
392        /**
393         * {@inheritDoc}
394         */
395        public boolean next() throws Exception
396        {
397            checkNotClosed( "next()" );
398            /*
399             * If the cursor over the values of the current key is null or is
400             * extinguished then we need to advance to the next key.
401             */
402            if ( null == dupsCursor || ! dupsCursor.next() )
403            {
404                /*
405                 * If the wrappedCursor cursor has more elements we get the next
406                 * key/AvlTree Tuple to work with and get a cursor over it.
407                 */
408                if ( wrappedCursor.next() )
409                {
410                    wrappedTuple.setBoth( wrappedCursor.get() );
411                    SingletonOrOrderedSet<V> values = wrappedTuple.getValue();
412    
413                    if ( values.isOrderedSet())
414                    {
415                        dupsCursor = new AvlTreeCursor<V>( values.getOrderedSet() );
416                    }
417                    else
418                    {
419                        dupsCursor = new SingletonCursor<V>( values.getSingleton(), wrappedCursor.getValuComparator() );
420                    }
421    
422                    /*
423                     * Since only tables with duplicate keys enabled use this
424                     * cursor, entries must have at least one value, and therefore
425                     * call to next() after bringing the cursor to beforeFirst()
426                     * will always return true.
427                     */
428                    dupsCursor.beforeFirst();
429                    dupsCursor.next();
430                }
431                else
432                {
433                    dupsCursor = null;
434                    return false;
435                }
436            }
437    
438            /*
439             * If we get to this point then cursor has more elements and
440             * wrappedTuple holds the Tuple containing the key and the 
441             * AvlTree of values for that key which the Cursor traverses.  All we
442             * need to do is populate our tuple object with the key and the value
443             * in the cursor.
444             */
445            returnedTuple.setKey( wrappedTuple.getKey() );
446            returnedTuple.setValue( dupsCursor.get() );
447            return valueAvailable = true;
448        }
449    
450        
451        /**
452         * {@inheritDoc}
453         */
454        public boolean previous() throws Exception
455        {
456            checkNotClosed( "previous()" );
457            /*
458             * If the cursor over the values of the current key is null or is
459             * extinguished then we need to advance to the previous key.
460             */
461            if ( null == dupsCursor || ! dupsCursor.previous() )
462            {
463                /*
464                 * If the wrappedCursor cursor has more elements we get the previous
465                 * key/AvlTree Tuple to work with and get a cursor over it's
466                 * values.
467                 */
468                if ( wrappedCursor.previous() )
469                {
470                    wrappedTuple.setBoth( wrappedCursor.get() );
471                    SingletonOrOrderedSet<V> values = wrappedTuple.getValue();
472    
473                    if ( values.isOrderedSet() )
474                    {
475                        dupsCursor = new AvlTreeCursor<V>( values.getOrderedSet() );
476                    }
477                    else
478                    {
479                        dupsCursor = new SingletonCursor<V>( values.getSingleton(), wrappedCursor.getValuComparator() );
480                    }
481    
482                    /*
483                     * Since only tables with duplicate keys enabled use this
484                     * cursor, entries must have at least one value, and therefore
485                     * call to previous() after bringing the cursor to afterLast()
486                     * will always return true.
487                     */
488                    dupsCursor.afterLast();
489                    dupsCursor.previous();
490                }
491                else
492                {
493                    dupsCursor = null;
494                    return false;
495                }
496            }
497    
498            returnedTuple.setKey( wrappedTuple.getKey() );
499            returnedTuple.setValue( dupsCursor.get() );
500            return valueAvailable = true;
501        }
502    
503    
504        /**
505         * Clears the returned Tuple and makes sure valueAvailable returns false.
506         */
507        private void clearValue()
508        {
509            returnedTuple.setKey( null );
510            returnedTuple.setValue( null );
511            valueAvailable = false;
512        }
513    }