// bubblesort.fleet
// Author: Thomas Kho <tkho@eecs.berkeley.edu>

#import edu.berkeley.fleet.ships

// 20 elements in memory
#memory { 1, 2, 6, 1, 3, 9, 4, 4, 7, 1,
          9, 4, 7, 6, 1, 2, 3, 0, 9, 3 }

#ship memread      : MemoryReadShip   // ports: addr, stride, count, data, done
#ship memwrite     : MemoryWriteShip  // ports: addr, stride, count, data, done

#ship halt         : HaltShip         // ports: in
#ship fetch        : FetchShip        // ports: codebag, release, revoke, done
#ship tokensource  : TokenSourceShip  // ports: out
#ship bitbucket    : BitBucketShip    // ports: token, data
#ship debug        : DebugShip        // ports: token, data
#ship counter      : HomeworkCounter  // ports: load, zero, positive, ask
#ship itercnt      : HomeworkCounter  // ports: load, zero, positive, ask

#ship max          : ArithmeticShip   // ports: A, B, cmd, out
#ship min          : ArithmeticShip   // ports: A, B, cmd, out

#ship dup1         : DuplicatorShip   // ports: in, out1, out2, out3, out4
#ship dup2         : DuplicatorShip   // ports: in, out1, out2, out3, out4

#ship tokenfifo    : TokenFifo        // ports: in, out
#ship donecodebag  : FifoShip         // ports: in, out

#ship nextcodebag  : FifoShip         // ports: in, out
#ship exitcodebag  : FifoShip         // ports: in, out

// first, load itercnt counter
{
  fetch.done -> bitbucket.token

  move+ack itercnt.load -> fetch.release
  itercnt.load -[*]-> ()

  itercnt.positive -[*]-> nextcodebag.out
  itercnt.zero -> exitcodebag.out
  // use tokens from itercnt to trigger delivery of the correct codebag
  triggered move nextcodebag.out -[*]-> fetch.codebag
  triggered move exitcodebag.out -[*]-> fetch.codebag
  CLEANUP -> exitcodebag.in

  FETCH_NEXT -> fetch.codebag
  19 -> itercnt.load
} -> fetch.codebag
nop+ack itercnt.load -> fetch.release

FETCH_NEXT: { // itercnt loaded
  fetch.done -> bitbucket.token

  LOOP_BODY -> nextcodebag.in
  tokensource.out -> itercnt.ask
  tokensource.out -> fetch.release
}

LOOP_BODY: {
  fetch.done -> bitbucket.token

  // donecodebag.in is called after one iteration of sort
  FETCH_NEXT -> donecodebag.in
  tokensource.out -> fetch.release
  SORT_ONCE -> fetch.codebag
}

CLEANUP: {
  fetch.done -> bitbucket.token

  nop+ack exitcodebag.out -> tokenfifo.in
  nop+ack nextcodebag.out -> tokenfifo.in
  nop+ack itercnt.positive -> tokenfifo.in
  nextcodebag.out -> bitbucket.data
  tokenfifo.out -[2]-> bitbucket.token
  tokenfifo.out -> halt.in
}

