Comparable আর Comparator — সাজানোর নিয়ম

১ · সাজাতে হলে একটি নিয়ম লাগে — “কে আগে?”

SSC বা HSC-র ফল বের হলে একটি স্কুল তার মেধাতালিকা টাঙায়। সেই তালিকা বানাতে কম্পিউটারকে কী জানতে হয়? সাজানোর অ্যালগরিদম কম্পিউটার আগে থেকেই জানে — Java-র ভেতরে সেটা তৈরি আছে। যা সে জানে না, তা হলো আপনার নিয়ম: দুজন ছাত্রের মধ্যে কে আগে বসবে। GPA বেশি যার, সে আগে? GPA সমান হলে? তখন মোট নম্বর? সেটাও সমান হলে নামের ক্রম? যেকোনো sort অ্যালগরিদম আসলে এই একটি প্রশ্ন হাজারবার জিজ্ঞেস করে, প্রতিবার দুজনকে নিয়ে। প্রশ্নের উত্তর দেওয়ার দায়িত্ব আপনার।

Java এই উত্তর দেওয়ার দুটি জায়গা দেয়:

আগে যা দেখেছেন — compareTo-এর চুক্তি

পর্ব ২৩-এ (equals, hashCode, toString আর compareTo) Comparable আর compareTo দেখেছেন। সংক্ষেপে মনে করিয়ে দিই, কারণ Comparator-এর compare(a, b) হুবহু একই চুক্তি মানে:

• শুধু চিহ্ন গুরুত্বপূর্ণ: ঋণাত্মক মানে a আগে, শূন্য মানে ক্রমে সমান, ধনাত্মক মানে a পরে। −১ আর −৫০০-এর মানে একই।
• উল্টালে চিহ্ন উল্টাবে: compare(a, b) ঋণাত্মক হলে compare(b, a) ধনাত্মক হতেই হবে।
• transitive: a আগে b, আর b আগে c হলে a আগে c.
• বিয়োগ নয়, Integer.compare: a - b বড় বা বিপরীত চিহ্নের সংখ্যায় integer overflow করে চিহ্ন উল্টে দেয়। Comparator-এ এই ভুল আরও বেশি দেখা যায়, কারণ lambda-য় (a, b) -> a.score - b.score লেখা খুব সহজ।

Class-এর এই স্বাভাবিক ক্রমকে বলে natural ordering. কিন্তু বাস্তব সফটওয়্যারে একটি জিনিস প্রায় কখনো এক ক্রমে সাজাতে হয় না। একটি অনলাইন দোকানের পণ্যের তালিকায় ব্যবহারকারী চাপেন “দাম: কম থেকে বেশি”, “রেটিং: বেশি থেকে কম”, “নতুন আগে”। একটি প্রোগ্রামিং কনটেস্টের leaderboard সাজায় সমাধান করা সমস্যার সংখ্যায়, সমান হলে penalty-তে। প্রতিটি ক্রমের জন্য Product বা Team class বদলানো অসম্ভব — তাই Comparator.

২ · কোথায় সাজাবেন — list, array আর primitive

নিয়ম হাতে থাকলে সেটা কাকে দেবেন? Java-তে তিনটি প্রচলিত দরজা আছে:

আধুনিক কোডে list.sort(cmp) সবচেয়ে প্রচলিত — পড়তে সহজ, আর ArrayList-এর ক্ষেত্রে সরাসরি ভেতরের array সাজায়। List.of(...) দিয়ে বানানো list বদলানো যায় না, তাই তার ওপর sort ডাকলে UnsupportedOperationException আসে — আগে new ArrayList<>(...) দিয়ে কপি করে নিন (পর্ব ৩০)।

primitive array — Comparator চলে না

int[] বড় থেকে ছোট সাজাতে স্বাভাবিকভাবে মনে হয় Arrays.sort(a, Comparator.reverseOrder()) লিখি। javac রাজি হয় না:

Main.java:6: error: no suitable method found for sort(int[],Comparator<T#1>)
        Arrays.sort(a, Comparator.reverseOrder());
              ^
(তারপর কয়েক লাইনে ব্যাখ্যা: inference variable T#2 has incompatible bounds … equality constraints: int, upper bounds: Object)

কারণ generics শুধু reference টাইপ নিয়ে কাজ করে (পর্ব ২৮) — Comparator<int> বলে কিছু হয় না। শেষ লাইনটাই আসল কথা বলছে: T-কে int হতে হবে, অথচ T Object-এর নিচের কিছু হতে হবে। তিনটি বাস্তব সমাধান:

• ছোট থেকে বড় সাজিয়ে উল্টে নিন: Arrays.sort(a), তারপর একটি লুপে দুই প্রান্ত থেকে অদলবদল। বড় array-তে সবচেয়ে দ্রুত, কোনো বাড়তি object নেই।
• শুরু থেকেই Integer[] রাখুন: Arrays.sort(b, Comparator.reverseOrder()) চলে — কিন্তু প্রতিটি সংখ্যা এখন একটি আলাদা object.
• Stream দিয়ে box করে আবার unbox: Arrays.stream(a).boxed().sorted(Comparator.reverseOrder()).mapToInt(Integer::intValue).toArray() — এক লাইনে, তবে অনেক autoboxing; Stream পর্ব ৩৫-এ।

Primitive array-এর Arrays.sort ভেতরে একটি আলাদা অ্যালগরিদম চালায় — Dual-Pivot Quicksort — যা object-এর sort-এর মতো stable নয়। ভয়ের কিছু নেই: দুটি সমান int-কে আলাদা করে চেনার কোনো উপায়ই নেই, তাই কে আগে গেল তা কেউ টের পায় না (ভাবনার প্রশ্ন ৪)।

৩ · Comparator-এর বিবর্তন — anonymous class থেকে এক লাইন

Comparator একটি functional interface — এর একটিমাত্র abstract method, int compare(T a, T b). Java 1.2 (১৯৯৮) থেকে interface-টি আছে, কিন্তু লেখার ধরন সময়ের সাথে নাটকীয়ভাবে বদলেছে। একই নিয়ম — “GPA বেশি যার, সে আগে” — চার যুগে:

// Java 7 পর্যন্ত — ছয় লাইন, আসল কথা একটি
list.sort(new Comparator<Student>() {
    @Override
    public int compare(Student a, Student b) {
        return Double.compare(b.gpa(), a.gpa());   // b আগে লেখা = বড় থেকে ছোট
    }
});

// Java 8 থেকে — একই কাজ এক লাইনে
list.sort((a, b) -> Double.compare(b.gpa(), a.gpa()));

// Java 8 থেকে — "কী দিয়ে" বলুন, "কীভাবে" নয়
list.sort(Comparator.comparing(Student::gpa).reversed());

// key primitive হলে — boxing ছাড়া
list.sort(Comparator.comparingDouble(Student::gpa).reversed());

লক্ষ করুন, Comparator.comparing নিজে কিছু সাজায় না। এটি একটি function (key extractor) নেয়, আর ফেরত দেয় আরেকটি function (Comparator) — function থেকে function বানানোর কারখানা। এমন method-কে বলে higher-order function. reversed(), thenComparing() — এরাও একটি Comparator নিয়ে নতুন Comparator ফেরত দেয়; আসলটি বদলায় না। এজন্যই এদের শিকলের মতো জোড়া যায়, আর একবার বানানো Comparator নিরাপদে বহু জায়গায় আবার ব্যবহার করা যায় (ভাবনার প্রশ্ন ৫)।

৪ · নিয়মের শিকল — thenComparing, reversed আর মেধাতালিকা

বাস্তব নিয়ম প্রায় কখনো এক ধাপের নয়। উদাহরণ হিসেবে একটি স্কুলের মেধাতালিকার নিয়ম ধরি (নিয়মগুলো এই পর্বের উদাহরণ, কোনো বোর্ডের সরকারি নিয়ম নয়): GPA বেশি আগে; GPA সমান হলে মোট নম্বর বেশি আগে; সেটাও সমান হলে নামের বর্ণানুক্রমে। প্রতিটি পরের নিয়ম একটি tie-breaker — আগের নিয়মে সমান হলেই কেবল কাজে লাগে। Java-তে এটা হুবহু এক বাক্যে লেখা যায়। নিচের প্রোগ্রামে Student একটি record, যার natural ordering রোল নম্বর:

import java.util.*;

record Student(int roll, String name, double gpa, int total) implements Comparable<Student> {
    @Override public int compareTo(Student o) { return Integer.compare(roll, o.roll); }
}

class Main {
    public static void main(String[] args) {
        List<Student> list = new ArrayList<>(List.of(
            new Student(104, "Rafi", 5.00, 1180), new Student(101, "Mitu", 4.83, 1105),
            new Student(103, "Anika", 5.00, 1180), new Student(102, "Sakib", 5.00, 1215),
            new Student(105, "Joy", 4.83, 1120)));
        Collections.sort(list);                          // natural ordering: roll
        System.out.println("roll:  " + list.stream().map(Student::name).toList());

        Comparator<Student> merit = Comparator.comparingDouble(Student::gpa).reversed()
            .thenComparing(Comparator.comparingInt(Student::total).reversed())
            .thenComparing(Student::name);
        list.sort(merit);
        for (Student s : list) System.out.printf("%-6s %.2f %d%n", s.name(), s.gpa(), s.total());

        list.sort(Comparator.comparingDouble(Student::gpa).thenComparing(Student::name).reversed());
        System.out.println("wrong: " + list.stream().map(Student::name).toList());
    }
}

Sakib  5.00 1215
Anika  5.00 1180
Rafi   5.00 1180
Joy    4.83 1120
Mitu   4.83 1105

Sort চলার সময় এই merit Comparator-কে বারবার দুজন ছাত্র দেওয়া হয়। একটি জোড়া কীভাবে নিষ্পত্তি হয়, ধাপে ধাপে দেখুন:

1merit.compare(a, b):2  comparingDouble(Student::gpa).reversed()3  .thenComparing(comparingInt(Student::total).reversed())4  .thenComparing(Student::name)

reversed()-এর ফাঁদ — কাকে উল্টায়?

প্রোগ্রামের শেষ লাইনটি এই পর্বের সবচেয়ে প্রচলিত bug. লেখক চেয়েছিলেন “GPA বড় থেকে ছোট, তারপর নাম A থেকে Z”. লিখলেন comparingDouble(gpa).thenComparing(name).reversed() — ভেবেছিলেন reversed শুধু GPA-র জন্য। কিন্তু Java-তে method chain বাঁ থেকে ডানে চলে: reversed() ডাকা হয় তার আগের পুরো শিকলের ফলাফলের ওপর।

Joy 4.83 · Mitu 4.83 · Anika 5.00 · Rafi 5.00 · Sakib 5.00
GPA ছোট থেকে বড়; সমান GPA-র ভেতরে ক্রম এখনো ঠিক হয়নি

[Joy, Mitu, Anika, Rafi, Sakib]
এখন একটি সম্পূর্ণ নিয়ম: GPA ↑, তারপর নাম ↑

[Sakib, Rafi, Anika, Mitu, Joy]
GPA ↓ ঠিক আছে, কিন্তু নামও ↓ — Z থেকে A

[Anika, Rafi, Sakib, Joy, Mitu]
reversed শুধু GPA-কে উল্টাল, তারপর নাম যোগ হলো ↑

lambda দিয়ে লিখলে আরেকটি অবাক করা error

Student::gpa-র বদলে lambda লিখে তার ওপর reversed ডাকলে javac একটি বিভ্রান্তিকর error দেয়:

list.sort(Comparator.comparing(s -> s.gpa()).reversed());   // compile হয় না

Main.java:8: error: cannot find symbol
        list.sort(Comparator.comparing(s -> s.gpa()).reversed());
                                             ^
  symbol:   method gpa()
  location: variable s of type Object

s-কে Object ভাবল কেন? Java-র type inference সাধারণত বাইরের প্রসঙ্গ দেখে lambda-র টাইপ বোঝে — list.sort চায় Comparator<Student>, তাই s হলো Student. কিন্তু এখানে comparing-এর ফলাফলের ওপর সরাসরি .reversed() ডাকা হয়েছে; method chain-এর মাঝের ধাপে বাইরের প্রসঙ্গ পৌঁছায় না, তাই javac কোনো তথ্য না পেয়ে s-কে Object ধরে। সমাধান তিনটি: method reference (Student::gpa নিজেই টাইপ বলে দেয়), lambda-য় টাইপ লেখা ((Student s) -> s.gpa()), অথবা Comparator.<Student, Double>comparing(...). এই কারণেই Comparator-এর শিকলে method reference সবচেয়ে প্রচলিত।

৫ · stable sort — সমান যারা, তারা আগের ক্রমে

ধরুন একটি ওয়েবসাইটে ছাত্রদের তালিকা আগে নামের ক্রমে দেখানো হচ্ছিল। ব্যবহারকারী এবার “GPA” কলামের শিরোনামে চাপলেন। GPA সমান ছাত্ররা এখন কোন ক্রমে থাকবে? Stable sort কথা দেয়: নতুন নিয়মে যারা সমান, তারা sort-এর আগের ক্রমেই থাকবে। অর্থাৎ GPA সমান ছাত্ররা নামের ক্রমেই থাকবে — ব্যবহারকারী ঠিক যা আশা করেন। Java-র List.sort, Collections.sort আর object array-এর Arrays.sort — সবগুলো Javadoc-এ stable হওয়ার নিশ্চয়তা দেয়।

Rafi 5.00 · Mitu 4.83 · Anika 5.00 · Sakib 5.00 · Joy 4.83

Anika 5.00 · Joy 4.83 · Mitu 4.83 · Rafi 5.00 · Sakib 5.00

5.00 দল: Anika → Rafi → Sakib   (এখনকার ক্রমে)
4.83 দল: Joy → Mitu

[Anika, Rafi, Sakib, Joy, Mitu]
প্রতিটি দলের ভেতরে নামের ক্রম অক্ষত

[Sakib, Anika, Rafi, Mitu, Joy]
GPA নিয়ম মানা হয়েছে — তবু ক্রম "এলোমেলো"

ভেতরে কী চলে — TimSort, হালকাভাবে

Java 7 থেকে object-এর sort চালায় TimSort — ২০০২ সালে Tim Peters-এর Python-এর জন্য বানানো অ্যালগরিদম, Java-তে আনেন Joshua Bloch. এর মূল বুদ্ধি: বাস্তবের ডেটা প্রায়ই আংশিক সাজানো থাকে (গতকালের মেধাতালিকায় আজ দুজন নতুন ছাত্র)। TimSort আগে ডেটার মধ্যে আগে থেকেই সাজানো টুকরো (run) খোঁজে, ছোট টুকরোকে insertion sort দিয়ে একটু বড় করে, তারপর merge sort-এর মতো টুকরোগুলো জোড়ে। ফলে:

• সবচেয়ে খারাপ ক্ষেত্রে O(n log n) তুলনা — time complexity-র ভাষায়, ১০ লাখ উপাদানে মোটামুটি ২ কোটির কাছাকাছি তুলনা, ১০ লাখ × ১০ লাখ নয়।
• আগে থেকে সাজানো ডেটায় প্রায় O(n) — একবার দেখেই বুঝে যায়, সাজানোর কিছু নেই।
• Stable, কারণ merge করার সময় সমান হলে সবসময় বাঁ দিকেরটি আগে নেয়।
• দাম: merge-এর জন্য বাড়তি মেমরি (সবচেয়ে খারাপ ক্ষেত্রে n/2 আকারের)। প্রতিটি তুলনা আপনার Comparator ডাকে — তাই Comparator-এর ভেতরে ভারী কাজ (ডেটাবেস ডাকা, String বানানো) রাখবেন না; সেটা কোটিবার চলবে।

৬ · null, উল্টো ক্রম আর বড়-ছোট হাতের অক্ষর

একটি ই-কমার্স সাইটের পণ্যের তালিকা ভাবুন: Product(name, price, rating). নতুন পণ্যের এখনো কোনো রেটিং নেই — rating হলো null (টাইপ Double, primitive নয়)। “রেটিং: বেশি থেকে কম” চাপলে কী হবে?

record Product(String name, int price, Double rating) {}
// Fan 3200 4.5 · Kettle 1450 null · Iron 1450 4.1 · Lamp 900 4.8

shop.sort(Comparator.comparingInt(Product::price));
// [Lamp, Kettle, Iron, Fan]      ← Kettle আর Iron-এর দাম সমান: আগের ক্রম রইল (stable)

shop.sort(Comparator.comparing(Product::rating));
// NullPointerException           ← null-এর compareTo ডাকা যায় না

shop.sort(Comparator.comparing(Product::rating, Comparator.nullsLast(Comparator.reverseOrder())));
// [Lamp, Fan, Iron, Kettle]      ← রেটিং বেশি আগে, রেটিং-হীন পণ্য সবার শেষে

মন্তব্যে লেখা ফলগুলো OpenJDK 21-এ চালিয়ে যাচাই করা। এখানে তিনটি নতুন হাতিয়ার:

শেষেরটি কেন লাগে? String-এর compareTo প্রতিটি অক্ষরের UTF-16 code unit-এর সংখ্যা তুলনা করে, আর সব বড় হাতের ইংরেজি অক্ষরের সংখ্যা (A = 65 … Z = 90) সব ছোট হাতের অক্ষরের (a = 97 …) চেয়ে কম। ফলে সাধারণ sort-এ ["banana", "Cherry", "apple", "Apple"] হয়ে যায় [Apple, Cherry, apple, banana] — Cherry বসে apple-এর আগে! সেই সাজানো list-এ এবার String.CASE_INSENSITIVE_ORDER দিলে [Apple, apple, banana, Cherry]. আর এখানে stability আবার কাজে লাগল: Apple আর apple এই নিয়মে সমান, তাই আগের sort-এর ক্রম (Apple আগে) রইল। মূল ইনপুটে সরাসরি দিলে ইনপুটের ক্রম থাকত — [apple, Apple, banana, Cherry]. সব ফলই যাচাই করা।

leaderboard — একটি নিয়ম উল্টো, আরেকটি সোজা

প্রোগ্রামিং কনটেস্টের র‍্যাঙ্কিং-এর প্রচলিত নিয়ম: বেশি সমস্যা সমাধান করা দল আগে; সমান হলে কম penalty-র দল আগে। একটি অংশ উল্টো, পরেরটি সোজা — reversed-কে ঠিক জায়গায় বসানোর নিখুঁত অনুশীলন:

record Team(String name, int solved, int penalty) {}

board.sort(Comparator.comparingInt(Team::solved).reversed()
                     .thenComparingInt(Team::penalty));

thenComparingInt হলো thenComparing-এর boxing-মুক্ত রূপ। reversed এখানে শুধু solved-এর ঠিক পরে — তখন পর্যন্ত শিকলে ওই একটিই নিয়ম ছিল, তাই উল্টাল শুধু সেটাই।

৭ · বাংলা নাম সাজানো — compareTo, Collator আর Unicode

বর্ণানুক্রম ভাষার নিয়ম, কম্পিউটারের নয়। সুইডিশ ভাষায় ä বসে z-এর পরে, জার্মানে a-এর পাশে। একই তিনটি শব্দ — zebra, ärlig, apa — Java-র Collator দিয়ে সাজিয়ে দেখা ফল: সুইডিশ locale-এ [apa, zebra, ärlig], জার্মানে [apa, ärlig, zebra]. এই ভাষাভিত্তিক নিয়মের আন্তর্জাতিক মানদণ্ড হলো Unicode Collation Algorithm (ভাবনার প্রশ্ন ৩)। Collator হলো java.text-এর class, যা locale অনুযায়ী String তুলনা করে, আর নিজেই একটি Comparator — তাই সরাসরি list.sort(collator) লেখা যায়।

বাংলা নামের ক্ষেত্রে আসল প্রশ্ন দুটি: সাধারণ compareTo কী করে, আর Collator কি ভালো কিছু করে? দুটোই Wandbox-এর OpenJDK 21-এ চালিয়ে যাচাই করা হয়েছে:

• সাধারণ compareTo বাংলাকে Unicode code unit-এর সংখ্যা দিয়ে সাজায়। বাংলা Unicode block-এ স্বরবর্ণ আর ব্যঞ্জনবর্ণ মোটামুটি বর্ণমালার ক্রমেই বসানো, তাই সাধারণ নামে ফল বেশ স্বাভাবিক দেখায়: [অনিক, আরিফ, ইমন, ঋতু, করিম, রহিম, শাওন].
• ইংরেজি আর বাংলা মেশালে সব ইংরেজি আগে — কারণ ইংরেজি অক্ষরের সংখ্যা ছোট। আর compareTo-তে বড় হাতের ইংরেজিও ছোট হাতের আগে: [Anik, Rahim, rafi, আরিফ]; Collator-এ [Anik, rafi, Rahim, আরিফ].
• Java-র নিজের Collator-এ বাংলার জন্য আলাদা কোনো নিয়ম নেই। Collator.getAvailableLocales()-এর তালিকায় bn নেই; Collator.getInstance(Locale.forLanguageTag("bn")) যে নিয়ম দেয়, তা হুবহু root locale-এর সাধারণ নিয়ম। যতগুলো বাংলা নামের তালিকা পরীক্ষা করা হয়েছে (ক্ষ, ঋ-কার, ং, চন্দ্রবিন্দু, য়-সহ), প্রতিটিতে Collator-এর ক্রম সাধারণ compareTo-র ক্রমের সাথে হুবহু মিলেছে।

তাহলে Collator কি বাংলায় অকেজো? না — একটি জায়গায় এটি সত্যিই বাঁচায়: একই দেখতে লেখার আলাদা Unicode রূপ। “বড়” শব্দের ড় দুইভাবে লেখা যায়: একটি আলাদা অক্ষর হিসেবে (U+09DC), অথবা ড + নুক্তা চিহ্ন (U+09A1 U+09BC). পর্দায় দুটি হুবহু এক, কিন্তু কিবোর্ড বা ফোন ভেদে আলাদা রূপ আসে। ধাপে ধাপে দেখুন:

a = "বড়"   → 09AC 09DC
b = "বড়"   → 09AC 09A1 09BC
ড় একটি অক্ষর বনাম ড + নুক্তা (দুটি code unit)

equals    → false
compareTo → 59   (0x09DC − 0x09A1)
new TreeSet<>(List.of(a, b)).size() → 2

coll.getDecomposition() → 0  (NO_DECOMPOSITION)
coll.compare(a, b)      → 1   (এখনো আলাদা)

coll.compare(a, b) → 0
TreeSet(coll)-এ দুটি যোগ করলে size → 1

Normalizer.normalize(a, NFC).equals(Normalizer.normalize(b, NFC)) → true
ডেটা ঢোকার সময়ই এক রূপে আনুন — তখন equals, HashSet, compareTo সব ঠিক

বাংলা অভিধানের পূর্ণ, ভাষাভিত্তিক ক্রম দরকার হলে (যেমন যুক্তবর্ণের অবস্থান নিয়ে অভিধানের নিজস্ব নিয়ম), JDK-র Collator-এর ওপর নির্ভর করা যায় না। সেজন্য সাধারণত ICU4J library ব্যবহার করা হয় — Unicode Consortium-এর ICU প্রজেক্টের Java সংস্করণ, যা UCA আর CLDR-এর ভাষাভিত্তিক নিয়ম মেনে চলে। এটি JDK-র অংশ নয়, Maven দিয়ে যোগ করতে হয় (পর্ব ৪৬)। আপনার তালিকায় কোন ক্রম “সঠিক”, তা আগে ব্যবহারকারী বা প্রতিষ্ঠানের সাথে ঠিক করুন, তারপর আসল ডেটা দিয়ে পরীক্ষা করুন।

৮ · TreeSet, TreeMap, PriorityQueue — Comparator যখন সমতাও ঠিক করে

এ পর্যন্ত Comparator শুধু ক্রম ঠিক করেছে। কিন্তু পর্ব ৩১-এর TreeSet আর TreeMap আর পর্ব ৩২-এর PriorityQueue-এর constructor-এও Comparator দেওয়া যায় — আর সেখানে একটি সূক্ষ্ম পার্থক্য আছে। HashSet সমতা যাচাই করে equals দিয়ে; TreeSet আর TreeMap যাচাই করে compare দিয়ে. compare শূন্য দিলে তাদের চোখে দুটি উপাদান একই — equals যা-ই বলুক।

import java.util.*;

record Student(String name, double gpa) {}

class Main {
    public static void main(String[] args) {
        List<Student> all = List.of(new Student("Rafi", 5.00), new Student("Mitu", 4.83),
                                    new Student("Anika", 5.00), new Student("Joy", 4.83));
        Comparator<Student> byGpa = Comparator.comparingDouble(Student::gpa).reversed();

        Set<Student> bad = new TreeSet<>(byGpa);
        for (Student s : all) System.out.print(bad.add(s) + " ");
        System.out.println("-> size " + bad.size() + " " + bad.stream().map(Student::name).toList());
        System.out.println("contains Nobody(5.00)? " + bad.contains(new Student("Nobody", 5.00)));

        Set<Student> good = new TreeSet<>(byGpa.thenComparing(Student::name));
        good.addAll(all);
        System.out.println("fixed: size " + good.size() + " " + good.stream().map(Student::name).toList());
        System.out.println("HashSet size " + new HashSet<>(all).size());
    }
}

true true false false -> size 2 [Rafi, Mitu]
contains Nobody(5.00)? true
fixed: size 4 [Anika, Rafi, Joy, Mitu]
HashSet size 4

1bad.add(Rafi 5.00)2bad.add(Mitu 4.83)3bad.add(Anika 5.00)4bad.add(Joy 4.83)5bad.contains(Nobody 5.00)

PriorityQueue-এর আচরণ এখানে আলাদা: সে ডুপ্লিকেট বাদ দেয় না, compare শুধু কে আগে বের হবে তা ঠিক করে। new PriorityQueue<>(merit) দিলে poll() প্রথমে Sakib, তারপর Anika দেয় — মেধাতালিকার শীর্ষ থেকে (যাচাই করা)। মনে রাখবেন, PriorityQueue-এর ভেতরের heap পুরোপুরি সাজানো থাকে না; লুপ দিয়ে ছাপলে বা toString-এ ক্রম আশা করবেন না — ক্রম পাওয়া যায় শুধু poll করে করে (পর্ব ৩২)। TreeMap-এ Comparator দিয়ে key-এর ক্রমও বদলানো যায়, যেমন new TreeMap<Double, String>(Comparator.reverseOrder()) — সবচেয়ে বেশি GPA প্রথমে।

যখন নিয়মই ভাঙা — “Comparison method violates its general contract!”

Comparator চুক্তি ভাঙলে (যেমন সমান দুটি উপাদানে compare(a, b) আর compare(b, a) দুটোই ধনাত্মক) TimSort মাঝে মাঝে সেটা টের পায় আর থেমে যায়। একটি পরিচিত ভুল Comparator দিয়ে — (x, y) -> x < y ? -1 : 1, যা সমান হলে কখনো শূন্য দেয় না — অনেক ডুপ্লিকেট-ভরা ২০০০টি সংখ্যা সাজাতে গিয়ে OpenJDK 21-এ পাওয়া গেল:

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
	at java.base/java.util.TimSort.mergeLo(TimSort.java:781)
	at java.base/java.util.TimSort.mergeAt(TimSort.java:518)
	at java.base/java.util.TimSort.mergeCollapse(TimSort.java:448)
	at java.base/java.util.TimSort.sort(TimSort.java:245)
	at java.base/java.util.Arrays.sort(Arrays.java:1308)
	at java.base/java.util.ArrayList.sort(ArrayList.java:1804)
	at Main.main(Main.java:8)

Stack trace-টি নিচ থেকে পড়ুন: আপনার list.sort → ArrayList.sort → Arrays.sort → TimSort-এর merge ধাপ, যেখানে সে লক্ষ করল যে আগের তুলনার উত্তরের সাথে এখনকারটি মেলে না। সবচেয়ে বিপজ্জনক দিক: এই exception নিশ্চিত নয়। ছোট বা কম ডুপ্লিকেটের ডেটায় একই ভাঙা Comparator চুপচাপ একটি ভুল ক্রম দেয়; বড় ডেটা এলে হঠাৎ production-এ crash. কারণগুলো প্রায় সবসময় এর কোনো একটি: বিয়োগ দিয়ে লেখা compare, সমান অবস্থায় শূন্য না দেওয়া, তুলনার মাঝখানে বদলে যাওয়া মান, অথবা Math.random() দিয়ে “এলোমেলো” sort (এলোমেলো করতে Collections.shuffle লিখুন)।

৯ · AI-এর যুগে — সাজানোর নিয়ম যাচাই করা আপনার কাজ

“ছাত্রদের GPA অনুযায়ী সাজাও” — AI এক সেকেন্ডে কোড দেয়, আর ছোট টেস্টে তা প্রায় সবসময় ঠিক দেখায়। সমস্যা হলো, Comparator-এর bug-গুলো লুকিয়ে থাকে সমান মানে, খুব বড় মানে, null-এ আর ভাষায় — ঠিক যে ডেটা টেস্টে কেউ রাখে না। AI-এর লেখা কোডে যে ভুলগুলো বারবার দেখা যায়:

AI-এর লেখা Comparator হাতে পেলে — যাচাইয়ের চেকলিস্ট

• কোথাও a.x - b.x নেই; সংখ্যা তুলনা comparingInt/Double বা Integer/Double.compare দিয়ে
• প্রতিটি reversed() শুধু তার নিজের নিয়মটি উল্টাচ্ছে — শিকলের শেষে কোনো অপ্রত্যাশিত reversed নেই
• সমান মানের অন্তত দুটি উপাদান দিয়ে চালিয়ে দেখেছি; শেষ tie-breaker একটি অনন্য field
• null হতে পারে এমন field-এ nullsFirst/nullsLast আছে
• TreeSet/TreeMap-এ ব্যবহার করলে compare শূন্য হয় শুধু equals true হলে
• বাংলা/মিশ্র নামে আসল ডেটা দিয়ে ক্রম দেখেছি, আর ইনপুট normalize করা হচ্ছে
• Comparator-এর ভেতরে ভারী কাজ (ডেটাবেস, নতুন String বানানো) নেই — এটা কোটিবার চলতে পারে