/*
 * Lab 11, Task 3
 * CS 112
 */

public class Lab10Task3 {
    /*
     * numDigits - takes an integer and returns the number of digits
     * that it has
     */ 
    public static int numDigits(int val) {
        String valString = Integer.toString(Math.abs(val));
        return valString.length();
    }
    
    /* 
     * divideByLength - takes an array of integers and returns a List 
     * (either an ArrayList or LLList) in which all of the one-digit numbers 
     * come first, followed by all of the two-digit numbers, followed by 
     * all of the three-digit numbers. In the returned List, the numbers in 
     * a given subgroup (e.g., the one-digit numbers) are in the same order 
     * with respect to each other as they were in the original array.
     */
    public static List divideByLength(int[] values) {
        // We use three queues -- one for one-digit numbers, 
        // one for two-digit numbers, one for three-digit numbers.
        // We use queues because they maintain the relative ordering of 
        // each subgroup.
        // We use LLQueues because we don't know how many of each type of number
        // we'll have, and LLQueues start out empty and grow as needed.
        LLQueue<Integer> one = new LLQueue<Integer>();
        LLQueue<Integer> two = new LLQueue<Integer>();
        LLQueue<Integer> three = new LLQueue<Integer>();

        // Here's the one scan that we're allowed over the original array.
        // We insert each value into the appropriate queue.
        for (int i = 0; i < values.length; i++) {
            int n = numDigits(values[i]);
            if (n == 1) {
                one.insert(values[i]);
            } else if (n == 2) {
                two.insert(values[i]);
            } else {
                three.insert(values[i]);
            }
        }
        
        // In order to efficiently create a list that maintains the relative 
        // order of the numbers in each subgroup, we use an ArrayList, 
        // since we can add to the end of it in constant time. 
        ArrayList results = new ArrayList(values.length);
        
        int i = 0;   // index of the next item to add
        while (! one.isEmpty()) {
            int val = one.remove();
            results.addItem(val, i);
            i++;
        }
        while (! two.isEmpty()) {
            int val = two.remove();
            results.addItem(val, i);
            i++;
        }
        while (! three.isEmpty()) {
            int val = three.remove();
            results.addItem(val, i);
            i++;
        }
        
        return results;
    }
}