sorting strings with embedder digits
tony
'track 4.mp3'. My problem is that a simple sort will put track 11 first
because it's alphabetical. My approach seems tortuous - split around
any digits, then from there build an array holding each part in turn.
Once that is done, you can compare the array entries and where digits
are involved, compare them numerically.
Does anyone know of a neater way to do this?
Tony
Donkey Hottie
Sure. A custom Comparator. Should be quite straightforward.
--
Do not overtax your powers.
Tom Anderson
It'll have to do the same work under the hood, though, so i don't see why
it would be any more straightforward than what Tony is currently doing.
Still, it's a way of packaging the logic, and it might be neater than
however he currently has it packaged.
I'd suggest implementing a Collator rather than a Comparator, so you can
make CollationKeys, and so avoid having to repeat the analysis of the
strings for each comparison. Having written your FilenameCollator, you can
do:
public void sortUsingCollator(List<String> strings, Collator collator) {
CollationKey[] keys = new CollationKey[strings.size()];
for (int i = 0; i < keys.length; ++i) {
keys[i] = collator.getCollationKey(string);
}
Arrays.sort(keys);
for (int i = 0; i < keys.length; ++i) {
strings.set(i, keys[i].getSourceString());
}
}
It's a shame there isn't a method to do this in the standard library (is
there?), since it's absolutely generic.
tom
--
IME the only lousy shags are when she says no! -- John Rowland
Roedy Green
wrote, quoted or indirectly quoted someone who said :
>Currently I need to sort a list of filenames such as 'track 11.mp3',
>'track 4.mp3'. My problem is that a simple sort will put track 11 first
>because it's alphabetical. My approach seems tortuous - split around
>any digits, then from there build an array holding each part in turn.
>Once that is done, you can compare the array entries and where digits
>are involved, compare them numerically.
see the Comparator in http://mindprod.com/products1.html#INI
--
Roedy Green Canadian Mind Products
http://mindprod.com
I mean the word proof not in the sense of the lawyers, who set two half proofs equal to a whole one, but in the sense of a mathematician, where half proof = 0, and it is demanded for proof that every doubt becomes impossible.
~ Carl Friedrich Gauss
bugbear
It sounds as if you (actually) want any text to act
as a primary sort key, with a track number to act a secondary.
There's no way to get this without treating the text
and track number quite separately.
BugBear
rossum
It might be possible if you pre-process the text to insert the
appropriate number of leading zeros. Text numbers with enough leading
zeros will sort correctly: 001, 002, 003 ... 010, 011, ... 045, 046,
rossum
bugbear
Still fails; if the preceding text fields are different lengths,
the digits are in different positions and don't "play nice"
The approach would work, but only if the text AND digits were both padded
(which involves identifying and processing them separately, of course...)
BugBear
rossum
Good point, but in this case the examples given in the OP would allow
this scheme to work:
track 04.mp3
track 11.mp3
etc.
In every example given the preceeding text is "track " so that can be
ignord for the purposes of ordering.
rossum
Eric Sosman
> rossum wrote:
>> On Fri, 27 Nov 2009 09:06:08 +0000, bugbear
>> <bugbear@trim_papermule.co.uk_trim> wrote:
>>
>>> tony wrote:
>>>> Currently I need to sort a list of filenames such as 'track 11.mp3',
>>>> 'track 4.mp3'. My problem is that a simple sort will put track 11
>>>> first because it's alphabetical. My approach seems tortuous - split
>>>> around any digits, then from there build an array holding each part
>>>> in turn. Once that is done, you can compare the array entries and
>>>> where digits are involved, compare them numerically.
>>>>
>>>> Does anyone know of a neater way to do this?
>>> It sounds as if you (actually) want any text to act
>>> as a primary sort key, with a track number to act a secondary.
>>>
>>> There's no way to get this without treating the text
>>> and track number quite separately.
>>>
>>> BugBear
>> It might be possible if you pre-process the text to insert the
>> appropriate number of leading zeros. Text numbers with enough leading
>> zeros will sort correctly: 001, 002, 003 ... 010, 011, ... 045, 046,
>
> Still fails; if the preceding text fields are different lengths,
> the digits are in different positions and don't "play nice"
If the preceding text fields are of different lengths, the
two Strings disagree before the values of the digit strings need
be considered. "XYZ10" vs. "XY9" never needs to worry about
"10" vs. "9". It might worry about "Z" vs. "9" or about "Z"
vs 9, but that's all.
More directly to the O.P.'s question, see
http://sourcefrog.net/projects/natsort/
(yes, that's "frog" and not "forge"), where there's C code to
compare strings this way. There's also a link to a Java version
http://pierre-luc.paour.9online.fr/NaturalOrderComparator.java
... but I haven't used it myself.
--
Eric Sosman
eso...@ieee-dot-org.invalid
Bent C Dalager
I wrote something like this once, I have put it here:
http://www.pvv.org/~bcd/StringNumberComparator.java
Cheers,
Bent D
--
Bent Dalager - b...@pvv.org - http://www.pvv.org/~bcd
powered by emacs
tony
> On 2009-11-26, tony <to...@tonyb.demon.co.uk> wrote:
>> Currently I need to sort a list of filenames such as 'track 11.mp3',
>> 'track 4.mp3'. My problem is that a simple sort will put track 11
>> first because it's alphabetical. My approach seems tortuous - split
>> around any digits, then from there build an array holding each part in
>> turn. Once that is done, you can compare the array entries and where
>> digits are involved, compare them numerically.
>>
>> Does anyone know of a neater way to do this?
>
> I wrote something like this once, I have put it here:
> http://www.pvv.org/~bcd/StringNumberComparator.java
>
> Cheers,
> Bent D
I'd actually got as far as using a custom comparator. I didn't want to
assume that the initial text was the same in each case, so the approach
was:
1: If there were no digits, just use the String compareTo otherwise
2: split each string with split("[0-9]") and remove any empty entries.
3: rebuild the array inserting any digit sequences by finding their
position, extracting them and putting hem in the right place
4: Compare the matching array elements until a decision could be made.
The digit strings are identified and compared by parsing as integers.
There were a few hiccups but it seems to work. I've modified it slightly
to have one for files using filenames as well.
Tony
Nigel Wade
I would have thought it would be much simpler and easier to use a regular
expression and a match group. Something like:
Pattern p = Pattern.compile(".*?(\\d+).*");
Matcher m = p.matcher(yourString);
if ( m.matches() ) {
// The Pattern matched yourString, and contains a set of digits.
// m.group(1) should contain the matched string of digits.
}
You can tweak the RE to get a more accurate match if it's not exactly as
required for your string contents.
--
Nigel Wade
Eric Sosman
"file12.ver3"
"file12.ver10"
--
Eric Sosman
eso...@ieee-dot-org.invalid
Roedy Green
<see_w...@mindprod.com.invalid> wrote, quoted or indirectly quoted
someone who said :
>On Thu, 26 Nov 2009 16:25:23 +0000, tony <to...@tonyb.demon.co.uk>
>wrote, quoted or indirectly quoted someone who said :
>
>>Currently I need to sort a list of filenames such as 'track 11.mp3',
>>'track 4.mp3'. My problem is that a simple sort will put track 11 first
>>because it's alphabetical. My approach seems tortuous - split around
>>any digits, then from there build an array holding each part in turn.
>>Once that is done, you can compare the array entries and where digits
>>are involved, compare them numerically.
>
>see the Comparator in http://mindprod.com/products1.html#INI
for alpha-numeric preprocess the keys into an alpha and numeric key.
/**
* Compare alphabetically with numeric tie breaker.
* Defines default the sort order for Item Objects.
* Compare this Item with another Item.
* Compares alphaKey then numericKey.
* Informally, returns (this-other) or +ve if this is more
positive than other.
*
* @param other other Item to compare with this one
*
* @return +ve if this>other, 0 if this==other, -ve if
this<other
*/
public final int compareTo( Item other )
{
int diff = this.alphaKey.compareToIgnoreCase(
other.alphaKey );
if ( diff != 0 )
{
return diff;
}
return Long.signum( this.numericKey - other.numericKey );
Tom Anderson
> return Long.signum( this.numericKey - other.numericKey );
Never do that! Consider this.numericKey = Long.MIN_VALUE and
other.numericKey = 1 - the answer should be negative, because the former
is less than the latter, but it will be positive.
Or are the numericKeys ints, and you're thinking that putting the
subtraction inside the call to signum will coax them to long, thus
avoiding this problem? It doesn't. You could achieve this by casting one
of the operands to long, though.
However, i suggest doing:
return new Long(this.numericKey).compareTo(other.numericKey);
And trusting that the optimiser will flatten out the boxing and the method
call.
tom
--
... a tale for which the world is not yet prepared
Lew
> return new Long(this.numericKey).compareTo(other.numericKey);
>
> And trusting that the optimiser will flatten out the boxing and the
> method call.
Or you can use Long.valueOf().
--
Lew
Nigel Wade
> Nigel Wade wrote:
>> You can tweak the RE to get a more accurate match if it's not exactly
>> as required for your string contents.
>
> "file12.ver3"
> "file12.ver10"
Which can be matched correctly by tweaking the RE, as I said. The RE I
provided was nothing more than an example. Given that I don't know what
the filename specification is, I can hardly provide a definitive RE, can
I?
--
Nigel Wade