// Copyright (c) 2013, 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.

/// Tests algorithm utilities.
library;

import 'dart:math';

import 'package:collection/collection.dart';
import 'package:collection/src/algorithms.dart';
import 'package:test/test.dart';

void main() {
  void testShuffle(List list) {
    var copy = list.toList();
    shuffle(list);
    expect(const UnorderedIterableEquality().equals(list, copy), isTrue);
  }

  test('Shuffle 0', () {
    testShuffle([]);
  });
  test('Shuffle 1', () {
    testShuffle([1]);
  });
  test('Shuffle 3', () {
    testShuffle([1, 2, 3]);
  });
  test('Shuffle 10', () {
    testShuffle([1, 2, 3, 4, 5, 1, 3, 5, 7, 9]);
  });
  test('Shuffle shuffles', () {
    var l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
    var c = l.toList();
    var count = 0;
    for (;;) {
      shuffle(l);
      if (!const ListEquality().equals(c, l)) return;
      // Odds of not changing the order should be one in ~ 16! ~= 2e+13.
      // Repeat this 10 times, and the odds of accidentally shuffling to the
      // same result every time is disappearingly tiny.
      count++;
      // If this happens even once, it's ok to report it.
      print('Failed shuffle $count times');
      if (count == 10) fail("Shuffle didn't change order.");
    }
  });
  test('Shuffle sublist', () {
    var l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
    var c = l.toList();
    shuffle(l, 4, 12);
    expect(const IterableEquality().equals(l.getRange(0, 4), c.getRange(0, 4)),
        isTrue);
    expect(
        const IterableEquality().equals(l.getRange(12, 16), c.getRange(12, 16)),
        isTrue);
    expect(
        const UnorderedIterableEquality()
            .equals(l.getRange(4, 12), c.getRange(4, 12)),
        isTrue);
  });

  test('binsearch0', () {
    expect(binarySearch([], 2), equals(-1));
  });

  test('binsearch1', () {
    expect(binarySearch([5], 2), equals(-1));
    expect(binarySearch([5], 5), equals(0));
    expect(binarySearch([5], 7), equals(-1));
  });

  test('binsearch3', () {
    expect(binarySearch([0, 5, 10], -1), equals(-1));
    expect(binarySearch([0, 5, 10], 0), equals(0));
    expect(binarySearch([0, 5, 10], 2), equals(-1));
    expect(binarySearch([0, 5, 10], 5), equals(1));
    expect(binarySearch([0, 5, 10], 7), equals(-1));
    expect(binarySearch([0, 5, 10], 10), equals(2));
    expect(binarySearch([0, 5, 10], 12), equals(-1));
  });

  test('binsearchCompare0', () {
    expect(binarySearch(<C>[], C(2), compare: compareC), equals(-1));
  });

  test('binsearchCompare1', () {
    var l1 = [C(5)];
    expect(binarySearch(l1, C(2), compare: compareC), equals(-1));
    expect(binarySearch(l1, C(5), compare: compareC), equals(0));
    expect(binarySearch(l1, C(7), compare: compareC), equals(-1));
  });

  test('binsearchCompare3', () {
    var l3 = [C(0), C(5), C(10)];
    expect(binarySearch(l3, C(-1), compare: compareC), equals(-1));
    expect(binarySearch(l3, C(0), compare: compareC), equals(0));
    expect(binarySearch(l3, C(2), compare: compareC), equals(-1));
    expect(binarySearch(l3, C(5), compare: compareC), equals(1));
    expect(binarySearch(l3, C(7), compare: compareC), equals(-1));
    expect(binarySearch(l3, C(10), compare: compareC), equals(2));
    expect(binarySearch(l3, C(12), compare: compareC), equals(-1));
  });

  test('lowerbound0', () {
    expect(lowerBound([], 2), equals(0));
  });

  test('lowerbound1', () {
    expect(lowerBound([5], 2), equals(0));
    expect(lowerBound([5], 5), equals(0));
    expect(lowerBound([5], 7), equals(1));
  });

  test('lowerbound3', () {
    expect(lowerBound([0, 5, 10], -1), equals(0));
    expect(lowerBound([0, 5, 10], 0), equals(0));
    expect(lowerBound([0, 5, 10], 2), equals(1));
    expect(lowerBound([0, 5, 10], 5), equals(1));
    expect(lowerBound([0, 5, 10], 7), equals(2));
    expect(lowerBound([0, 5, 10], 10), equals(2));
    expect(lowerBound([0, 5, 10], 12), equals(3));
  });

  test('lowerboundRepeat', () {
    expect(lowerBound([5, 5, 5], 5), equals(0));
    expect(lowerBound([0, 5, 5, 5, 10], 5), equals(1));
  });

  test('lowerboundCompare0', () {
    expect(lowerBound(<C>[], C(2), compare: compareC), equals(0));
  });

  test('lowerboundCompare1', () {
    var l1 = [C(5)];
    expect(lowerBound(l1, C(2), compare: compareC), equals(0));
    expect(lowerBound(l1, C(5), compare: compareC), equals(0));
    expect(lowerBound(l1, C(7), compare: compareC), equals(1));
  });

  test('lowerboundCompare3', () {
    var l3 = [C(0), C(5), C(10)];
    expect(lowerBound(l3, C(-1), compare: compareC), equals(0));
    expect(lowerBound(l3, C(0), compare: compareC), equals(0));
    expect(lowerBound(l3, C(2), compare: compareC), equals(1));
    expect(lowerBound(l3, C(5), compare: compareC), equals(1));
    expect(lowerBound(l3, C(7), compare: compareC), equals(2));
    expect(lowerBound(l3, C(10), compare: compareC), equals(2));
    expect(lowerBound(l3, C(12), compare: compareC), equals(3));
  });

  test('lowerboundCompareRepeat', () {
    var l1 = [C(5), C(5), C(5)];
    var l2 = [C(0), C(5), C(5), C(5), C(10)];
    expect(lowerBound(l1, C(5), compare: compareC), equals(0));
    expect(lowerBound(l2, C(5), compare: compareC), equals(1));
  });

  void testSort(String name,
      void Function(List<int> elements, [int? start, int? end]) sort) {
    test('${name}Random', () {
      var random = Random();
      for (var i = 0; i < 250; i += 10) {
        var list = [
          for (var j = 0; j < i; j++)
            random.nextInt(25) // Expect some equal elements.
        ];
        sort(list);
        for (var j = 1; j < i; j++) {
          expect(list[j - 1], lessThanOrEqualTo(list[j]));
        }
      }
    });

    test('${name}SubRanges', () {
      var l = [6, 5, 4, 3, 2, 1];
      sort(l, 2, 4);
      expect(l, equals([6, 5, 3, 4, 2, 1]));
      sort(l, 1, 1);
      expect(l, equals([6, 5, 3, 4, 2, 1]));
      sort(l, 4, 6);
      expect(l, equals([6, 5, 3, 4, 1, 2]));
      sort(l, 0, 2);
      expect(l, equals([5, 6, 3, 4, 1, 2]));
      sort(l, 0, 6);
      expect(l, equals([1, 2, 3, 4, 5, 6]));
    });

    test('$name insertionSortSpecialCases', () {
      var l = [6, 6, 6, 6, 6, 6];
      sort(l);
      expect(l, equals([6, 6, 6, 6, 6, 6]));

      l = [6, 6, 3, 3, 0, 0];
      sort(l);
      expect(l, equals([0, 0, 3, 3, 6, 6]));
    });
  }

  int intId(int x) => x;
  int intCompare(int a, int b) => a - b;
  testSort('insertionSort', (list, [start, end]) {
    insertionSortBy(list, intId, intCompare, start ?? 0, end ?? list.length);
  });
  testSort('mergeSort compare', (list, [start, end]) {
    mergeSort(list,
        start: start ?? 0, end: end ?? list.length, compare: intCompare);
  });
  testSort('mergeSort comparable', (list, [start, end]) {
    mergeSort(list, start: start ?? 0, end: end ?? list.length);
  });
  testSort('mergeSortBy', (list, [start, end]) {
    mergeSortBy(list, intId, intCompare, start ?? 0, end ?? list.length);
  });
  testSort('quickSort', (list, [start, end]) {
    quickSort(list, intCompare, start ?? 0, end ?? list.length);
  });
  testSort('quickSortBy', (list, [start, end]) {
    quickSortBy(list, intId, intCompare, start ?? 0, end ?? list.length);
  });
  test('MergeSortSpecialCases', () {
    for (var size in [511, 512, 513]) {
      // All equal.
      var list = List<OC>.generate(size, (i) => OC(0, i));
      mergeSort(list);
      for (var i = 0; i < size; i++) {
        expect(list[i].order, equals(i));
      }
      // All but one equal, first.
      list[0] = OC(1, 0);
      for (var i = 1; i < size; i++) {
        list[i] = OC(0, i);
      }
      mergeSort(list);
      for (var i = 0; i < size - 1; i++) {
        expect(list[i].order, equals(i + 1));
      }
      expect(list[size - 1].order, equals(0));

      // All but one equal, last.
      for (var i = 0; i < size - 1; i++) {
        list[i] = OC(0, i);
      }
      list[size - 1] = OC(-1, size - 1);
      mergeSort(list);
      expect(list[0].order, equals(size - 1));
      for (var i = 1; i < size; i++) {
        expect(list[i].order, equals(i - 1));
      }

      // Reversed.
      for (var i = 0; i < size; i++) {
        list[i] = OC(size - 1 - i, i);
      }
      mergeSort(list);
      for (var i = 0; i < size; i++) {
        expect(list[i].id, equals(i));
        expect(list[i].order, equals(size - 1 - i));
      }
    }
  });

  void testSortBy(
      String name,
      void Function<T, K>(List<T> elements, K Function(T element) keyOf,
              int Function(K a, K b) compare,
              [int start, int end])
          sort) {
    for (var n in [0, 1, 2, 10, 75, 250]) {
      var name2 = name;
      test('$name2: Same #$n', () {
        var list = List<OC>.generate(n, (i) => OC(i, 0));
        // Should succeed. Bad implementations of, e.g., quicksort can diverge.
        sort(list, _ocOrder, _compareInt);
      });
      test('$name: Pre-sorted #$n', () {
        var list = List<OC>.generate(n, (i) => OC(-i, i));
        var expected = list.toList();
        sort(list, _ocOrder, _compareInt);
        // Elements have not moved.
        expect(list, expected);
      });
      test('$name: Reverse-sorted #$n', () {
        var list = List<OC>.generate(n, (i) => OC(i, -i));
        sort(list, _ocOrder, _compareInt);
        expectSorted(list, _ocOrder, _compareInt);
      });
      test('$name: Random #$n', () {
        var random = Random();
        var list = List<OC>.generate(n, (i) => OC(i, random.nextInt(n)));
        sort(list, _ocOrder, _compareInt);
        expectSorted(list, _ocOrder, _compareInt);
      });
      test('$name: Sublist #$n', () {
        var random = Random();
        var list = List<OC>.generate(n, (i) => OC(i, random.nextInt(n)));
        var original = list.toList();
        var start = n ~/ 4;
        var end = start * 3;
        sort(list, _ocOrder, _compareInt, start, end);
        expectSorted(list, _ocOrder, _compareInt, start, end);
        expect(list.sublist(0, start), original.sublist(0, start));
        expect(list.sublist(end), original.sublist(end));
      });
    }
  }

  testSortBy('insertionSort', insertionSortBy);
  testSortBy('mergeSort', mergeSortBy);
  testSortBy('quickSortBy', quickSortBy);

  test('MergeSortPreservesOrder', () {
    var random = Random();
    // Small case where only insertion call is called,
    // larger case where the internal moving insertion sort is used
    // larger cases with multiple splittings, numbers just around a power of 2.
    for (var size in [8, 50, 511, 512, 513]) {
      // Class OC compares using id.
      // With size elements with id's in the range 0..size/4, a number of
      // collisions are guaranteed. These should be sorted so that the 'order'
      // part of the objects are still in order.
      var list = [
        for (var i = 0; i < size; i++) OC(random.nextInt(size >> 2), i)
      ];
      mergeSort(list);
      var prev = list[0];
      for (var i = 1; i < size; i++) {
        var next = list[i];
        expect(prev.id, lessThanOrEqualTo(next.id));
        if (next.id == prev.id) {
          expect(prev.order, lessThanOrEqualTo(next.order));
        }
        prev = next;
      }
      // Reverse compare on part of list.
      List copy = list.toList();
      var min = size >> 2;
      var max = size - min;
      mergeSort<OC>(list,
          start: min, end: max, compare: (a, b) => b.compareTo(a));
      prev = list[min];
      for (var i = min + 1; i < max; i++) {
        var next = list[i];
        expect(prev.id, greaterThanOrEqualTo(next.id));
        if (next.id == prev.id) {
          expect(prev.order, lessThanOrEqualTo(next.order));
        }
        prev = next;
      }
      // Equals on OC objects is identity, so this means the parts before min,
      // and the parts after max, didn't change at all.
      expect(list.sublist(0, min), equals(copy.sublist(0, min)));
      expect(list.sublist(max), equals(copy.sublist(max)));
    }
  });

  test('Reverse', () {
    var l = [6, 5, 4, 3, 2, 1];
    reverse(l, 2, 4);
    expect(l, equals([6, 5, 3, 4, 2, 1]));
    reverse(l, 1, 1);
    expect(l, equals([6, 5, 3, 4, 2, 1]));
    reverse(l, 4, 6);
    expect(l, equals([6, 5, 3, 4, 1, 2]));
    reverse(l, 0, 2);
    expect(l, equals([5, 6, 3, 4, 1, 2]));
    reverse(l, 0, 6);
    expect(l, equals([2, 1, 4, 3, 6, 5]));
  });

  test('mergeSort works when runtime generic is a subtype of the static type',
      () {
    // Regression test for https://github.com/dart-lang/collection/issues/317
    final length = 1000; // Larger than _mergeSortLimit
    // Out of order list, with first half guaranteed to empty first during
    // merge.
    final list = [
      for (var i = 0; i < length / 2; i++) -i,
      for (var i = 0; i < length / 2; i++) i + length,
    ];
    expect(() => mergeSort<num>(list), returnsNormally);
  });
}

class C {
  final int id;
  C(this.id);
}

int compareC(C one, C other) => one.id - other.id;

/// Class naturally ordered by its first constructor argument.
class OC implements Comparable<OC> {
  final int id;
  final int order;
  OC(this.id, this.order);

  @override
  int compareTo(OC other) => id - other.id;

  @override
  String toString() => 'OC[$id,$order]';
}

int _ocOrder(OC oc) => oc.order;

int _compareInt(int a, int b) => a - b;

/// Check that a list is sorted according to [compare] of [keyOf] of elements.
void expectSorted<T, K>(
    List<T> list, K Function(T element) keyOf, int Function(K a, K b) compare,
    [int start = 0, int? end]) {
  end ??= list.length;
  if (start == end) return;
  var prev = keyOf(list[start]);
  for (var i = start + 1; i < end; i++) {
    var next = keyOf(list[i]);
    expect(compare(prev, next), isNonPositive);
    prev = next;
  }
}