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