How meowditya/dsa-project works
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: event_queue.h Queue contract · difftest_core.cpp Differential tester · queue_factory.cpp Queue factory · simulator.cpp Timer simulator
Components 19
Simulation application
- Simulation CLI
app/sim_main.cpp - Queue factory
app/queue_factory.cpp - Timer simulator
app/simulator.cpp - Canonical output
include/canonical.h
Event queues
- Queue contract
include/event_queue.h - Lazy heap
src/structA/lazy_heap.cpp - Sequence table
src/structA/seq_table.cpp - AVL queue
src/structB/avl_queue.cpp - Sorted oracle
oracle/sorted_oracle.cpp - Reproducible RNG
include/rng.h
Replay and verification
- Operation streams
include/opstream.h - Replay engine
oracle/replay_core.cpp - Differential tester
oracle/difftest_core.cpp - Invariant checkers
oracle/checkers.cpp
Adversarial inputs
- Adversarial generator
adversary/gen.cpp - Adversarial suites
adversary/suites
Performance analysis
- Hold and sweep
bench - Benchmark results
results
Other components
- User
Connections 27
- User → Simulation CLI: runs
README.md - Simulation CLI → Queue factory: selects queue
app/sim_main.cpp - Simulation CLI → Timer simulator: runs simulation
app/sim_main.cpp - Queue factory → Lazy heap: constructs
app/queue_factory.cpp - Queue factory → AVL queue: constructs
app/queue_factory.cpp - Queue factory → Sorted oracle: constructs
app/queue_factory.cpp - Timer simulator → Queue contract: uses queue
- Timer simulator → Reproducible RNG: draws randomness
app/simulator.cpp - Timer simulator → Canonical output: formats results
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
README.md - Operation streams → Replay engine: parses stream
- Replay engine → Queue contract: applies operations
- Differential tester → Replay engine: replays histories
oracle/difftest_core.cpp - Differential tester → Invariant checkers: checks queues
oracle/difftest_core.cpp - Differential tester → Reproducible RNG: generates histories
oracle/difftest_core.cpp - Differential tester → Sorted oracle: compares against
- Adversarial generator → Operation streams: writes streams
adversary/gen.cpp - Adversarial generator → Reproducible RNG: draws randomness
adversary/gen.cpp - User → Adversarial generator: requests attacks
README.md - Adversarial suites → Differential tester: exercise queues
- User → Hold and sweep: runs experiments
README.md - Hold and sweep → Benchmark results: records measurements
README.md - Hold and sweep → Queue contract: measures queues