Iterating and Calculating numbers in a Map

Question

I have a Map of Lists with key = GROUP and value = List numbers stored as Strings. One element is below

GROUP1/[3.0, 4.0, 2.0, 3.0, 3.0, 2.0, 2.0, 2.0, 2.0, -2.0, -2.0, -2.0, 2.0]

What I have to do is to cancel off (remove) all the negative numbers against the positives but reduce the +ve numbers by that value.

In the above example, 3 will cancel off against -2 (first -ve) leaving +1 as the interim total

Then +1 (total from prev) will cancel off -2 (next -ve) leaving -1 as the interim total

-1 has to square against 4 (next +ve in the list) leaving 3 as the interim total

Then, 3 squares off against -2 (next -ve) leaving a total of 1.

Thus all -ve are eliminated from the List, so are 3.0, 4.0 but the first element is now 1.0 (1.0 being the last interim total)

Final sequence being

[1.0, 2.0, 3.0, 3.0, 2.0, 2.0, 2.0, 2.0, 2.0]

The code I have so far just totals up the List as below.

Map<String, List<String>> m = new HashMap<String, List<String>>();

...

for (Entry<String, List<String>> entry : m.entrySet()) 
{ 
  System.out.println(entry.getKey() + "/" + entry.getValue()); 
  double calc = 0;
  for (String element:entry.getValue()){
      //System.out.println(element);
      calc = calc + new Double(element).doubleValue();

  }
  //if (calc > 0.0)
      System.out.println("Total for Item: " + entry.getKey() + " is "+calc);
} 

Total for Item: GROUP1 is 19.0

I know we should not remove elements from the List as we iterate, so question is

A) Ideal Logic for removing the numbers in the sequence above.

B) Should I build a new List and add elements into it as I iterate ?

C) Should I change the collection I'm storing from Map of Lists to some class structure ?

Answer 1

I think the simplest solution is to iterate through the list twice, pull out the negative numbers on the first iterations, and then adjust the remaining numbers on the second iteration. If there is no need to keep the original map state then I would do everything in place, though I'm not sure why you think you are changing the map as you iterate, as there is nothing in your code that does so (unless that is a typo and you meant the list).

As for the collection type I think the main question is what type of performance do you need for the various operations, versus the size/type of data. Below is an implementation of the algorithm I described above. Since this may potentially do alot of removes (depending on your data) it may be better if the Lists are LinkedLists since they can do remove in constant time. Of course you can always do these calculations with LinkedLists and then make a copy of the data as another type such as ArrayList if you need better performance for indexed access.

As I stated before here is an implementation using a two pass approach. Note I don't remove zero values, and at the end it insert a single negative value if the total is negative (not sure what your requriements are in that case):

for (Entry<String, List<String>> entry : m.entrySet()){ 
  System.out.println(entry.getKey() + "/" + entry.getValue()); 
  double calc=0,acc = 0, item;
  //First look for negative values
  for (Iterator<String> it=entry.getValue().iterator();it.hasNext();){
    item = Double.parseDouble(it.next());
    calc += item;
    if(item < 0){
      //accumulate them, and remove them from the list
      acc += item;
      it.remove();
    }
  }
  if(calc > 0){
    //now adjust the remaining positive numbers
    for (Iterator<String> it=entry.getValue().iterator();it.hasNext();){
      item = Double.parseDouble(it.next());
      //remove the number as we adjust it if it
      //is the last positive it will be reinserted
      //when the loop breaks
      it.remove();
      if((acc+=item) >= 0){
        //the accumulated numbers are now positive
        break;
      }
    }
    //re-insert the adjusted positive back into the list
    entry.getValue().add(0, Double.toString(acc));
  }else{
    //the total sum was negative or zero
    entry.getValue().clear();
    entry.getValue().add(Double.toString(calc));
  }
  System.out.println("Total for Item: " + entry.getKey() + " is "+calc);
  System.out.println("List is now: "+entry.getValue());
}