Format all dart: library files

sdk/lib/internal/sort.dart

 // Copyright (c) 2011, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 part of dart._internal;
 
 /**
  * Dual-Pivot Quicksort algorithm.
  *
  * This class implements the dual-pivot quicksort algorithm as presented in
@@ skipping 34 matching lines @@
   static void sortRange<E>(List<E> a, int from, int to, int compare(E a, E b)) {
     if ((from < 0) || (to > a.length) || (to < from)) {
       throw "OutOfRange";
     }
     _doSort(a, from, to - 1, compare);
   }
 
   /**
    * Sorts the list in the interval [:left:] to [:right:] (both inclusive).
    */
-  static void _doSort<E>(List<E> a, int left, int right,
-                         int compare(E a, E b)) {
+  static void _doSort<E>(
+      List<E> a, int left, int right, int compare(E a, E b)) {
     if ((right - left) <= _INSERTION_SORT_THRESHOLD) {
       _insertionSort(a, left, right, compare);
     } else {
       _dualPivotQuicksort(a, left, right, compare);
     }
   }
 
-  static void _insertionSort<E>(List<E> a, int left, int right,
-                                int compare(E a, E b)) {
+  static void _insertionSort<E>(
+      List<E> a, int left, int right, int compare(E a, E b)) {
     for (int i = left + 1; i <= right; i++) {
       var el = a[i];
       int j = i;
       while ((j > left) && (compare(a[j - 1], el) > 0)) {
         a[j] = a[j - 1];
         j--;
       }
       a[j] = el;
     }
   }
 
-  static void _dualPivotQuicksort<E>(List<E> a, int left, int right,
-                                     int compare(E a, E b)) {
+  static void _dualPivotQuicksort<E>(
+      List<E> a, int left, int right, int compare(E a, E b)) {
     assert(right - left > _INSERTION_SORT_THRESHOLD);
 
     // Compute the two pivots by looking at 5 elements.
     int sixth = (right - left + 1) ~/ 6;
     int index1 = left + sixth;
     int index5 = right - sixth;
-    int index3 = (left + right) ~/ 2;  // The midpoint.
+    int index3 = (left + right) ~/ 2; // The midpoint.
     int index2 = index3 - sixth;
     int index4 = index3 + sixth;
 
     var el1 = a[index1];
     var el2 = a[index2];
     var el3 = a[index3];
     var el4 = a[index4];
     var el5 = a[index5];
 
     // Sort the selected 5 elements using a sorting network.
-    if (compare(el1, el2) > 0) { var t = el1; el1 = el2; el2 = t; }
-    if (compare(el4, el5) > 0) { var t = el4; el4 = el5; el5 = t; }
-    if (compare(el1, el3) > 0) { var t = el1; el1 = el3; el3 = t; }
-    if (compare(el2, el3) > 0) { var t = el2; el2 = el3; el3 = t; }
-    if (compare(el1, el4) > 0) { var t = el1; el1 = el4; el4 = t; }
-    if (compare(el3, el4) > 0) { var t = el3; el3 = el4; el4 = t; }
-    if (compare(el2, el5) > 0) { var t = el2; el2 = el5; el5 = t; }
-    if (compare(el2, el3) > 0) { var t = el2; el2 = el3; el3 = t; }
-    if (compare(el4, el5) > 0) { var t = el4; el4 = el5; el5 = t; }
+    if (compare(el1, el2) > 0) {
+      var t = el1;
+      el1 = el2;
+      el2 = t;
+    }
+    if (compare(el4, el5) > 0) {
+      var t = el4;
+      el4 = el5;
+      el5 = t;
+    }
+    if (compare(el1, el3) > 0) {
+      var t = el1;
+      el1 = el3;
+      el3 = t;
+    }
+    if (compare(el2, el3) > 0) {
+      var t = el2;
+      el2 = el3;
+      el3 = t;
+    }
+    if (compare(el1, el4) > 0) {
+      var t = el1;
+      el1 = el4;
+      el4 = t;
+    }
+    if (compare(el3, el4) > 0) {
+      var t = el3;
+      el3 = el4;
+      el4 = t;
+    }
+    if (compare(el2, el5) > 0) {
+      var t = el2;
+      el2 = el5;
+      el5 = t;
+    }
+    if (compare(el2, el3) > 0) {
+      var t = el2;
+      el2 = el3;
+      el3 = t;
+    }
+    if (compare(el4, el5) > 0) {
+      var t = el4;
+      el4 = el5;
+      el5 = t;
+    }
 
     var pivot1 = el2;
     var pivot2 = el4;
 
     // el2 and el4 have been saved in the pivot variables. They will be written
     // back, once the partitioning is finished.
     a[index1] = el1;
     a[index3] = el3;
     a[index5] = el5;
 
     a[index2] = a[left];
     a[index4] = a[right];
 
-    int less = left + 1;    // First element in the middle partition.
-    int great = right - 1;  // Last element in the middle partition.
+    int less = left + 1; // First element in the middle partition.
+    int great = right - 1; // Last element in the middle partition.
 
     bool pivots_are_equal = (compare(pivot1, pivot2) == 0);
     if (pivots_are_equal) {
       var pivot = pivot1;
       // Degenerated case where the partitioning becomes a dutch national flag
       // problem.
       //
       // [ |  < pivot  | == pivot | unpartitioned | > pivot  | ]
       //  ^             ^          ^             ^            ^
       // left         less         k           great         right
@@ skipping 131 matching lines @@
       // All elements in the second partition are equal to the pivot. No
       // need to sort them.
       return;
     }
 
     // In theory it should be enough to call _doSort recursively on the second
     // partition.
     // The Android source however removes the pivot elements from the recursive
     // call if the second partition is too large (more than 2/3 of the list).
     if (less < index1 && great > index5) {
-      while (compare(a[less], pivot1) == 0) { less++; }
-      while (compare(a[great], pivot2) == 0) { great--; }
+      while (compare(a[less], pivot1) == 0) {
+        less++;
+      }
+      while (compare(a[great], pivot2) == 0) {
+        great--;
+      }
 
       // Copy paste of the previous 3-way partitioning with adaptions.
       //
       // We partition the list into three parts:
       //  1. == pivot1
       //  2. > pivot1 && < pivot2
       //  3. == pivot2
       //
       // During the loop we have:
       // [ == pivot1 | > pivot1 && < pivot2 | unpartitioned  | == pivot2 ]
@@ skipping 53 matching lines @@
     } else {
       // The second partition looks as follows:
       // [  *  |  >= pivot1 && <= pivot2  | * ]
       //        ^                        ^
       //       less                    great
       // Simply sort it by recursive descent.
       _doSort(a, less, great, compare);
     }
   }
 }