// RUN: %target-typecheck-verify-swift
// RUN: %target-swift-frontend -debug-generic-signatures -emit-ir %s 2>&1 | %FileCheck %s

// https://github.com/apple/swift/issues/55258

public protocol DefaultInitializable {
  init()
}

public protocol AdjacencyEdge_ {
  associatedtype VertexID: Equatable
  associatedtype Properties

  var destination: VertexID { get set }
  var properties: Properties { get set }
}

public struct AdjacencyEdge<VertexID: Equatable, Properties>: AdjacencyEdge_ {
  public var destination: VertexID
  public var properties: Properties
}

public protocol AdjacencyVertex_ {
  associatedtype Edges: Collection where Edges.Element: AdjacencyEdge_
  associatedtype Properties

  var edges: Edges { get set }
  var properties: Properties { get set }
}

public struct AdjacencyVertex<Edges: Collection, Properties> : AdjacencyVertex_
  where Edges.Element: AdjacencyEdge_
{
  public var edges: Edges
  public var properties: Properties
}

public protocol BinaryFunction {
  associatedtype Parameter0
  associatedtype Parameter1
  associatedtype Result

  func callAsFunction(_: Parameter0, _: Parameter1) -> Result
}

public struct GeneralAdjacencyList<
  Spine: Collection, VertexIDToIndex: BinaryFunction
>
  where Spine.Element : AdjacencyVertex_,
        VertexIDToIndex.Parameter0 == Spine,
        VertexIDToIndex.Parameter1 == Spine.Element.Edges.Element.VertexID,
        VertexIDToIndex.Result == Spine.Index
{
  public let vertexIDToIndex: VertexIDToIndex
  public var spine: Spine
}

public struct IdentityVertexIDToIndex<Spine: Collection>: BinaryFunction
  where Spine.Element : AdjacencyVertex_,
        Spine.Element.Edges.Element.VertexID == Spine.Index
{
  public func callAsFunction(_: Spine, _ id: Spine.Index) -> Spine.Index {
    return id
  }
}

public extension GeneralAdjacencyList {
  typealias VertexID = VertexIDToIndex.Parameter1
  typealias VertexProperties = Spine.Element.Properties
  typealias EdgeProperties = Spine.Element.Edges.Element.Properties

  struct EdgeID: Equatable {
    /// The source vertex.
    let source: VertexIDToIndex.Parameter1
    /// The position of the edge in `source`'s list of edges.
    let targetIndex: Spine.Index
  }
}

// CHECK-LABEL: Generic signature: <Spine, VertexIDToIndex where Spine : RangeReplaceableCollection, VertexIDToIndex == IdentityVertexIDToIndex<Spine>, Spine.[Sequence]Element : AdjacencyVertex_, Spine.[Collection]Index == Spine.[Sequence]Element.[AdjacencyVertex_]Edges.[Sequence]Element.[AdjacencyEdge_]VertexID, Spine.[Sequence]Element.[AdjacencyVertex_]Edges : BidirectionalCollection, Spine.[Sequence]Element.[AdjacencyVertex_]Edges : RangeReplaceableCollection>
public extension GeneralAdjacencyList
  where VertexIDToIndex == IdentityVertexIDToIndex<Spine>,
        Spine: RangeReplaceableCollection,
        Spine.Element.Edges: RangeReplaceableCollection
          & BidirectionalCollection // Because https://github.com/apple/swift/issues/55257
{
  func addVertex(storing properties: VertexProperties) -> VertexID {
    return spine.indices.first!
  }
}