graph TB
    A[Phase 1: Configuration] --> B[Time Slots + Teachers]
    B --> C[Phase 2: Validation]
    C --> D{All Subjects<br/>Schedulable?}
    D -->|No| E[Conflict Resolution]
    D -->|Yes| F[Phase 3: Period Creation]
 
    E --> G[Reorder Blocking Classes]
    E --> H[Suggest Alternative Teachers]
    E --> I[Show Detailed Diagnostics]
 
    G --> J[Retry Validation]
    J --> D
 
    F --> K[Atomic DB Transaction]
    K --> L[Complete Schedule]
 
    I --> M[User Manual Resolution]
    M --> A
 

function cspScheduling(classes: Class[]): Schedule {
  for (const classToSchedule of classes) {
    if (!canSchedule(classToSchedule)) {
      // Backtrack and reorder previous classes
      const conflictingClass = findBlockingClass(classToSchedule);
      reorderAndReschedule(conflictingClass);
      retry(classToSchedule);
    }
  }
}

function greedyScheduling(classes: Class[]): Schedule {
  const conflictGraph = buildConflictGraph(classes);
  const sortedClasses = topologicalSort(conflictGraph); // Most constrained first
 
  for (const cls of sortedClasses) {
    while (!canSchedule(cls)) {
      const bestReordering = findMinimalConflictReordering(conflictGraph);
      applyReordering(bestReordering);
    }
  }
}

function annealingScheduling(classes: Class[]): Schedule {
  let current = greedyInitialSchedule(classes);
  let temperature = 1000;
 
  while (temperature > 0.1) {
    const neighbor = randomReordering(current);
    const delta = evaluate(neighbor) - evaluate(current);
 
    // Accept better OR probabilistically accept worse (to escape local minima)
    if (delta > 0 || Math.random() < Math.exp(delta / temperature)) {
      current = neighbor;
    }
 
    temperature *= 0.95; // Cool down
  }
}

function ilpScheduling(classes: Class[]): Schedule {
  const objective = minimizeTeacherConflicts;
  const constraints = [
    eachSubjectScheduledOnce,
    teacherNotDoubleBooked,
    respectDisplayOrder,
    maxPeriodsPerDay,
  ];
 
  return solver.solve(objective, constraints); // Google OR-Tools
}

function hybridScheduling(classes: Class[]): Schedule {
  // Phase 1: Greedy (handles 90% of cases quickly)
  const greedyResult = greedyScheduling(classes);
 
  if (greedyResult.success) {
    return greedyResult.schedule; // ✅ Fast path
  }
 
  // Phase 2: CSP Backtracking (handles complex conflicts)
  console.log("⚙️ Greedy failed, using CSP backtracking...");
  return cspBacktrackingSchedule(
    greedyResult.partialSchedule,
    greedyResult.failedClasses
  );
}

flowchart TD
    A[User: Schedule Class Semester] --> B[Validate All Prerequisites]
    B --> C{All Subjects<br/>Configured?}
    C -->|No| D[Error: Configure subjects first]
    C -->|Yes| E[START: Atomic Transaction]
 
    E --> F[Phase 1: Simulation]
    F --> G[For each subject in order]
    G --> H[Simulate Period Creation]
    H --> I{Teacher<br/>Available?}
 
    I -->|Yes| J[Mark simulation success]
    I -->|No| K[Conflict Detected!]
 
    K --> L{Can Reorder<br/>Blocking Class?}
    L -->|Yes| M[Reorder Algorithm]
    L -->|No| N{Alternative<br/>Teacher Available?}
 
    M --> O[Reschedule Blocking Class]
    O --> P[Retry Current Subject]
    P --> I
 
    N -->|Yes| Q[Suggest Teacher Change]
    N -->|No| R[FAIL: Impossible to Schedule]
 
    J --> S{More<br/>Subjects?}
    S -->|Yes| G
    S -->|No| T[All Subjects Validated ✓]
 
    T --> U[Phase 2: Period Creation]
    U --> V[Create ALL Periods in DB]
    V --> W[COMMIT Transaction]
    W --> X[Success: Complete Schedule]
 
    R --> Y[ROLLBACK Transaction]
    Y --> Z[Show Conflict Diagnostics]
    Z --> AA[User Action Required]
 
    Q --> AA
    D --> AA
 
    AA --> AB{User<br/>Choice}
    AB -->|Change Teacher| AC[Update Configuration]
    AB -->|Reorder Subjects| AD[Automatic Reorder]
    AB -->|Cancel| AE[Exit]
 
    AC --> A
    AD --> A
 
    style E fill:#e3f2fd
    style K fill:#fff3e0
    style M fill:#fce4ec
    style U fill:#e8f5e8
    style W fill:#f3e5f5
    style Y fill:#ffebee

