// 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.

library map_test;

import 'dart:collection';

// Test that length/isEmpty operations are constant time on
// maps, strings and collections.

void testString(int n) {
  String s = "x";
  String string = "";
  int length = n;
  while (true) {
    if ((length & 1) == 1) {
      string += s;
    }
    length >>= 1;
    if (length == 0) break;
    s += s;
  }
  testLength(string, n);
  testLength(string.codeUnits, n);
}

void testMap(Map map, int n) {
  for (int i = 0; i < n; i++) {
    map[i] = i;
  }
  testLength(map, n);
  testLength(map.keys, n);
  testLength(map.values, n);
}

void testCollection(var collection, n) {
  for (int i = 0; i < n; i++) {
    collection.add(i);
  }
  testLength(collection, n);
}

void testList(List list, n) {
  // Works even if list is fixed-length.
  for (int i = 0; i < n; i++) {
    list[i] = i;
  }
  testLength(list, n);
}

void testLength(dynamic lengthable, int size) {
  print(lengthable.runtimeType); // Show what hangs the test.
  int length = 0;
  // If length, isEmpty or isNotEmpty is not a constant-time (or very fast)
  // operation, this will timeout.
  for (int i = 0; i < 100000; i++) {
    if (!lengthable.isEmpty) length += lengthable.length as int;
    if (lengthable.isNotEmpty) length += lengthable.length as int;
  }
  if (length != size * 200000) throw "Bad length: $length / size: $size";
}

main() {
  const int N = 100000;
  testMap(new HashMap(), N);
  testMap(new LinkedHashMap(), N);
  testMap(new SplayTreeMap(), N);
  testCollection(new HashSet(), N);
  testCollection(new LinkedHashSet(), N);
  testCollection(new ListQueue(), N);
  testCollection(new DoubleLinkedQueue(), N);
  testList([]..length = N, N);
  testList(new List.filled(0, null, growable: true)..length = N, N);
  testList(new List.filled(N, null), N);
  testString(N);
}