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.xdbm.search.impl;
021    
022    
023    import java.util.ArrayList;
024    import java.util.HashSet;
025    import java.util.List;
026    import java.util.Set;
027    
028    import org.apache.directory.server.i18n.I18n;
029    import org.apache.directory.server.xdbm.IndexEntry;
030    import org.apache.directory.server.xdbm.AbstractIndexCursor;
031    import org.apache.directory.server.xdbm.IndexCursor;
032    import org.apache.directory.server.xdbm.search.Evaluator;
033    import org.apache.directory.shared.ldap.cursor.Cursor;
034    import org.apache.directory.shared.ldap.cursor.InvalidCursorPositionException;
035    import org.apache.directory.shared.ldap.entry.ServerEntry;
036    import org.apache.directory.shared.ldap.filter.ExprNode;
037    
038    
039    /**
040     * A Cursor returning candidates satisfying a logical disjunction expression.
041     *
042     * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
043     * @version $Rev$
044     */
045    public class OrCursor<V, ID> extends AbstractIndexCursor<V, ServerEntry, ID>
046    {
047        private static final String UNSUPPORTED_MSG = I18n.err( I18n.ERR_722 );
048        private final List<IndexCursor<V, ServerEntry, ID>> cursors;
049        private final List<Evaluator<? extends ExprNode, ServerEntry, ID>> evaluators;
050        private final List<Set<ID>> blacklists;
051        private int cursorIndex = -1;
052        private boolean available = false;
053    
054    
055        // TODO - do same evaluator fail fast optimization that we do in AndCursor
056        public OrCursor( List<IndexCursor<V, ServerEntry, ID>> cursors,
057            List<Evaluator<? extends ExprNode, ServerEntry, ID>> evaluators )
058        {
059            if ( cursors.size() <= 1 )
060            {
061                throw new IllegalArgumentException( I18n.err( I18n.ERR_723 ) );
062            }
063    
064            this.cursors = cursors;
065            this.evaluators = evaluators;
066            this.blacklists = new ArrayList<Set<ID>>();
067    
068            for ( int ii = 0; ii < cursors.size(); ii++ )
069            {
070                this.blacklists.add( new HashSet<ID>() );
071            }
072            this.cursorIndex = 0;
073        }
074    
075    
076        public boolean available()
077        {
078            return available;
079        }
080    
081    
082        public void before( IndexEntry<V, ServerEntry, ID> element ) throws Exception
083        {
084            throw new UnsupportedOperationException( UNSUPPORTED_MSG );
085        }
086    
087    
088        public void after( IndexEntry<V, ServerEntry, ID> element ) throws Exception
089        {
090            throw new UnsupportedOperationException( UNSUPPORTED_MSG );
091        }
092    
093    
094        public void beforeValue( ID id, V value ) throws Exception
095        {
096            throw new UnsupportedOperationException( UNSUPPORTED_MSG );
097        }
098    
099    
100        public void afterValue( ID id, V value ) throws Exception
101        {
102            throw new UnsupportedOperationException( UNSUPPORTED_MSG );
103        }
104    
105    
106        public void beforeFirst() throws Exception
107        {
108            checkNotClosed( "beforeFirst()" );
109            cursorIndex = 0;
110            cursors.get( cursorIndex ).beforeFirst();
111            available = false;
112        }
113    
114    
115        public void afterLast() throws Exception
116        {
117            checkNotClosed( "afterLast()" );
118            cursorIndex = cursors.size() - 1;
119            cursors.get( cursorIndex ).afterLast();
120            available = false;
121        }
122    
123    
124        public boolean first() throws Exception
125        {
126            beforeFirst();
127            return available = next();
128        }
129    
130    
131        public boolean last() throws Exception
132        {
133            afterLast();
134            return available = previous();
135        }
136    
137    
138        private boolean isBlackListed( ID id )
139        {
140            return blacklists.get( cursorIndex ).contains( id );
141        }
142    
143    
144        /**
145         * The first sub-expression Cursor to advance to an entry adds the entry
146         * to the blacklists of other Cursors that might return that entry.
147         *
148         * @param indexEntry the index entry to blacklist
149         * @throws Exception if there are problems accessing underlying db
150         */
151        private void blackListIfDuplicate( IndexEntry<?, ServerEntry, ID> indexEntry ) throws Exception
152        {
153            for ( int ii = 0; ii < evaluators.size(); ii++ )
154            {
155                if ( ii == cursorIndex )
156                {
157                    continue;
158                }
159    
160                if ( evaluators.get( ii ).evaluate( indexEntry ) )
161                {
162                    blacklists.get( ii ).add( indexEntry.getId() );
163                }
164            }
165        }
166    
167    
168        public boolean previous() throws Exception
169        {
170            while ( cursors.get( cursorIndex ).previous() )
171            {
172                checkNotClosed( "previous()" );
173                IndexEntry<?, ServerEntry, ID> candidate = cursors.get( cursorIndex ).get();
174                if ( !isBlackListed( candidate.getId() ) )
175                {
176                    blackListIfDuplicate( candidate );
177                    return available = true;
178                }
179            }
180    
181            while ( cursorIndex > 0 )
182            {
183                checkNotClosed( "previous()" );
184                cursorIndex--;
185                cursors.get( cursorIndex ).afterLast();
186    
187                while ( cursors.get( cursorIndex ).previous() )
188                {
189                    checkNotClosed( "previous()" );
190                    IndexEntry<?, ServerEntry, ID> candidate = cursors.get( cursorIndex ).get();
191                    if ( !isBlackListed( candidate.getId() ) )
192                    {
193                        blackListIfDuplicate( candidate );
194                        return available = true;
195                    }
196                }
197            }
198    
199            return available = false;
200        }
201    
202    
203        public boolean next() throws Exception
204        {
205            while ( cursors.get( cursorIndex ).next() )
206            {
207                checkNotClosed( "next()" );
208                IndexEntry<?, ServerEntry, ID> candidate = cursors.get( cursorIndex ).get();
209                if ( !isBlackListed( candidate.getId() ) )
210                {
211                    blackListIfDuplicate( candidate );
212                    return available = true;
213                }
214            }
215    
216            while ( cursorIndex < cursors.size() - 1 )
217            {
218                checkNotClosed( "previous()" );
219                cursorIndex++;
220                cursors.get( cursorIndex ).beforeFirst();
221    
222                while ( cursors.get( cursorIndex ).next() )
223                {
224                    checkNotClosed( "previous()" );
225                    IndexEntry<?, ServerEntry, ID> candidate = cursors.get( cursorIndex ).get();
226                    if ( !isBlackListed( candidate.getId() ) )
227                    {
228                        blackListIfDuplicate( candidate );
229                        return available = true;
230                    }
231                }
232            }
233    
234            return available = false;
235        }
236    
237    
238        public IndexEntry<V, ServerEntry, ID> get() throws Exception
239        {
240            checkNotClosed( "get()" );
241            if ( available )
242            {
243                return cursors.get( cursorIndex ).get();
244            }
245    
246            throw new InvalidCursorPositionException( I18n.err( I18n.ERR_708 ) );
247        }
248    
249    
250        public boolean isElementReused()
251        {
252            return cursors.get( cursorIndex ).isElementReused();
253        }
254    
255    
256        public void close() throws Exception
257        {
258            super.close();
259            for ( Cursor<?> cursor : cursors )
260            {
261                cursor.close();
262            }
263        }
264    }