Coverage Report

Coverage Report - org.apache.maven.index.DefaultIteratorResultSet

Classes in this File

Line Coverage

Branch Coverage

Complexity

DefaultIteratorResultSet

91 %

114/125

80 %

58/72

3,688

 package org.apache.maven.index;
 
 /*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License.  You may obtain a copy of the License at
  *
  *   http://www.apache.org/licenses/LICENSE-2.0    
  *
  * Unless required by applicable law or agreed to in writing,
  * software distributed under the License is distributed on an
  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  * KIND, either express or implied.  See the License for the
  * specific language governing permissions and limitations
  * under the License.
  */
 
 import java.io.IOException;
 import java.io.StringReader;
 import java.util.ArrayList;
 import java.util.Iterator;
 import java.util.List;
 
 import org.apache.lucene.analysis.CachingTokenFilter;
 import org.apache.lucene.analysis.TokenStream;
 import org.apache.lucene.document.Document;
 import org.apache.lucene.search.Explanation;
 import org.apache.lucene.search.IndexSearcher;
 import org.apache.lucene.search.Query;
 import org.apache.lucene.search.TopDocs;
 import org.apache.lucene.search.highlight.Formatter;
 import org.apache.lucene.search.highlight.Highlighter;
 import org.apache.lucene.search.highlight.InvalidTokenOffsetsException;
 import org.apache.lucene.search.highlight.QueryScorer;
 import org.apache.lucene.search.highlight.SimpleHTMLFormatter;
 import org.apache.lucene.search.highlight.TextFragment;
 import org.apache.maven.index.context.IndexUtils;
 import org.apache.maven.index.context.IndexingContext;
 import org.apache.maven.index.creator.JarFileContentsIndexCreator;
 
 /**
  * Default implementation of IteratorResultSet. TODO: there is too much of logic, refactor this!
  * 
  * @author cstamas
  */
 public class DefaultIteratorResultSet
     implements IteratorResultSet
 {
     private final IteratorSearchRequest searchRequest;
 
     private final IndexSearcher indexSearcher;
 
     private final List<IndexingContext> contexts;
 
     private final int[] starts;
 
     private final ArtifactInfoFilter filter;
 
     private final ArtifactInfoPostprocessor postprocessor;
 
     private final List<MatchHighlightRequest> matchHighlightRequests;
 
     private final TopDocs hits;
 
     private final int from;
 
     private final int count;
 
     private final int maxRecPointer;
 
     private int pointer;
 
     private int processedArtifactInfoCount;
 
     private ArtifactInfo ai;
 
     protected DefaultIteratorResultSet( final IteratorSearchRequest request, final IndexSearcher indexSearcher,
                                         final List<IndexingContext> contexts, final TopDocs hits )
         throws IOException
     {
         this.searchRequest = request;
 
         this.indexSearcher = indexSearcher;
 
         this.contexts = contexts;
 
         {
             int maxDoc = 0;
             this.starts = new int[contexts.size() + 1]; // build starts array
             for ( int i = 0; i < contexts.size(); i++ )
             {
                 starts[i] = maxDoc;
                 maxDoc += contexts.get( i ).getIndexReader().maxDoc(); // compute maxDocs
             }
             starts[contexts.size()] = maxDoc;
         }
 
         this.filter = request.getArtifactInfoFilter();
 
         this.postprocessor = request.getArtifactInfoPostprocessor();
 
         this.matchHighlightRequests = request.getMatchHighlightRequests();
 
         this.hits = hits;
 
         this.from = request.getStart();
 
         this.count =
             ( request.getCount() == AbstractSearchRequest.UNDEFINED ? hits.scoreDocs.length : Math.min(
                 request.getCount(), hits.scoreDocs.length ) );
 
         this.pointer = from;
 
         this.processedArtifactInfoCount = 0;
 
         this.maxRecPointer = from + count;
 
         ai = createNextAi();
 
         if ( ai == null )
         {
             cleanUp();
         }
     }
 
     public boolean hasNext()
     {
         return ai != null;
     }
 
     public ArtifactInfo next()
     {
         ArtifactInfo result = ai;
 
         try
         {
             ai = createNextAi();
         }
         catch ( IOException e )
         {
             ai = null;
 
             throw new IllegalStateException( "Cannot fetch next ArtifactInfo!", e );
         }
         finally
         {
             if ( ai == null )
             {
                 cleanUp();
             }
         }
 
         return result;
     }
 
     public void remove()
     {
         throw new UnsupportedOperationException( "Method not supported on " + getClass().getName() );
     }
 
     public Iterator<ArtifactInfo> iterator()
     {
         return this;
     }
 
     public void close()
     {
         cleanUp();
     }
 
     public int getTotalProcessedArtifactInfoCount()
     {
         return processedArtifactInfoCount;
     }
 
     @Override
     public void finalize()
         throws Throwable
     {
         super.finalize();
 
         if ( !cleanedUp )
         {
             System.err.println( "#WARNING: Lock leaking from " + getClass().getName() + " for query "
                 + searchRequest.getQuery().toString() );
 
             cleanUp();
         }
     }
 
     // ==
 
     protected ArtifactInfo createNextAi()
         throws IOException
     {
         ArtifactInfo result = null;
 
         // we should stop if:
         // a) we found what we want
         // b) pointer advanced over more documents that user requested
         // c) pointer advanced over more documents that hits has
         // or we found what we need
         while ( ( result == null ) && ( pointer < maxRecPointer ) && ( pointer < hits.scoreDocs.length ) )
         {
             Document doc = indexSearcher.doc( hits.scoreDocs[pointer].doc );
 
             IndexingContext context = getIndexingContextForPointer( doc, hits.scoreDocs[pointer].doc );
 
             result = IndexUtils.constructArtifactInfo( doc, context );
 
             if ( result != null )
             {
                 // WARNING: NOT FOR PRODUCTION SYSTEMS, THIS IS VERY COSTLY OPERATION
                 // For debugging only!!!
                 if ( searchRequest.isLuceneExplain() )
                 {
                     result.getAttributes().put( Explanation.class.getName(),
                         indexSearcher.explain( searchRequest.getQuery(), hits.scoreDocs[pointer].doc ).toString() );
                 }
 
                 result.setLuceneScore( hits.scoreDocs[pointer].score );
 
                 result.repository = context.getRepositoryId();
 
                 result.context = context.getId();
 
                 if ( filter != null )
                 {
                     if ( !filter.accepts( context, result ) )
                     {
                         result = null;
                     }
                 }
 
                 if ( result != null && postprocessor != null )
                 {
                     postprocessor.postprocess( context, result );
                 }
 
                 if ( result != null && matchHighlightRequests.size() > 0 )
                 {
                     calculateHighlights( context, doc, result );
                 }
             }
 
             pointer++;
             processedArtifactInfoCount++;
         }
 
         return result;
     }
 
     private volatile boolean cleanedUp = false;
 
     protected synchronized void cleanUp()
     {
         if ( cleanedUp )
         {
             return;
         }
 
         for ( IndexingContext ctx : contexts )
         {
             ctx.unlock();
         }
 
         this.cleanedUp = true;
     }
 
     /**
      * Creates the MatchHighlights and adds them to ArtifactInfo if found/can.
      * 
      * @param context
      * @param d
      * @param ai
      */
     protected void calculateHighlights( IndexingContext context, Document d, ArtifactInfo ai )
         throws IOException
     {
         IndexerField field = null;
 
         String text = null;
 
         List<String> highlightFragment = null;
 
         for ( MatchHighlightRequest hr : matchHighlightRequests )
         {
             field = selectStoredIndexerField( hr.getField() );
 
             if ( field != null )
             {
                 text = ai.getFieldValue( field.getOntology() );
 
                 if ( text != null )
                 {
                     highlightFragment = highlightField( context, hr, field, text );
 
                     if ( highlightFragment != null && highlightFragment.size() > 0 )
                     {
                         MatchHighlight matchHighlight = new MatchHighlight( hr.getField(), highlightFragment );
 
                         ai.getMatchHighlights().add( matchHighlight );
                     }
                 }
             }
         }
     }
 
     /**
      * Select a STORED IndexerField assigned to passed in Field.
      * 
      * @param field
      * @return
      */
     protected IndexerField selectStoredIndexerField( Field field )
     {
         // hack here
         if ( MAVEN.CLASSNAMES.equals( field ) )
         {
             return JarFileContentsIndexCreator.FLD_CLASSNAMES;
         }
         else
         {
             return field.getIndexerFields().isEmpty() ? null : field.getIndexerFields().iterator().next();
         }
     }
 
     /**
      * Returns a string that contains match fragment highlighted in style as user requested.
      * 
      * @param context
      * @param hr
      * @param field
      * @param doc
      * @return
      * @throws IOException
      */
     protected List<String> highlightField( IndexingContext context, MatchHighlightRequest hr, IndexerField field,
                                            String text )
         throws IOException
     {
         // exception with classnames
         if ( MAVEN.CLASSNAMES.equals( field.getOntology() ) )
         {
             text = text.replace( '/', '.' ).replaceAll( "^\\.", "" ).replaceAll( "\n\\.", "\n" );
         }
 
         Query rewrittenQuery = hr.getQuery().rewrite( context.getIndexReader() );
 
         CachingTokenFilter tokenStream =
             new CachingTokenFilter( context.getAnalyzer().tokenStream( field.getKey(), new StringReader( text ) ) );
 
         Formatter formatter = null;
 
         if ( MatchHighlightMode.HTML.equals( hr.getHighlightMode() ) )
         {
             formatter = new SimpleHTMLFormatter();
         }
         else
         {
             throw new UnsupportedOperationException( "Hightlight more \"" + hr.getHighlightMode().toString()
                 + "\" is not supported!" );
         }
 
         return getBestFragments( rewrittenQuery, formatter, tokenStream, text, 3 );
     }
 
     protected final List<String> getBestFragments( Query query, Formatter formatter, TokenStream tokenStream,
                                                    String text, int maxNumFragments )
         throws IOException
     {
         Highlighter highlighter = new Highlighter( formatter, new CleaningEncoder(), new QueryScorer( query ) );
 
         highlighter.setTextFragmenter( new OneLineFragmenter() );
 
         tokenStream.reset();
 
         maxNumFragments = Math.max( 1, maxNumFragments ); // sanity check
 
         TextFragment[] frag;
         // Get text
         ArrayList<String> fragTexts = new ArrayList<String>( maxNumFragments );
 
         try
         {
             frag = highlighter.getBestTextFragments( tokenStream, text, false, maxNumFragments );
 
             for ( int i = 0; i < frag.length; i++ )
             {
                 if ( ( frag[i] != null ) && ( frag[i].getScore() > 0 ) )
                 {
                     fragTexts.add( frag[i].toString() );
                 }
             }
         }
         catch ( InvalidTokenOffsetsException e )
         {
             // empty?
         }
 
         return fragTexts;
     }
 
     protected IndexingContext getIndexingContextForPointer( Document doc, int docPtr )
     {
         return contexts.get( readerIndex( docPtr, this.starts, this.contexts.size() ) );
     }
 
     private static int readerIndex( int n, int[] starts, int numSubReaders )
     { // find reader for doc n:
         int lo = 0; // search starts array
         int hi = numSubReaders - 1; // for first element less
 
         while ( hi >= lo )
         {
             int mid = ( lo + hi ) >>> 1;
             int midValue = starts[mid];
             if ( n < midValue )
             {
                 hi = mid - 1;
             }
             else if ( n > midValue )
             {
                 lo = mid + 1;
             }
             else
             { // found a match
                 while ( mid + 1 < numSubReaders && starts[mid + 1] == midValue )
                 {
                     mid++; // scan to last match
                 }
                 return mid;
             }
         }
         return hi;
     }
 }

