1	#Region "Microsoft.VisualBasic::3d0f98729dabf9adc41e585745d2c0ac, Microsoft.VisualBasic.Core\Language\Language\Java\Collections.vb"
2
3	' Author:
4	'
5	'       asuka (amethyst.asuka@gcmodeller.org)
6	'       xie (genetics@smrucc.org)
7	'       xieguigang (xie.guigang@live.com)
8	'
9	' Copyright (c) 2018 GPL3 Licensed
10	'
11	'
12	' GNU GENERAL PUBLIC LICENSE (GPL3)
13	'
14	'
15	' This program is free software: you can redistribute it and/or modify
16	' it under the terms of the GNU General Public License as published by
17	' the Free Software Foundation, either version 3 of the License, or
18	' (at your option) any later version.
19	'
20	' This program is distributed in the hope that it will be useful,
21	' but WITHOUT ANY WARRANTY; without even the implied warranty of
22	' MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
23	' GNU General Public License for more details.
24	'
25	' You should have received a copy of the GNU General Public License
26	' along with this program. If not, see <http://www.gnu.org/licenses/>.
27
28
29
30	' /********************************************************************************/
31
32	' Summaries:
33
34	'     Module Collections
35	'
36	'         Function: [get], (+2 Overloads) binarySearch, (+2 Overloads) indexedBinarySearch, (+2 Overloads) iteratorBinarySearch
37	'
38	'
39	' /********************************************************************************/
40
41	#End Region
42
43	Imports System
44	Imports System.Diagnostics
45	Imports System.Collections
46	Imports System.Collections.Generic
47	Imports Microsoft.VisualBasic.Linq
48
49	' ' * Copyright (c) 1997, 2014, Oracle and/or its affiliates. All rights reserved.
50	' * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
51	' *
52	' *
53	' *
54	' *
55	' *
56	' *
57	' *
58	' *
59	' *
60	' *
61	' *
62	' *
63	' *
64	' *
65	' *
66	' *
67	' *
68	' *
69	' *
70	' *
71	'
72
73	Namespace Language.Java
74
75	''' <summary>
76	''' This class consists exclusively of static methods that operate on or return
77	''' collections.  It contains polymorphic algorithms that operate on
78	''' collections, "wrappers", which return a new collection backed by a
79	''' specified collection, and a few other odds and ends.
80	'''
81	''' &lt;p>The methods of this class all throw a <tt>NullPointerException</tt>
82	''' if the collections or class objects provided to them are null.
83	'''
84	''' &lt;p>The documentation for the polymorphic algorithms contained in this class
85	''' generally includes a brief description of the <i>implementation</i>.  Such
86	''' descriptions should be regarded as <i>implementation notes</i>, rather than
87	''' parts of the <i>specification</i>.  Implementors should feel free to
88	''' substitute other algorithms, so long as the specification itself is adhered
89	''' to.  (For example, the algorithm used by <tt>sort</tt> does not have to be
90	''' a mergesort, but it does have to be <i>stable</i>.)
91	'''
92	''' &lt;p>The "destructive" algorithms contained in this [Class], that is, the
93	''' algorithms that modify the collection on which they operate, are specified
94	''' to throw <tt>UnsupportedOperationException</tt> if the collection does not
95	''' support the appropriate mutation primitive(s), such as the <tt>set</tt>
96	''' method.  These algorithms may, but are not required to, throw this
97	''' exception if an invocation would have no effect on the collection.  For
98	''' example, invoking the <tt>sort</tt> method on an unmodifiable list that is
99	''' already sorted may or may not throw <tt>UnsupportedOperationException</tt>.
100	'''
101	''' &lt;p>This class is a member of the
102	''' <a href="{@docRoot}/../technotes/guides/collections/index.html">
103	''' Java Collections Framework</a>.
104	'''
105	''' @author  Josh Bloch
106	''' @author  Neal Gafter </summary>
107	Public Module Collections
108
109	' Algorithms
110
111	'
112	'     * Tuning parameters for algorithms - Many of the List algorithms have
113	'     * two implementations, one of which is appropriate for RandomAccess
114	'     * lists, the other for "sequential."  Often, the random access variant
115	'     * yields better performance on small sequential access lists.  The
116	'     * tuning parameters below determine the cutoff point for what constitutes
117	'     * a "small" sequential access list for each algorithm.  The values below
118	'     * were empirically determined to work well for LinkedList. Hopefully
119	'     * they should be reasonable for other sequential access List
120	'     * implementations.  Those doing performance work on this code would
121	'     * do well to validate the values of these parameters from time to time.
122	'     * (The first word of each tuning parameter name is the algorithm to which
123	'     * it applies.)
124	'
125	Private Const BINARYSEARCH_THRESHOLD As Integer = 5000
126	Private Const REVERSE_THRESHOLD As Integer = 18
127	Private Const SHUFFLE_THRESHOLD As Integer = 5
128	Private Const FILL_THRESHOLD As Integer = 25
129	Private Const ROTATE_THRESHOLD As Integer = 100
130	Private Const COPY_THRESHOLD As Integer = 10
131	Private Const REPLACEALL_THRESHOLD As Integer = 11
132	Private Const INDEXOFSUBLIST_THRESHOLD As Integer = 35
133
134
135
136	''' <summary>
137	''' Searches the specified list for the specified object using the binary
138	''' search algorithm.  The list must be sorted into ascending order
139	''' according to the Comparable natural ordering of its
140	''' elements (as by the #sort(List) method) prior to making this
141	''' call.  If it is not sorted, the results are undefined.  If the list
142	''' contains multiple elements equal to the specified object, there is no
143	''' guarantee which one will be found.
144	'''
145	''' &lt;p>This method runs in log(n) time for a "random access" list (which
146	''' provides near-constant-time positional access).  If the specified list
147	''' does not implement the RandomAccess interface and is large,
148	''' this method will do an iterator-based binary search that performs
149	''' O(n) link traversals and O(log n) element comparisons.
150	''' </summary>
151	''' <typeparam name="T">the class of the objects in the list</typeparam>
152	''' <param name="list"> the list to be searched. </param>
153	''' <param name="key"> the key to be searched for. </param>
154	''' <returns> the index of the search key, if it is contained in the list;
155	'''         otherwise, &lt;tt>(-(&lt;i>insertion point&lt;/i>) - 1)&lt;/tt>.  The
156	'''         &lt;i>insertion point&lt;/i> is defined as the point at which the
157	'''         key would be inserted into the list: the index of the first
158	'''         element greater than the key, or &lt;tt>list.size()&lt;/tt> if all
159	'''         elements in the list are less than the specified key.  Note
160	'''         that this guarantees that the return value will be &gt;= 0 if
161	'''         and only if the key is found.
162	''' </returns>
163	Public Function binarySearch(Of T As IComparable(Of T))(list As List(Of T), key As T) As Integer
164	If list.Count < BINARYSEARCH_THRESHOLD Then
165	Return Collections.indexedBinarySearch(list, key)
166	Else
167	Return Collections.iteratorBinarySearch(list, key)
168	End If
169	End Function
170
171	'JAVA TO VB CONVERTER TODO TASK: There is no .NET equivalent to the Java 'super' constraint:
172	'JAVA TO VB CONVERTER TODO TASK: Java wildcard generics are not converted to .NET:
173	Private Function indexedBinarySearch(Of T, T1 As IComparable(Of T))(list As List(Of T1), key As T) As Integer
174	Dim low As Integer = 0
175	Dim high As Integer = list.Count - 1
176
177	Do While low <= high
178	Dim mid As Integer = CInt(CUInt((low + high)) >> 1)
179	'JAVA TO VB CONVERTER TODO TASK: There is no .NET equivalent to the Java 'super' constraint:
180	'JAVA TO VB CONVERTER TODO TASK: Java wildcard generics are not converted to .NET:
181	Dim midVal As IComparable(Of T) = list(mid)
182	Dim cmp As Integer = midVal.CompareTo(key)
183
184	If cmp < 0 Then
185	low = mid + 1
186	ElseIf cmp > 0 Then
187	high = mid - 1
188	Else
189	Return mid ' key found
190	End If
191	Loop
192	Return -(low + 1) ' key not found
193	End Function
194
195	Private Function iteratorBinarySearch(Of T, T1 As IComparable(Of T))(list As List(Of T1), key As T) As Integer
196	Dim low As Integer = 0
197	Dim high As Integer = list.Count - 1
198	'JAVA TO VB CONVERTER TODO TASK: There is no .NET equivalent to the Java 'super' constraint:
199	'JAVA TO VB CONVERTER TODO TASK: Java wildcard generics are not converted to .NET:
200	Dim i As IEnumerator(Of IComparable(Of T)) = list.GetEnumerator()
201
202	Do While low <= high
203	Dim mid As Integer = CInt(CUInt((low + high)) >> 1)
204	'JAVA TO VB CONVERTER TODO TASK: There is no .NET equivalent to the Java 'super' constraint:
205	'JAVA TO VB CONVERTER TODO TASK: Java wildcard generics are not converted to .NET:
206	Dim midVal As IComparable(Of T) = [get](i, mid)
207	Dim cmp As Integer = midVal.CompareTo(key)
208
209	If cmp < 0 Then
210	low = mid + 1
211	ElseIf cmp > 0 Then
212	high = mid - 1
213	Else
214	Return mid ' key found
215	End If
216	Loop
217	Return -(low + 1) ' key not found
218	End Function
219
220	''' <summary>
221	''' Gets the ith element from the given list by repositioning the specified
222	''' list listIterator.
223	''' </summary>
224	Private Function [get](Of T)(i As IEnumerator(Of T), index As Integer) As T
225	Dim obj As T = Nothing
226	Dim pos As Integer '= i.nextIndex()
227	If pos <= index Then
228	Dim tempVar As Boolean
229	Do
230	obj = i.Next
231	tempVar = pos < index
232	pos += 1
233	Loop While tempVar
234	Else
235	Do
236	obj = i.Previous()
237	pos -= 1
238	Loop While pos > index
239	End If
240	Return obj
241	End Function
242
243
244	''' <summary>
245	''' Searches the specified list for the specified object using the binary
246	''' search algorithm.  The list must be sorted into ascending order
247	''' according to the specified comparator (as by the
248	''' #sort(List, Comparator) sort(List, Comparator)
249	''' method), prior to making this call.  If it is
250	''' not sorted, the results are undefined.  If the list contains multiple
251	''' elements equal to the specified object, there is no guarantee which one
252	''' will be found.
253	'''
254	''' &lt;p>This method runs in log(n) time for a "random access" list (which
255	''' provides near-constant-time positional access).  If the specified list
256	''' does not implement the RandomAccess interface and is large,
257	''' this method will do an iterator-based binary search that performs
258	''' O(n) link traversals and O(log n) element comparisons.
259	''' </summary>
260	''' <typeparam name="T">the class of the objects in the list</typeparam>
261	''' <param name="list"> the list to be searched. </param>
262	''' <param name="key"> the key to be searched for. </param>
263	''' <param name="c"> the comparator by which the list is ordered.
264	'''         A <tt>null</tt> value indicates that the elements'
265	'''         Comparable natural ordering should be used. </param>
266	''' <returns> the index of the search key, if it is contained in the list;
267	'''         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
268	'''         <i>insertion point</i> is defined as the point at which the
269	'''         key would be inserted into the list: the index of the first
270	'''         element greater than the key, or <tt>list.size()</tt> if all
271	'''         elements in the list are less than the specified key.  Note
272	'''         that this guarantees that the return value will be &gt;= 0 if
273	'''         and only if the key is found. </returns>
274	Public Function binarySearch(Of T As IComparable(Of T))(list As List(Of T), key As T, c As IComparer(Of T)) As Integer
275	If c Is Nothing Then Return binarySearch(list, key)
276
277	If list.Count < BINARYSEARCH_THRESHOLD Then
278	Return Collections.indexedBinarySearch(list, key, c)
279	Else
280	Return Collections.iteratorBinarySearch(list, key, c)
281	End If
282	End Function
283
284	'JAVA TO VB CONVERTER TODO TASK: There is no .NET equivalent to the Java 'super' constraint:
285	Private Function indexedBinarySearch(Of T)(l As List(Of T), key As T, c As IComparer(Of T)) As Integer
286	Dim low As Integer = 0
287	Dim high As Integer = l.Count - 1
288
289	Do While low <= high
290	Dim mid As Integer = CInt(CUInt((low + high)) >> 1)
291	Dim midVal As T = l.Get(mid)
292	Dim cmp As Integer = c.Compare(midVal, key)
293
294	If cmp < 0 Then
295	low = mid + 1
296	ElseIf cmp > 0 Then
297	high = mid - 1
298	Else
299	Return mid ' key found
300	End If
301	Loop
302	Return -(low + 1) ' key not found
303	End Function
304
305	'JAVA TO VB CONVERTER TODO TASK: There is no .NET equivalent to the Java 'super' constraint:
306	Private Function iteratorBinarySearch(Of T)(l As List(Of T), key As T, c As IComparer(Of T)) As Integer
307	Dim low As Integer = 0
308	Dim high As Integer = l.Count - 1
309
310	Do While low <= high
311	Dim mid As Integer = CInt(CUInt((low + high)) >> 1)
312	Dim midVal As T = l(mid)
313	Dim cmp As Integer = c.Compare(midVal, key)
314
315	If cmp < 0 Then
316	low = mid + 1
317	ElseIf cmp > 0 Then
318	high = mid - 1
319	Else
320	Return mid ' key found
321	End If
322	Loop
323	Return -(low + 1) ' key not found
324	End Function
325
326	' ''' <summary>
327	' ''' Reverses the order of the elements in the specified list.<p>
328	' '''
329	' ''' This method runs in linear time.
330	' ''' </summary>
331	' ''' <param name="list"> the list whose elements are to be reversed. </param>
332	' ''' <exception cref="UnsupportedOperationException"> if the specified list or
333	' '''         its list-iterator does not support the <tt>set</tt> operation. </exception>
334	''JAVA TO VB CONVERTER TODO TASK: Most Java annotations will not have direct .NET equivalent attributes:
335	' Public  Sub reverse(Of T1)(  list As List(Of T1))
336	'            Dim size As Integer = list.Count
337	'            If size < REVERSE_THRESHOLD OrElse TypeOf list Is RandomAccess Then
338	' Dim i As Integer=0
339	' Dim mid As Integer=size>>1
340	' Dim j As Integer=size-1
341	' Do While i<mid
342	'                    list.Swap(i, j)
343	'                    i += 1
344	' j -= 1
345	' Loop
346	' Else
347	' ' instead of using a raw type here, it's possible to capture
348	' ' the wildcard but it will require a call to a supplementary
349	' ' private method
350	' Dim fwd As ListIterator = list.GetEnumerator()
351	' Dim rev As ListIterator = list.listIterator(size)
352	' Dim i As Integer=0
353	'                Dim mid As Integer = list.Count >> 1
354	'                Do While i<mid
355	' Dim tmp As Object = fwd.next()
356	' fwd.set(rev.previous())
357	' rev.set(tmp)
358	' i += 1
359	' Loop
360	' End If
361	' End Sub
362
363	'        ''' <summary>
364	'        ''' Randomly permutes the specified list using a default source of
365	'        ''' randomness.  All permutations occur with approximately equal
366	'        ''' likelihood.
367	'        '''
368	'        ''' <p>The hedge "approximately" is used in the foregoing description because
369	'        ''' default source of randomness is only approximately an unbiased source
370	'        ''' of independently chosen bits. If it were a perfect source of randomly
371	'        ''' chosen bits, then the algorithm would choose permutations with perfect
372	'        ''' uniformity.
373	'        '''
374	'        ''' <p>This implementation traverses the list backwards, from the last
375	'        ''' element up to the second, repeatedly swapping a randomly selected element
376	'        ''' into the "current position".  Elements are randomly selected from the
377	'        ''' portion of the list that runs from the first element to the current
378	'        ''' position, inclusive.
379	'        '''
380	'        ''' <p>This method runs in linear time.  If the specified list does not
381	'        ''' implement the <seealso cref="RandomAccess"/> interface and is large, this
382	'        ''' implementation dumps the specified list into an array before shuffling
383	'        ''' it, and dumps the shuffled array back into the list.  This avoids the
384	'        ''' quadratic behavior that would result from shuffling a "sequential
385	'        <span class="xml_comment">''' </span>access" list in place.
386	'        ''' </summary>
387	'        ''' <param name="list"> the list to be shuffled. </param>
388	'        ''' <exception cref="UnsupportedOperationException"> if the specified list or
389	'        '''         its list-iterator does not support the <tt>set</tt> operation. </exception>
390	'        Public  Sub shuffle(Of T1)(  list As List(Of T1))
391	' Dim rnd As Random = r
392	' If rnd Is Nothing Then
393	' rnd = New Random
394	' r = rnd
395	' End If
396	' shuffle(list, rnd)
397	' End Sub
398
399	' Private  r As Random
400
401	' ''' <summary>
402	' ''' Randomly permute the specified list using the specified source of
403	' ''' randomness.  All permutations occur with equal likelihood
404	' ''' assuming that the source of randomness is fair.<p>
405	' '''
406	' ''' This implementation traverses the list backwards, from the last element
407	' ''' up to the second, repeatedly swapping a randomly selected element into
408	' ''' the "current position".  Elements are randomly selected from the
409	' ''' portion of the list that runs from the first element to the current
410	' ''' position, inclusive.<p>
411	' '''
412	' ''' This method runs in linear time.  If the specified list does not
413	' ''' implement the <seealso cref="RandomAccess"/> interface and is large, this
414	' ''' implementation dumps the specified list into an array before shuffling
415	' ''' it, and dumps the shuffled array back into the list.  This avoids the
416	' ''' quadratic behavior that would result from shuffling a "sequential
417	' <span class="xml_comment">''' </span>access" list in place.
418	' ''' </summary>
419	' ''' <param name="list"> the list to be shuffled. </param>
420	' ''' <param name="rnd"> the source of randomness to use to shuffle the list. </param>
421	' ''' <exception cref="UnsupportedOperationException"> if the specified list or its
422	' '''         list-iterator does not support the <tt>set</tt> operation. </exception>
423	''JAVA TO VB CONVERTER TODO TASK: Most Java annotations will not have direct .NET equivalent attributes:
424	' Public  Sub shuffle(Of T1)(  list As List(Of T1),   rnd As Random)
425	' Dim size As Integer = list.size()
426	' If size < SHUFFLE_THRESHOLD OrElse TypeOf list Is RandomAccess Then
427	' For i As Integer = size To 2 Step -1
428	' swap(list, i-1, rnd.Next(i))
429	' Next i
430	' Else
431	' Dim arr As Object() = list.ToArray()
432
433	' ' Shuffle array
434	' For i As Integer = size To 2 Step -1
435	' swap(arr, i-1, rnd.Next(i))
436	' Next i
437
438	' ' Dump array back into list
439	' ' instead of using a raw type here, it's possible to capture
440	' ' the wildcard but it will require a call to a supplementary
441	' ' private method
442	' Dim it As ListIterator = list.GetEnumerator()
443	' For i As Integer = 0 To arr.Length - 1
444	' it.next()
445	' it.set(arr(i))
446	' Next i
447	' End If
448	' End Sub
449
450	'        ''' <summary>
451	'        ''' Replaces all of the elements of the specified list with the specified
452	'        ''' element. <p>
453	'        '''
454	'        ''' This method runs in linear time.
455	'        ''' </summary>
456	'        ''' @param  <T> the class of the objects in the list </param>
457	'        ''' <param name="list"> the list to be filled with the specified element. </param>
458	'        ''' <param name="obj"> The element with which to fill the specified list. </param>
459	'        ''' <exception cref="UnsupportedOperationException"> if the specified list or its
460	'        '''         list-iterator does not support the <tt>set</tt> operation. </exception>
461	'        'JAVA TO VB CONVERTER TODO TASK: There is no .NET equivalent to the Java 'super' constraint:
462	'        Public  Sub fill(Of T, T1)(  list As List(Of T1),   obj As T)
463	'            Dim size As Integer = list.Count
464
465	'            If size < FILL_THRESHOLD OrElse TypeOf list Is RandomAccess Then
466	'                For i As Integer = 0 To size - 1
467	'                    list(i) = obj
468	'                Next
469	'            Else
470	''JAVA TO VB CONVERTER TODO TASK: There is no .NET equivalent to the Java 'super' constraint:
471	''JAVA TO VB CONVERTER TODO TASK: Java wildcard generics are not converted to .NET:
472	' Dim itr As ListIterator(Of ?) = list.GetEnumerator()
473	'                For i As Integer = 0 To size - 1
474	'                    itr.next()
475	'                    itr.set(obj)
476	'                Next
477	'            End If
478	' End Sub
479
480	'        ''' <summary>
481	'        ''' Rotates the elements in the specified list by the specified distance.
482	'        ''' After calling this method, the element at index <tt>i</tt> will be
483	'        ''' the element previously at index <tt>(i - distance)</tt> mod
484	'        ''' <tt>list.size()</tt>, for all values of <tt>i</tt> between <tt>0</tt>
485	'        ''' and <tt>list.size()-1</tt>, inclusive.  (This method has no effect on
486	'        ''' the size of the list.)
487	'        '''
488	'        ''' <p>For example, suppose <tt>list</tt> comprises<tt> [t, a, n, k, s]</tt>.
489	'        ''' After invoking <tt>Collections.rotate(list, 1)</tt> (or
490	'        ''' <tt>Collections.rotate(list, -4)</tt>), <tt>list</tt> will comprise
491	'        ''' <tt>[s, t, a, n, k]</tt>.
492	'        '''
493	'        ''' <p>Note that this method can usefully be applied to sublists to
494	'        ''' move one or more elements within a list while preserving the
495	'        ''' order of the remaining elements.  For example, the following idiom
496	'        ''' moves the element at index <tt>j</tt> forward to position
497	'        ''' <tt>k</tt> (which must be greater than or equal to <tt>j</tt>):
498	'        ''' <pre>
499	'        '''     Collections.rotate(list.subList(j, k+1), -1);
500	'        ''' </pre>
501	'        ''' To make this concrete, suppose <tt>list</tt> comprises
502	'        ''' <tt>[a, b, c, d, e]</tt>.  To move the element at index <tt>1</tt>
503	'        ''' (<tt>b</tt>) forward two positions, perform the following invocation:
504	'        ''' <pre>
505	'        '''     Collections.rotate(l.subList(1, 4), -1);
506	'        ''' </pre>
507	'        ''' The resulting list is <tt>[a, c, d, b, e]</tt>.
508	'        '''
509	'        ''' <p>To move more than one element forward, increase the absolute value
510	'        ''' of the rotation distance.  To move elements backward, use a positive
511	'        ''' shift distance.
512	'        '''
513	'        ''' <p>If the specified list is small or implements the {@link
514	'        ''' RandomAccess} interface, this implementation exchanges the first
515	'        ''' element into the location it should go, and then repeatedly exchanges
516	'        ''' the displaced element into the location it should go until a displaced
517	'        ''' element is swapped into the first element.  If necessary, the process
518	'        ''' is repeated on the second and successive elements, until the rotation
519	'        ''' is complete.  If the specified list is large and doesn't implement the
520	'        ''' <tt>RandomAccess</tt> interface, this implementation breaks the
521	'        ''' list into two sublist views around index <tt>-distance mod size</tt>.
522	'        ''' Then the <seealso cref="#reverse(List)"/> method is invoked on each sublist view,
523	'        ''' and finally it is invoked on the entire list.  For a more complete
524	'        ''' description of both algorithms, see Section 2.3 of Jon Bentley's
525	'        ''' <i>Programming Pearls</i> (Addison-Wesley, 1986).
526	'        ''' </summary>
527	'        ''' <param name="list"> the list to be rotated. </param>
528	'        ''' <param name="distance"> the distance to rotate the list.  There are no
529	'        '''        constraints on this value; it may be zero, negative, or
530	'        '''        greater than <tt>list.size()</tt>. </param>
531	'        ''' <exception cref="UnsupportedOperationException"> if the specified list or
532	'        '''         its list-iterator does not support the <tt>set</tt> operation.
533	'        ''' @since 1.4 </exception>
534	'        Public  Sub rotate(Of T1)(  list As List(Of T1),   distance As Integer)
535	' If TypeOf list Is RandomAccess OrElse list.size() < ROTATE_THRESHOLD Then
536	' rotate1(list, distance)
537	' Else
538	' rotate2(list, distance)
539	' End If
540	' End Sub
541
542	' Private  Sub rotate1(Of T)(  list As List(Of T),   distance As Integer)
543	' Dim size As Integer = list.size()
544	' If size = 0 Then Return
545	' distance = distance Mod size
546	' If distance < 0 Then distance += size
547	' If distance = 0 Then Return
548
549	' Dim cycleStart As Integer = 0
550	' Dim nMoved As Integer = 0
551	' Do While nMoved <> size
552	' Dim displaced As T = list.get(cycleStart)
553	' Dim i As Integer = cycleStart
554	' Do
555	' i += distance
556	' If i >= size Then i -= size
557	' displaced = list.set(i, displaced)
558	' nMoved += 1
559	' Loop While i <> cycleStart
560	' cycleStart += 1
561	' Loop
562	' End Sub
563
564	' Private  Sub rotate2(Of T1)(  list As List(Of T1),   distance As Integer)
565	' Dim size As Integer = list.size()
566	' If size = 0 Then Return
567	' Dim mid As Integer = -distance Mod size
568	' If mid < 0 Then mid += size
569	' If mid = 0 Then Return
570
571	' reverse(list.subList(0, mid))
572	' reverse(list.subList(mid, size))
573	' reverse(list)
574	' End Sub
575
576	' ''' <summary>
577	' ''' Replaces all occurrences of one specified value in a list with another.
578	' ''' More formally, replaces with <tt>newVal</tt> each element <tt>e</tt>
579	' ''' in <tt>list</tt> such that
580	' ''' <tt>(oldVal==null ? e==null : oldVal.equals(e))</tt>.
581	' ''' (This method has no effect on the size of the list.)
582	' ''' </summary>
583	' ''' @param  <T> the class of the objects in the list </param>
584	' ''' <param name="list"> the list in which replacement is to occur. </param>
585	' ''' <param name="oldVal"> the old value to be replaced. </param>
586	' ''' <param name="newVal"> the new value with which <tt>oldVal</tt> is to be
587	' '''        replaced. </param>
588	' ''' <returns> <tt>true</tt> if <tt>list</tt> contained one or more elements
589	' '''         <tt>e</tt> such that
590	' '''         <tt>(oldVal==null ?  e==null : oldVal.equals(e))</tt>. </returns>
591	' ''' <exception cref="UnsupportedOperationException"> if the specified list or
592	' '''         its list-iterator does not support the <tt>set</tt> operation.
593	' ''' @since  1.4 </exception>
594	' Public  Function replaceAll(Of T)(  list As List(Of T),   oldVal As T,   newVal As T) As Boolean
595	' Dim result As Boolean = False
596	' Dim size As Integer = list.size()
597	' If size < REPLACEALL_THRESHOLD OrElse TypeOf list Is RandomAccess Then
598	' If oldVal Is Nothing Then
599	' For i As Integer = 0 To size - 1
600	' If list.get(i) Is Nothing Then
601	' list.set(i, newVal)
602	' result = True
603	' End If
604	' Next i
605	' Else
606	' For i As Integer = 0 To size - 1
607	' If oldVal.Equals(list.get(i)) Then
608	' list.set(i, newVal)
609	' result = True
610	' End If
611	' Next i
612	' End If
613	' Else
614	' Dim itr As ListIterator(Of T)=list.GetEnumerator()
615	' If oldVal Is Nothing Then
616	' For i As Integer = 0 To size - 1
617	' If itr.next() Is Nothing Then
618	' itr.set(newVal)
619	' result = True
620	' End If
621	' Next i
622	' Else
623	' For i As Integer = 0 To size - 1
624	' If oldVal.Equals(itr.next()) Then
625	' itr.set(newVal)
626	' result = True
627	' End If
628	' Next i
629	' End If
630	' End If
631	' Return result
632	' End Function
633
634	' ''' <summary>
635	' ''' Returns the starting position of the first occurrence of the specified
636	' ''' target list within the specified source list, or -1 if there is no
637	' ''' such occurrence.  More formally, returns the lowest index <tt>i</tt>
638	' ''' such that {@code source.subList(i, i+target.size()).equals(target)},
639	' ''' or -1 if there is no such index.  (Returns -1 if
640	' ''' {@code target.size() > source.size()})
641	' '''
642	' ''' <p>This implementation uses the "brute force" technique of scanning
643	' ''' over the source list, looking for a match with the target at each
644	' ''' location in turn.
645	' ''' </summary>
646	' ''' <param name="source"> the list in which to search for the first occurrence
647	' '''        of <tt>target</tt>. </param>
648	' ''' <param name="target"> the list to search for as a subList of <tt>source</tt>. </param>
649	' ''' <returns> the starting position of the first occurrence of the specified
650	' '''         target list within the specified source list, or -1 if there
651	' '''         is no such occurrence.
652	' ''' @since  1.4 </returns>
653	' Public  Function indexOfSubList(Of T1, T2)(  source As List(Of T1),   target As List(Of T2)) As Integer
654	' Dim sourceSize As Integer = source.size()
655	' Dim targetSize As Integer = target.size()
656	' Dim maxCandidate As Integer = sourceSize - targetSize
657
658	' If sourceSize < INDEXOFSUBLIST_THRESHOLD OrElse (TypeOf source Is RandomAccess AndAlso TypeOf target Is RandomAccess) Then
659	' nextCand:
660	' For candidate As Integer = 0 To maxCandidate
661	' Dim i As Integer=0
662	' Dim j As Integer=candidate
663	' Do While i<targetSize
664	' If Not eq(target.get(i), source.get(j)) Then GoTo nextCand ' Element mismatch, try next cand
665	' i += 1
666	' j += 1
667	' Loop
668	' Return candidate ' All elements of candidate matched target
669	' Next candidate ' Iterator version of above algorithm
670	' Else
671	''JAVA TO VB CONVERTER TODO TASK: Java wildcard generics are not converted to .NET:
672	' Dim si As ListIterator(Of ?) = source.GetEnumerator()
673	' nextCand:
674	' For candidate As Integer = 0 To maxCandidate
675	''JAVA TO VB CONVERTER TODO TASK: Java wildcard generics are not converted to .NET:
676	' Dim ti As ListIterator(Of ?) = target.GetEnumerator()
677	' For i As Integer = 0 To targetSize - 1
678	' If Not eq(ti.next(), si.next()) Then
679	' ' Back up source iterator to next candidate
680	' For j As Integer = 0 To i - 1
681	' si.previous()
682	' Next j
683	' GoTo nextCand
684	' End If
685	' Next i
686	' Return candidate
687	' Next candidate
688	' End If
689	' Return -1 ' No candidate matched the target
690	' End Function
691
692	' ''' <summary>
693	' ''' Returns the starting position of the last occurrence of the specified
694	' ''' target list within the specified source list, or -1 if there is no such
695	' ''' occurrence.  More formally, returns the highest index <tt>i</tt>
696	' ''' such that {@code source.subList(i, i+target.size()).equals(target)},
697	' ''' or -1 if there is no such index.  (Returns -1 if
698	' ''' {@code target.size() > source.size()})
699	' '''
700	' ''' <p>This implementation uses the "brute force" technique of iterating
701	' ''' over the source list, looking for a match with the target at each
702	' ''' location in turn.
703	' ''' </summary>
704	' ''' <param name="source"> the list in which to search for the last occurrence
705	' '''        of <tt>target</tt>. </param>
706	' ''' <param name="target"> the list to search for as a subList of <tt>source</tt>. </param>
707	' ''' <returns> the starting position of the last occurrence of the specified
708	' '''         target list within the specified source list, or -1 if there
709	' '''         is no such occurrence.
710	' ''' @since  1.4 </returns>
711	' Public  Function lastIndexOfSubList(Of T1, T2)(  source As List(Of T1),   target As List(Of T2)) As Integer
712	' Dim sourceSize As Integer = source.size()
713	' Dim targetSize As Integer = target.size()
714	' Dim maxCandidate As Integer = sourceSize - targetSize
715
716	' If sourceSize < INDEXOFSUBLIST_THRESHOLD OrElse TypeOf source Is RandomAccess Then ' Index access version
717	' nextCand:
718	' For candidate As Integer = maxCandidate To 0 Step -1
719	' Dim i As Integer=0
720	' Dim j As Integer=candidate
721	' Do While i<targetSize
722	' If Not eq(target.get(i), source.get(j)) Then GoTo nextCand ' Element mismatch, try next cand
723	' i += 1
724	' j += 1
725	' Loop
726	' Return candidate ' All elements of candidate matched target
727	' Next candidate ' Iterator version of above algorithm
728	' Else
729	' If maxCandidate < 0 Then Return -1
730	''JAVA TO VB CONVERTER TODO TASK: Java wildcard generics are not converted to .NET:
731	' Dim si As ListIterator(Of ?) = source.listIterator(maxCandidate)
732	' nextCand:
733	' For candidate As Integer = maxCandidate To 0 Step -1
734	''JAVA TO VB CONVERTER TODO TASK: Java wildcard generics are not converted to .NET:
735	' Dim ti As ListIterator(Of ?) = target.GetEnumerator()
736	' For i As Integer = 0 To targetSize - 1
737	' If Not eq(ti.next(), si.next()) Then
738	' If candidate <> 0 Then
739	' ' Back up source iterator to next candidate
740	' For j As Integer = 0 To i+1
741	' si.previous()
742	' Next j
743	' End If
744	' GoTo nextCand
745	' End If
746	' Next i
747	' Return candidate
748	' Next candidate
749	' End If
750	' Return -1 ' No candidate matched the target
751	' End Function
752
753	End Module
754
755	End Namespace