SORT_ONCE: {
  fetch.done -> bitbucket.token

  0 -> memread.addr
  1 -> memread.stride
  20 -> memread.count
  memread.done -> bitbucket.token

  // in-place sorting
  0 -> memwrite.addr
  1 -> memwrite.stride
  20 -> memwrite.count
  memwrite.done -> bitbucket.token

  // clear standing moves at inboxes that will ack
  nop+ack dup1.in -> tokenfifo.in
  nop+ack dup2.in -> tokenfifo.in
  nop+ack max.A -> tokenfifo.in
  nop+ack max.B -> tokenfifo.in
  nop+ack max.cmd -> tokenfifo.in
  nop+ack min.A -> tokenfifo.in
  nop+ack min.B -> tokenfifo.in
  nop+ack min.cmd -> tokenfifo.in
  nop+ack memwrite.data -> tokenfifo.in
  nop+ack counter.load -> tokenfifo.in
  tokenfifo.out -[9]-> bitbucket.token
  tokenfifo.out -> fetch.release

  {
    fetch.done -> bitbucket.token

    move+ack counter.load -> fetch.release
    counter.load -[*]-> () // restore standing move
    19 -> counter.load // load N - 1 into counter

    { // on counter load, seed pipeline
      fetch.done -> bitbucket.token

      tokensource.out -[3]-> counter.ask
    } -> fetch.codebag

    // send first memread.data to dup2.in
    memread.data -> dup2.in

    // counting pipeline: min.out -> memwrite.data
    triggered move min.out -[*]-> memwrite.data
    accept+ack memwrite.data -[*]-> counter.ask
    counter.positive -[*]-> min.out

    // standing commands on min, max ships
    copy min.cmd -[*]-> ()
    "MIN ZERO ZERO" -> min.cmd
    copy max.cmd -[*]-> ()
    "MAX ZERO ZERO" -> max.cmd

    // pipelines: dup1 -> max, dup2 -> max, dup1 -> min, dup2 -> min
    triggered move dup1.out1 -[*]-> max.A
    accept+ack max.A -[*]-> dup1.out1
    triggered move dup2.out1 -[*]-> max.B
    accept+ack max.B -[*]-> dup2.out1
    triggered move dup1.out2 -[*]-> min.A
    accept+ack min.A -[*]-> dup1.out2
    triggered move dup2.out2 -[*]-> min.B
    accept+ack min.B -[*]-> dup2.out2

    // pipeline: max.out -> dup2.in
    triggered move max.out -[*]-> dup2.in
    accept+ack dup2.in -[*]-> max.out

    // pipeline: memread.data -> dup1.in
    triggered move memread.data -[*]-> dup1.in
    accept+ack dup1.in -[*]-> memread.data

    // seed the above 6 pipelines
    tokensource.out -[3]-> dup1.out1
    tokensource.out -[3]-> dup1.out2
    tokensource.out -[3]-> dup2.out1
    tokensource.out -[3]-> dup2.out2
    tokensource.out -[3]-> memread.data
    tokensource.out -[2]-> max.out // also seeded with first data

    // ignore dup[12].out[03]
    dup1.out3 -[*]-> bitbucket.data
    dup1.out0 -[*]-> bitbucket.data
    dup2.out3 -[*]-> bitbucket.data
    dup2.out0 -[*]-> bitbucket.data

    // setup exit condition
    counter.zero -[2]-> bitbucket.token
    counter.zero -> fetch.release

    { // after N-1 writes
      fetch.done -> bitbucket.token

      // once we're done with N-1 writes, we can flush the last one
      // by comparing with MAXINT
      999 -> dup1.in
      tokensource.out -> min.out
      counter.zero -> fetch.release // trigger next codebag
    } -> fetch.codebag

    { // cleanup codebag
      fetch.done -> bitbucket.token

      // clear outbox standing moves
      nop+ack dup1.out0 -> tokenfifo.in
      nop+ack dup1.out3 -> tokenfifo.in
      nop+ack dup2.out0 -> tokenfifo.in
      nop+ack dup2.out3 -> tokenfifo.in
      nop+ack counter.positive -> tokenfifo.in
      nop+ack min.out -> tokenfifo.in

      // get rid of tokens
      triggered nop+ack memread.data -[4]-> tokenfifo.in // 3 + flush
      triggered nop+ack max.out -[3]-> tokenfifo.in
      triggered nop+ack dup1.out1 -[3]-> tokenfifo.in
      triggered nop+ack dup1.out2 -[3]-> tokenfifo.in
      triggered nop+ack dup2.out1 -[3]-> tokenfifo.in
      triggered nop+ack dup2.out2 -[3]-> tokenfifo.in

      // this, paired with MAXINT at port B, will kill standing copy
      0 -> max.A
      0 -> min.A
      max.out -> bitbucket.data
      min.out -> bitbucket.data

      // restore unacked inbox standing moves
      nop+ack memwrite.data -> tokenfifo.in
      memwrite.data -[*]-> ()
      nop+ack dup1.in -> tokenfifo.in
      dup1.in -[*]-> ()
      nop+ack dup2.in -> tokenfifo.in
      dup2.in -[*]-> ()
      nop+ack max.A -> tokenfifo.in
      max.A -[*]-> ()
      nop+ack min.A -> tokenfifo.in
      min.A -[*]-> ()
      nop+ack max.B -> tokenfifo.in
      max.B -[*]-> ()
      nop+ack min.B -> tokenfifo.in
      min.B -[*]-> ()
      nop+ack max.cmd -> tokenfifo.in
      max.cmd -[*]-> ()
      nop+ack min.cmd -> tokenfifo.in
      min.cmd -[*]-> ()

      tokenfifo.out -[33]-> bitbucket.token
      tokenfifo.out -> fetch.release
    } -> fetch.codebag

    {
      fetch.done -> bitbucket.token

      // standing copy is gone, so get rid of this last cmd
      0 -> max.A
      0 -> min.A
      0 -> max.B
      0 -> min.B

      // probably lax on the sequencing here
      max.out -> bitbucket.data
      min.out -> bitbucket.data

      // "function calls" return with a continuation
      tokensource.out -> fetch.release
      donecodebag.out -> fetch.codebag
    } -> fetch.codebag
  } -> fetch.codebag
}