片鱗懐古のブログ: java : 連番ファイル名のソート

ありがちなコードのはずなのにネットで検索してもすぐ出てこなかったのでComparatorを作って見ました。車輪の再発明ですな。

仕様は、

ファイル名の比較。絶対パスでの比較はしない。
数字は1塊に付き「全桁がLong型に変換可能な18文字」まで比較可能。 18文字以上の数字の塊があった場合、比較結果は未定義。
数字として認識するのは半角のみ。
大文字と小文字を区別なく比較する。全く同じ文字列だったときのみ大文字と小文字を区別して比較しなおす。

ちょいと謎な仕様もありますが、まぁ自分用コードということでこんな感じです。

// FileNameComparator.java
package 適当なパッケージ名;

import java.io.File;
import java.util.Comparator;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * ファイル名の比較。絶対パスでの比較はしない。
 * 数字は、1塊に付き全桁がLong型に変換可能な18文字まで比較可能。
 * 18文字以上の数字の塊があった場合、比較結果は未定義。
 */
public final class FileNameComparator implements Comparator<File>
{
    private Pattern _pattern;

    public FileNameComparator()
    {
        _pattern = Pattern.compile("\\d{1,18}");
    }

    @Override public int compare(File f1, File f2)
    {
        if(f1 == f2)
            return 0;

        String s1 = f1.getName();
        String s2 = f2.getName();

        int res = compareString(s1, s2);

        // compareStringでは大文字小文字の区別をしないので、
        // そちらの結果が「等しい」ならここで大文字小文字の区別を含めた比較を改めて行う。
        return res == 0 ? s1.compareTo(s2) : res;
    }

    private int compareString(final String o1, final String o2)
    {
        final int len1 = o1.length();
        final int len2 = o2.length();
        Matcher matcher1 = _pattern.matcher(o1);
        Matcher matcher2 = _pattern.matcher(o2);
        int start1 = 0, start2 = 0, end1 = 0, end2 = 0, index1 = 0, index2 = 0;
        String strD1 = null;
        String strD2 = null;
        long d1 = 0;
        long d2 = 0;

        while(true)
        {
            boolean find1 = matcher1.find();
            boolean find2 = matcher2.find();

            if(find1)
            {
                start1 = matcher1.start();
                end1 = matcher1.end();
                strD1 = o1.substring(index1, start1);
                d1 = Long.parseLong(o1.substring(start1, end1) );
                index1 = end1;
            }
            else
            {
                strD1 = o1.substring(index1);
                index1 = len1;
            }

            if(find2)
            {
                start2 = matcher2.start();
                end2 = matcher2.end();
                strD2 = o2.substring(index2, start2);
                d2 = Long.parseLong(o2.substring(start2, end2) );
                index2 = end2;
            }
            else
            {
                strD2 = o2.substring(index2);
                index2 = len2;
            }

            if(find1 || find2) // どちらかに数字が含まれる
            {
                int eq = strD1.compareToIgnoreCase(strD2);
                if(eq != 0)
                {
                    return eq;
                }

                if(find1 && (!find2) ) // o1が(文字列+数字)でo2が(文字列)のみ → o2の方が先
                {
                    return 1;
                }
                else if( (!find1) && find2) // o1が(文字列)のみでo2が(文字列+数字) → o1の方が先
                {
                    return -1;
                }
                else if(d1 != d2) // 数字で比較
                {
                    return d1 < d2 ? -1 : 1;
                }
                else // 数字が同じなら、数字の文字数で比較。それも同じなら次の比較へ
                {
                    eq = (end1 - start1) - (end2 - start2);
                    if(eq != 0)
                    {
                        return eq;
                    }
                }
            }
            else // 両方文字列のみ
            {
                return strD1.compareToIgnoreCase(strD2);
            }

            if(index1 == len1)
            {
                return index2 == len2 ? 0 : -1;
            }
            else if(index2 == len2)
            {
                return 1;
            }
        }
    }
}

正規表現で[数字以外の文字列+数字]のセットを探して「数字以外の文字列を比較→数字を比較」をやっています。比較対象の文字列の頭に数字があって、[数字以外の文字列]の部分が無い場合は空の文字列""で代用です。

NetBeansで作ったので、付属のJUnitで簡単なテストをしました。「テスト項目に抜けがあるかもしれないなぁ」と思ったけど、「ステップ実行で全分岐を見たし、いいかな?」というような感じです。

// FileNameComparatorTest.java
package 適当なパッケージ名;

import java.io.File;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Random;
import java.util.TreeSet;
import org.junit.After;
import org.junit.AfterClass;
import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.Test;
import static org.junit.Assert.*;

public class FileNameComparatorTest {

    private Random _rand;

    public FileNameComparatorTest() {
        _rand = new Random(System.currentTimeMillis() );
    }

    @BeforeClass
    public static void setUpClass() throws Exception {
    }

    @AfterClass
    public static void tearDownClass() throws Exception {
    }

    @Before
    public void setUp() {
    }

    @After
    public void tearDown() {
    }

