Implement forwardSearch and backwardSearch
- Dominant language
- Haskell
- Stars
- 96
- Forks
- 9
- PR merge metrics
- No merged PRs in 30d
Description
The `RangeMin` tree is based on the ideas from [Fully-Functional Succinct Trees](https://cs.uwaterloo.ca/~imunro/cs840/ProjectPapers/SODA10_013_sadakanek.pdf) by Sadakane and Navarro.
However, I only store the minima rather than both minima and maxima, based on an observation in [Fast Compressed Tries through Path Decompositions](http://arxiv.org/pdf/1111.5220v2.pdf) by Grossi and Ottaviano.
I also store the encoding of the minima as a delta in order to get a proper monoid.
Since the structure I have is trivially isomorphic to Grossi and Ottaviano's, it should be capable of supporting fwd-search and bwd-search which is necessary for fast balanced-parentheses trees.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by locating the RangeMin tree and its search operations in the repository, then read the cited papers to understand forward and backward search. Done means the structure supports fwd-search and bwd-search as required for fast balanced-parentheses trees.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- haskell
- Domain
- data
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100