Explore our sites

Stack Exchange
tour help careers 2.0
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 5 down vote favorite
1

(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).

share|improve this question
 
Are you saying you want to treat sortListOfIpv4s as a black box? You're not allowed to change it? –  Ismail Badawi Aug 26 '12 at 23:23
 
Precisely. Team environment, large team, and it's a library function not meant to altered for every unique use-case. –  ink.robot Aug 26 '12 at 23:25
add comment

3 Answers

up vote 2 down vote accepted

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;
}
share|improve this answer
 
Unfortunately, that's not possible. It's a library function and it's being used heavily by other developers. It would be met with a lot of criticism if I demanded that it be modified for this particular scenario. So I have to make a wrapper function around it. –  ink.robot Aug 26 '12 at 23:24
 
No. I have already mentioned under caveats that if an IP repeats twice, in the original unsorted list, then both are guaranteed to have the same prefix. –  ink.robot Aug 26 '12 at 23:30
 
@refactor.me: Ok, then you can cache the prefixes before sorting the list, and recover them later from the cached map. See my updated answer. –  João Silva Aug 26 '12 at 23:33
 
Flawless victory. It's 4 a.m. and my brain isn't really working. Thanks for the quick help. Much appreciated. Answer accepted. –  ink.robot Aug 26 '12 at 23:34
 
@refactor.me: You're welcome, glad I could help. –  João Silva Aug 26 '12 at 23:35
show 1 more comment
up vote 0 down vote

Your method could move any prefix to the end of the String, sort the list, and then go through the Strings again and move the prefixes from the end back to the start.

share|improve this answer
 
That would do the job, but would be pretty ugly. It's pretty easy to implement a custom sort that can deal with the prefix in java, rather than move the prefix out of the equation. –  Tobias N. Sasse Aug 26 '12 at 23:47
add comment
up vote 0 down vote

You could implement Comparator:

public class IpComparator implements Comparator<String> {
    @Override
    public int compare(String ipA, String ipB) {
        return doComparison( ipA.substring(1), ipB.substring(1) );
    }
}

Then you can use it:

return Collections.sort(unsortedIPv4s, new IpComparator());
share|improve this answer
 
Hah, same idea :-) –  Tobias N. Sasse Aug 26 '12 at 23:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.