/*
 * Expense Policy Rule Engine
 * 
 * This is a low-level design problem that was asked in a Rippling interview.
 * 
 * Problem:
 * You are given a list of expenses. Each expense belongs to a trip and has 
 * an amount, type (restaurant, airfare, entertainment, etc.), and other details.
 * The system needs to evaluate these expenses against company policies and 
 * flag any violations with clear reasons.
 * 
 * Rules can be of two types:
 * - Expense-level rules (checked on individual expenses)
 *   e.g., restaurant expenses should not exceed $75, airfare not allowed
 * - Trip-level rules (checked across all expenses of a trip)
 *   e.g., total trip spend should not exceed a limit
 * 
 * New rules should be easy to add later without modifying existing code.
 * 
 * Approach:
 * Instead of using a big if-else or creating a class for every expense type,
 * I modeled the rules as strategies. Each rule is a separate class that 
 * implements either ExpenseRule or TripRule. A RuleRegistry holds which 
 * rules apply where, and a RuleEngine applies them and collects violations.
 * 
 * This keeps the design open for extension (new rules can be added by 
 * writing a new class and registering it) and avoids duplicating logic.
 * 
 * Note: Everything is in one file here so it can run on Ideone. 
 * In a normal project these would be split into separate classes and packages.
 */

import java.util.*;
import java.util.stream.Collectors;

enum ExpenseType {
    RESTAURANT, AIRFARE, ENTERTAINMENT, HOTEL, SUPPLIES
}

// Simple expense entity
class Expense {
    private final String expenseId;
    private final String tripId;
    private final double amountUSD;
    private final ExpenseType type;

    public Expense(String expenseId, String tripId, double amountUSD, ExpenseType type) {
        this.expenseId = expenseId;
        this.tripId = tripId;
        this.amountUSD = amountUSD;
        this.type = type;
    }

    public String getExpenseId() { return expenseId; }
    public String getTripId() { return tripId; }
    public double getAmountUSD() { return amountUSD; }
    public ExpenseType getType() { return type; }

    @Override
    public String toString() {
        return "Expense{" + expenseId + ", trip=" + tripId + ", $" + amountUSD + ", " + type + "}";
    }
}

// Represents a rule violation with a message
class Violation {
    private final String message;

    private Violation(String message) {
        this.message = message;
    }

    // Factory method so we don't expose the constructor
    public static Violation of(String message) {
        return new Violation(message);
    }

    public String getMessage() { return message; }

    @Override
    public String toString() {
        return "Violation: " + message;
    }
}

// Strategy interface for expense-level rules
interface ExpenseRule {
    Optional<Violation> check(Expense expense);
}

// Strategy interface for trip-level rules
interface TripRule {
    Optional<Violation> check(List<Expense> expenses);
}

// Rule that disallows a specific expense type entirely
class DisallowRule implements ExpenseRule {
    private final ExpenseType disallowedType;

    public DisallowRule(ExpenseType disallowedType) {
        this.disallowedType = disallowedType;
    }

    @Override
    public Optional<Violation> check(Expense expense) {
        if (expense.getType() == disallowedType) {
            return Optional.of(Violation.of(disallowedType + " expenses are not allowed"));
        }
        return Optional.empty();
    }
}

// Rule that checks if an expense exceeds a maximum amount
class MaxAmountRule implements ExpenseRule {
    private final double maxAmount;

    public MaxAmountRule(double maxAmount) {
        this.maxAmount = maxAmount;
    }

    @Override
    public Optional<Violation> check(Expense expense) {
        if (expense.getAmountUSD() > maxAmount) {
            return Optional.of(Violation.of(
                "Amount $" + expense.getAmountUSD() + " exceeds max allowed $" + maxAmount));
        }
        return Optional.empty();
    }
}

// Trip-level rule that checks total spend of a trip
class TripTotalMaxRule implements TripRule {
    private final double maxAmount;

    public TripTotalMaxRule(double maxAmount) {
        this.maxAmount = maxAmount;
    }

