How to populate array with elements based on priority?

Question

I try to solve this problem quick but I see it will be not so easy.

I have map where key is Unit type and value is Integer that represents unit priority when to show unit on the screen.

So I need to fill List<String> list with Unit types.

In basic words if list = [A, B, C, D] this is an order to show them up.

A -> B -> C -> D.

I wrote basic class and it works as expected.

public class MonsterSort2 {

/**
 * @param args
 */
public static void main(String[] args) {

    int elementCount = 20;

    List<String> list = new ArrayList<String>(elementCount);

    Map<String, Integer>  map = new LinkedHashMap<String, Integer>();

    map.put("A", 1);
    map.put("C", 2);
    map.put("D", 2);
    map.put("B", 3);



    Iterator<String> it = map.keySet().iterator();

    int shift = 0;


    while(it.hasNext()){
        String unitName = it.next();

        for(int i=shift; i<elementCount; i++){
            list.add(unitName);

            if(i == elementCount/map.size() -1 + shift){
                shift = i;
                break;
            }
        }       

    }//while

    System.out.println(list);

}
} 

So I get Output:

[A, A, A, A, A, C, C, C, C, C, D, D, D, D, D, B, B, B, B, B]

However the problem is what if 2 or 3 or 4 units have the same priority?

My mind says to show them randomly. For followed priorities:

map.put("A", 1);
map.put("C", 2);
map.put("D", 2);
map.put("B", 3);

Expected output should be:

 [A, A, A, A, A, C, D, D, C, C, D, D, C, D, C, B, B, B, B, B]

as you can see C and D stay on random places but after A and before B.

How can I achieve this logic?

Thanks,

Answer 1

I created:

Map<String, Double> pseudoMap = new HashMap<String, Double>(elementCount);

after generated random double number from 0 to 1 but different from 0 and 1:

double d = 0.0;

// generate double <> 0 or 1
while(d == 0.0 || d == 1.0){
  d = rand.nextDouble();
} 

I populated my pseudoMap with key and postfix and added random number:

pseudoMap.put(unitName + "_" + i, (double)(unitMap.get(unitName) + d));  

I got:

{B_15=3.1016031962291204, B_14=3.4563893967442123, B_16=3.11280085831218,
 B_12=3.2976658355169466, C_8=2.6491871264729765, D_6=2.223351148643601, 
 B_13=3.577597012082142, C_9=2.541821826106959, D_5=2.4389896004212637, 
 D_4=2.2044652083865226, D_8=2.7914089043360315, D_7=2.2760755825849546, 
 A_1=1.6863051487791398, A_0=1.0879832608200397, C_11=2.552343819848361, 
 C_12=2.6759559071285404, C_10=2.7712147590013814, A_4=1.9764299942651913,
 A_3=1.973038652207146, A_2=1.1844902000282258}

Next, created class:

public class PriorityComparator  implements Comparator<String> {

Map<String, Double> base;
public PriorityComparator(Map<String, Double> base) {
    this.base = base;
}


public int compare(String a, String b) {
    if (base.get(a) <= base.get(b)) {
        return -1;
    } else {
        return 1;
    } 
  }
}

and sorted all 20 units by double value.

The main point is: since random between 0 and 1, it does not influence on standalone priority. For example unit A will flow between 1 and 1.9999999 but never jump in to B position.

So after sorting I got as expected:

[A, A, A, A, A, C, C, C, D, D, D, C, C, D, D, B, B, B, B, B]

This is a full example code:

public class MonsterSort2 {

/**
 * @param args
 */
public static void main(String[] args) {

    int elementCount = 23;

    List<String> list = new ArrayList<String>(elementCount);

    Map<String, Integer>  unitMap = new LinkedHashMap<String, Integer>();

    unitMap.put("A", 1);
    unitMap.put("C", 2);
    unitMap.put("D", 2);
    unitMap.put("B", 3);

    Random rand = new Random();

    ValueComparator bvc =  new ValueComparator(unitMap);

    TreeMap<String,Integer> sorted_map = new TreeMap<String,Integer>(bvc);

    Map<String, Double> pseudoMap = new HashMap<String, Double>(elementCount);


    sorted_map.putAll(unitMap);

    unitMap = new LinkedHashMap<String, Integer>(sorted_map);

    Iterator<String> it = unitMap.keySet().iterator();

    int shift = 0;

    while(it.hasNext()){
        String unitName = it.next();

        //prevPrior = unitList.get(unitName);

        for(int i=shift; i<elementCount; i++){
            //list.add(unitName);

            double d = 0.0;

            // generate double <> 0 or 1
            while(d == 0.0 || d == 1.0){
                d = rand.nextDouble();
            }

            pseudoMap.put(unitName + "_" + i, (double)(unitMap.get(unitName) + d));

            if(i == elementCount/unitMap.size() -1 + shift){
                shift = i;
                break;
            }
        }       

    }//while


    PriorityComparator prComp =  new PriorityComparator(pseudoMap);

    TreeMap<String,Double> sorted_map_total = new TreeMap<String,Double>(prComp);

    sorted_map_total.putAll(pseudoMap);

    list = new ArrayList<String>(elementCount);

    it = sorted_map_total.keySet().iterator();

    while(it.hasNext()){
        String unitName = it.next();

        list.add(unitName.split("_")[0]);


    }//while

    System.out.println(list);

}
}

Answer 2

I suggest to create a class for your monster like so:

class Monster implements Comparable<Monster> {
  public String name;
  public int priority;

  public int compareTo(Monster o) {
     if (priority != o.priority )
       return priority - o.priority;
     return (Math.random() > 0.5)?1:-1;
  }
}

add your monsters to a TreeSet<Monster> and voila.