Java: Tricky sorting of prefixed Strings (ArrayLists)

arraylist, java, sorting, split, string

Solution

Don't remove the prefixes prior to passing it to the sorting function. Instead, in the `sortListOfIpv4s` method, always compare Strings using `s.substring(1)`, which will give you the entire string without the prefix, and add `s` to the resulting sorted array.

If `sortListOfIpv4s` is a black box and you are required to pass the prefix-free Strings, then you could cache the prefixes beforehand in a `Map` from `prefix-free IP -> prefix`:

Map<String, String> prefixMap = new HashMap<String, String>();
for (String ip : unsortedIPv4s) {
  prefixMap.put(ip.substring(1), ip.substring(0, 1));
}

Then sort and recover the prefixes from the `Map`:

List<String> sortedIPV4s = sortListOfIpv4s(unsortedIPv4s);
for (String ip : sortedIPV4s) {
  String prefix = prefixMap.get(ip);
  String originalIp = prefix + ip;
}

Problem

(No networking knowledge required whatsoever. This is purely String and Lists). Say I have a function in place, one that accepts a list of String IPv4 dotted address, and sorts them in ascending order. (Not alphabetical, true ip long format sorting). Let's call this: ``` public static ArrayList<String> sortListOfIpv4s(ArrayList<String> unsortedIPv4s); ``` This function already works correctly. Given an input: ``` 192.168.1.1, 8.8.8.8, 4.5.6.7, 244.244.244.244, 146.144.111.6 ``` It will output the list: ``` 4.5.6.7, 8.8.8.8, 146.144.111.6, 192.168.1.1, 244.244.244.244 ``` (Let's not get into a debate on whether it should modify the list in place or return a new list. It just returns a new list. Also, the function cannot be modified because of numerous reasons.) However, my input list looks like this: ``` e192.168.1.1, f8.8.8.8, e4.5.6.7, f244.244.244.244, e146.144.111.6 ``` When I remove the prefixes (only one of e or f, NOT NECESSARILY alternating) and create a clean array to pass to the sorting function, I lose the prefix information. What I would like is an output of the type: ``` e4.5.6.7, f8.8.8.8, e146.144.111.6, e192.168.1.1, f244.244.244.244 ``` Basically, prior to sorting, whatever prefix was present for each element in the unsorted list, the same prefix needs to be added back to the elements in the sorted list. Caveats: - An IP Address can repeat in the original list, a maximum of two times - When repeating twice, each of the two elements will have the same prefix, guaranteed - Sorting algorithm will not remove duplicates. A little algorithmic help please? (Remember, we already have a function that can sort clean IPv4 String arraylists).

Original source