Improve Data Structures for finding Departures
Nobody has claimed this yet.
- Dominant language
- C++
- Stars
- 24
- Forks
- 7
- PR merge metrics
- No merged PRs in 30d
Description
The data structures that allow finding departures can probably be improved. The goal is a data structure that stores all stops and their respective departures on a line. The look-ups should support the following operations:
### Line + Stop -> localID
For every line, and every stop, we should get the position of the stop along the line. This look-up should be possible to do in **O(1)** (via hashing), but we might be able to offer something better. It could be that lines in general are short enough so that _linear scan remains an option_.
### localID + Time -> Time
For every local ID and a arrival time, we want to be able to find the next departure of the line from the stop. The look-up itself probably requires **logarithmic** time + x, if we do a binary search over all departures.
### localID + Time -> {stops, duration}
When we know the actual departure for a localID, we should be able to collect all stops + durations along the line (so that search algorithms) can reach the next stops on a line. This look-up should also be possible in **O(1)**, if we store appropriate information with the previous two look-ups which are required to access the line table anyhow.
### Usage
The usage of this data structure should hide all access of the first two look-ups and simply allow an access via `stop-id` and `arrival time` to `{stops,durations,departure_time}`, which is a trip that leaves at `departure_time` and can reach `stops` in offsets stored in `durations`.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by locating the existing data structures and departure lookup entry points in the C++ router, then compare them with the three requested lookup operations. Done means providing a line-and-stop lookup, next-departure lookup, and trip stop/duration access behind the proposed stop-id and arrival-time interface, with the stated complexity targets validated.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- backend
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 25/100