// Try to schedule Math for Class 10B at Monday 07:15
const conflict = checkTeacherAvailability(
  teacherId: "Nguyễn Văn A",
  date: "2025-01-06",
  time: "07:15"
);
 
// Result:
conflict = {
  isAvailable: false,
  blockingClass: {
    classId: 10A,
    className: "Lớp 10A",
    subject: "Math",
    date: "2025-01-06",
    time: "07:15"
  }
}

// Current order: Math(1) → Physics(2) → Programming(3)
// New order:     Physics(1) → Math(2) → Programming(3)
 
reorderClass({
  classId: 10A,
  newSubjectOrder: [
    { subjectId: 2, newOrder: 1 }, // Physics moves to 1
    { subjectId: 1, newOrder: 2 }, // Math moves to 2
    { subjectId: 3, newOrder: 3 }  // Programming stays
  ]
});
 
// Result: Math moved to Tuesday 07:15
// Monday 07:15 now FREE for Class 10B!

// Find alternative qualified teachers
const alternatives = getQualifiedTeachers({
  subjectId: 1, // Math
  available: true,
  date: "2025-01-06",
  time: "07:15",
});
 
// Result: [Teacher Phạm Thị D, Teacher Hoàng Văn E]
// Suggest to user: "Use Teacher Phạm Thị D instead?"

sequenceDiagram
    participant UI as User Interface
    participant API as Scheduling API
    participant V as Validation Engine
    participant R as Reorder Engine
    participant DB as Database
 
    UI->>API: scheduleClassSemester(classId, semesterId)
    API->>DB: BEGIN TRANSACTION
 
    API->>V: Validate ALL subjects
 
    loop For each subject
        V->>V: Simulate period creation
        V->>R: Check teacher availability
 
        alt Teacher Available
            V->>V: Mark subject valid ✓
        else Conflict Detected
            R->>R: Try reorder blocking class
            alt Reorder Success
                R->>V: Conflict resolved ✓
            else Reorder Failed
                R->>R: Find alternative teachers
                alt Alternatives Found
                    R-->>UI: Suggest teacher change
                    UI-->>API: User decision
                else No Solution
                    R-->>API: FAIL with diagnostics
                    API->>DB: ROLLBACK TRANSACTION
                    API-->>UI: Show conflict details
                end
            end
        end
    end
 
    alt All Subjects Valid
        API->>DB: CREATE all periods
        API->>DB: COMMIT TRANSACTION
        API-->>UI: Success ✓
    else Validation Failed
        API->>DB: ROLLBACK TRANSACTION
        API-->>UI: Detailed error
    end

const validationResults = await validateAllSubjects({
  classId,
  semesterId,
  subjects,
});
 
// In-memory simulation - NO database writes
// Returns: {
//   success: boolean,
//   validSubjects: Subject[],
//   conflicts: Conflict[],
//   suggestions: Resolution[]
// }

if (validationResults.success) {
  await ctx.db.transaction(async (trx) => {
    // Create ALL periods for ALL subjects
    for (const subject of subjects) {
      const periods = generatePeriodsForSubject(subject);
      await trx.insert(periods).values(periods);
    }
    // Commits only if no errors
  });
}

function findOptimalReordering(
  blockingClass: Class,
  conflictingSubject: Subject,
  targetTimeSlot: TimeSlot
): SubjectOrder[] {
  const currentOrder = blockingClass.subjectOrder;
 
  // Try all permutations of subjects (limited depth search)
  const permutations = generateSmartPermutations(
    currentOrder,
    conflictingSubject
  );
 
  for (const newOrder of permutations) {
    const simulation = simulateScheduleWithOrder(blockingClass, newOrder);
 
    if (simulation.freesTargetTimeSlot && simulation.noNewConflicts) {
      return newOrder; // ✅ Found valid reordering
    }
  }
 
  return null; // ❌ No valid reordering found
}

function generateSmartPermutations(
  currentOrder: Subject[],
  conflictingSubject: Subject
): SubjectOrder[][] {
  const index = currentOrder.indexOf(conflictingSubject);
  const permutations = [];
 
  // Strategy 1: Swap with next subject
  if (index < currentOrder.length - 1) {
    permutations.push(swap(currentOrder, index, index + 1));
  }
 
  // Strategy 2: Move to end
  permutations.push(moveToEnd(currentOrder, index));
 
  // Strategy 3: Move to position after lunch break
  permutations.push(moveToAfternoon(currentOrder, index));
 
  // Sort by predicted conflict reduction
  return permutations.sort(
    (a, b) => estimateConflicts(a) - estimateConflicts(b)
  );
}