    @Override
    public Optional<Violation> check(List<Expense> expenses) {
        double total = expenses.stream().mapToDouble(Expense::getAmountUSD).sum();
        if (total > maxAmount) {
            return Optional.of(Violation.of(
                "Trip total $" + total + " exceeds max allowed $" + maxAmount));
        }
        return Optional.empty();
    }
}

// Holds all the rules. In a real system this would be loaded from config/DB.
class RuleRegistry {
    private final Map<ExpenseType, List<ExpenseRule>> typeRules = new HashMap<>();
    private final List<ExpenseRule> globalExpenseRules = new ArrayList<>();
    private final List<TripRule> tripRules = new ArrayList<>();

    public void addTypeRule(ExpenseType type, ExpenseRule rule) {
        typeRules.computeIfAbsent(type, k -> new ArrayList<>()).add(rule);
    }

    public void addGlobalExpenseRule(ExpenseRule rule) {
        globalExpenseRules.add(rule);
    }

    public void addTripRule(TripRule rule) {
        tripRules.add(rule);
    }

    // Returns both type-specific and global rules for an expense type
    public List<ExpenseRule> getRulesFor(ExpenseType type) {
        List<ExpenseRule> rules = new ArrayList<>(globalExpenseRules);
        rules.addAll(typeRules.getOrDefault(type, Collections.emptyList()));
        return rules;
    }

    public List<TripRule> getTripRules() {
        return tripRules;
    }
}

interface RuleEngine {
    Map<String, List<Violation>> evaluate(List<Expense> expenses, RuleRegistry registry);
}

class SimpleRuleEngine implements RuleEngine {
    @Override
    public Map<String, List<Violation>> evaluate(List<Expense> expenses, RuleRegistry registry) {
        Map<String, List<Violation>> result = new LinkedHashMap<>();

        // Apply expense-level rules
        for (Expense expense : expenses) {
            List<Violation> violations = new ArrayList<>();
            for (ExpenseRule rule : registry.getRulesFor(expense.getType())) {
                rule.check(expense).ifPresent(violations::add);
            }
            if (!violations.isEmpty()) {
                result.put(expense.getExpenseId(), violations);
            }
        }

        // Apply trip-level rules (group expenses by trip first)
        Map<String, List<Expense>> byTrip = expenses.stream()
            .collect(Collectors.groupingBy(Expense::getTripId));

        for (var entry : byTrip.entrySet()) {
            String tripId = entry.getKey();
            List<Expense> tripExpenses = entry.getValue();
            List<Violation> tripViolations = new ArrayList<>();

            for (TripRule rule : registry.getTripRules()) {
                rule.check(tripExpenses).ifPresent(tripViolations::add);
            }

            if (!tripViolations.isEmpty()) {
                result.computeIfAbsent("TRIP-" + tripId, k -> new ArrayList<>()).addAll(tripViolations);
            }
        }

        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        // Sample expenses for demonstration
        List<Expense> expenses = Arrays.asList(
            new Expense("E1", "T1", 80, ExpenseType.RESTAURANT),
            new Expense("E2", "T1", 120, ExpenseType.AIRFARE),
            new Expense("E3", "T1", 40, ExpenseType.ENTERTAINMENT),
            new Expense("E4", "T1", 200, ExpenseType.HOTEL)
        );

        // Register the rules
        RuleRegistry registry = new RuleRegistry();
        registry.addTypeRule(ExpenseType.RESTAURANT, new MaxAmountRule(75));
        registry.addTypeRule(ExpenseType.AIRFARE, new DisallowRule(ExpenseType.AIRFARE));
        registry.addTypeRule(ExpenseType.ENTERTAINMENT, new DisallowRule(ExpenseType.ENTERTAINMENT));
        registry.addGlobalExpenseRule(new MaxAmountRule(250));
        registry.addTripRule(new TripTotalMaxRule(300));

        // Evaluate
        RuleEngine engine = new SimpleRuleEngine();
        Map<String, List<Violation>> violations = engine.evaluate(expenses, registry);

        System.out.println("=== Violations ===");
        if (violations.isEmpty()) {
            System.out.println("No violations found.");
        } else {
            violations.forEach((id, vList) -> {
                System.out.println(id + ":");
                vList.forEach(v -> System.out.println("  - " + v));
            });
        }
    }
}