File deduplication

from collections import defaultdict


def group(paths, key):
    """Buckets paths by key(path); keeps only buckets with two or more."""
    buckets = defaultdict(list)
    for p in paths:
        buckets[key(p)].append(p)
    return [b for b in buckets.values() if len(b) >= 2]


def find_duplicates(files, prefix_len):
    """files: path -> contents. Returns (duplicate groups, bytes read)."""
    read = 0

    def prefix(p):                       # reading the start of a file costs bytes
        nonlocal read
        read += min(prefix_len, len(files[p]))
        return files[p][:prefix_len]

    def content(p):                      # the rest of it, only for real candidates
        nonlocal read
        read += max(0, len(files[p]) - prefix_len)
        return files[p]                  # on disk: a SHA-256 of the file, read in chunks

    groups = []
    for by_size in group(files, lambda p: len(files[p])):   # free: no file is opened
        for by_prefix in group(by_size, prefix):
            for by_content in group(by_prefix, content):
                groups.append(sorted(by_content))
    return sorted(groups), read

#include <algorithm>
#include <map>
#include <string>
#include <utility>
#include <vector>
using namespace std;

// Buckets paths by key(path); keeps only buckets with two or more.
template <class Key>
vector<vector<string>> group(const vector<string>& paths, Key key) {
    map<decltype(key(paths[0])), vector<string>> buckets;
    for (auto& p : paths) buckets[key(p)].push_back(p);
    vector<vector<string>> out;
    for (auto& [k, b] : buckets)
        if (b.size() >= 2) out.push_back(b);
    return out;
}

// files: path -> contents. Returns {duplicate groups, bytes read}.
pair<vector<vector<string>>, long long> find_duplicates(const map<string, string>& files, size_t prefix_len) {
    long long read = 0;
    auto size = [&](const string& p) { return files.at(p).size(); };   // free: no file is opened
    auto prefix = [&](const string& p) {                                 // reading the start costs bytes
        const string& data = files.at(p);
        read += min(prefix_len, data.size());
        return data.substr(0, prefix_len);
    };
    auto content = [&](const string& p) {                                // the rest, only for real candidates
        const string& data = files.at(p);
        read += data.size() > prefix_len ? data.size() - prefix_len : 0;
        return data;                    // on disk: a SHA-256 of the file, read in chunks
    };

    vector<string> paths;
    for (auto& [p, data] : files) paths.push_back(p);
    vector<vector<string>> groups;
    if (paths.empty()) return {groups, read};
    for (auto& by_size : group(paths, size))
        for (auto& by_prefix : group(by_size, prefix))
            for (auto by_content : group(by_prefix, content)) {
                sort(by_content.begin(), by_content.end());
                groups.push_back(by_content);
            }
    sort(groups.begin(), groups.end());
    return {groups, read};
}

import java.util.*;
import java.util.function.Function;

class Dedup {
    long read = 0;   // bytes read so far

    // Buckets paths by key(path); keeps only buckets with two or more.
    static List<List<String>> group(List<String> paths, Function<String, Object> key) {
        Map<Object, List<String>> buckets = new LinkedHashMap<>();
        for (String p : paths) buckets.computeIfAbsent(key.apply(p), k -> new ArrayList<>()).add(p);
        List<List<String>> out = new ArrayList<>();
        for (List<String> b : buckets.values()) if (b.size() >= 2) out.add(b);
        return out;
    }

    // files: path -> contents. Returns the duplicate groups; `read` counts the bytes read.
    List<List<String>> findDuplicates(Map<String, String> files, int prefixLen) {
        Function<String, Object> size = p -> files.get(p).length();     // free: no file is opened
        Function<String, Object> prefix = p -> {                         // reading the start costs bytes
            String data = files.get(p);
            read += Math.min(prefixLen, data.length());
            return data.substring(0, Math.min(prefixLen, data.length()));
        };
        Function<String, Object> content = p -> {                        // the rest, only for real candidates
            String data = files.get(p);
            read += Math.max(0, data.length() - prefixLen);
            return data;                // on disk: a SHA-256 of the file, read in chunks
        };

        List<List<String>> groups = new ArrayList<>();
        for (List<String> bySize : group(new ArrayList<>(files.keySet()), size))
            for (List<String> byPrefix : group(bySize, prefix))
                for (List<String> byContent : group(byPrefix, content)) {
                    Collections.sort(byContent);
                    groups.add(byContent);
                }
        groups.sort((a, b) -> {
            for (int i = 0; i < Math.min(a.size(), b.size()); i++) {
                int c = a.get(i).compareTo(b.get(i));
                if (c != 0) return c;
            }
            return Integer.compare(a.size(), b.size());
        });
        return groups;
    }
}