<commit_before>//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2015 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
// RUN: %target-run-stdlib-swift
// REQUIRES: executable_test

public enum ApproximateCount {
  case Unknown
  case Precise(IntMax)
  case Underestimate(IntMax)
  case Overestimate(IntMax)
}

public protocol ApproximateCountableSequenceType : SequenceType {
  /// Complexity: amortized O(1).
  var approximateCount: ApproximateCount { get }
}

/// A collection that provides an efficient way to spilt its index ranges.
public protocol SplittableCollectionType : CollectionType {
  // We need this protocol so that collections with only forward or bidirectional
  // traversals could customize their splitting behavior.
  //
  // FIXME: all collections with random access should conform to this protocol
  // automatically.

  /// Splits a given range of indicies into a set of disjoint ranges covering
  /// the same elements.
  ///
  /// Complexity: amortized O(1).
  ///
  /// FIXME: should that be O(log n) to cover some strange collections?
  ///
  /// FIXME: index invalidation rules?
  ///
  /// FIXME: a better name.  Users will never want to call this method
  /// directly.
  ///
  /// FIXME: return an optional for the common case when split() can not
  /// subdivide the range further.
  func split(range: Range<Index>) -> [Range<Index>]
}

internal func _splitRandomAccessIndexRange<Index : RandomAccessIndexType>(
  range: Range<Index>
) -> [Range<Index>] {
  let startIndex = range.startIndex
  let endIndex = range.endIndex
  let length = distance(startIndex, endIndex).toIntMax()
  if length < 2 {
    return [ range ]
  }
  let middle = advance(startIndex, Index.Distance(length / 2))
  return [
    Range(start: startIndex, end: middle),
    Range(start: middle, end: endIndex)
  ]
}

/// A helper object to build a collection incrementally in an efficient way.
///
/// Using a builder can be more efficient than creating an empty collection
/// instance and adding elements one by one.
public protocol CollectionBuilderType {
  typealias Collection : CollectionType
  typealias Element = Collection.Generator.Element

  init()

  /// Gives a hint about the expected approximate number of elements in the
  /// collection that is being built.
  mutating func sizeHint(approximateSize: Int)

  /// Append `element` to `self`.
  ///
  /// If a collection being built supports a user-defined order, the element is
  /// added at the end.
  ///
  /// Complexity: amortized O(1).
  mutating func append(element: Collection.Generator.Element)

  /// Append `elements` to `self`.
  ///
  /// If a collection being built supports a user-defined order, the element is
  /// added at the end.
  ///
  /// Complexity: amortized O(n), where `n` is equal to `count(elements)`.
  mutating func appendContentsOf<
    C : CollectionType
    where
    C.Generator.Element == Element
  >(elements: C)

  /// Append elements from `otherBuilder` to `self`, emptying `otherBuilder`.
  ///
  /// Equivalent to::
  ///
  ///   self.appendContentsOf(otherBuilder.takeResult())
  ///
  /// but is more efficient.
  ///
  /// Complexity: O(1).
  mutating func moveContentsOf(inout otherBuilder: Self)

  /// Build the collection from the elements that were added to this builder.
  ///
  /// Once this function is called, the builder may not be reused and no other
  /// methods should be called.
  ///
  /// Complexity: O(n) or better (where `n` is the number of elements that were
  /// added to this builder); typically O(1).
  mutating func takeResult() -> Collection
}

public protocol BuildableCollectionType : CollectionType {
  typealias Builder : CollectionBuilderType
}

extension Array : SplittableCollectionType {
  public func split(range: Range<Int>) -> [Range<Int>] {
    return _splitRandomAccessIndexRange(range)
  }
}

public struct ArrayBuilder<T> : CollectionBuilderType {
  // FIXME: the compiler didn't complain when I remove public on 'Collection'.
  // File a bug.
  public typealias Collection = Array<T>
  public typealias Element = T

  internal var _resultParts = [[T]]()
  internal var _resultTail = [T]()

  public init() {}

  public mutating func sizeHint(approximateSize: Int) {
    _resultTail.reserveCapacity(approximateSize)
  }

  public mutating func append(element: T) {
    _resultTail.append(element)
  }

  public mutating func appendContentsOf<
    C : CollectionType
    where
    C.Generator.Element == T
  >(elements: C) {
    _resultTail.appendContentsOf(elements)
  }