    @Test
    public void testCompare()
    {
        System.out.println("compare");
        FileNameComparator c = new FileNameComparator();

        assertTrue(checkOrder("test_a", "test_b", c) );       // 文字列のみの比較
        assertTrue(checkSameOrder("test_a", "test_a", c) );   // 文字列のみの比較
        assertTrue(checkOrder("tEST_a", "test_a", c) );       // 文字列のみの比較(一部大文字)
        assertTrue(checkOrder("test_a", "tEST_b", c) );       // 文字列のみの比較(違う文字列、一部大文字、辞書順)
        assertTrue(checkOrder("123", "456", c) );             // 数字のみの比較
        assertTrue(checkSameOrder("354", "354", c) );         // 数字のみの比較
        assertTrue(checkOrder("0123", "000123", c) );         // 同じ数字の場合、文字数の少ない方が先
        assertTrue(checkOrder("674812", "test", c) );         // 文字列と数字の比較
        assertTrue(checkOrder("test 96", "test 120", c) );    // 同じ文字列+数字の比較
        assertTrue(checkSameOrder("test11", "test11", c) );   // 同じ文字列+同じ数字の比較
        assertTrue(checkOrder("tEST531", "test531", c) );     // 同じ文字列+同じ数字の比較(一部大文字)
        assertTrue(checkOrder("test1", "test01", c) );        // 同じ数字の場合、文字数の少ない方が先
        assertTrue(checkOrder("test78", "testtest13", c) );   // 違う文字列+数字の比較
        assertTrue(checkOrder("8test", "222test", c) );       // 数字+同じ文字列の比較
        assertTrue(checkSameOrder("05test", "05test", c) );   // 数字+同じ文字列の比較
        assertTrue(checkOrder("246test", "00246test", c) );   // 同じ数字の場合、文字数の少ない方が先
        assertTrue(checkOrder("te st", "te st987", c) );      // 同じ文字列+片方に数字の比較
        assertTrue(checkOrder("test64", "test64test", c) );   // 同じ文字列+同じ数字+片方に文字列の比較
        assertTrue(checkOrder("test72ab", "test72xy", c) );   // 同じ文字列+同じ数字+違う文字列の比較
        assertTrue(checkOrder("test81ab", "test999ab", c) );   // 同じ文字列+違う数字+同じ文字列の比較
        assertTrue(checkOrder("t0e1s2t3T4E5S6T", "t0e1s2t3T9E5S6T", c) ); // 複合1
        assertTrue(checkOrder("t0e1s2t3T4E5S6T", "t0e1s2t3T!!!4E9S6T", c) ); // 複合2
        assertTrue(checkSameOrder("日本語も88通るはずa123b", "日本語も88通るはずa123b", c) ); // 日本語
        assertTrue(checkOrder("あい99うえお", "あいう99えお", c) );     // 日本語
        assertTrue(checkOrder("比較12します", "比較164532します", c) ); // 日本語
        assertTrue(checkOrder("test098765432109876543210", "test12345678901234567890", c) ); // 数字の18文字制限。「こうなるべき」というテスト項目ではなく、ステップ実行で様子を見るための項目。

        assertTrue(sort(c) );
    }

    // f1、f2の順になるような引数を渡す。
    private boolean checkOrder(String s1, String s2, FileNameComparator comparator)
    {
        System.out.println("  " + s1 + " ＜ " + s2);

        File f1 = new File(s1);
        File f2 = new File(s2);

        if(0 <= comparator.compare(f1, f2) )
            return false;
        if(comparator.compare(f2, f1) <= 0)
            return false;

        // comparator.compareの戻り値に勘違いがあってはいけないのでSortedSetでも並び替えて確認。
        TreeSet<File> set = new TreeSet<>(comparator);
        set.add(f1);
        set.add(f2);
        Iterator<File> iterator = set.iterator();

        if(iterator.next() != f1)
            return false;
        if(iterator.next() != f2)
            return false;

        set.clear();

        set.add(f2);
        set.add(f1);
        iterator = set.iterator();

        if(iterator.next() != f1)
            return false;
        return iterator.next() == f2;
    }

    private boolean checkSameOrder(String s1, String s2, FileNameComparator comparator)
    {
        System.out.println("  " + s1 + " == " + s2);
        return comparator.compare(new File(s1), new File(s2) ) == 0;
    }

    private boolean sort(FileNameComparator comparator)
    {
        File[] files1 = new File[]{
            new File("2012年4月"),
            new File("2012年05月"),
            new File("2012年6月"),
            new File("2012年07月"),
            new File("2012年8月"),
            new File("2012年9月"),
            new File("2012年10月"),
            new File("2012年11月"),
            new File("2012年12月"),
            new File("2013年01月"),
            new File("2013年2月"),
            new File("2013年3月")
        };
        File[] files2 = Arrays.copyOf(files1, files1.length);

        for(int i = 0; i < files2.length * 2; i++)
        {
            int j = 0, k = 0;
            while(j == k)
            {
                j = _rand.nextInt(files2.length);
                k = _rand.nextInt(files2.length);
            }

            File tmp = files2[j];
            files2[j] = files2[k];
            files2[k] = tmp;
        }
        System.out.println("  ソート前");
        for(File file : files2)
            System.out.println("    " + file.getName() );

        TreeSet<File> set = new TreeSet<>(comparator);
        set.addAll(Arrays.asList(files2) );

        System.out.println("  ソート後");
        int i = 0;
        for(File file : set)
        {
            System.out.println("    " + file.getName() );
            if(file != files1[i] )
            {
                return false;
            }
            i++;
        }

        return true;
    }
}

片鱗懐古のブログ

2012年8月7日火曜日

java : 連番ファイル名のソート

閲覧数が多い投稿

ラベル

広告

投稿した動画

ブログアーカイブ