collections_test.dart 6.08 KB
Newer Older
Ian Hickson's avatar
Ian Hickson committed
1
// Copyright 2014 The Flutter Authors. All rights reserved.
2 3 4
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5
import 'dart:math';
6

7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
import 'package:flutter/src/foundation/collections.dart';
import 'package:flutter_test/flutter_test.dart';

void main() {
  test('listEquals', () {
    final List<int> listA = <int>[1, 2, 3];
    final List<int> listB = <int>[1, 2, 3];
    final List<int> listC = <int>[1, 2];
    final List<int> listD = <int>[3, 2, 1];

    expect(listEquals<void>(null, null), isTrue);
    expect(listEquals(listA, null), isFalse);
    expect(listEquals(null, listB), isFalse);
    expect(listEquals(listA, listA), isTrue);
    expect(listEquals(listA, listB), isTrue);
    expect(listEquals(listA, listC), isFalse);
    expect(listEquals(listA, listD), isFalse);
  });
  test('setEquals', () {
    final Set<int> setA = <int>{1, 2, 3};
    final Set<int> setB = <int>{1, 2, 3};
    final Set<int> setC = <int>{1, 2};
    final Set<int> setD = <int>{3, 2, 1};

    expect(setEquals<void>(null, null), isTrue);
    expect(setEquals(setA, null), isFalse);
    expect(setEquals(null, setB), isFalse);
    expect(setEquals(setA, setA), isTrue);
    expect(setEquals(setA, setB), isTrue);
    expect(setEquals(setA, setC), isFalse);
    expect(setEquals(setA, setD), isTrue);
  });
  test('mapEquals', () {
    final Map<int, int> mapA = <int, int>{1:1, 2:2, 3:3};
    final Map<int, int> mapB = <int, int>{1:1, 2:2, 3:3};
    final Map<int, int> mapC = <int, int>{1:1, 2:2};
    final Map<int, int> mapD = <int, int>{3:3, 2:2, 1:1};
    final Map<int, int> mapE = <int, int>{3:1, 2:2, 1:3};

    expect(mapEquals<void, void>(null, null), isTrue);
    expect(mapEquals(mapA, null), isFalse);
    expect(mapEquals(null, mapB), isFalse);
    expect(mapEquals(mapA, mapA), isTrue);
    expect(mapEquals(mapA, mapB), isTrue);
    expect(mapEquals(mapA, mapC), isFalse);
    expect(mapEquals(mapA, mapD), isTrue);
    expect(mapEquals(mapA, mapE), isFalse);
  });
  test('binarySearch', () {
    final List<int> items = <int>[1, 2, 3];

    expect(binarySearch(items, 1), 0);
    expect(binarySearch(items, 2), 1);
    expect(binarySearch(items, 3), 2);
    expect(binarySearch(items, 12), -1);
  });
63 64 65
  test('MergeSortRandom', () {
    final Random random = Random();
    for (int i = 0; i < 250; i += 1) {
66 67
      // Expect some equal elements.
      final List<int> list = List<int>.generate(i, (int j) => random.nextInt(i));
68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
      mergeSort(list);
      for (int j = 1; j < i; j++) {
        expect(list[j - 1], lessThanOrEqualTo(list[j]));
      }
    }
  });
  test('MergeSortPreservesOrder', () {
    final Random 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 (final int size in <int>[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.
84
      final List<OrderedComparable> list = List<OrderedComparable>.generate(
85 86 87
        size,
        (int i) => OrderedComparable(random.nextInt(size >> 2), i),
      );
88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
      mergeSort(list);
      OrderedComparable prev = list[0];
      for (int i = 1; i < size; i++) {
        final OrderedComparable 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.
      final List<OrderedComparable> copy = list.toList();
      final int min = size >> 2;
      final int max = size - min;
      mergeSort<OrderedComparable>(
        list,
        start: min,
        end: max,
        compare: (OrderedComparable a, OrderedComparable b) => b.compareTo(a),
      );
      prev = list[min];
      for (int i = min + 1; i < max; i++) {
        final OrderedComparable 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('MergeSortSpecialCases', () {
    for (final int size in <int>[511, 512, 513]) {
      // All equal.
126
      final List<OrderedComparable> list = List<OrderedComparable>.generate(size, (int i) => OrderedComparable(0, i));
127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173
      mergeSort(list);
      for (int i = 0; i < size; i++) {
        expect(list[i].order, equals(i));
      }
      // All but one equal, first.
      list[0] = OrderedComparable(1, 0);
      for (int i = 1; i < size; i++) {
        list[i] = OrderedComparable(0, i);
      }
      mergeSort(list);
      for (int 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 (int i = 0; i < size - 1; i++) {
        list[i] = OrderedComparable(0, i);
      }
      list[size - 1] = OrderedComparable(-1, size - 1);
      mergeSort(list);
      expect(list[0].order, equals(size - 1));
      for (int i = 1; i < size; i++) {
        expect(list[i].order, equals(i - 1));
      }

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

class OrderedComparable implements Comparable<OrderedComparable> {
  OrderedComparable(this.id, this.order);
  final int id;
  final int order;
  @override
  int compareTo(OrderedComparable other) => id - other.id;
  @override
  String toString() => 'OverrideComparable[$id,$order]';
174
}