🚕 Ride-Sharing Dispatch & Trip Management System

A High-End, STL-Free Data Structures & Algorithms Engine in C++

---

📌 Introduction

This repository contains the design and implementation of an in-memory Ride-Sharing Dispatch & Trip Management System (similar to Uber or Careem).

Built strictly from scratch without relying on C++ Standard Template Library (STL) containers, this project focuses on low-level data structures, graph traversal algorithms, finite state machines, and dynamic rollback mechanics to demonstrate efficient memory control and custom algorithmic design.

---

🏛️ System Architecture

The architecture follows modular Object-Oriented Programming (OOP) principles where each component handles a single responsibility:

• City: Manages the geographic map network.
• Driver & Rider: Core entity models with status tracking.
• Trip: Encapsulates state-machine transitions for trip lifecycles.
• DispatchEngine: Core matching logic pairing riders with the nearest drivers.
• RollbackManager: LIFO transaction engine for undo operations.
• RideShareSystem: Central controller interface coordinating system components.
• main.cpp: Comprehensive test harness verifying system capabilities.

---

🛠️ Core Components & Features

1. City Network (Weighted Graph)

• Structure: Represented using an Adjacency Matrix where nodes denote locations and edges denote distance weights.
• Routing: Uses Dijkstra’s Algorithm to compute the global shortest paths between pickup and drop-off points without STL dependencies.

2. Driver & Rider Management

• Drivers are tracked using ID, real-time location, and availability status.
• Efficiently stored in fixed-size arrays with strict constructor-based dynamic memory initialization.

3. Trip Lifecycle (State Machine)

• Managed using a deterministic finite state machine to avoid race conditions: $$\text{REQUESTED} \longrightarrow \text{ASSIGNED} \longrightarrow \text{COMPLETED}$$ $$\text{REQUESTED / ASSIGNED} \longrightarrow \text{CANCELLED}$$

4. Greedy Dispatch Engine

• Pairs trip requests with the optimal available driver using a greedy approach integrated with Dijkstra’s shortest path output.

5. Stack-Based Rollback System

• Implements a custom LIFO Stack enabling instant $\mathcal{O}(1)$ transactional rollbacks for operations like trip cancellations.

---

⚡ Complexity Analysis

Module / Operation	Data Structure / Algorithm	Time Complexity	Space Complexity
Shortest Path	Dijkstra's Algorithm	$\mathcal{O}(V^2)$	$\mathcal{O}(V^2)$
Driver Matching	Greedy Proximity Search	$\mathcal{O}(D \times V^2)$	$\mathcal{O}(1)$
State Mutation	Finite State Machine	$\mathcal{O}(1)$	$\mathcal{O}(1)$
System Rollback	Custom LIFO Stack	$\mathcal{O}(1)$	$\mathcal{O}(S)$

Where $V$ = Map Locations, $D$ = Total Drivers, and $S$ = Rollback History Depth.

---

🧪 Testing Strategy

The engine includes a suite of test cases integrated into main.cpp validating:

1. Shortest path routing correctness.
2. Dynamic driver reassignments upon trip cancellation.
3. Edge-case handling (cancelling completed or non-existent trips).
4. LIFO stack state restoration.

---

🚀 Building & Running

Prerequisites

• C++ Compiler: GCC / G++ (MinGW on Windows, Clang on macOS)

Build Steps

1. Compile all source files:

   g++ *.cpp -o main.exe