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.

Sign up for GitHub

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

Jump to bottom

Intrusive singly-linked list #8

Closed
hawkw opened this issue Jan 20, 2018 · 27 comments
Closed

Intrusive singly-linked list #8

hawkw opened this issue Jan 20, 2018 · 27 comments
Labels
enhancement good first issue
Milestone
intruder_alarm 0.1.0

Comments

@hawkw
Copy link
Member

hawkw commented Jan 20, 2018

No description provided.

@hawkw hawkw self-assigned this Jan 20, 2018
@hawkw hawkw added this to the intruder_alarm 0.1.0 milestone Jan 20, 2018
@hawkw hawkw removed their assignment Jan 21, 2018
@hawkw
Copy link
Member Author

hawkw commented Jan 21, 2018

Someone with a little Rust experience could probably do this fairly easily by copying the doubly-linked list code.

@amanjeev
Copy link
Member

✋ Raises hand. No Rust experience so far but willing to learn.

@hawkw
Copy link
Member Author

hawkw commented Jan 22, 2018

@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?

@amanjeev
Copy link
Member

@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.

@hawkw
Copy link
Member Author

hawkw commented Jan 22, 2018

@amanjeev The Rust Programming Language is probably a good place to start for basic Rust syntax and idioms/

@amanjeev
Copy link
Member

Thank you! I shall begin. :-)

@amanjeev
Copy link
Member

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.

@hawkw
Copy link
Member Author

hawkw commented Jan 27, 2018 •
edited
Loading

@amanjeev

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.

@amanjeev
Copy link
Member

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!

@amanjeev
Copy link
Member

amanjeev commented Jan 29, 2018 •
edited
Loading

@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

@leshow
Copy link
Collaborator

leshow commented Jan 29, 2018 •
edited
Loading

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.

@hawkw
Copy link
Member Author

hawkw commented Jan 29, 2018 •
edited
Loading

@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.

@amanjeev amanjeev mentioned this issue Jan 30, 2018
Closed
@amanjeev
Copy link
Member

amanjeev commented Jan 30, 2018 •
edited
Loading

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. :) )

@hawkw
Copy link
Member Author

hawkw commented Jan 30, 2018

@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?

@hawkw
Copy link
Member Author

hawkw commented Jan 30, 2018

(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!)

@amanjeev
Copy link
Member

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.

@amanjeev
Copy link
Member

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.

@hawkw
Copy link
Member Author

hawkw commented Jan 31, 2018

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.

@amanjeev
Copy link
Member

It looks like you're on the right track so far!

Yay!

the code could be made somewhat simpler by removing the Links struct

Sounds good to me.

@amanjeev
Copy link
Member

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

@amanjeev
Copy link
Member

@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`

@hawkw
Copy link
Member Author

hawkw commented Jan 31, 2018

@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!

@amanjeev amanjeev mentioned this issue Jan 31, 2018
Closed
@amanjeev
Copy link
Member

amanjeev commented Feb 1, 2018

Forgive my ignorance. What does // + Drop mean?

Like https://github.com/hawkw/alarm/blob/master/intruder_alarm/src/doubly/mod.rs#L58

@hawkw
Copy link
Member Author

hawkw commented Feb 1, 2018

@amanjeev It means I was considering adding a Drop bound on Linked, realised it wasn't necessary, commented it out, and then forgot to remove it. :)

@amanjeev
Copy link
Member

amanjeev commented Feb 1, 2018

If you think its worth something, should I open a PR? Please let me know if you have suggestions for further improvements.

@hawkw
Copy link
Member Author

hawkw commented Feb 1, 2018 •
edited
Loading

@amanjeev if the implementation is done and the tests pass, please open a PR! :D

@amanjeev amanjeev mentioned this issue Feb 1, 2018
Merged
@amanjeev
Copy link
Member

amanjeev commented Feb 1, 2018

Opened #35 😨 😃

@hawkw hawkw closed this as completed in 2b0614a Feb 1, 2018
This was referenced Feb 1, 2018
Open
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement good first issue
Projects
None yet
Milestone
intruder_alarm 0.1.0
Development

No branches or pull requests
3 participants
@amanjeev @leshow @hawkw