// SpaceSorter.java
// Michele Loreti and the jSpace Developers, 2017
// Modified by Andrew Davison, ad@coe.psu.ac.th, May 2023

/* A concurrent version of mergesort
   https://en.wikipedia.org/wiki/Merge_sort

   Create multiple Splitter and Merger threads. 
   The Splitter threads will read a tuple of the form:
      ("SPLITING", arr)

   and put back out two new SPLITING tuples with the
   lower and upper halves of arr.

   If the array size == 1, then a 
   (MERGING, arr) is put out instead which are processed by
   the Merging threads.

   Only one Merging thread can read from the space at once, by
   grabbing the ("MERGE") tuple. It reads in any two 
   MERGING tuples, merges the two arrays together in ascending order
   and puts out a new, bigger MERGING tuple with the new array.

   When the new array is the size of the original unsorted 
   array, then merging is complete and the thread puts out a
   (FIN, arr) instead, which is read in by main() and reported.
   
  Original code at:
    https://gitlab.gbar.dtu.dk/02148/home/-/blob/master/solutions/java/Exercise_2_4/Exercise_2_4.java

  Usage:
    > compile.bat SpaceSorter.java
    > run.bat SpaceSorter

    Part of the application made up of:
       * SpaceSorter.java
       * Splitter.java
       * Merger.java
*/

import java.util.*;

import org.jspace.*;


public class SpaceSorter
{
  public static void main(String[] args)
                            throws InterruptedException
  {
    // Space space = new SequentialSpace();
    Space space = new VisSpace(100);   // small delay: 0.1 sec

    PrintAreas pas = new PrintAreas(4);

    int[] arr = new int[] {7, 6, 5, 4, 3, 2, 1};
    System.out.println("Unsorted array: " + Arrays.toString(arr));

    /* place the array to be sorted in the tuple space, which
       starts the splitting of the array into subarrays */
    space.put("SPLITING", arr);

    /* the MERGE tuple is used to allow one Merge thread 
       to read from the space at a time */
    space.put("MERGE");

    // create the workers (any number)
    new Thread( new Splitter(0, pas, space), "Splitter-0").start();
    new Thread( new Splitter(1, pas, space), "Splitter-1").start();
    new Thread( new Merger(2, arr.length, pas, space), "Merger-0").start();
    new Thread( new Merger(3, arr.length, pas, space), "Merger-1").start();

    // wait for the sorted array FIN tuple
    Object[] res = space.query( new ActualField("FIN"), 
                                new FormalField(Object.class));
    int[] sortedArr = (int[])res[1];
    System.out.println("Sorted array: " + Arrays.toString(sortedArr));
  } /* main */


}  // end of SpaceSorter class