  public mutating func moveContentsOf(inout otherBuilder: ArrayBuilder<T>) {
    // FIXME: do something smart with the capacity set in this builder and the
    // other builder.
    _resultParts.append(_resultTail)
    _resultTail = []
    // FIXME: not O(1)!
    _resultParts.appendContentsOf(otherBuilder._resultParts)
    otherBuilder._resultParts = []
    swap(&_resultTail, &otherBuilder._resultTail)
  }

  public mutating func takeResult() -> Collection {
    _resultParts.append(_resultTail)
    _resultTail = []
    // FIXME: optimize.  parallelize.
    return join([], _resultParts)
  }
}

extension Array : BuildableCollectionType {
  public typealias Builder = ArrayBuilder<Element>
}

//===----------------------------------------------------------------------===//
// Fork-join
//===----------------------------------------------------------------------===//

// As sad as it is, I think for practical performance reasons we should rewrite
// the inner parts of the fork-join framework in C++.  In way too many cases
// than necessary Swift requires an extra allocation to pin objects in memory
// for safe multithreaded access.  -Dmitri

import SwiftShims
import SwiftPrivate
import Darwin
import Dispatch

// A wrapper for pthread_t with platform-independent interface.
public struct _stdlib_pthread_t : Equatable, Hashable {
  internal let _value: pthread_t

  public var hashValue: Int {
    return _value.hashValue
  }
}

public func == (lhs: _stdlib_pthread_t, rhs: _stdlib_pthread_t) -> Bool {
  return lhs._value == rhs._value
}

public func _stdlib_pthread_self() -> _stdlib_pthread_t {
  return _stdlib_pthread_t(_value: pthread_self())
}

struct _ForkJoinMutex {
  var _mutex: UnsafeMutablePointer<pthread_mutex_t>

  init() {
    _mutex = UnsafeMutablePointer.alloc(1)
    if pthread_mutex_init(_mutex, nil) != 0 {
      fatalError("pthread_mutex_init")
    }
  }

