codezonediitj / pydatastructs

A python package for data structures and algorithms
https://pydatastructs.readthedocs.io/en/stable/
Other
199 stars 270 forks source link

Added Suffix Tree implementation using Ukkonen algorithm #524

Open CarolLuca opened 1 year ago

CarolLuca commented 1 year ago

References to other Issues or PRs or Relevant literature

Brief description of what is fixed or changed

Added suffix tree class

Other comments

May be considered as GSoC 23 work sample

czgdp1807 commented 1 year ago

I would recommend to always shift to a new branch (other than main before making a new PR). Right now you have made your PR using your main branch. Keep this PR as is but from next time onwards update your main locally and then switch to a new branch for a new feature/bug fix.

codecov[bot] commented 1 year ago

Codecov Report

Merging #524 (b8c6b45) into main (2482adb) will increase coverage by 0.045%. The diff coverage is 100.000%.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## main #524 +/- ## ============================================= + Coverage 98.558% 98.603% +0.045% ============================================= Files 32 33 +1 Lines 4092 4226 +134 ============================================= + Hits 4033 4167 +134 Misses 59 59 ``` | [Impacted Files](https://codecov.io/gh/codezonediitj/pydatastructs/pull/524?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=codezonediitj) | Coverage Δ | | |---|---|---| | [pydatastructs/strings/\_\_init\_\_.py](https://codecov.io/gh/codezonediitj/pydatastructs/pull/524?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=codezonediitj#diff-cHlkYXRhc3RydWN0cy9zdHJpbmdzL19faW5pdF9fLnB5) | `100.000% <100.000%> (ø)` | | | [pydatastructs/strings/suffix\_tree.py](https://codecov.io/gh/codezonediitj/pydatastructs/pull/524?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=codezonediitj#diff-cHlkYXRhc3RydWN0cy9zdHJpbmdzL3N1ZmZpeF90cmVlLnB5) | `100.000% <100.000%> (ø)` | | | [pydatastructs/utils/misc\_util.py](https://codecov.io/gh/codezonediitj/pydatastructs/pull/524?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=codezonediitj#diff-cHlkYXRhc3RydWN0cy91dGlscy9taXNjX3V0aWwucHk=) | `99.250% <100.000%> (+0.120%)` | :arrow_up: | [![Impacted file tree graph](https://codecov.io/gh/codezonediitj/pydatastructs/pull/524/graphs/tree.svg?width=650&height=150&src=pr&token=mZMqq5ubAu&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=codezonediitj)](https://codecov.io/gh/codezonediitj/pydatastructs/pull/524?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=codezonediitj)
czgdp1807 commented 1 year ago

See, https://app.codecov.io/gh/codezonediitj/pydatastructs/pull/524/blob/pydatastructs/strings/suffix_tree.py. There are lots of lines (see the red ones) which aren't tested.

Also add SuffixTree to the following list,

https://github.com/codezonediitj/pydatastructs/blob/2482adb276055403485266d6d02a1489451c8e76/pydatastructs/utils/tests/test_code_quality.py#L151-L177

CarolLuca commented 1 year ago

I followed all the requested changes and added more tests such that the testing covers all the methods and sub-cases. I would be grateful if you could tell me if I can polish the classes in any other way.

CarolLuca commented 1 year ago

Thanks for this. Sorry for the later review. Mostly related to documentation.

I combined the __new__ and __init__ methods successfully, and added documentation for the main class, but also for the auxiliary classes from misc_util.py