TreeSetの使い方

#導入
こんにちは。けちょんです。
TreeSet使ってますか？
私は今日初めて見ました。
類似のHashSetやTreeMapは使ったことがあるんでないでしょうか。

#TreeSetとは
重複を許さず、addするときにソートして保持してくれるクラスです。
競技プログラミングで役立ちそうな気がするクラスですね。

#使ってみる
##まず、TreeSetにaddするオブジェクトを作成

class Product {
	private int id;
	private String name;

	public Product() {
	}

	public Product(int id, String name) {
		this.id = id;
		this.name = name;
	}

	public int getId() {
		return this.id;
	}

	public String getName() {
		return this.name;
	}

}

idとnameのフィールドと、コンストラクターと、アクセッサーを作成しました。

##次に、インスタンスを追加

Set<Product> tree = new TreeSet<>();
tree.add(new Product(1, "kechong"));
tree.add(new Product(2, "me"));
tree.add(new Product(3, "you"));
for (Product product : tree) {
	System.out.print("id:" + product.getId() + ", ");
	System.out.print("name:" + product.getName());
	System.out.println();
}

はい、実行してみます。

Exception in thread "main" java.lang.ClassCastException: Product cannot be cast to java.base/java.lang.Comparable
	at java.base/java.util.TreeMap.compare(TreeMap.java:1291)
	at java.base/java.util.TreeMap.put(TreeMap.java:536)
	at java.base/java.util.TreeSet.add(TreeSet.java:255)
	at Main.main(Main.java:26)

エラーが出ましたね。

##どんなエラー？
ClassCastExceptionが投げられていますね。
ProductがComparableにキャストできないって怒られています。
発生場所は、TreeSetにaddしようとしたときです。

###なぜキャストしようとしているか
キャストとかしないでいいのに、、、
と、思いますが、これはTreeSetには必要なんです。

TreeSetは順序という概念を持っています。
TreeSetにaddするときに、保持する位置を定めるために順序を決める必要があります。
Productクラスを自分で作成した時に、「Productオブジェクトを比較する方法」を定めなかったためにエラーが発生しています。

##比較という概念を追加する
具体的には、Comparableインターフェースを実装します。

class Product implements Comparable<Product> {
	private int id;
	private String name;

	public Product() {
	}

	public Product(int id, String name) {
		this.id = id;
		this.name = name;
	}

	public int getId() {
		return this.id;
	}

	public String getName() {
		return this.name;
	}

	@Override
	public int compareTo(Product o) {
		return this.id - o.id;
	}

}

はい、implementsして、compareToメソッドをオーバーライドしました。

##もう一回実行すると、、、

id:1, name:kechong
id:2, name:me
id:3, name:you

はい、良さそうですね！

#ちなみに
今回はProductクラスでComparableインターフェースを実装しました。
が、TreeSetのインスタンス化時に、コンストラクターの引数に以下のように指定することでも同様の出力となります。

Set<Product> tree = new TreeSet<>(Comparator.comparing(Product::getId));

これはTreeSet側に比較方法を与えることで、順序を決定できるようにしています。

#まとめ
TreeSetに自作オブジェクトを追加する場合は、以下のいずれかの作業が必要
・自作オブジェクトでComparableインターフェースを実装する
・TreeSetのコンストラクター引数に比較方法を指定する