While Loop not updating value of TreeMap

Question

I am currently trying to write a program which converts integers from 0-3999 into Roman Numerals, and I have got the basis of the code correct, as when I type e.g. 6, it produces IIIIII. However, I want it to convert to the correct roman numeral, which would be VI. I feel there is something wrong with my While loop, but cannot seem to figure out why the Key in my TreeMap will always be 1, meaning the numeral will always be I. What is wrong with my code, and how do I alter it to give me the correct Roman Numeral. Any help will be appreciated.

    public String generate(int number) {
    // System.out.println("NUMBER: " + number);
    if (number < MinNumber || number > MaxNumber) {
        System.out.println("Number is out of range");
        return null;
    }

    StringBuilder romanToString = new StringBuilder();
    NavigableMap<Integer, String> romanMap = createRomanMap();
    // TreeMap<Integer, String> romanMap = createRomanMap();
    for (Map.Entry<Integer, String> entries : romanMap.entrySet()) {
        Integer key = entries.getKey();
        String value = entries.getValue();

        while (number >= key) {
            number -= key;
            romanToString.append(value);
        }
    }
    System.out.println("Stringbuilder:  " + romanToString.toString());
    return romanToString.toString();

}

"I have got the basis of the code correct, as when I type e.g. 6, it produces IIIIII" => Hmm, 6 is VI, isn't it? — Seelenvirtuose, Jul 15 '18 at 14:37
Well, because your first key is 1. You then decrement number until it's < 1 (i.e. 0). In the following iterations, number is always lower than the key in your map. This is trivial to discover by using a debugger. Learn to use it **now**. — JB Nizet, Jul 15 '18 at 14:39
@Seelenvirtuose yeah, but my code isn't producing those numerals, which is what I want it to do. — John Lewis, Jul 15 '18 at 14:42
I think you'll need `romanMap.descendingMap().entrySet()` or construct your `TreeMap` with a `Comparator` that ensures reverse ordering. — d.j.brown, Jul 15 '18 at 14:48
Possible duplicate of [Converting Integers to Roman Numerals - Java](https://stackoverflow.com/q/12967896/5221149) — Andreas, Jul 15 '18 at 14:49
@d.j.brown this fixed my issue perfectly! Thank you so much. — John Lewis, Jul 15 '18 at 14:52

score 2 · Accepted Answer · answered Jul 15 '18 at 15:10

The issue is that you are traversing the TreeMap in its natural key ordering.

So consider a minimal Roman map like this, with this key ordering:

key = 1, value = "I"

key = 5, value = "V"

With the input 6 the following occurs:

First key = 1, first value = "I", number = 6

In your while loop you have 6 >= 1 => true, so append "I" and decrement 6 by the key 1.

This then repeats for 5, 4, 3, 2, 1 until the while loop invariant is broken.

However, if the Roman map is in descending order (i.e. reverse of the natural ordering), you will get the expected behavior:

First key = 5, first value = "V", number = 6

You now have 6 >= 5 => true, so append "V" and decrement 6 by the key 5, so 1. Then 1 >= 5 => false, so move onto the next Roman map entry.

How to achieve this?

Option 1

Use the descending map view's entry set:

Map.Entry<Integer, String> entrySet = romanMap.descendingMap().entrySet();

Option 2

Construct your TreeMap with a custom Comparator to change the ordering of the TreeMap, e.g.:

SortedMap<Integer, String> romanMap = new TreeMap<>((int1, int2) -> Integer.compare(int2, int1));

While Loop not updating value of TreeMap

1 Answers1