read_re.cpp

#include <cmath>
#include <algorithm>
#include "read_re.h"
#include <random>
#include <chrono>
#include <string>
#include <climits>
#include <utility>

void Reader::read_request()
{
    int n_read, request_id, object_id;
    std::cin >> n_read;
    for (int i = 1; i <= n_read; i++) {
        scanf("%d%d", &request_id, &object_id); // request_id starts from 1, increments by 1
        // Assign to data_.request
        Request& request = data_.request.at(request_id);
        Object& object = data_.object.at(object_id);
        request.request_id = request_id;
        request.object_id = object_id;
        request.prev_id = data_.object.at(object_id).last_request_point;
        request.is_done = false;
        request.timestamp = data_.timestamp;
        object.last_request_point = request_id;
        object.request_ids.emplace_back(request_id);
        object.is_requested = true;
        data_.request_num++;
    }
}

// int Reader::pass1_or_read0(int distance, int current_phase){
//     int tokens_reading = 0;
//     for(int i = 0 ;i < distance ; i++){
//         tokens_reading += get_read_cost(i + current_phase);
//     } 
//     if(distance + 64 > tokens_reading){
//         return 0;
//     }
//     else{
//         return 1;
//     }
// }

int Reader::get_nearest_object(int disk_id ,int point_index ) {
    int disk_point = data_.disk_point[disk_id][point_index]; // Get current disk head position
    std::vector<int>& disk = data_.disk.at(disk_id); // Get current disk
    // Find nearest requested object starting from current head
    int total_advance = 0;
    do {
        // Check if there is an object at current head position
        if (disk[disk_point] != 0) {
            int object_id = disk[disk_point]; // Get current object ID
            Object& object = data_.object.at(object_id); // Get current object
            int replica_id = get_replica_id(object_id, disk_id);

            // Return if current object has request
            if (object.is_requested && !data_.request[object.last_request_point].is_done) {
                return object_id;
            } else {
                disk_point = point_advance(disk_point, object.size); // Advance head position by size
                total_advance += object.size; // Accumulate moved distance
            }
        } else {
            disk_point = point_advance(disk_point, 1);  // Advance head position by size
            total_advance += 1; // Accumulate moved distance
        }
    } while (total_advance <= data_.V); // Continue searching if moved distance is less than disk size
    // Return 0 if no requested object found
    return 0;
}

int Reader::f(int object_id, double timepast) {
    Object& object = data_.object[object_id];
    int g = (object.size + 1) * 0.5;
    double total_score = 0;
    for (int id : object.request_ids) {
        Request& request = data_.request[id];
        if (request.is_done) continue;
        double time_val;
        double x = data_.timestamp - request.timestamp + timepast;
        if (x <= 10) {
            time_val = 1 - 0.005 * x;
        } else if (x > 10 && x <= 105) {
            time_val = 1.05 - 0.01 * x;
        } else {
            time_val = 0;
        }
        total_score += g * time_val;
    } 
    return total_score;
    //return g;
}