// Step 1: Identify subject to move (Math)
const subjectToMove = "Math";
 
// Step 2: Generate candidate reorderings
const candidates = [
  ["Physics", "Math", "Programming"], // Swap with next
  ["Physics", "Programming", "Math"], // Move to end
  ["Programming", "Physics", "Math"], // Full **reorder**
];
 
// Step 3: Simulate each candidate
for (const newOrder of candidates) {
  const result = simulateReorder(Class10A, newOrder);
 
  if (result.success && result.freesMonday0715) {
    applyReordering(Class10A, newOrder);
    return; // ✅ Conflict resolved
  }
}

interface ConflictDiagnostics {
  message: string;
  conflicts: Array<{
    subject: string;
    teacher: string;
    timeSlot: string;
    blockingClass: string;
    blockingSubject: string;
  }>;
  resolutions: Array<{
    type: "CHANGE_TEACHER" | "REORDER_SUBJECTS";
    description: string;
    actionLabel: string;
    onClick: () => void;
  }>;
}

const handleReorder = async (blockingClass: Class) => {
  const confirmed = await showConfirmation({
    title: "Reorder Class Schedule?",
    message: `This will reschedule ${blockingClass.name} to resolve conflicts. Continue?`,
    confirmLabel: "Reorder",
    cancelLabel: "Cancel",
  });
 
  if (confirmed) {
    await api.scheduling.reorderClassSubjects.mutate({
      classId: blockingClass.id,
      semesterId,
      autoResolveConflicts: true,
    });
 
    // Retry current class scheduling
    retryScheduling();
  }
};

const handleChangeTeacher = async (
  subject: Subject,
  alternativeTeacher: Teacher
) => {
  await api.scheduling.updateSubjectConfig.mutate({
    classId: currentClass.id,
    semesterId,
    subjectId: subject.id,
    assignedTeacherId: alternativeTeacher.id,
  });
 
  // Retry scheduling with new teacher
  retryScheduling();
};

api.scheduling.scheduleClassSemester.useMutation({
  input: {
    classId: number;
    semesterId: number;
    autoResolveConflicts: boolean; // Enable automatic reordering
  },
  output: {
    success: boolean;
    periodsCreated?: number;
    conflicts?: ConflictDiagnostics;
  }
});

api.scheduling.validateClassSchedule.useQuery({
  input: {
    classId: number;
    semesterId: number;
  },
  output: {
    isValid: boolean;
    conflicts: Conflict[];
    suggestions: Resolution[];
  }
});

api.scheduling.reorderClassSubjects.useMutation({
  input: {
    classId: number;
    semesterId: number;
    autoResolveConflicts: boolean;
  },
  output: {
    success: boolean;
    newOrder: SubjectOrder[];
    periodsRescheduled: number;
  }
});

ALTER TABLE class_subject_progress
ADD COLUMN canReorder BOOLEAN NOT NULL DEFAULT true,
ADD COLUMN reorderPriority INTEGER, -- Lower = less likely to be reordered
ADD COLUMN lastReordered TIMESTAMP;

CREATE TABLE scheduling_conflicts (
  id SERIAL PRIMARY KEY,
  classId INTEGER NOT NULL,
  semesterId INTEGER NOT NULL,
  subjectId INTEGER NOT NULL,
  conflictType VARCHAR(50) NOT NULL, -- 'TEACHER_UNAVAILABLE', 'TIME_CONFLICT'
  blockingClassId INTEGER,
  blockingSubjectId INTEGER,
  resolutionType VARCHAR(50), -- 'REORDER', 'CHANGE_TEACHER', 'MANUAL'
  resolvedAt TIMESTAMP,
  createdAt TIMESTAMP DEFAULT NOW()
);

CREATE TABLE subject_reorder_history (
  id SERIAL PRIMARY KEY,
  classId INTEGER NOT NULL,
  semesterId INTEGER NOT NULL,
  oldOrder JSONB NOT NULL, -- [{"subjectId": 1, "order": 1}, ...]
  newOrder JSONB NOT NULL,
  reason TEXT,
  triggeredBy INTEGER, -- User ID or NULL for automatic
  createdAt TIMESTAMP DEFAULT NOW()
);