1		package org.apache.maven.index;
2
3		/*
4		* Licensed to the Apache Software Foundation (ASF) under one
5		* or more contributor license agreements. See the NOTICE file
6		* distributed with this work for additional information
7		* regarding copyright ownership. The ASF licenses this file
8		* to you under the Apache License, Version 2.0 (the
9		* "License"); you may not use this file except in compliance
10		* with the License. You may obtain a copy of the License at
11		*
12		* http://www.apache.org/licenses/LICENSE-2.0
13		*
14		* Unless required by applicable law or agreed to in writing,
15		* software distributed under the License is distributed on an
16		* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
17		* KIND, either express or implied. See the License for the
18		* specific language governing permissions and limitations
19		* under the License.
20		*/
21
22		import java.io.IOException;
23		import java.io.StringReader;
24		import java.util.ArrayList;
25		import java.util.Iterator;
26		import java.util.List;
27
28		import org.apache.lucene.analysis.CachingTokenFilter;
29		import org.apache.lucene.analysis.TokenStream;
30		import org.apache.lucene.document.Document;
31		import org.apache.lucene.search.Explanation;
32		import org.apache.lucene.search.IndexSearcher;
33		import org.apache.lucene.search.Query;
34		import org.apache.lucene.search.TopDocs;
35		import org.apache.lucene.search.highlight.Formatter;
36		import org.apache.lucene.search.highlight.Highlighter;
37		import org.apache.lucene.search.highlight.InvalidTokenOffsetsException;
38		import org.apache.lucene.search.highlight.QueryScorer;
39		import org.apache.lucene.search.highlight.SimpleHTMLFormatter;
40		import org.apache.lucene.search.highlight.TextFragment;
41		import org.apache.maven.index.context.IndexUtils;
42		import org.apache.maven.index.context.IndexingContext;
43		import org.apache.maven.index.creator.JarFileContentsIndexCreator;
44
45		/**
46		* Default implementation of IteratorResultSet. TODO: there is too much of logic, refactor this!
47		*
48		* @author cstamas
49		*/
50	334	public class DefaultIteratorResultSet
51		implements IteratorResultSet
52		{
53		private final IteratorSearchRequest searchRequest;
54
55		private final IndexSearcher indexSearcher;
56
57		private final List<IndexingContext> contexts;
58
59		private final int[] starts;
60
61		private final ArtifactInfoFilter filter;
62
63		private final ArtifactInfoPostprocessor postprocessor;
64
65		private final List<MatchHighlightRequest> matchHighlightRequests;
66
67		private final TopDocs hits;
68
69		private final int from;
70
71		private final int count;
72
73		private final int maxRecPointer;
74
75		private int pointer;
76
77		private int processedArtifactInfoCount;
78
79		private ArtifactInfo ai;
80
81		protected DefaultIteratorResultSet( final IteratorSearchRequest request, final IndexSearcher indexSearcher,
82		final List<IndexingContext> contexts, final TopDocs hits )
83		throws IOException
84	115	{
85	115	this.searchRequest = request;
86
87	115	this.indexSearcher = indexSearcher;
88
89	115	this.contexts = contexts;
90
91		{
92	115	int maxDoc = 0;
93	115	this.starts = new int[contexts.size() + 1]; // build starts array
94	232	for ( int i = 0; i < contexts.size(); i++ )
95		{
96	117	starts[i] = maxDoc;
97	117	maxDoc += contexts.get( i ).getIndexReader().maxDoc(); // compute maxDocs
98		}
99	115	starts[contexts.size()] = maxDoc;
100		}
101
102	115	this.filter = request.getArtifactInfoFilter();
103
104	115	this.postprocessor = request.getArtifactInfoPostprocessor();
105
106	115	this.matchHighlightRequests = request.getMatchHighlightRequests();
107
108	115	this.hits = hits;
109
110	115	this.from = request.getStart();
111
112	115	this.count =
113		( request.getCount() == AbstractSearchRequest.UNDEFINED ? hits.scoreDocs.length : Math.min(
114		request.getCount(), hits.scoreDocs.length ) );
115
116	115	this.pointer = from;
117
118	115	this.processedArtifactInfoCount = 0;
119
120	115	this.maxRecPointer = from + count;
121
122	115	ai = createNextAi();
123
124	115	if ( ai == null )
125		{
126	45	cleanUp();
127		}
128	115	}
129
130		public boolean hasNext()
131		{
132	400	return ai != null;
133		}
134
135		public ArtifactInfo next()
136		{
137	334	ArtifactInfo result = ai;
138
139		try
140		{
141	334	ai = createNextAi();
142		}
143	0	catch ( IOException e )
144		{
145	0	ai = null;
146
147	0	throw new IllegalStateException( "Cannot fetch next ArtifactInfo!", e );
148		}
149		finally
150		{
151	334	if ( ai == null )
152		{
153	69	cleanUp();
154		}
155		}
156
157	334	return result;
158		}
159
160		public void remove()
161		{
162	0	throw new UnsupportedOperationException( "Method not supported on " + getClass().getName() );
163		}
164
165		public Iterator<ArtifactInfo> iterator()
166		{
167	2	return this;
168		}
169
170		public void close()
171		{
172	93	cleanUp();
173	93	}
174
175		public int getTotalProcessedArtifactInfoCount()
176		{
177	0	return processedArtifactInfoCount;
178		}
179
180		@Override
181		public void finalize()
182		throws Throwable
183		{
184	115	super.finalize();
185
186	115	if ( !cleanedUp )
187		{
188	0	System.err.println( "#WARNING: Lock leaking from " + getClass().getName() + " for query "
189		+ searchRequest.getQuery().toString() );
190
191	0	cleanUp();
192		}
193	115	}
194
195		// ==
196
197		protected ArtifactInfo createNextAi()
198		throws IOException
199		{
200	449	ArtifactInfo result = null;
201
202		// we should stop if:
203		// a) we found what we want
204		// b) pointer advanced over more documents that user requested
205		// c) pointer advanced over more documents that hits has
206		// or we found what we need
207	825	while ( ( result == null ) && ( pointer < maxRecPointer ) && ( pointer < hits.scoreDocs.length ) )
208		{
209	376	Document doc = indexSearcher.doc( hits.scoreDocs[pointer].doc );
210
211	376	IndexingContext context = getIndexingContextForPointer( doc, hits.scoreDocs[pointer].doc );
212
213	376	result = IndexUtils.constructArtifactInfo( doc, context );
214
215	376	if ( result != null )
216		{
217		// WARNING: NOT FOR PRODUCTION SYSTEMS, THIS IS VERY COSTLY OPERATION
218		// For debugging only!!!
219	376	if ( searchRequest.isLuceneExplain() )
220		{
221	4	result.getAttributes().put( Explanation.class.getName(),
222		indexSearcher.explain( searchRequest.getQuery(), hits.scoreDocs[pointer].doc ).toString() );
223		}
224
225	376	result.setLuceneScore( hits.scoreDocs[pointer].score );
226
227	376	result.repository = context.getRepositoryId();
228
229	376	result.context = context.getId();
230
231	376	if ( filter != null )
232		{
233	47	if ( !filter.accepts( context, result ) )
234		{
235	41	result = null;
236		}
237		}
238
239	376	if ( result != null && postprocessor != null )
240		{
241	0	postprocessor.postprocess( context, result );
242		}
243
244	376	if ( result != null && matchHighlightRequests.size() > 0 )
245		{
246	20	calculateHighlights( context, doc, result );
247		}
248		}
249
250	376	pointer++;
251	376	processedArtifactInfoCount++;
252	376	}
253
254	449	return result;
255		}
256
257	115	private volatile boolean cleanedUp = false;
258
259		protected synchronized void cleanUp()
260		{
261	207	if ( cleanedUp )
262		{
263	92	return;
264		}
265
266	115	for ( IndexingContext ctx : contexts )
267		{
268	117	ctx.unlock();
269		}
270
271	115	this.cleanedUp = true;
272	115	}
273
274		/**
275		* Creates the MatchHighlights and adds them to ArtifactInfo if found/can.
276		*
277		* @param context
278		* @param d
279		* @param ai
280		*/
281		protected void calculateHighlights( IndexingContext context, Document d, ArtifactInfo ai )
282		throws IOException
283		{
284	20	IndexerField field = null;
285
286	20	String text = null;
287
288	20	List<String> highlightFragment = null;
289
290	20	for ( MatchHighlightRequest hr : matchHighlightRequests )
291		{
292	20	field = selectStoredIndexerField( hr.getField() );
293
294	20	if ( field != null )
295		{
296	20	text = ai.getFieldValue( field.getOntology() );
297
298	20	if ( text != null )
299		{
300	20	highlightFragment = highlightField( context, hr, field, text );
301
302	20	if ( highlightFragment != null && highlightFragment.size() > 0 )
303		{
304	5	MatchHighlight matchHighlight = new MatchHighlight( hr.getField(), highlightFragment );
305
306	5	ai.getMatchHighlights().add( matchHighlight );
307	20	}
308		}
309		}
310		}
311	20	}
312
313		/**
314		* Select a STORED IndexerField assigned to passed in Field.
315		*
316		* @param field
317		* @return
318		*/
319		protected IndexerField selectStoredIndexerField( Field field )
320		{
321		// hack here
322	20	if ( MAVEN.CLASSNAMES.equals( field ) )
323		{
324	5	return JarFileContentsIndexCreator.FLD_CLASSNAMES;
325		}
326		else
327		{
328	15	return field.getIndexerFields().isEmpty() ? null : field.getIndexerFields().iterator().next();
329		}
330		}
331
332		/**
333		* Returns a string that contains match fragment highlighted in style as user requested.
334		*
335		* @param context
336		* @param hr
337		* @param field
338		* @param doc
339		* @return
340		* @throws IOException
341		*/
342		protected List<String> highlightField( IndexingContext context, MatchHighlightRequest hr, IndexerField field,
343		String text )
344		throws IOException
345		{
346		// exception with classnames
347	20	if ( MAVEN.CLASSNAMES.equals( field.getOntology() ) )
348		{
349	5	text = text.replace( '/', '.' ).replaceAll( "^\\.", "" ).replaceAll( "\n\\.", "\n" );
350		}
351
352	20	Query rewrittenQuery = hr.getQuery().rewrite( context.getIndexReader() );
353
354	20	CachingTokenFilter tokenStream =
355		new CachingTokenFilter( context.getAnalyzer().tokenStream( field.getKey(), new StringReader( text ) ) );
356
357	20	Formatter formatter = null;
358
359	20	if ( MatchHighlightMode.HTML.equals( hr.getHighlightMode() ) )
360		{
361	20	formatter = new SimpleHTMLFormatter();
362		}
363		else
364		{
365	0	throw new UnsupportedOperationException( "Hightlight more \"" + hr.getHighlightMode().toString()
366		+ "\" is not supported!" );
367		}
368
369	20	return getBestFragments( rewrittenQuery, formatter, tokenStream, text, 3 );
370		}
371
372		protected final List<String> getBestFragments( Query query, Formatter formatter, TokenStream tokenStream,
373		String text, int maxNumFragments )
374		throws IOException
375		{
376	20	Highlighter highlighter = new Highlighter( formatter, new CleaningEncoder(), new QueryScorer( query ) );
377
378	20	highlighter.setTextFragmenter( new OneLineFragmenter() );
379
380	20	tokenStream.reset();
381
382	20	maxNumFragments = Math.max( 1, maxNumFragments ); // sanity check
383
384		TextFragment[] frag;
385		// Get text
386	20	ArrayList<String> fragTexts = new ArrayList<String>( maxNumFragments );
387
388		try
389		{
390	20	frag = highlighter.getBestTextFragments( tokenStream, text, false, maxNumFragments );
391
392	40	for ( int i = 0; i < frag.length; i++ )
393		{
394	20	if ( ( frag[i] != null ) && ( frag[i].getScore() > 0 ) )
395		{
396	5	fragTexts.add( frag[i].toString() );
397		}
398		}
399		}
400	0	catch ( InvalidTokenOffsetsException e )
401		{
402		// empty?
403	20	}
404
405	20	return fragTexts;
406		}
407
408		protected IndexingContext getIndexingContextForPointer( Document doc, int docPtr )
409		{
410	376	return contexts.get( readerIndex( docPtr, this.starts, this.contexts.size() ) );
411		}
412
413		private static int readerIndex( int n, int[] starts, int numSubReaders )
414		{ // find reader for doc n:
415	376	int lo = 0; // search starts array
416	376	int hi = numSubReaders - 1; // for first element less
417
418	775	while ( hi >= lo )
419		{
420	406	int mid = ( lo + hi ) >>> 1;
421	406	int midValue = starts[mid];
422	406	if ( n < midValue )
423		{
424	20	hi = mid - 1;
425		}
426	386	else if ( n > midValue )
427		{
428	379	lo = mid + 1;
429		}
430		else
431		{ // found a match
432	7	while ( mid + 1 < numSubReaders && starts[mid + 1] == midValue )
433		{
434	0	mid++; // scan to last match
435		}
436	7	return mid;
437		}
438	399	}
439	369	return hi;
440		}
441		}