//===--- TwoSum.swift -----------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

// This test is solves 2SUM problem:
// Given an array and a number C, find elements A and B such that A+B = C
import TestsUtils

public let TwoSum = BenchmarkInfo(
  name: "TwoSum",
  runFunction: run_TwoSum,
  tags: [.validation, .api, .Dictionary, .Array, .algorithm])

let array = [
  959,  81, 670, 727, 416, 171, 401, 398, 707, 596, 200,   9, 414,  98,  43,
  352, 752, 158, 593, 418, 240, 912, 542, 445, 429, 456, 993, 618,  52, 649,
  759, 190, 126, 306, 966,  37, 787, 981, 606, 372, 597, 901, 158, 284, 809,
  820, 173, 538, 644, 428, 932, 967, 962, 959, 233, 467, 220,   8, 729, 889,
  277, 494, 554, 670,  91, 657, 606, 248, 644,   8, 366, 815, 567, 993, 696,
  763, 800, 531, 301, 863, 680, 703, 279, 388, 871, 124, 302, 617, 410, 366,
  813, 599, 543, 508, 336, 312, 212,  86, 524,  64, 641, 533, 207, 893, 146,
  534, 104, 888, 534, 464, 423, 583, 365, 420, 642, 514, 336, 974, 846, 437,
  604, 121, 180, 794, 278, 467, 818, 603, 537, 167, 169, 704,   9, 843, 555,
  154, 598, 566, 676, 682, 828, 128, 875, 445, 918, 505, 393, 571,   3, 406,
  719, 165, 505, 750, 396, 726, 404, 391, 532, 403, 728, 240,  89, 917, 665,
  561, 282, 302, 438, 714,   6, 290, 939, 200, 788, 128, 773, 900, 934, 772,
  130, 884,  60, 870, 812, 750, 349,  35, 155, 905, 595, 806, 771, 443, 304,
  283, 404, 905, 861, 820, 338, 380, 709, 927,  42, 478, 789, 656, 106, 218,
  412, 453, 262, 864, 701, 686, 770,  34, 624, 597, 843, 913, 966, 230, 942,
  112, 991, 299, 669, 399, 630, 943, 934, 448,  62, 745, 917, 397, 440, 286,
  875,  22, 989, 235, 732, 906, 923, 643, 853,  68,  48, 524,  86,  89, 688,
  224, 546,  73, 963, 755, 413, 524, 680, 472,  19, 996,  81, 100, 338, 626,
  911, 358, 887, 242, 159, 731, 494, 985,  83, 597,  98, 270, 909, 828, 988,
  684, 622, 499, 932, 299, 449, 888, 533, 801, 844, 940, 642, 501, 513, 735,
  674, 211, 394, 635, 372, 213, 618, 280, 792, 487, 605, 755, 584, 163, 358,
  249, 784, 153, 166, 685, 264, 457, 677, 824, 391, 830, 310, 629, 591,  62,
  265, 373, 195, 803, 756, 601, 592, 843, 184, 220, 155, 396, 828, 303, 553,
  778, 477, 735, 430,  93, 464, 306, 579, 828, 759, 809, 916, 759, 336, 926,
  776, 111, 746, 217, 585, 441, 928, 236, 959, 417, 268, 200, 231, 181, 228,
  627, 675, 814, 534,  90, 665,   1, 604, 479, 598, 109, 370, 719, 786, 700,
  591, 536,   7, 147, 648, 864, 162, 404, 536, 768, 175, 517, 394,  14, 945,
  865, 490, 630, 963,  49, 904, 277,  16, 349, 301, 840, 817, 590, 738, 357,
  199, 581, 601,  33, 659, 951, 640, 126, 302, 632, 265, 894, 892, 587, 274,
  487, 499, 789, 954, 652, 825, 512, 170, 882, 269, 471, 571, 185, 364, 217,
  427,  38, 715, 950, 808, 270, 746, 830, 501, 264, 581, 211, 466, 970, 395,
  610, 930, 885, 696, 568, 920, 487, 764, 896, 903, 241, 894, 773, 896, 341,
  126,  22, 420, 959, 691, 207, 745, 126, 873, 341, 166, 127, 108, 426, 497,
  681, 796, 430, 367, 363
]

@inline(never)
public func run_TwoSum(_ N: Int) {
  var i1: Int?
  var i2: Int?
  var Dict: Dictionary<Int, Int> = [:]
  for _ in 1...2*N {
    for Sum in 500..<600 {
      Dict = [:]
      i1 = nil
      i2 = nil
      for n in 0..<array.count {
        if let m = Dict[Sum-array[n]] {
          i1 = m
          i2 = n
          break
        }
        Dict[array[n]] = n
      }
      CheckResults(i1 != nil && i2 != nil)
      CheckResults(Sum == array[i1!] + array[i2!])
    }
  }
}