std::pair<int, int> Reader::findMaxScoreInterval(std::vector<int> &disk, int s, int disk_id, int point_index)
{
    std::vector<Segment> segments;
    int start = 1;
    
    // Split non-zero segments and calculate score
    while (start <= data_.V) {
        while (start <= data_.V) {
            int object_id = disk[start];
            if (object_id == 0) {
                start++;
                continue;
            }
            Object& object = data_.object[object_id];
            if (has_requested_object(disk, object, disk_id, point_index)) break;
            start += object.size;
        }
        if (start > data_.V) break;
        int end = start;
        while (end <= data_.V) {
            int object_id = disk[end];
            if (object_id == 0) break;
            Object& object = data_.object[object_id];
            if (!has_requested_object(disk, object, disk_id, point_index)) break;
            end += object.size;
        }
        end--;
        
        // Calculate score for current segment
        int current_score = 0;
        int obj_start = start;
        double timepast = 0;
        while (obj_start <= end) {
            int object_id = disk[obj_start];
            int obj_end = obj_start;
            while (obj_end <= end && disk[obj_end] == object_id) obj_end++;
            timepast += (obj_end - obj_start) / 20;
            current_score += f(object_id, timepast);
            obj_end--;
            obj_start = obj_end + 1;
        }
        segments.push_back({start, end, current_score});
        start = end + 1;
    }
    
    if (segments.empty()) return {0, 0};
    
    // Calculate distance between adjacent segments
    std::vector<int> distances;
    for (int i = 0; i < segments.size() - 1; i++) {
        int distance = segments[i + 1].start - segments[i].end - 1;
        distances.push_back(distance);
    }
    
    int max_score = INT_MIN;
    int result_start = -1, result_end = -1;
    int num_segments = segments.size();
    
    for (int i = 0; i < num_segments; i++) {
        int current_score = segments[i].score;
        int current_start = segments[i].start;
        int current_end = segments[i].end;
        
        // Update current segment score
        if (current_score > max_score || (current_score == max_score && current_start < result_start)) {
            max_score = current_score;
            result_start = current_start;
            result_end = current_end;
        }
        
        // Try to merge subsequent segments
        for (int j = i + 1; j < num_segments; j++) {
            if (distances[j - 1] > s) break; // Cannot merge if distance exceeds s
            current_score += segments[j].score;
            current_end = segments[j].end;
            
            // Update max score and start index
            if (current_score > max_score || (current_score == max_score && current_start < result_start)) {
                max_score = current_score;
                result_start = current_start;
                result_end = current_end;
            }
        }
    }

    for (int i = result_start; i <= result_end;) {
        int object_id = disk[i];
        if (object_id == 0) {
            i++;
            continue;
        }
        Object& object = data_.object[object_id];
        object.assigned_disk = disk_id;
        object.assigned_point_index = point_index;
        i += object.size;
    }
    
    return {result_start, result_end};
}

bool Reader::assign_object_helper(int disk_id, int point_index) {
    int object_id = get_nearest_object(disk_id,point_index);
    if (object_id == 0) return false;
    current_object[disk_id][point_index] = object_id;
    Object& object = data_.object.at(object_id);

    // Reset requests for this object
    finish_list[disk_id][point_index].clear();
    for (int r : object.request_ids) {
        if (data_.request.at(r).is_done) continue;
        finish_list[disk_id][point_index].push_back(r);
    }
    object.request_ids.clear();
    object.is_requested = false;
    object.assigned_disk = 0;
    object.assigned_point_index = -1;
    return true;
}

// Assign request object to current disk
void Reader::assign_object(int disk_id,int point_index) {
    if (current_object[disk_id][point_index] != 0) return;
    assign_object_helper(disk_id,point_index);
}

void Reader::record_read_done(int disk_id, int& success_read, std::vector<int> &req_id , int point_index) {
    if (current_object[disk_id][point_index] == 0) return;
    int object_id = current_object[disk_id][point_index];
    Object& object = data_.object.at(object_id);
    if (current_phase[disk_id][point_index] == object.size) { 
        if (!object.is_delete) {
            for (int r : finish_list[disk_id][point_index]) {
                if(data_.request.at(r).is_done == false){
                    req_id.push_back(r);
                    data_.request.at(r).is_done = true;
                    success_read++;   
                }     
            }
        } 
        current_object[disk_id][point_index] = 0;
        current_phase[disk_id][point_index] = 0;
    }
}



