; In the Job Sequencing with Deadlines problem, a state is a partial
;   schedule, and consists of
;     a schedule (a list of jobs), and
;     a list of remaining jobs, each represented by a pair (ID DEADLINE)
;       which is a job number followed by a deadline

(define (schedule state) (car state))
(define (jobs state) (cadr state))
(define (id job) (car job))
(define (deadline job) (cdr job))
(define (build-state s d) (list s d))

(define start1 '(() ((1 . 4) (2 . 5) (3 . 1) (4 . 4) (5 . 2))))
(define start2 '(() ((1 . 4) (2 . 5) (3 . 1) (4 . 4) (5 . 2) (6 . 4))))
(define start3 '(() ((1 . 3) (2 . 5) (3 . 1) (4 . 3) (5 . 2))))
(define start4 '(() ((1 . 4) (2 . 5) (3 . 1) (4 . 6) (5 . 2) (6 . 4))))
(define start5 '(() ((1 . 3) (2 . 5) (3 . 3) (4 . 6) (5 . 3) (6 . 6))))
(define start6 '(() ((1 . 3) (2 . 5) (3 . 3) (4 . 5) (5 . 3) (6 . 5))))


; Since only feasible states are assumed to be generated,
;   the GOAL? predicate need only check that all jobs have been scheduled

(define (goal? state) (null? (jobs state)))


; Long partial schedules get priority for extension over short ones

(define (estimator state) (length (deadline (jobs state))))


; To find successors,
;   consider all possible jobs whose deadlines are later than the current
;   partial schedule length, as continuations of the current partial schedule
; The MAP function adds each remaining job to the beginning of the schedule
; The FILTER function enforces the deadline constraint, and puts each new
;   job at the end of the schedule.
; The REMOVE function removes the first occurrence of its first argument
;   from the list represented by its second argument

(define (successors state)
  (define (filter states)
    (cond ((null? states) states)
          (else
            (let ((current-state (car states)))
              (let ((new-job (car (schedule current-state))))
                (cond ((>= (deadline new-job)
                           (length (schedule current-state)))
                       (cons (build-state
                               (append (cdr (schedule current-state))
                                       (list new-job))
                               (jobs current-state))
                             (filter (cdr states))))
                      (else (filter (cdr states)))))))))
  (define (remove x s)
    (cond ((null? s) s)
          ((equal? x (car s)) (cdr s))
          (else (cons (car s) (remove x (cdr s))))))
  (filter (map (lambda (job)
                 (build-state (cons job (schedule state))
                              (remove job (jobs state))))
               (jobs state))))