The Wayback Machine - https://web.archive.org/web/20220722235013/https://github.com/TheAlgorithms/C/pull/927
Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Rewrite the trie example #927

Merged
merged 1 commit into from Mar 20, 2022
Merged

Rewrite the trie example #927

merged 1 commit into from Mar 20, 2022

Conversation

dbeecham
Copy link
Contributor

@dbeecham dbeecham commented Jan 7, 2022

The trie example had some issues;

  • It did not follow the code convention in CONTRIBUTING.md
  • The createTrieNode used an inefficient zeroing method (looping over
    the entries) which also does not zero out holes in the structure (e.g.
    an alternative would be to use "*node = &(TrieNode){0}", but calloc
    does all that anyway
  • It used an inefficient and clumsy printArray method
  • It used strlen inside the algorithm; this new method could get rid of
    any strlen/strnlen usage (inserts/searches could be sanitized by
    snprintf)
  • This version can allow for a custom mapping function, e.g. if NULL is
    a valid separator (say that you want a trie for certain binary
    packages)
  • The previous version actually contained out-of-bounds array indexing;
    there were no checks for out-of-bound indexing and words in the word
    list did contain out of bounds words. It's a surprise it was working
    so well.
  • This version just returns 'int' to allow for error checks (instead of
    a printf inside the algorithm), and uses double pointers for return
    values (good practice)
  • The usage example contained unnecessary mallocs, switched that out for
    scanf. The example is just an example after all, in real applications
    you'd have better input sanitazion.

Description of Change

References

Checklist

  • Added description of change
  • Added file name matches File name guidelines
  • Added tests and example, test must pass
  • Relevant documentation/comments is changed or added
  • PR title follows semantic commit guidelines
  • Search previous suggestions before making a new one, as yours may be a duplicate.
  • I acknowledge that all my contributions will be made under the project's license.

Notes:

The trie example had some issues;

* It did not follow the code convention in CONTRIBUTING.md
* The createTrieNode used an inefficient zeroing method (looping over
  the entries) which also does not zero out holes in the structure (e.g.
  an alternative would be to use "*node = &(TrieNode){0}", but calloc
  does all that anyway
* It used an inefficient and clumsy printArray method
* It used strlen inside the algorithm; this new method could get rid of
  any strlen/strnlen usage (inserts/searches could be sanitized by
  snprintf)
* This version can allow for a custom mapping function, e.g. if NULL is
  a valid separator (say that you want a trie for certain binary
  packages)
* The previous version actually contained out-of-bounds array indexing;
  there were no checks for out-of-bound indexing and words in the word
  list did contain out of bounds words. It's a surprise it was working
  so well.
* This version just returns 'int' to allow for error checks (instead of
  a printf inside the algorithm), and uses double pointers for return
  values (good practice)
* The usage example contained unnecessary mallocs, switched that out for
  scanf. The example is just an example after all, in real applications
  you'd have better input sanitazion.
@Panquesito7 Panquesito7 added the enhancement label Jan 7, 2022
@Panquesito7 Panquesito7 requested a review from aminoxix Jan 7, 2022
@github-actions
Copy link

@github-actions github-actions bot commented Feb 17, 2022

This pull request has been automatically marked as abandoned because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

@github-actions
Copy link

@github-actions github-actions bot commented Mar 20, 2022

This pull request has been automatically marked as abandoned because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

@github-actions github-actions bot added the Stale label Mar 20, 2022
@Panquesito7 Panquesito7 removed the Stale label Mar 20, 2022
@Panquesito7 Panquesito7 merged commit 2314a19 into TheAlgorithms:master Mar 20, 2022
6 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

5 participants