ldes_region.h

Go to the documentation of this file.

/*
 * Copyright (c) 2012-2026, QORE Lab, Imperial College London
 * All rights reserved.
 */
#ifndef LINE_SOLVERS_LDES_LDES_REGION_H
#define LINE_SOLVERS_LDES_LDES_REGION_H
 
/**
 * @file
 * @ingroup line_solvers
 * Finite capacity regions for the native LDES engine.
 *
 * A region caps the jobs held ACROSS a set of stations, which no per-station
 * capacity can express: three stations each able to hold 5 jobs but at most 6
 * between them is a region, not three caps. Four constraints may apply at once
 * and an arrival must satisfy all of them:
 *
 *  - the GLOBAL job cap of the region;
 *  - the PER-CLASS job cap;
 *  - the MEMORY budget, a weighted count where each class carries its own
 *    footprint (JMT's classSize, so a region can hold many small jobs or few
 *    large ones);
 *  - the LINEAR constraints A n <= b, which subsume the other three and are
 *    what a mix constraint like "2 n_1 + n_2 <= 10" needs.
 *
 * A REJECTED ARRIVAL EITHER DROPS OR WAITS, per class, and the two are
 * different populations. A DROPped job is gone. A WAITQ job is parked OUTSIDE
 * every station's own buffer -- it has not entered the region, so it is not in
 * the region's queue length, but it IS still in the system and is charged to
 * the station it was trying to enter. Conflating the two makes a WAITQ region
 * lose jobs, which on a closed model changes the population.
 *
 * MEMBERSHIP IS INDEPENDENT OF THE CAPS. `members` says which stations the
 * region spans; a member may have every cap unbounded and still constrain
 * nothing while participating in the linear constraints.
 */
 
#include <cmath>
#include <cstddef>
#include <limits>
#include <string>
#include <vector>
 
#include "line/lang/lang_types.h"
 
namespace line {
namespace ldes {
namespace engine {
 
/** One finite capacity region, resolved to what the event loop needs. */
struct Region {
    std::string name;
    std::vector<bool> members;              ///< per station
    double global_cap = -1.0;               ///< -1 = unbounded
    std::vector<double> class_cap;          ///< per class, -1 = unbounded
    double max_mem = -1.0;                  ///< -1 = unbounded
    std::vector<double> class_size;         ///< memory footprint per class
    std::vector<double> class_weight;       ///< occupancy weight per class
    std::vector<lang::DropStrategy> rule;   ///< per class: DROP or WAITQ
    std::vector<std::vector<double>> lincon_A;
    std::vector<double> lincon_b;
 
    // ---- live state --------------------------------------------------------
    std::vector<double> jobs;      ///< per class, inside the region
    double mem = 0.0;              ///< weighted memory in use
    std::vector<double> blocked;   ///< per class, parked outside by WAITQ
    std::vector<double> dropped;   ///< per class, lost
 
    // ---- time-weighted statistics -----------------------------------------
    std::vector<double> tot_jobs, tot_weight, tot_mem;
    double last_update = 0.0;
    std::vector<double> completed, resp_sum, resp_cnt;
    std::vector<double> entry_time;  ///< unused placeholder for per-job entry
 
    /**
     * True when one more job of `r` would violate ANY of the region's caps.
     *
     * The memory rule is JMT's: admit iff used + incoming <= max, with an
     * epsilon because a footprint may be fractional and the running total
     * accumulates rounding.
     */
    bool would_exceed(std::size_t r) const {
        double total = 0.0;
        for (double n : jobs) total += n;
        if (global_cap >= 0.0 && total + 1.0 > global_cap) return true;
        if (r < class_cap.size() && class_cap[r] >= 0.0 && jobs[r] + 1.0 > class_cap[r])
            return true;
        if (max_mem >= 0.0) {
            const double incoming = (r < class_size.size()) ? class_size[r] : 1.0;
            if (mem + incoming > max_mem + 1e-9) return true;
        }
        for (std::size_t c = 0; c < lincon_A.size(); ++c) {
            double lhs = (r < lincon_A[c].size()) ? lincon_A[c][r] : 0.0;
            for (std::size_t k = 0; k < jobs.size() && k < lincon_A[c].size(); ++k)
                lhs += lincon_A[c][k] * jobs[k];
            if (lhs > lincon_b[c]) return true;
        }
        return false;
    }
 
    void enter(std::size_t r) {
        jobs[r] += 1.0;
        mem += (r < class_size.size()) ? class_size[r] : 1.0;
    }
    void leave(std::size_t r) {
        jobs[r] -= 1.0;
        mem -= (r < class_size.size()) ? class_size[r] : 1.0;
    }
 
    /**
     * Advance the region's time integrals to `now`. Call BEFORE any change to
     * `jobs`, exactly as the station integrals require.
     *
     * The JOB count and the WEIGHTED occupancy are separate series because a
     * region may cap either: reporting only the raw count hides a region that
     * is memory-bound rather than job-bound.
     */
    void update(double now) {
        const double dt = now - last_update;
        last_update = now;
        if (!(dt > 0.0)) return;
        for (std::size_t r = 0; r < jobs.size(); ++r) {
            tot_jobs[r] += jobs[r] * dt;
            const double w = (r < class_weight.size()) ? class_weight[r] : 1.0;
            tot_weight[r] += jobs[r] * w * dt;
            const double sz = (r < class_size.size()) ? class_size[r] : 1.0;
            tot_mem[r] += jobs[r] * sz * dt;
        }
    }
 
    bool drops(std::size_t r) const {
        return r >= rule.size() || rule[r] != lang::DropStrategy::WAITQ;
    }
};
 
}  // namespace engine
}  // namespace ldes
}  // namespace line
 
#endif  // LINE_SOLVERS_LDES_LDES_REGION_H