Graph_Theory_Using_Flat_Buffers/Flat_Buffer_Graph.cpp

/**
 * @author: Lewis Price
 * @date: 06-09-2026 (MM-DD-YYYY)
 * @brief: This file contains the class definition for the Flat_Buffer_Graph, which is a graph data structure that uses flat buffers to store points and edges. The class provides methods for adding and deleting points and edges, as well as printing the graph for debugging purposes.
 * @version: 1.0.0
 */


#include "Flat_Buffer_Graph.h"

// Begin : Construction & Deconstruction
Flat_Buffer_Graph::Flat_Buffer_Graph(size_t max_points, size_t max_edges) noexcept 
{
	all_points = new(std::nothrow) Point[max_points] {};
	all_edges = new(std::nothrow) Edge[max_edges] {};

	if(all_points && all_edges) 
	{
		p_capacity = max_points;
		e_capacity = max_edges;
	}
}

Flat_Buffer_Graph::~Flat_Buffer_Graph() 
{
	delete[] all_points;
	delete[] all_edges;
}

Flat_Buffer_Graph::Flat_Buffer_Graph(Flat_Buffer_Graph&& new_location) noexcept
	: all_points(std::exchange(new_location.all_points, nullptr)),
	all_edges(std::exchange(new_location.all_edges, nullptr)),
	p_capacity(std::exchange(new_location.p_capacity, 0)),
	e_capacity(std::exchange(new_location.e_capacity, 0)) {}
// End : Construction & Deconstruction

// ----------------------- BEGIN : Printing -----------------------
void Flat_Buffer_Graph::print_graph() noexcept
{
    for (size_t i = 0; i < p_capacity; ++i) {
        Point& p = all_points[i];
        if (p.e_count == -1) continue;

        printf("Point %zu: %s (x:%.2f, y:%.2f, z:%.2f)\n", i, p.name.c_str(), p.x, p.y, p.z);

        int current_edge_idx = p.first_edge;
        while (current_edge_idx != -1) {
            Edge& e = all_edges[current_edge_idx];
            printf("  -> Edge to Point %d [Weight: %.2f]\n", e.end_point, e.e_weight);
            current_edge_idx = e.next_edge;
        }
    }
}

// ----------------------- END : Printing -----------------------


// ----------------------- BEGIN : Getters -----------------------

Point* Flat_Buffer_Graph::get_points() noexcept 
{
	return all_points;
}

Edge* Flat_Buffer_Graph::get_p_edges(int p_index) noexcept 
{
    if(p_index < 0 || (size_t)p_index >= p_capacity) return nullptr;

    int head_idx = all_points[p_index].first_edge;
    if(head_idx == -1) return nullptr;

    return &all_edges[head_idx];
}
// ----------------------- END : Getters -----------------------


// ----------------------- BEGIN : Mutators -----------------------

Point* Flat_Buffer_Graph::add_point(std::string name, float x, float y, float z) noexcept {
    int target = -1;

    if (next_free_point != -1) {
        target = next_free_point;
        // The hijacked 'first_edge' tells us where the NEXT hole is
        next_free_point = all_points[target].first_edge;
    }
    else if (num_points < p_capacity) {
        target = (int)num_points;
        num_points++;
    }
    else return nullptr; 

    Point* p = &all_points[target];
    p->name = name;
    p->x = x; p->y = y; p->z = z;
    p->first_edge = -1; 
    p->e_count = 0;

    return p;
}


bool Flat_Buffer_Graph::delete_point(int p_index) {
    if (p_index < 0 || (size_t)p_index >= p_capacity) return false;

    // 1. IMPORTANT: Clean up all edges belonging to this point first!
    // While the point has edges, delete the 'end_point' of the first edge.
    while (all_points[p_index].first_edge != -1) {
        int target_end = all_edges[all_points[p_index].first_edge].end_point;
        delete_edge(p_index, target_end);
    }

    // 2. Hijack point for Free List
    all_points[p_index].first_edge = next_free_point;
    all_points[p_index].e_count = -1; 
    next_free_point = p_index;

    return true;
}


Edge* Flat_Buffer_Graph::add_edge(int e_start, int e_end, float weight) noexcept {
    // Validation: Ensure indices are within bounds
    if (e_start < 0 || (size_t)e_start >= p_capacity || 
        e_end < 0 || (size_t)e_end >= p_capacity) return nullptr;

    int target_edge = -1;

    if (next_free_edge != -1) {
        target_edge = next_free_edge;
        next_free_edge = all_edges[target_edge].next_edge;
    } 
    else if (num_edges < e_capacity) {
        target_edge = (int)num_edges;
        num_edges++;
    } 
    else return nullptr; 

    // Initialize and Link
    all_edges[target_edge].end_point = e_end;
    all_edges[target_edge].e_weight = weight;
    
    // Link to Point's head
    all_edges[target_edge].next_edge = all_points[e_start].first_edge;
    all_points[e_start].first_edge = target_edge;
    all_points[e_start].e_count++;

    return &all_edges[target_edge];
}

bool Flat_Buffer_Graph::delete_edge(int e_start, int e_end) noexcept {
    Point& p = all_points[e_start];
    int current = p.first_edge;
    int prev = -1;

    // 1. Traverse the linked list of edges for this point
    while (current != -1) {
        if (all_edges[current].end_point == e_end) {
            // 2. Unhook the node
            if (prev == -1) p.first_edge = all_edges[current].next_edge;
            else            all_edges[prev].next_edge = all_edges[current].next_edge;

            // 3. Add the edge slot back to the global free list
            all_edges[current].next_edge = next_free_edge;
            next_free_edge = current;

            p.e_count--;
            return true;
        }
        prev = current;
        current = all_edges[current].next_edge;
    }
    return false;
}


// ----------------------- END : Mutators -----------------------