//! # rc-dlist-deque - Doubly-linked list based on `std::Rc`
//!
//! This crate provides a doubly-linked list implementation for
//! circumstances where `Rc` is suitable for managing the individual
//! nodes.
//!

//  Copyright (C) 2019-2022 Ian Jackson
//
//  This program is free software: you can redistribute it and/or modify
//  it under the terms of the GNU General Public License as published by
//  the Free Software Foundation, either version 3 of the License, or
//  (at your option) any later version.

//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program.  If not, see <http://www.gnu.org/licenses/>.

//! How to use this crate
//! =====================
//!
//! See the [module-level documentation](dlist/index.html)
//! 
//! When not to use this crate
//! ==========================
//!
//! Many programmers new to Rust look for a linked list when another
//! data structure is better.  Consider `Vec` and `VecDeque`.
//! A doubly-linked list is good if:
//!
//!  * You need to retain and store, long-term, a reference to the
//!    middle of your list, and you need quick access to the
//!    corresponding item, *and*
//!
//!  * You need to be able to quickly add or remove items in the
//!    middle of your list, based on such references; or your
//!    references into the middle of the list must remain valid even
//!    as you add or remove other items elsewhere in the middle, *and*
//!
//!  * Your lists might be long.
//!
//! In other circumstances, which is most circumstances, you
//! probably wanted `Vec` or `VecDeque` instead.  They have much lower
//! overhead and are simpler to work with.
//!
//! In particular:
//!
//!  * If you don't need to add/remove items in the middle, then a
//!    `Vec` or `VecDeque` works well.  You can use array indices as
//!    your references.
//!
//!  * If you want a `VecDeque` with stable indices, this can be
//!    achieved by maintaining a signed counter of elements
//!    pushed/popped at the start, as done by
//!    [`vecdeque-stableix`](https://lib.rs/crates/vecdeque-stableix).
//!
//!  * If you don't need to retain long-term references to the middle
//!    of the list, then you can use a vector.  Adding or removing
//!    items in the middle does mean copying to shuffle items up or
//!    down, but if you aren't keeping a reference to the modification
//!    location you will have to walk along to find the right place
//!    anyway.
//!
//! Note that there are a number of deque-ish alternatives to
//! <code>std::VecDeque</code> which are not doubly linked lists and
//! do not aim to support modification in the middle of the list,
//! at least some of which seem like they might be useful.
//! Search crates.io for <kbd>deque</kbd>,
//! and also consider <a href="https://lib.rs/crates/blist"><code>blist</code></a>.
//!
//! Other doubly-linked list libraries
//! ==================================
//!
//! If you do need a doubly-linked list, but do not need your items to
//! be on more than one list at once, consider
//! [`generational_token_list`](https://lib.rs/crates/generational_token_list)
//! instead.
//! It has a much simpler ownership model and will be faster too.
//!
//! If you want each item to be able to be on more than one list at
//! once (perhaps even selecting the linked list link within each
//! node dynamically at runtime), then this crate
//! `rc-dlist-deque` may be what you want.
//!
//! Survey of available Rust doubly linked lists, compared to VecDeque
//! ------------------------------------------------------------------
//!
//! (This table is rendered rather poorly by Rustdoc, lib.rs, etc.
//! Use the
//! [correctly formatted version](https://www.chiark.greenend.org.uk/~ianmdlvl/rc-dlist-deque/) 
//! built standalone with pandoc, instead.)
//!
//! <style>
//!   table.dlist_survey th,
//!   table.dlist_survey td {
//!     border-top-color: black;
//!     border-bottom-color: black;
//!     border-left-color: black;
//!     border-right-color: black;
//!     border: 1px solid;
//!     text-align: center;
//!     vertical-align: middle;
//!   }
//! </style>
//! <table rules=all class="dlist_survey">
//!   <tr>
//!     <th rowspan=2>Crate or module</th>
//!     <th colspan=4>Ref to element (aka Index or Cursor)</th>
//!     <th rowspan=2>Other misuse possible, and consequences</th>
//!     <th rowspan=2>List owns (<code>T</code> is element type)</th>
//!     <th colspan=2>Cost of editing in middle</th>
//!     <th rowspan=2>Memory locality</th>
//!     <th rowspan=2>Element can be on multiple lists</th>
//!     <th rowspan=2>API complete&shy;ness</th>
//!     <th rowspan=2><code>Send/&#8203;Sync</code></th>
//!     <th rowspan=2>Safety</th>
//!     <th rowspan=2>Comments</th>
//!   </tr>
//!   <tr>
//!     <th>Type</th>
//!     <th>After altering list at front/&#8203;back</th>
//!     <th>After altering list in middle</th>
//!     <th>After removing ref'd element</th>
//!     <th>Given ref to elem</th>
//!     <th>Without ref to elem</th>
//!   </tr>
//!   <tr>
//!     <th colspan=14>Choose one of these approaches</th>
//!   </tr>
//!   <tr>
//!     <td><a href="https://doc.rust-lang.org/std/collections/struct.VecDeque.html"><code>std VecDeque</code></a><br>(or another deque library)</td>
//!     <td><code>usize</code><br>position</td>
//!     <td>wrong element if alteration at start</td>
//!     <td colspan=2>wrong element (or <code>None</code> or panic)</td>
//!     <td>Rich API can invalidate indices</td>
//!     <td rowspan=2><code>T</code></td>
//!     <td rowspan=2>O(n)</td>
//!     <td rowspan=5>O(n)</td>
//!     <td>sequential</td>
//!     <td>-</td>
//!     <td>++</td>
//!     <td>Yes</td>
//!     <td>Good</td>
//!     <td><strong>Use if you don't need persistent cursors</strong></td>
//!   </tr>
//!   <tr>
//!     <td><a href="https://lib.rs/crates/vecdeque-stableix"><code>vecdeque-stableix</code></a></td>
//!     <td><code>i64 isize</code> ...</td>
//!     <td>valid</td>
//!     <td colspan=2>not supported</td>
//!     <td>Index can overflow, giving panics.</td>
//!     <td>sequential</td>
//!     <td>-</td>
//!     <td>+</td>
//!     <td>Yes</td>
//!     <td>Safe</td>
//!     <td>Consider if you need to modify only at ends</td>
//!   </tr>
//!   <tr>
//!     <td><a href="dlist/index.html"><code>rc-dlist-deque</code></a></td>
//!     <td><code>Pointer&#8203;&lt;L,S&gt;</code></td>
//!     <td>valid</td>
//!     <td>valid</td>
//!     <td>valid</td>
//!     <td>Specify wrong list for alteration: <code>debug_assert</code>, "tangling"</td>
//!     <td><code>Rc&lt;T&gt;</code></td>
//!     <td rowspan=3>O(1)</td>
//!     <td>scattered to heap</td>
//!     <td>Yes</td>
//!     <td>+</td>
//!     <td>-</td>
//!     <td>Safe</td>
//!     <td>Consider if you need each element on multiple lists</td>
//!   </tr>
//!   <tr>
//!     <td><a href="https://lib.rs/crates/generational_token_list"><code>generational_token_list</code></a></td>
//!     <td><code>ItemToken</code><br>slot+gen.</td>
//!     <td rowspan=2>valid</td>
//!     <td rowspan=2>valid</td>
//!     <td rowspan=2>reliably <code>None</code> (<code>[]</code> panics)</td>
//!     <td rowspan=2>Specify wrong list for access or alteration: Maybe detected by luck, giving <code>None</code>, otherwise wrong element</td>
//!     <td rowspan=2><code>T</code></td>
//!     <td rowspan=2>random order in vector</td>
//!     <td rowspan=2>-</td>
//!     <td>++</td>
//!     <td rowspan=2>Yes</td>
//!     <td rowspan=2>Safe (exc.&#8203;<code>IterMut</code>)</td>
//!     <td rowspan=2><strong>Otherwise, use one of these</strong></td>
//!   </tr>
//!   <tr>
//!     <td><a href="https://lib.rs/crates/dlv-list"><code>dlv-list</code></a></td>
//!     <td><code>Index&#8203;&lt;T&gt;</code><br>slot+gen.</td>
//!     <td>++</td>
//!   </tr>
//!   <tr>
//!     <th colspan=14>Use <code>generational_token_list</code> or <code>dlv-list</code> instead of any of the following</th>
//!   </tr>
//!   <tr>
//!     <td><a href="https://lib.rs/crates/chainlink"><code>chainlink</code></a></td>
//!     <td><code>Index</code><br>slot+gen.</td>
//!     <td rowspan=5>valid</td>
//!     <td rowspan=5>valid</td>
//!     <td rowspan=2>reliably <code>None</code></td>
//!     <td rowspan=7>Specify wrong list for access or alteration: Maybe detected by luck, giving <code>None</code>, otherwise wrong element</td>
//!     <td rowspan=3><code>T</code></td>
//!     <td rowspan=3>O(1)</td>
//!     <td rowspan=8>O(n)</td>
//!     <td rowspan=3>random order in vector</td>
//!     <td>-</td>
//!     <td>-</td>
//!     <td>Yes</td>
//!     <td>Safe</td>
//!     <td rowspan=2>No <code>IterMut</code>; otherwise plausible</td>
//!   </tr>
//!   <tr>
//!     <td><a href="https://lib.rs/crates/indexlist"><code>indexlist</code></a></td>
//!     <td><code>Index&#8203;&lt;T&gt;</code><br>slot+gen.</td>
//!     <td>-</td>
//!     <td>-&nbsp;-</td>
//!     <td>Yes</td>
//!     <td>Safe</td>
//!   </tr>
//!   <tr>
//!     <td><a href="https://lib.rs/crates/index_list"><code>index_list</code></a></td>
//!     <td><code>Index</code><br>slot</td>
//!     <td rowspan=3><code>None</code> (or panic), or (later) wrong element</td>
//!     <td>-</td>
//!     <td>+</td>
//!     <td>Yes</td>
//!     <td>Safe</td>
//!   </tr>
//!   <tr>
//!     <td><a href="https://lib.rs/crates/slabigator"><code>slabigator</code></a></td>
//!     <td><code>usize</code><br>slot</td>
//!     <td><code>T</code></td>
//!     <td>O(1)</td>
//!     <td>random order in vector</td>
//!     <td>-</td>
//!     <td>-</td>
//!     <td>Yes</td>
//!     <td>uses <code>unsafe</code></td>
//!     <td rowspan=2><code>usize</code> slot indices are a poor API choice</td>
//!   </tr>
//!   <tr>
//!     <td><a href="https://lib.rs/crates/array-linked-list"><code>array-linked-list</code></a></td>
//!     <td><code>usize</code><br>slot</td>
//!     <td><code>T</code></td>
//!     <td>O(1)</td>
//!     <td>random order in vector</td>
//!     <td>-</td>
//!     <td>+</td>
//!     <td>Yes</td>
//!     <td>needless <code>unsafe</code></td>
//!   </tr>
//!   <tr>
//!     <td><code><a href="https://lib.rs/crates/im">im</a>/<a href="https://lib.rs/crates/im-rc">im-rc</a> <a href="https://docs.rs/im/latest/im/struct.Vector.html">Vector</a></code></td>
//!     <td rowspan=2><code>usize</code><br>position</td>
//!     <td rowspan=2>wrong element if alteration at start</td>
//!     <td rowspan=2 colspan=2>wrong element (or <code>None</code> or panic)</td>
//!     <td><code>T</code></td>
//!     <td>O(log(n))</td>
//!     <td>chunks in heap</td>
//!     <td>-</td>
//!     <td>+</td>
//!     <td><code>im</code></td>
//!     <td>uses <code>unsafe</code></td>
//!     <td rowspan=2><code>usize</code> position indices are a correctness hazard</td>
//!   </tr>
//!   <tr>
//!     <td><a href="https://lib.rs/crates/skip-linked-list"><code>skip-linked-list</code></a></td>
//!     <td><code>T</code></td>
//!     <td>O(log(n))</td>
//!     <td>scattered to heap</td>
//!     <td>-</td>
//!     <td>-</td>
//!     <td>-</td>
//!     <td>uses <code>unsafe</code></td>
//!   </tr>
//!   <tr>
//!     <td><a href="https://lib.rs/crates/cddl"><code>cddl</code></a></td>
//!     <td><code>Cursor</code>, <code>DoubleCursor</code></td>
//!     <td>valid</td>
//!     <td>valid</td>
//!     <td>not supported</td>
//!     <td></td>
//!     <td><code>T</code></td>
//!     <td>O(1)</td>
//!     <td>scattered to heap</td>
//!     <td>-</td>
//!     <td>-&nbsp;-&nbsp;-</td>
//!     <td>-</td>
//!     <td>uses <code>unsafe</code></td>
//!     <td>Strange and limited API</td>
//!   </tr>
//!   <tr>
//!     <th colspan=14>Use VecDeque instead of any of the following</th>
//!   </tr>
//!   <tr>
//!     <td><code><a href="https://lib.rs/crates/intrusive-collections"><code>intrusive-collections</a> <a href="https://docs.rs/intrusive-collections/latest/intrusive_collections/linked_list/index.html">linked_&#8203;list</a></code></td>
//!     <td><code>Cursor</code>&#8203;[<code>Mut</code>]</td>
//!     <td rowspan=8 colspan=4>Mutation not possible while
//!     any other cursor exists (prevented by lifetimes).  This almost entirely defeats the point of using a doubly
//!     linked list.</td>
//!     <td>Various</td>
//!     <td rowspan=7>O(1)</td>
//!     <td rowspan=13>O(n)</td>
//!     <td>scattered to heap</td>
//!     <td>Yes</td>
//!     <td>+</td>
//!     <td>Yes</td>
//!     <td>uses <code>unsafe</code></td>
//!     <td rowspan=12>If this API is enough for you, use <code>VecDeque</code> instead</td>
//!   </tr>
//!   <tr>
//!     <td><code><a href="https://lib.rs/crates/cordyceps">cordyceps</a> <a href="https://docs.rs/cordyceps/latest/cordyceps/struct.List.html">List</a></code></td>
//!     <td><code>Cursor</code>&#8203;[<code>Mut</code>] (roughly)</td>
//!     <td><code>unsafe impl Handle</code></td>
//!     <td>scattered to heap</td>
//!     <td>-</td>
//!     <td></td>
//!     <td>Yes</td>
//!     <td><code>unsafe</code> to use!</td>
//!   </tr>
//!   <tr>
//!     <td><a href="https://lib.rs/crates/tsil_cev"><code>tsil_cev</code></a></td>
//!     <td><code>Cursor</code>&#8203;[<code>Mut</code>]</td>
//!     <td><code>T</code></td>
//!     <td rowspan=2>random order in vector</td>
//!     <td>-</td>
//!     <td></td>
//!     <td>Yes</td>
//!     <td>Safe (exc.&#8203;<code>IterMut</code>)</td>
//!   </tr>
//!   <tr>
//!     <td><a href="https://lib.rs/crates/ixlist"><code>ixlist</code></a></td>
//!     <td><code>Cursor<code/></td>
//!     <td><code>T</code></td>
//!     <td>-</td>
//!     <td>+</td>
//!     <td>Yes</td>
//!     <td>needless <code>unsafe</code></td>
//!   </tr>
//!   <tr>
//!     <td><a href="https://lib.rs/crates/linked-list"><code>linked-list</code></a></td>
//!     <td><code>Cursor</code></td>
//!     <td><code>T</code></td>
//!     <td>scattered to heap</td>
//!     <td>-</td>
//!     <td></td>
//!     <td>Yes</td>
//!     <td>uses <code>unsafe</code></td>
//!   </tr>
//!   <tr>
//!     <td><a href="https://lib.rs/crates/cyclic_list"><code>cyclic_list</code></a></td>
//!     <td><code>Cursor</code>&#8203;[<code>Mut</code>]</td>
//!     <td><code>T</code></td>
//!     <td>scattered to heap</td>
//!     <td></td>
//!     <td></td>
//!     <td>Yes</td>
//!     <td>uses <code>unsafe</code></td>
//!   </tr>
//!   <tr>
//!     <td><a href="https://lib.rs/crates/pin-list"><code>pin-list</code></a></td>
//!     <td><code>Cursor</code>&#8203;[<code>Mut</code>]</td>
//!     <td>Complicated</td>
//!     <td>user provides <code>Pin&lt;&amp;mut Node&gt;</code></td>
//!     <td>-</td>
//!     <td></td>
//!     <td>Yes</td>
//!     <td>uses <code>unsafe</code></td>
//!   </tr>
//!   <tr>
//!     <td><a href="https://lib.rs/crates/key-node-list"><code>key-node-list</code></a></td>
//!     <td><code>Cursor</code>&#8203;[<code>Mut</code>]</td>
//!     <td><code>T</code></td>
//!     <td>O(log(n))</td>
//!     <td>in vector (via <code>HashMap</code>)</td>
//!     <td>-</td>
//!     <td>-</td>
//!     <td>Yes</td>
//!     <td></td>
//!   </tr>
//!   <tr>
//!     <td><a href="https://doc.rust-lang.org/std/collections/struct.LinkedList.html"><code>std LinkedList</code></a></td>
//!     <td rowspan=5 colspan=4>Not supported.  This defeats the point of using a doubly
//!     linked list.</td>
//!     <td></td>
//!     <td><code>T</code></td>
//!     <td rowspan=5>n/a</td>
//!     <td>scattered to heap</td>
//!     <td>-</td>
//!     <td></td>
//!     <td>Yes</td>
//!     <td></td>
//!   </tr>
//!   <tr>
//!     <td><a href="https://lib.rs/crates/doubly"><code>doubly</code></a></td>
//!     <td></td>
//!     <td><code>T</code></td>
//!     <td>scattered to heap</td>
//!     <td>-</td>
//!     <td></td>
//!     <td>Yes</td>
//!     <td>uses <code>unsafe</code></td>
//!   </tr>
//!   <tr>
//!     <td><a href="https://lib.rs/crates/linked_lists_rs"><code>linked_lists_rs</code></a> / <a href="https://lib.rs/crates/rust_linked_list"><code>rust_linked_list</code></a></td> 
//!     <td></td>
//!     <td><code>T</code></td>
//!     <td>scattered to heap</td>
//!     <td>-</td>
//!     <td></td>
//!     <td>Yes</td>
//!     <td>uses <code>unsafe</code></td>
//!   </tr>
//!   <tr>
//!     <td><a href="https://lib.rs/crates/xor_list"><code>xor_list</code></a></td> 
//!     <td></td>
//!     <td><code>T</code></td>
//!     <td>scattered to heap</td>
//!     <td>-</td>
//!     <td></td>
//!     <td>-</td>
//!     <td>uses <code>unsafe</code></td>
//!   </tr>
//!   <tr>
//!     <td><a href="https://lib.rs/crates/index_queue"><code>index_queue</code></a></td>
//!     <td></td>
//!     <td><code>T</code></td>
//!     <td>sequential</td>
//!     <td>-</td>
//!     <td>-&nbsp;-</td>
//!     <td>Yes</td>
//!     <td></td>
//!     <td>Reimplementation of <code>VecDeque</code></td>
//!   </tr>
//! </table>
//! <p>
//!
//! It can be hard to implement `IterMut` without using
//! `unsafe` , so no criticism is intended for those crates
//! that use unsafe for this.
//!
//! ### Not considered
//!
//! #### Single-ended, or special purpose)
//!
//! Not considered here because they are a single-ended list
//! (so there is little reason to use anything but a `Vec`);
//! or because they are special purpose:
//!
//! `c_linked_list`,
//! `char-list`,
//! `concurrent_list`,
//! `cons-list`,
//! `doubly_linked_list`,
//! `fplist`,
//! `functional_list`,
//! `fwdlist`,
//! `im-list`,
//! `linked_hash_map`,
//! `linked_hash_set`,
//! `linked_list_allocator`,
//! `linked-tail-list`,
//! `list`,
//! `moonlight_collections`,
//! `nerdondon-hopscotch`,
//! `nt_list`,
//! `persistent-list`,
//! `rose_bloom`,
//! `secured_linked_list`,
//! `simple-stack`,
//! `stack_list`,
//! `static-linkedlist`,
//! `weak-list2`,
//! `uell`,
//! `unrolled_linked_list`.
//!
//! #### Not intended (or not suitable) for general use
//!
//! Not considered here because of poor or missing docs, very poor API,
//! Nightly-only, won't build,
//! or other indications that
//! they're not intended (or suitable) for use by the world in general:
//!
//! `cll`,
//! `clist`,
//! `double_linkedlist`,
//! `dynalist`,
//! `ilist`,
//! `linkedlist`,
//! `rs_trie`,
//! `static-linkedlist`,
//! `matecito-dll`.
//!
//! ### Survey colophon
//!
//! Last updated, and last resurveyed, November 2022.
//! If I do a future survey, I may look at only the most popular crates.
//! Please let me know if you think your library ought to be
//! listed in the section "Choose one of these approaches".
//!
//! Changelog and colophon for `rc-dlist-deque`
//! ===========================================
//! 
//! Minimum Supported Rust Version is 1.31.0.
//! MSRV policy:
//! We do not anticipate changing the MSRV in the foreseeable future.
//! If we do, it will be at least a minor version bump.
//! We will not increase the MSRV beyond that available in Debian oldstable.
//!
//! #### 1.1.2
//! 
//!  * Minor updates to doubly linked list survey (crate level docs).
//!  * No API or implementation changes.
//! 
//! #### 1.1.1
//! 
//!  * Minor updates to doubly linked list survey (crate level docs).
//!  * No API or implementation changes.
//! 
//! #### 1.1.0
//! 
//!  * **MSRV 1.31.0** (was 1.30.0)
//!  * Change to 2018 edition.
//!  * Add this Changelog.
//!  * Update doubly linked list survey (crate level docs).
//!  * Changes to documentation generation and release arrangements.
//! 
//! #### 1.0.0
//!
//!  * Documentation.  No API or implemnetation changes.
//! 
//! #### 0.1.0
//! 
//!  * First public release.
//!
//! `rc-dlist-deque` is Copyright 2019-2022 Ian Jackson.
//! GNU GPLv3+; NO WARRANTY.

pub mod dlist;