Intrusive singly-linked list
hawkw opened this issue · 27 comments
Someone with a little Rust experience could probably do this fairly easily by copying the doubly-linked list code.
✋ Raises hand. No Rust experience so far but willing to learn.
@amanjeev sounds good! I'd be happy to walk you through it step by step, but probably won't have the time until next weekend. If you'd like to start now, I can give you pointers to resources and answer questions as you go?
@hawkw Thank you for responding! I understand it is pretty busy. I think "pointers to resources" for now is the best place to start. Hopefully, this will save you some time as well and will allow me to dive in.
@amanjeev The Rust Programming Language is probably a good place to start for basic Rust syntax and idioms/
Thank you! I shall begin. :-)
Is it going to be too verbose and annoying if I leave insights as I go. :D
Here is one for today - Learnt that I had to use nightly build instead of stable.
$ rustup show
Default host: x86_64-apple-darwin
installed toolchains
--------------------
stable-x86_64-apple-darwin
nightly-x86_64-apple-darwin (default)
active toolchain
----------------
nightly-x86_64-apple-darwin (default)
rustc 1.25.0-nightly (bacb5c58d 2018-01-26)
OK, maybe it will be bad. I will keep it to the questions then.
Is it going to be too verbose and annoying if I leave insights as I go. :D
No, please feel free to post any insights and document your progress! Hopefully others will find it useful as well.
Here is one for today - Learnt that I had to use nightly build instead of stable.
Yes, this library currently only builds against the nightly compiler --- there's an issue open, #12, for eventually being able to build against the next stable release as well. This definitely should be documented elsewhere, though; that's my fault for not putting it in the README!
EDIT: I've added a note in the README documenting the Rust compiler requirement --- thanks again for pointing this out.
This definitely should be documented elsewhere
I was about to reply with I could do that but you beat me to it. 👍
No, please feel free to post any insights and document your progress! Hopefully others will find it useful as well.
Thank you!
@hawkw What does your setup look like? Example of the things I would like to know
- OS
- IDE or Editor
- Any special plugin setup
Thank you.
PS: I am trying Jetbrains CLion with rust plugin mainly so that I can easily jump to the declarations but it does not work for core lib for me. I opened a question for the plugin folks - intellij-rust/intellij-rust#2238
VSCode is popular if you need a full IDE type experience, the rls plugins work well but can be annoying to set up on nightly.
To start you really just need to install rust with rustup and pick any editor and start coding (I started with just vim and a syntax highlighting plugin), try to get the project to build with cargo. The rust compiler produces good errors, that should be enough for now.
@amanjeev, @leshow's advice is pretty much spot on. I'm using VS Code with the RLS plugin; there's also a comparable RLS plugin for Atom which works alright.
If you have trouble installing a working version of RLS, check out editor-rs/vscode-rust#363 (comment) --- it should save you a bit of pain. This applies to any editor that uses the RLS as a backend.
So far, I have been able to copy doubly to create a new mod for singly and basically able to fail some tests (related to all prev()). Now, on to implement those prev methods, which are obviously inefficient than doubly.
(Commenting so you can point out obvious flaws in my reasoning/thinking etc. :) )
@amanjeev I'm not sure if we actually want a singly-linked list to have the ability to traverse backwards (e.g. prev() methods, cursor, DoubleEndedIterator, etc).
The primary use-case I can see for a singly-linked list is when you intend to use a list exclusively as a stack and thus don't need the additional overhead of maintaining a set of reverse links. Furthermore, I'm not really sure how one would go about giving a node with only a forward reference the ability to reference the previous node...
What do you think?
(also, if you'd like to, please feel free to push up a work in progress branch at any point and I can check out what you're working on!)
The primary use-case I can see for a singly-linked list is when you intend to use a list exclusively as a stack
I am an idiot. I kept thinking I had to contain most of the functionality. Sorry about that, @hawkw.
My branch is feature/singly-list-playground (forgive the name, I was going to clean up later). I have not been able to push anything after that because I kept struggling with Rust itself.
I, literally, just commented out and deleted a bunch of stuff from mod and test. Definitely, needs some refactoring which I will do next. Like changing pop_front() to pop(), since, it is essentially a stack. Please correct me if I am mistaken. Thank you.
It looks like you're on the right track so far!
I suspect the code could be made somewhat simpler by removing the Links struct and making the singly::Linked trait just return a next link directly, since for a singly-linked list, a node ... has a single link. This isn't necessary but might help make the code a little cleaner.
It looks like you're on the right track so far!
Yay!
the code could be made somewhat simpler by removing the
Linksstruct
Sounds good to me.
I tried to follow your advice about removing Links struct https://github.com/amanjeev/alarm/tree/feature/singly-list-playground/intruder_alarm/src/singly.
Took me a while to wrap my head around the traits, although I still falter with multiple impls and stuff like impl x for y. I think I need to read (and write) more.
//keeping-fingers-crossed
@hawkw I see a bunch of changes when I run cargo fmt; even in the files I have not touched. 😞
I also see a bunch of warnings like these...(click to open)
Warning: Unknown configuration option `chain_base_indent`
Warning: Unknown configuration option `chain_indent`
Warning: Unknown configuration option `chains_overflow_last`
Warning: Unknown configuration option `enum_trailing_comma`
Warning: Unknown configuration option `fn_arg_indent`
Warning: Unknown configuration option `fn_args_layout`
Warning: Unknown configuration option `fn_brace_style`
Warning: Unknown configuration option `fn_call_width`
Warning: Unknown configuration option `fn_empty_single_line`
Warning: Unknown configuration option `fn_return_indent`
Warning: Unknown configuration option `generics_indent`
Warning: Unknown configuration option `impl_empty_single_line`
Warning: Unknown configuration option `item_brace_style`
Warning: Unknown configuration option `match_wildcard_trailing_comma`
Warning: Unknown configuration option `space_after_bound_colon`
Warning: Unknown configuration option `space_after_type_annotation_colon`
Warning: Unknown configuration option `space_before_bound`
Warning: Unknown configuration option `space_before_type_annotation`
Warning: Unknown configuration option `struct_lit_multiline_style`
Warning: Unknown configuration option `struct_lit_style`
Warning: Unknown configuration option `struct_lit_trailing_comma`
Warning: Unknown configuration option `struct_lit_width`
Warning: Unknown configuration option `struct_trailing_comma`
Warning: Unknown configuration option `struct_variant_width`
Warning: Unknown configuration option `where_indent`
Warning: Unknown configuration option `where_layout`
Warning: Unknown configuration option `where_pred_indent`
Warning: Unknown configuration option `where_trailing_comma`
Warning: Unknown configuration option `wrap_match_arms`
Warning: Unknown configuration option `chain_base_indent`
Warning: Unknown configuration option `chain_indent`
Warning: Unknown configuration option `chains_overflow_last`
Warning: Unknown configuration option `enum_trailing_comma`
Warning: Unknown configuration option `fn_arg_indent`
Warning: Unknown configuration option `fn_args_layout`
Warning: Unknown configuration option `fn_brace_style`
Warning: Unknown configuration option `fn_call_width`
Warning: Unknown configuration option `fn_empty_single_line`
Warning: Unknown configuration option `fn_return_indent`
Warning: Unknown configuration option `generics_indent`
Warning: Unknown configuration option `impl_empty_single_line`
Warning: Unknown configuration option `item_brace_style`
Warning: Unknown configuration option `match_wildcard_trailing_comma`
Warning: Unknown configuration option `space_after_bound_colon`
Warning: Unknown configuration option `space_after_type_annotation_colon`
Warning: Unknown configuration option `space_before_bound`
Warning: Unknown configuration option `space_before_type_annotation`
Warning: Unknown configuration option `struct_lit_multiline_style`
Warning: Unknown configuration option `struct_lit_style`
Warning: Unknown configuration option `struct_lit_trailing_comma`
Warning: Unknown configuration option `struct_lit_width`
Warning: Unknown configuration option `struct_trailing_comma`
Warning: Unknown configuration option `struct_variant_width`
Warning: Unknown configuration option `where_indent`
Warning: Unknown configuration option `where_layout`
Warning: Unknown configuration option `where_pred_indent`
Warning: Unknown configuration option `where_trailing_comma`
Warning: Unknown configuration option `wrap_match_arms`
Warning: Unknown configuration option `chain_base_indent`
Warning: Unknown configuration option `chain_indent`
Warning: Unknown configuration option `chains_overflow_last`
Warning: Unknown configuration option `enum_trailing_comma`
Warning: Unknown configuration option `fn_arg_indent`
Warning: Unknown configuration option `fn_args_layout`
Warning: Unknown configuration option `fn_brace_style`
Warning: Unknown configuration option `fn_call_width`
Warning: Unknown configuration option `fn_empty_single_line`
Warning: Unknown configuration option `fn_return_indent`
Warning: Unknown configuration option `generics_indent`
Warning: Unknown configuration option `impl_empty_single_line`
Warning: Unknown configuration option `item_brace_style`
Warning: Unknown configuration option `match_wildcard_trailing_comma`
Warning: Unknown configuration option `space_after_bound_colon`
Warning: Unknown configuration option `space_after_type_annotation_colon`
Warning: Unknown configuration option `space_before_bound`
Warning: Unknown configuration option `space_before_type_annotation`
Warning: Unknown configuration option `struct_lit_multiline_style`
Warning: Unknown configuration option `struct_lit_style`
Warning: Unknown configuration option `struct_lit_trailing_comma`
Warning: Unknown configuration option `struct_lit_width`
Warning: Unknown configuration option `struct_trailing_comma`
Warning: Unknown configuration option `struct_variant_width`
Warning: Unknown configuration option `where_indent`
Warning: Unknown configuration option `where_layout`
Warning: Unknown configuration option `where_pred_indent`
Warning: Unknown configuration option `where_trailing_comma`
Warning: Unknown configuration option `wrap_match_arms`
@amanjeev, yeah, the rustfmt configuration is from an out of date version of rustfmt --- i keep meaning to update it. please feel free to open an issue for that!
Forgive my ignorance. What does // + Drop mean?
Like https://github.com/hawkw/alarm/blob/master/intruder_alarm/src/doubly/mod.rs#L58
If you think its worth something, should I open a PR? Please let me know if you have suggestions for further improvements.