import javafoundations.LinkedQueue; //for use of a Queue implementation
import javafoundations.Queue;

import java.util.Vector;
import java.util.Scanner;
import java.io.File;
import java.io.IOException;

/**
 * RadixSort.java Implements Radix sort for base-10, proper integers, each
 * of the same defined length.
 *
 * @author CS230 staff (SK)
 * @version  Fall 2020
 * */

public class RadixSort {
    //instance variables
    private final int NUMLENGTH = 3; //length of each number in input
    private final int BASE = 10; //number system we are working on

    private Vector<Integer> input; //to hold the input ints
    private Vector<String> workingVec; //holds the Strings during processing
    private Vector<Integer> output; //holds final sorted ints

    /**
     * constructor
     * This version just hardwires a few numbers for input
     * */
    public RadixSort(String inF) {
        //create vectors to hold the input and output
        input = new Vector<Integer>();
        readInput(inF);
        workingVec = new Vector<String>();
        output = new Vector<Integer>();

        //copy input ints into output Vector as strings
        for (int i=0; i<input.size(); i++) {
            workingVec.add(input.get(i)+""); //convert int into a string
        }
    }

    /**
     * reads input file into a vector of ints.
     * Assumes an integer per line in the file
     */
    private void readInput(String f) {
        try {
            Scanner scan = new Scanner(new File(f));
            while (scan.hasNextLine()) {
                input.add(Integer.parseInt(scan.nextLine()));
            }
            scan.close();
        } catch (IOException e) {
            System.out.println("Input file (" + f + ") cannot be read");
        }
    }

    /**
     * looks at one position (pos) of each string in the output Vector,
     * and enqueues the string to the corresponding q.
     * For example: if the current string is "514", and 'pos' is 0,
     * the string will be enqueued in the 5th queue,
     * b/c its digit at the 0th position is 5.
     * */
    private void processOnePosition(int pos) {
        String currentStr;
        Character currentChar;
        int currentDigit;

        //a vector of queues of Strings to be used during the sorting process
        Vector<Queue<String>> qs;
        //create a vector of the needed queues: as many as the digits
        //in the system we are working in. Each one starts out empty.
        qs = new Vector<Queue<String>>();
        for (int i=0; i<BASE; i++) {
            qs.add(new LinkedQueue<String>());
        }

        //for each str in the working vector
        for (int i = 0; i < workingVec.size(); i++)  {
            currentStr = workingVec.get(i);

            //get its character at input position 'pos'
            currentChar = currentStr.charAt(pos);
            // convert that char into an int
            currentDigit = Character.getNumericValue(currentChar);

            //use this int as an index into the vector of queues,
            //to enqueue the currentStr
            qs.get(currentDigit).enqueue(currentStr);
        }

        //empty each one of the queues into the output vector
        Queue<String> currentQ; //temporary variable
        //empty output vector each time you sort on a digit
        workingVec = new Vector<String>();

        for (int i=0; i<BASE; i++) { //for each queue in the vector
            currentQ = qs.get(i);
            //empty the queue into the output vector
            while (!currentQ.isEmpty()) {
                workingVec.add(currentQ.dequeue());
            }
        }
    }

    /**
     * Sorts the integers in the input in ascending order,
     * using Radix Sort.
     *
     * @throws a StringIndexOutOfBoundsException when the input integers
     * are not of the same length
     */
    public void sort() {
        try {
            //process each position,
            //starting with the least significant one
            for (int i=NUMLENGTH-1; i>=0; i--) {
                processOnePosition(i);
            }

            //fill in the final output vector with the sorted numbers
            for (int i=0; i<workingVec.size(); i++) {
                //now convert strings in output back into integers
                //and add them to the outputFinal vector of ints
                output.add(Integer.parseInt(workingVec.get(i)));
            }
        } catch (StringIndexOutOfBoundsException e) {
            System.out.println("Correct your input: All integers should have the same length");

        }
    }

    /*
     * returns a string containing the input and the sorted output integers
     *
     *@return the input and the sorted output integers
     */
    public String toString() {
        String s = "Initial numbers:\n" + input.toString();
        s = s + "\n\nSorted numbers:\n";
        s = s + output;
        return s;
    }

    public static void main(String[] args) {
        RadixSort sorter = new RadixSort("inputInts_1.txt");
        sorter.sort();
        System.out.println(sorter);

    }
}