  func `deinit`() {
    if pthread_mutex_destroy(_mutex) != 0 {
      fatalError("pthread_mutex_init")<commit_msg>CollectionTransformers.swift uses modules that are not available on Linux<commit_after>//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2015 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
// RUN: %target-run-stdlib-swift
// REQUIRES: executable_test

public enum ApproximateCount {
  case Unknown
  case Precise(IntMax)
  case Underestimate(IntMax)
  case Overestimate(IntMax)
}

public protocol ApproximateCountableSequenceType : SequenceType {
  /// Complexity: amortized O(1).
  var approximateCount: ApproximateCount { get }
}

/// A collection that provides an efficient way to spilt its index ranges.
public protocol SplittableCollectionType : CollectionType {
  // We need this protocol so that collections with only forward or bidirectional
  // traversals could customize their splitting behavior.
  //
  // FIXME: all collections with random access should conform to this protocol
  // automatically.

  /// Splits a given range of indicies into a set of disjoint ranges covering
  /// the same elements.
  ///
  /// Complexity: amortized O(1).
  ///
  /// FIXME: should that be O(log n) to cover some strange collections?
  ///
  /// FIXME: index invalidation rules?
  ///
  /// FIXME: a better name.  Users will never want to call this method
  /// directly.
  ///
  /// FIXME: return an optional for the common case when split() can not
  /// subdivide the range further.
  func split(range: Range<Index>) -> [Range<Index>]
}

internal func _splitRandomAccessIndexRange<Index : RandomAccessIndexType>(
  range: Range<Index>
) -> [Range<Index>] {
  let startIndex = range.startIndex
  let endIndex = range.endIndex
  let length = distance(startIndex, endIndex).toIntMax()
  if length < 2 {
    return [ range ]
  }
  let middle = advance(startIndex, Index.Distance(length / 2))
  return [
    Range(start: startIndex, end: middle),
    Range(start: middle, end: endIndex)
  ]
}

/// A helper object to build a collection incrementally in an efficient way.
///
/// Using a builder can be more efficient than creating an empty collection
/// instance and adding elements one by one.
public protocol CollectionBuilderType {
  typealias Collection : CollectionType
  typealias Element = Collection.Generator.Element

  init()

  /// Gives a hint about the expected approximate number of elements in the
  /// collection that is being built.
  mutating func sizeHint(approximateSize: Int)

  /// Append `element` to `self`.
  ///
  /// If a collection being built supports a user-defined order, the element is
  /// added at the end.
  ///
  /// Complexity: amortized O(1).
  mutating func append(element: Collection.Generator.Element)

  /// Append `elements` to `self`.
  ///
  /// If a collection being built supports a user-defined order, the element is
  /// added at the end.
  ///
  /// Complexity: amortized O(n), where `n` is equal to `count(elements)`.
  mutating func appendContentsOf<
    C : CollectionType
    where
    C.Generator.Element == Element
  >(elements: C)

  /// Append elements from `otherBuilder` to `self`, emptying `otherBuilder`.
  ///
  /// Equivalent to::
  ///
  ///   self.appendContentsOf(otherBuilder.takeResult())
  ///
  /// but is more efficient.
  ///
  /// Complexity: O(1).
  mutating func moveContentsOf(inout otherBuilder: Self)

  /// Build the collection from the elements that were added to this builder.
  ///
  /// Once this function is called, the builder may not be reused and no other
  /// methods should be called.
  ///
  /// Complexity: O(n) or better (where `n` is the number of elements that were
  /// added to this builder); typically O(1).
  mutating func takeResult() -> Collection
}

public protocol BuildableCollectionType : CollectionType {
  typealias Builder : CollectionBuilderType
}

extension Array : SplittableCollectionType {
  public func split(range: Range<Int>) -> [Range<Int>] {
    return _splitRandomAccessIndexRange(range)
  }
}

public struct ArrayBuilder<T> : CollectionBuilderType {
  // FIXME: the compiler didn't complain when I remove public on 'Collection'.
  // File a bug.
  public typealias Collection = Array<T>
  public typealias Element = T

  internal var _resultParts = [[T]]()
  internal var _resultTail = [T]()

  public init() {}

  public mutating func sizeHint(approximateSize: Int) {
    _resultTail.reserveCapacity(approximateSize)
  }

  public mutating func append(element: T) {
    _resultTail.append(element)
  }

  public mutating func appendContentsOf<
    C : CollectionType
    where
    C.Generator.Element == T
  >(elements: C) {
    _resultTail.appendContentsOf(elements)
  }

  public mutating func moveContentsOf(inout otherBuilder: ArrayBuilder<T>) {
    // FIXME: do something smart with the capacity set in this builder and the
    // other builder.
    _resultParts.append(_resultTail)
    _resultTail = []
    // FIXME: not O(1)!
    _resultParts.appendContentsOf(otherBuilder._resultParts)
    otherBuilder._resultParts = []
    swap(&_resultTail, &otherBuilder._resultTail)
  }

  public mutating func takeResult() -> Collection {
    _resultParts.append(_resultTail)
    _resultTail = []
    // FIXME: optimize.  parallelize.
    return join([], _resultParts)
  }
}

extension Array : BuildableCollectionType {
  public typealias Builder = ArrayBuilder<Element>
}

//===----------------------------------------------------------------------===//
// Fork-join
//===----------------------------------------------------------------------===//

// As sad as it is, I think for practical performance reasons we should rewrite
// the inner parts of the fork-join framework in C++.  In way too many cases
// than necessary Swift requires an extra allocation to pin objects in memory
// for safe multithreaded access.  -Dmitri

import SwiftShims
import SwiftPrivate
import Darwin
import Dispatch

// FIXME: port to Linux.
// XFAIL: linux

// A wrapper for pthread_t with platform-independent interface.
public struct _stdlib_pthread_t : Equatable, Hashable {
  internal let _value: pthread_t

  public var hashValue: Int {
    return _value.hashValue
  }
}

public func == (lhs: _stdlib_pthread_t, rhs: _stdlib_pthread_t) -> Bool {
  return lhs._value == rhs._value
}

public func _stdlib_pthread_self() -> _stdlib_pthread_t {
  return _stdlib_pthread_t(_value: pthread_self())
}

struct _ForkJoinMutex {
  var _mutex: UnsafeMutablePointer<pthread_mutex_t>

  init() {
    _mutex = UnsafeMutablePointer.alloc(1)
    if pthread_mutex_init(_mutex, nil) != 0 {
      fatalError("pthread_mutex_init")
    }
  }

  func `deinit`() {
    if pthread_mutex_destroy(_mutex) != 0 {
      fatalError("pthread_mutex_init")
{'fraction_non_alphanumeric': 0.14163212805488065, 'fraction_numerical': 0.003001286265542375, 'mean_word_length': 2.8279540481400436, 'pattern_counts': {'":': 0, '<': 33, '<?xml version=': 0, '>': 45, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4902681', 'n_tokens_mistral': 3980, 'n_tokens_neox': 3864, 'n_words': 1339}