void Reader::read_object() {
    int success_read = 0;
    std::vector<int> req_id;
    std::vector<std::vector<std::string>> output(data_.N + 1, std::vector<std::string>(2, ""));
    //////////////////////////////////////
    for(int i = 1; i <= data_.N; i++) {
        std::vector<int>& disk = data_.disk[i];
        std::vector<int> tokens_comsumed (2 , 0); // Tokens consumed in this time slice

        for (int point_index = 0; point_index < 2; point_index++) {
            int disk_point = data_.disk_point[i][point_index]; // Current disk head position
            if ((start[i][point_index] == 0 || disk_point > end[i][point_index]) ) {
                auto p = findMaxScoreInterval(disk, data_.G / 16, i, point_index);
                start[i][point_index] = p.first;
                end[i][point_index] = p.second;
                /////////////////////////////
                if (start[i][point_index] != 0) {
                    data_.disk_point[i][point_index] = start[i][point_index];
                    int distance = dist(disk_point, start[i][point_index]);
                    if (!assign_object_helper(i, point_index)) continue;
                    current_phase[i][point_index] = 0;
                    read_count[i][point_index] = 0;
                    if (distance > data_.G - get_read_cost(i , point_index)) {
                        output[i][point_index] += "j " + std::to_string(start[i][point_index]) + "\n";
                        continue; 
                    } else {
                        for (int j = 1; j <= distance; j++) {
                            output[i][point_index] += "p";
                        }
                        tokens_comsumed[point_index] += distance;
                    }
                }
            }
            //////////// Select object to read for disk head ///////////////////
            assign_object(i, point_index); 
            if (current_object[i][point_index] == 0) {
                // printf("#\n");
                output[i][point_index] += "#\n";
                continue;
            } 
            ///////////////////////////////////
            int object_id = current_object[i][point_index];
            Object& object = data_.object.at(object_id);
            
            int current_rep_id = get_replica_id(object_id, i); // Replica ID of object required by current request
            int current_block_point = object.unit[current_rep_id][current_phase[i][point_index] + 1]; // Position of object block to be read on disk
            

            if (dist(disk_point, current_block_point) > data_.G && tokens_comsumed[point_index] == 0) { // Check if jump is needed
                output[i][point_index] += "j " + std::to_string(current_block_point) + "\n";
                // std::cout << "j " << current_block_point << std::endl;
                data_.disk_point[i][point_index] = current_block_point;
                read_count[i][point_index] = 0;
                continue;
            }

            bool can_read = true; // 标记是否可以读取
            
            while (current_object[i][point_index] > 0) { // If no jump, keep moving or reading until tokens are exhausted
                object_id = current_object[i][point_index];
                Object& object = data_.object.at(object_id);
                disk_point = data_.disk_point[i][point_index]; 
                current_rep_id = get_replica_id(object_id, i);
                current_block_point = object.unit[current_rep_id][current_phase[i][point_index] + 1]; 
                int read_cost = get_read_cost(i, point_index); // Tokens consumed if reading is chosen
                int count = 0 ; 
                if((  (dist(disk_point, current_block_point) <= 8 && read_count[i][point_index] >= 2) || (disk_point == current_block_point)) && can_read){ 
                    if (tokens_comsumed[point_index] + read_cost > data_.G) { // Not enough tokens to read, can only move
                        can_read = false;
                        continue;
                    }
                    output[i][point_index] += "r"; 
                    disk_point_advance(i, 1, point_index); // Disk head position + 1

                    if(disk_point == current_block_point) {current_phase[i][point_index]++; }// Object read count + 1
                    
                    read_count[i][point_index]++; // Continuous read count + 1
                    tokens_comsumed[point_index] += read_cost; 

                    // A disk can read multiple objects in one time slice
                    if (current_phase[i][point_index] == data_.object.at(object_id).size) {
                        record_read_done(i, success_read, req_id , point_index);
                        assign_object(i , point_index); 
                    }
                    if (tokens_comsumed[point_index] == data_.G) break; // Handle a special case

                } else { // If different, jump is needed
                    int distance = dist(disk_point, current_block_point);
                    if (!can_read || distance == 0) break;
                    if (distance + tokens_comsumed[point_index] > data_.G ) { // If tokens are not enough to move to next object block position
                        for (int j = 1; j <= data_.G - tokens_comsumed[point_index] - 1; j++) {
                            output[i][point_index] += "p";
                            // std::cout << "p";
                            disk_point_advance(i, 1,point_index);
                        }
                        read_count[i][point_index] = 0;
                        break;
                    } else {
                        for (int j = 1; j <= distance; j++) {
                            output[i][point_index] += "p";
                            // std::cout << "p";
                            disk_point_advance(i, 1,point_index);
                        }
                        tokens_comsumed[point_index] += distance;
                        read_count[i][point_index] = 0;
                    }
                }
            }
            output[i][point_index] += "#\n";
            // std::cout << "#" << std::endl; 
            }
    }
    ///////////////print////////////////
    for (int i = 1; i <= data_.N; i++) {
        for(int j=0; j < output[i].size(); j++){
            std::cout << output[i][j];
        }
    }
    std::cout << success_read << std::endl;
    for (int r : req_id) {
        std::cout << r << std::endl;
    }
    ///////////////拒绝请求///////////////
    refuse_request();
    /////////////////////////
    fflush(stdout);
}