EDD Airlines Flight Reservation System

A Python-based flight reservation system demonstrating key algorithms and data structures for managing flights, passengers, and reservations.

Features

• Flight Management: Add, search, delete flights with comprehensive validation
• Passenger Management: Add and delete passengers with cascading reservation cleanup
• Reservations: Book and cancel flights with double-booking prevention
• Search & Sorting:
  • Search flights by route and date with O(1) nested dict indexing
  • Sort by cost, date, and available seats using Timsort (O(n log n))
• Data Validation: 5 validation functions preventing invalid states
  • Date format validation
  • Unique flight numbers
  • Valid routes (origin ≠ destination)
  • Positive seat counts
  • Positive flight costs
• Comprehensive Logging: Audit trail with operation timestamps and performance metrics
• Persistent Storage: JSON-based persistence with atomic writes

Project Structure

algorithms/
  ├── indexing.py      # Flight index management (O(1) lookups)
  ├── searching.py     # Flight search by route/date
  └── sorting.py       # Timsort-based sorting (O(n log n))

data/
  ├── flights.py       # Flight data & operations
  ├── passengers.py    # Passenger data & operations
  └── reservations.py  # Reservation data & operations (O(n) scanning)

models/
  ├── flight.py        # Flight class
  ├── passenger.py     # Passenger class
  └── reservation.py   # Reservation class

utils/
  ├── menu.py          # Main user interface (14 menu options)
  ├── storage.py       # JSON persistence with atomic writes
  ├── validation.py    # 5 data validation functions
  ├── id_generator.py  # Unique ID generation
  └── logger.py        # Comprehensive logging system

data_store/
  ├── flights.json          # Flight data
  ├── passengers.json       # Passenger data
  ├── reservations.json     # Reservation data
  ├── flight_index.json     # Search index
  └── logs/                 # Session logs with daily rotation

Running the System

Prerequisites

• Python 3.8+
• Virtual environment (.venv/)

Installation

# Create virtual environment
python -m venv .venv

# Activate (Windows)
.\.venv\Scripts\activate

# Activate (macOS/Linux)
source .venv/bin/activate

Usage

python main.py

This launches the interactive console menu with 14 options:

1. Add Passenger
2. Add Flight
3. Search Flights
4. Book Reservation
5. Cancel Reservation
6. View Flights (unsorted)
7. View Flights by Cost
8. View Flights by Date
9. View Flights by Available Seats
10. View Reservations for Passenger
11. View Reservations for Flight
12. Delete Flight
13. Delete Passenger
14. Exit

Complexity Analysis

See BIG-O-ANALYSIS.md for detailed complexity analysis of all operations:

Operation	Time	Space	Notes
Search flights by route	O(1) lookup + O(k) retrieval	O(k)	Nested dict index
Book reservation	O(n) double-booking check	O(1)	Linear scan acceptable for 15k records
Sort flights	O(n log n)	O(n)	Python Timsort
Delete flight	O(n) cascade scan	O(1)	Finds & deletes all reservations

Logging

All operations are logged with timestamps and performance metrics:

• Console: INFO level and above
• File: DEBUG level and above (daily rotation)
• Location: data_store/logs/flight_system_YYYY-MM-DD.log

See LOGGING.md for detailed logging documentation.

Validation

System prevents invalid states:

• ✅ Duplicate flight numbers
• ✅ Double-bookings (same passenger on same flight)
• ✅ Invalid routes (origin = destination)
• ✅ Invalid seat counts (≤ 0 or overbooking)
• ✅ Invalid costs (≤ 0)

Design Decisions

Flight Index (O(1) Search)

Uses nested dictionary structure: origin → destination → date → [flight_numbers]

• Benefit: Constant-time search regardless of total flights
• Cost: Additional memory for index structure
• Justification: Search is critical user-facing operation

Reservation Scanning (O(n) Queries)

Direct list comprehension over all reservations instead of separate indexes

• Benefit: Simpler code, no synchronization complexity
• Cost: O(n) scan instead of O(1) lookup
• Justification: For 15k records, scan time ~1ms is negligible; simpler is better

Atomic Writes

Writes to temporary file, then atomic rename to prevent corruption

• Benefit: Data integrity even if process crashes
• Cost: Extra disk I/O (negligible)
• Note: No concurrency control for multi-user scenarios

Limitations & Future Work

1. Single-user only: No concurrency control (appropriate for local development)
2. JSON storage: Inefficient for 100k+ records (migrate to SQLite/PostgreSQL)
3. No seat assignment: Only tracks count, not specific seat numbers
4. Limited queries: Only search by route/date (extensible with additional functions)

Testing

Test data is loaded automatically on startup:

• 192,000+ records (flights, passengers, reservations)
• Demonstrates system performance with realistic data volume

Author

Luca Martinet - Noe Kurata - Aadit Karnavat Cardiff Metropolitan University - Algorithms and Data Structures Assignment