import java.util.*;

/**
 * The problem: given a collection of email messages, write an algorithm that computes the minimum number of email
 * batches such that no single batch contains a message addressed to the same recipient more than once.
 * <p/>
 * Example input: {Email1->a@example.com, Email2->b@example.com, Email3->a@example.com}
 * <p/>
 * Expected output: {{Email1->a@example.com, Email2->b@example.com}, {Email3->a@example.com}}
 * <p/>
 * The solution: use a map to count the number of times a "to address" occurs in the input.  Use the count as an index
 * into a list of resulting email batches.
 *
 * @author Chip Killmar
 */
public class EmailBatches {
    private static final Random random = new Random();

    private static final String fromAddress = "test@example.com";
    private static final List<String> randomToAddresses = Arrays.asList("a@example.com", "b@example.com", "c@example.com", "d@example.com");

    public static void main(String[] args) {
        // Create some test data.
        List<Email> emails = Arrays.asList(createRandomEmails(4));

        System.out.println("Input=" + emails);

        System.out.println("Output=" + createEmailBatches(emails));
    }

    private static Email[] createRandomEmails(int numberOfEmails) {
        Email[] emails = new Email[numberOfEmails];
        for (int i = 0; i < emails.length; ++i) {
            emails[i] = new Email(randomToAddresses.get(random.nextInt(4)), fromAddress, "Message-" + i);
        }
        return emails;
    }

    /**
     * An O(n) algorithm that uses a map to keep track of how many times an email to-address has been seen.  This count
     * is then used as an index into a list of email batches.
     *
     * @param emails An input collection of emails.
     * @return The minimum number of email batches such that no single batch contains a message addressed to the same
     *         recipient (to-address) more than once.
     */
    private static Collection<Collection<Email>> createEmailBatches(Collection<Email> emails) {
        List<Collection<Email>> emailBatches = new ArrayList<Collection<Email>>();

        Map<String, Integer> toAddressCountMap = new HashMap<String, Integer>();

        for (Email email : emails) {
            // Use a map to keep track of how many times we've seen a to-address.
            String toAddress = email.getToAddress();
            int toAddressCount = 1;
            if (toAddressCountMap.containsKey(toAddress)) {
                toAddressCount = toAddressCountMap.get(toAddress) + 1;
            }
            toAddressCountMap.put(toAddress, toAddressCount);

            Collection<Email> emailBatch;
            if (emailBatches.size() < toAddressCount) {
                // We need a new batch to put this email into.
                emailBatch = new ArrayList<Email>();
                emailBatches.add(emailBatch);
            } else {
                // Use the existing batch and add this email to the end of it.
                emailBatch = emailBatches.get(toAddressCount - 1);
            }
            emailBatch.add(email);
        }

        return emailBatches;
    }

    private static class Email {
        private String toAddress;
        private String fromAddress;
        private String message;

        public Email(String toAddress, String fromAddress, String message) {
            this.fromAddress = fromAddress;
            this.message = message;
            this.toAddress = toAddress;
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder();
            sb.append("Email");
            sb.append("{fromAddress='").append(fromAddress).append('\'');
            sb.append(", toAddress='").append(toAddress).append('\'');
            sb.append(", message='").append(message).append('\'');
            sb.append('}');
            return sb.toString();
        }

        public String getFromAddress() {
            return fromAddress;
        }

        public void setFromAddress(String fromAddress) {
            this.fromAddress = fromAddress;
        }

        public String getMessage() {
            return message;
        }

        public void setMessage(String message) {
            this.message = message;
        }

        public String getToAddress() {
            return toAddress;
        }

        public void setToAddress(String toAddress) {
            this.toAddress = toAddress;
        }
    }
}