• Post Reply Bookmark Topic Watch Topic
  • New Topic

Sorting 1.1.1.1.5. type structures  RSS feed

 
Paul Kaatranen
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

I need to know if anyone can help me in the right direction when trying to numericly sort the following data.
The data is a string which contains up to five levels of integer type data all separated by dots, eg 1.2.1.1.4.

1.1.
1.10.
1.11.
...
1.19.
1.2.
1.20.
1.21.
...

This should be sorted like this:

1.1.
1.2.
...
1.10.
1.11.
...
1.20.
1.21.

The same applies of to inner levels so

1.1.1.2.
1.1.1.2.1.
1.1.1.3.
1.1.1.3.1.
1.1.1.3.10.
1.1.1.3.11.
1.1.1.3.9.
1.1.1.3.2.
...

should be sorted
1.1.1.2.
1.1.1.2.1.
1.1.1.3.
1.1.1.3.1.
1.1.1.3.2.
...
1.1.1.3.9.
1.1.1.3.10.
1.1.1.3.11.

The amount of data which needs to be sorted at the moment is only around 250 strings, so it is quite small.
Any help would be greatly appreciated!

My guess is that some recursive function will be needed to handle the result at each level, but I am quite stumped atm.

Thanks!!

p.s. I am an old rancher, but I have totally forgot my previous login info
 
salvin francis
Saloon Keeper
Posts: 1644
37
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Perhaps a Comparator might help ?
 
Stephan van Hulst
Saloon Keeper
Posts: 7928
143
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
As Salvin has said, you can write a Comparator to do this.

I'm not a big fan of Strings, I would suggest you write a LeveledNumber class that wraps around such a String and is Comparable to itself.
 
Paul Kaatranen
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sounds like I will have to learn about Comparators! I like the idea of the wrapper class...will try and figure it out. Thanks
 
Campbell Ritchie
Marshal
Posts: 56221
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

Do your objects have the same level of nesting for all? Do they all contain 4 dots? You can create a Comparator<IntQuintuplet> quite simply. Or you can say that class supports natural order, in which case it may be simpler for it to implement Comparable<IntQuintuplet>. Start by reading about object ordering in the Java™ Tutorials. You can also use a Stream for sorting:-The meaning of lines 1-4 should be obvious.
You can get a Stream<T> from any List, and the Stream is implicitly the same generic type as the List, so don't try it on raw types.
You can pass a Comparator<T> to the sorted method as a parameter, or you can write a λ. If the type of the Stream implements Comparable (or more precisely T extends Comparable<? super T>), then you can use the no‑arguments version of Stream#sorted(). Using sorted() may require much memory until the sorting process is completed. That will probably only be a problem if you have many millions of items in the Stream.
The meaning of the toList method should be obvious. You get a List<T> implementation, but the Stream documentation doesn't specify what sort of List. If you want a particular implementation you can try this instead of line 8:-
  .collect(Collectors.toCollection(ArrayList::new));
The toCollection method returns a Collection and the ::new bit means you are calling a constructor of the type before :: so you get an ArrayList.

There is a simpler method if you don't mind losing the original order:-
quins.sort(null);

Assuming you have 4 dots in every item, then a typical IntQuintuplet might have this structure
 
Paul Kaatranen
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks guys for the great help!

I decided to do a bit of overtime and got it figured out using the Comparator.
 
Campbell Ritchie
Marshal
Posts: 56221
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well done
 
Stephan van Hulst
Saloon Keeper
Posts: 7928
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm curious how you implemented it, can you show us?
 
Paul Kaatranen
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

basically like this... I decided to "hard code" the int[10], but... it suits my purpose atm (with a minimum amount of testing)


 
Stephan van Hulst
Saloon Keeper
Posts: 7928
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Seeing as LevelIndicator is the thing you want to sort, you shouldn't make it a Comparator, you should make it Comparable. A Comparator is something used to compare *other* types of things.

When you do this, you don't have to call Collections.sort() with a separate Comparator object, you can just sort the LevelIndicators by their 'natural order'.

Another thing. You can easily avoid hardcoding lvls, by instantiating it with the length of parts.
 
Stephan van Hulst
Saloon Keeper
Posts: 7928
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One more thing. If you make something Comparable, you should probably also make it meaningfully equal to itself. Override equals() and hashCode(), and make compareTo() consistent with equals.

Consistency with equals means that whenever compareTo() returns 0, equals() returns true, and when compareTo() doesn't return 0, equals() returns false.
 
Campbell Ritchie
Marshal
Posts: 56221
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan is right.
Also don't use underscores in variable names.
You should split the String with "\\." You have to escape the dot with \\ because it is a metacharacter. At least I think that is correct.
Don't hardcode 10. Don't catch the Exception, except possibly to throw a different exception. If you have an array with other than 5 elements, or a non‑integer, let the Exception go and crash the program.
What do the four fields mean? I thought you would only need 1 field.
 
Paweł Baczyński
Bartender
Posts: 2061
44
Firefox Browser IntelliJ IDE Java Linux Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And make sure your fields are private.
 
Campbell Ritchie
Marshal
Posts: 56221
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Also, // comments should be short. I changed one // comment of yours to a /* comment */ because the lines were too long to read easily.
 
Stephan van Hulst
Saloon Keeper
Posts: 7928
143
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So here's a complete class that encapsulates all the logic for converting between int arrays and leveled strings, and imposing a natural ordering on them. I think an important thing to note is that it concerns itself with the levels only, and not other data that happens to be specific to the application. That means that it can be reused for various purposes (paragraph numbering, version numbering, etc.?). Another very important aspect is that it's immutable. That makes it perfect to use as a key in maps, among other things. Take a close look, and if you have questions for us, please don't hesitate.
 
Paul Kaatranen
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Wow - I didn't expect that - thanks!

As I am stuck with Java 7 I was forced to change the constructor implementations a bit and managed to get it working. I changed my own implementation based of yours and sorted out a couple of minor kinks in my own code.

Thanks again!!
 
Stephan van Hulst
Saloon Keeper
Posts: 7928
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I hope you draw inspiration from it for your future classes. Keep them simple. Make them immutable when possible and convenient. Always consider if it makes sense to make them Comparable. Override equals() and hashCode() when it makes sense. Check your parameters and throw exceptions when they're invalid, or when your object is in a wrong state.

You should also be precise in what behavior you expect from your classes, and document them as such. For example, look how the IntHierarchy makes a clear distinction between when it returns/expects non-negative integers and positive integers. Don't make users of your class guess how it behaves.
 
Campbell Ritchie
Marshal
Posts: 56221
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Note the regular expressions. You can use "\\." to get the dot because it is a meta‑character whose meaning you can find here.

Stephan: is "[.]" the same as "\\."? I use regexes so rarely that I can never remember.
 
Stephan van Hulst
Saloon Keeper
Posts: 7928
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
They are essentially the same. Dot is just a character class that matches every character (except for newlines, unless the DOTALL flag is used). "\\" escapes it, and "[]" treats it as a simple character. Likewise, "$" means 'end of input', and "\\$" and "[$]" both mean 'dollar sign'.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!