# meowditya/dsa-project architecture

> Architecture diagram of the GitHub repository meowditya/dsa-project, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2026-11-20). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/meowditya/dsa-project
- Repository: https://github.com/meowditya/dsa-project

## Overview

This is a data-structures laboratory project comparing two event-queue implementations against a sorted-array oracle, with a retransmission-timer simulator as its main application. The primary workflow selects a queue, runs the simulation, and emits a canonical summary; companion workflows replay operation streams, differential-check implementations, generate adversarial inputs, and measure hold-model and cancellation-sweep behavior. The graph preserves those documented capabilities. Some benchmark and CLI relationships are documented in the README rather than shown in sampled implementation excerpts.

Main entry points: [`include/event_queue.h`](https://github.com/meowditya/dsa-project/blob/main/include/event_queue.h) (Queue contract), [`oracle/difftest_core.cpp`](https://github.com/meowditya/dsa-project/blob/main/oracle/difftest_core.cpp) (Differential tester), [`app/queue_factory.cpp`](https://github.com/meowditya/dsa-project/blob/main/app/queue_factory.cpp) (Queue factory), [`app/simulator.cpp`](https://github.com/meowditya/dsa-project/blob/main/app/simulator.cpp) (Timer simulator)

## Diagram (Mermaid)

```mermaid
flowchart TD

subgraph group_app["Simulation application"]
  node_simcli["Simulation CLI<br/>[sim_main.cpp]"]
  node_factory["Queue factory<br/>[queue_factory.cpp]"]
  node_simulator["Timer simulator<br/>[simulator.cpp]"]
  node_summary["Canonical output<br/>[canonical.h]"]
end

subgraph group_queues["Event queues"]
  node_contract["Queue contract<br/>[event_queue.h]"]
  node_heap["Lazy heap<br/>[lazy_heap.cpp]"]
  node_seqtable["Sequence table<br/>[seq_table.cpp]"]
  node_avl["AVL queue<br/>[avl_queue.cpp]"]
  node_oracle["Sorted oracle<br/>[sorted_oracle.cpp]"]
  node_rng["Reproducible RNG<br/>[rng.h]"]
end

subgraph group_verification["Replay and verification"]
  node_opstream["Operation streams<br/>[opstream.h]"]
  node_replay["Replay engine<br/>[replay_core.cpp]"]
  node_difftest["Differential tester<br/>[difftest_core.cpp]"]
  node_checkers["Invariant checkers<br/>[checkers.cpp]"]
end

subgraph group_adversary["Adversarial inputs"]
  node_generator["Adversarial generator<br/>[gen.cpp]"]
  node_suites["Adversarial suites"]
end

subgraph group_analysis["Performance analysis"]
  node_benchmarks["Hold and sweep"]
  node_results["Benchmark results"]
end

node_user(("User"))

node_user -->|"runs"| node_simcli
node_simcli -->|"selects queue"| node_factory
node_simcli -->|"runs simulation"| node_simulator
node_factory -->|"constructs"| node_heap
node_factory -->|"constructs"| node_avl
node_factory -->|"constructs"| node_oracle
node_simulator -->|"uses queue"| node_contract
node_simulator -->|"draws randomness"| node_rng
node_simulator -->|"formats results"| node_summary
node_heap -->|"implements"| node_contract
node_heap -->|"tracks cancellations"| node_seqtable
node_avl -->|"implements"| node_contract
node_oracle -->|"implements"| node_contract
node_user -->|"provides operations"| node_opstream
node_opstream -->|"parses stream"| node_replay
node_replay -->|"applies operations"| node_contract
node_difftest -->|"replays histories"| node_replay
node_difftest -->|"checks queues"| node_checkers
node_difftest -->|"generates histories"| node_rng
node_difftest -.->|"compares against"| node_oracle
node_generator -->|"writes streams"| node_opstream
node_generator -->|"draws randomness"| node_rng
node_user -->|"requests attacks"| node_generator
node_suites -.->|"exercise queues"| node_difftest
node_user -->|"runs experiments"| node_benchmarks
node_benchmarks -->|"records measurements"| node_results
node_benchmarks -.->|"measures queues"| node_contract

click node_simcli "https://github.com/meowditya/dsa-project/blob/main/app/sim_main.cpp"
click node_factory "https://github.com/meowditya/dsa-project/blob/main/app/queue_factory.cpp"
click node_simulator "https://github.com/meowditya/dsa-project/blob/main/app/simulator.cpp"
click node_summary "https://github.com/meowditya/dsa-project/blob/main/include/canonical.h"
click node_contract "https://github.com/meowditya/dsa-project/blob/main/include/event_queue.h"
click node_heap "https://github.com/meowditya/dsa-project/blob/main/src/structA/lazy_heap.cpp"
click node_seqtable "https://github.com/meowditya/dsa-project/blob/main/src/structA/seq_table.cpp"
click node_avl "https://github.com/meowditya/dsa-project/blob/main/src/structB/avl_queue.cpp"
click node_oracle "https://github.com/meowditya/dsa-project/blob/main/oracle/sorted_oracle.cpp"
click node_rng "https://github.com/meowditya/dsa-project/blob/main/include/rng.h"
click node_opstream "https://github.com/meowditya/dsa-project/blob/main/include/opstream.h"
click node_replay "https://github.com/meowditya/dsa-project/blob/main/oracle/replay_core.cpp"
click node_difftest "https://github.com/meowditya/dsa-project/blob/main/oracle/difftest_core.cpp"
click node_checkers "https://github.com/meowditya/dsa-project/blob/main/oracle/checkers.cpp"
click node_generator "https://github.com/meowditya/dsa-project/blob/main/adversary/gen.cpp"
click node_suites "https://github.com/meowditya/dsa-project/tree/main/adversary/suites"
click node_benchmarks "https://github.com/meowditya/dsa-project/tree/main/bench"
click node_results "https://github.com/meowditya/dsa-project/tree/main/results"

classDef toneNeutral fill:#f8fafc,stroke:#334155,stroke-width:1.5px,color:#0f172a
classDef toneBlue fill:#dbeafe,stroke:#2563eb,stroke-width:1.5px,color:#172554
classDef toneAmber fill:#fef3c7,stroke:#d97706,stroke-width:1.5px,color:#78350f
classDef toneMint fill:#dcfce7,stroke:#16a34a,stroke-width:1.5px,color:#14532d
classDef toneRose fill:#ffe4e6,stroke:#e11d48,stroke-width:1.5px,color:#881337
classDef toneIndigo fill:#e0e7ff,stroke:#4f46e5,stroke-width:1.5px,color:#312e81
classDef toneTeal fill:#ccfbf1,stroke:#0f766e,stroke-width:1.5px,color:#134e4a
class node_simcli,node_factory,node_simulator,node_summary,node_user toneBlue
class node_contract,node_heap,node_seqtable,node_avl,node_oracle,node_rng toneAmber
class node_opstream,node_replay,node_difftest,node_checkers toneMint
class node_generator,node_suites toneRose
class node_benchmarks,node_results toneIndigo
```

## Components

### Simulation application

- [Simulation CLI](https://github.com/meowditya/dsa-project/blob/main/app/sim_main.cpp): `app/sim_main.cpp`
- [Queue factory](https://github.com/meowditya/dsa-project/blob/main/app/queue_factory.cpp): `app/queue_factory.cpp`
- [Timer simulator](https://github.com/meowditya/dsa-project/blob/main/app/simulator.cpp): `app/simulator.cpp`
- [Canonical output](https://github.com/meowditya/dsa-project/blob/main/include/canonical.h): `include/canonical.h`

### Event queues

- [Queue contract](https://github.com/meowditya/dsa-project/blob/main/include/event_queue.h): `include/event_queue.h`
- [Lazy heap](https://github.com/meowditya/dsa-project/blob/main/src/structA/lazy_heap.cpp): `src/structA/lazy_heap.cpp`
- [Sequence table](https://github.com/meowditya/dsa-project/blob/main/src/structA/seq_table.cpp): `src/structA/seq_table.cpp`
- [AVL queue](https://github.com/meowditya/dsa-project/blob/main/src/structB/avl_queue.cpp): `src/structB/avl_queue.cpp`
- [Sorted oracle](https://github.com/meowditya/dsa-project/blob/main/oracle/sorted_oracle.cpp): `oracle/sorted_oracle.cpp`
- [Reproducible RNG](https://github.com/meowditya/dsa-project/blob/main/include/rng.h): `include/rng.h`

### Replay and verification

- [Operation streams](https://github.com/meowditya/dsa-project/blob/main/include/opstream.h): `include/opstream.h`
- [Replay engine](https://github.com/meowditya/dsa-project/blob/main/oracle/replay_core.cpp): `oracle/replay_core.cpp`
- [Differential tester](https://github.com/meowditya/dsa-project/blob/main/oracle/difftest_core.cpp): `oracle/difftest_core.cpp`
- [Invariant checkers](https://github.com/meowditya/dsa-project/blob/main/oracle/checkers.cpp): `oracle/checkers.cpp`

### Adversarial inputs

- [Adversarial generator](https://github.com/meowditya/dsa-project/blob/main/adversary/gen.cpp): `adversary/gen.cpp`
- [Adversarial suites](https://github.com/meowditya/dsa-project/tree/main/adversary/suites): `adversary/suites`

### Performance analysis

- [Hold and sweep](https://github.com/meowditya/dsa-project/tree/main/bench): `bench`
- [Benchmark results](https://github.com/meowditya/dsa-project/tree/main/results): `results`

### Other components

- **User**

## Connections

- User → Simulation CLI: runs (evidence: `README.md`)
- Simulation CLI → Queue factory: selects queue (evidence: `app/sim_main.cpp`)
- Simulation CLI → Timer simulator: runs simulation (evidence: `app/sim_main.cpp`)
- Queue factory → Lazy heap: constructs (evidence: `app/queue_factory.cpp`)
- Queue factory → AVL queue: constructs (evidence: `app/queue_factory.cpp`)
- Queue factory → Sorted oracle: constructs (evidence: `app/queue_factory.cpp`)
- Timer simulator → Queue contract: uses queue
- Timer simulator → Reproducible RNG: draws randomness (evidence: `app/simulator.cpp`)
- Timer simulator → Canonical output: formats results (evidence: `app/simulator.cpp`)
- Lazy heap → Queue contract: implements
- Lazy heap → Sequence table: tracks cancellations
- AVL queue → Queue contract: implements
- Sorted oracle → Queue contract: implements
- User → Operation streams: provides operations (evidence: `README.md`)
- Operation streams → Replay engine: parses stream
- Replay engine → Queue contract: applies operations
- Differential tester → Replay engine: replays histories (evidence: `oracle/difftest_core.cpp`)
- Differential tester → Invariant checkers: checks queues (evidence: `oracle/difftest_core.cpp`)
- Differential tester → Reproducible RNG: generates histories (evidence: `oracle/difftest_core.cpp`)
- Differential tester → Sorted oracle: compares against
- Adversarial generator → Operation streams: writes streams (evidence: `adversary/gen.cpp`)
- Adversarial generator → Reproducible RNG: draws randomness (evidence: `adversary/gen.cpp`)
- User → Adversarial generator: requests attacks (evidence: `README.md`)
- Adversarial suites → Differential tester: exercise queues
- User → Hold and sweep: runs experiments (evidence: `README.md`)
- Hold and sweep → Benchmark results: records measurements (evidence: `README.md`)
- Hold and sweep → Queue contract: measures queues
