rc-dlist-deque 1.1.1

//
// rc-dlist-deque - doubly linked list for Rust
//
//  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/>.


//! See the <a href="../index.html">crate-level documentation</a>
//! for a discussion of whether to use this crate.
//!
//! Concepts
//! ========
//!
//! Your data structure is a collection of `Rc<N>`, where `N` is the
//! **node** type.  The node type `N` contain the list **link**(s).
//! The link type is defined by `rc_dlist_deque` (and, inside,
//! contains the back/next pointers).  Each link may be on one
//! **list**, or on none.
//!
//! A **pointer** is a reference to a node, qua one of its potential
//! list memberships.  I.e., it specifies both the node and the link.
//! It is not null.  Another way to look at it is that it is a
//! reference to a specific link within a specific node.
//!
//! A **cursor** is `Some(pointer)` or `None`.  It is used whenever
//! a pointer might be null.
//!
//! The nodes are not mutable, since they are inside `Rc`.
//! (The dlist implementation uses `std::cell:Cell` for interior mutability.)
//!
//! When each node can only be on one list (at once)
//! ------------------------------------------------
//!
//! If all you need is a simple list where each node is on at most one list
//! at once, you can use the convenience types `Node1<T>` and `List1<T>`
//! where `T` is your own data type.  A `Node1` is simply your `T` plus the
//! list link.
//!
//! Often `T` will be, or contain, a `RefCell` or `Cell`, since the nodes
//! themselves are not mutable.
//!
//! `Pointer1<T>` then represents a pointer to a node.  It is a newtype
//! wrapper for `Rc<Node1<T>>`.  Its type indicates its use as a list
//! pointer with
//! `Node1<T>` and `List1<T>`.  Also relevant is `Option<Pointer1<T>>`
//! (also known as `Cursor1<T>`) which is used for pointers which might
//! be null.
//!
//! When each node can be on multiple lists
//! ---------------------------------------
//!
//! If you want to do something more sophisticated, you should
//! use the types `List<N,S>` and `Node<N,S>`.
//!
//! You should define your own node type `N` containing one or more
//! `Link<N,S>`.
//!
//! You also need to define a type `S`, the **selector**.  Its type
//! and value identifies one of the links in a node.
//!
//! Simple, static, link selection
//! - - - - - - - - - - - - - - - 
//!
//! Suppose at each point you know statically which `Link` is to be
//! operated on, and it's the same in in all involved nodes.  Ie,
//! while you have different classes of list, and multiple links in
//! each node, each link in each node belongs to one of the list
//! classes.
//!
//! Then you want the different links and the corresponding lists to
//! have distinct types.  The intended link node is then identified by
//! the type system.
//!
//! In this case: for each link which appears in your node, define a
//! empty struct type (let us call it `FooSelector`).  It should
//! derive `Debug,Copy,Clone,PartialEq,Eq,Default`.  Use the
//! `DlistImplSelector` macro.  Then the corresponding types
//! are `List<N,FooSelector>`, `Pointer<N,FooSelector>` and
//! `Link<N,FooSelector>`.
//!
//! Run-time dynamic link selection
//! - - - - - - - - - - - - - - - -
//!
//! If you need to specify at run-time which link to use, you must
//! provide a nontrivial selector type `S`, which is the actual value
//! indicating which `Link` to use.
//! 
//! `S` must implement `Selector`.  It can still be helpful to use the
//! `DlistImplSelector` helper macro to provide the trait
//! implementation.
//!
//! The selector value may be different in different nodes on the same
//! list.  (Ie, the link contains not only the Rc references to the
//! nodes, but <code>Pointer</code>s, including both
//! <code>Selector</code>s.)  `S` must be `Copy`.
//!
//! Entrypoints
//! ===========
//!
//! Most of the useful functions are methods on `List`,
//! with a few on `Pointer` and `ListIterator`.
//!
//! Many of the methods take a parameter like `rev : bool` or `tail : bool`
//! or `after : bool`.  These are bidirectional methods: they can
//! operate in either direction, as specified.  Generally `false`
//! means forwards, or at the beginning.
//!
//! Ownership
//! =========
//!
//! A node which is on a list has a (strong) `Rc` reference owned by
//! the list.  Dropping a list will implictly remove all the items and
//! drop those references; whether that drops the nodes depends on
//! whether there are other references, as would be expected for `Rc`.
//!
//! Tangling and panics
//! ===================
//!
//! Linked lists can get tangled, for example if you put a node
//! on a list and then, without removing it from the first list,
//! insert it into another list.
//! It is the user's responsibility to know whether a node is on a
//! list, and what list it is on, and only to make appropriate calls.
//!
//! The specific requirements are indicated in each case a section
//! like this in each relevant function description:
//!
//! >  Panics, or tangles the list(s)
//!
//! **Any operation on a tangled list may panic**; tangled lists
//! can also result in infinite loops.
//!
//! When debug assertions are enabled, the library will nearly always
//! detect when a list is about to be tangled and panic immediately.
//! When debug assertions are disabled the additional records
//! needed for this are compiled out, and tangling a list may go
//! undetected, and result in panics some considerable time later.
//!
//! However, this library contains only safe Rust.  So while tangled
//! lists can result in panics and algorithmic malfunctions, they
//! cannot result in undefined behaviour.

#![allow(unused_macros)]
#![allow(dead_code)]

use std::rc::Rc;
use std::cell::Cell;
use std::marker::PhantomData;
use std::fmt;
use std::fmt::Formatter;
use std::result::Result;
use std::default::Default;

// ----- types and the public DefineListEntry macro -----

pub type Cursor<N,S> = Option<Pointer<N,S>>;

type ListID = (std::thread::ThreadId, usize);

/// In a node, its potential membership of a list.
///
/// At least one of these should appear in each node.
///
/// Not needed with `Node1`, where this is implicit.
///
/// ```struct Link<N,S> where S : Selector<Node=N>```
pub struct Link<N, S> where S : Selector<Node=N> {
    pn : [ Cell<Cursor<N, S>> ; 2 ],
    #[cfg(debug_assertions)] busy : Cell<Option<ListID>>,
}

/// The general list type.
///
/// Use `List1` if each node only needs to be on one list a time.
///
/// ```struct List<N, S> where S : Selector<Node=N>```
pub struct List<N, S> where S : Selector<Node=N> {
    ht : [ Cursor<N, S> ; 2 ],
    #[cfg(debug_assertions)] id : ListID,
}

/// Reference to a node, with respect to its potential membership
/// of a list.
///
/// If the node can be a member of multiple lists,
/// a reference to a specific one of its potential memberships.
/// (Another way to look at this is that a pointer is a reference
/// to a particular link within a node.)
///
/// May be kept persistently in other data structures.
///
/// May point to an element which is not currently on a list,
/// but may not point to no element.
///
/// Holds an <code>Rc</code> onto the node.
pub struct Pointer<N, S> where S : Selector<Node=N> + Clone {
    node : Rc<N>, // Do not simply change this to Arc<> - see below
    selector : S,
}
// Note on thread safety.
//
// This whole module is not thread safe.  The core list manipulation
// code is not suitable for simply wrapping up in a mutex and hoping,
// at least not without thought.  So although it looks like you
// might be able to make this threadsafe by switching from Rc to
// Arc and from Cell to some mutex, this will not work properly
// unless you also consider lock lifetime wrt the list manipulations
// (which might otherwise tangle lists on concurrent access)
// and lock hierarchy (to avoid deadlock).

/// Iterator (forwards) through the list.
///
/// Care must be taken if the list is modified while the iterator
/// exists: the iterator keeps a reference to the next item to be
/// returned.  If that item is removed from the list, and maybe put
/// onto some other list, the iterator will continue with that item,
/// and, thereeafter, whatever its successors are on whatever list it
/// ends up on.
///
/// However, a consequece is: it _does_ work to iterate over a list,
/// sometimes removing the item returned by the iterator.
/// Also, modification of the list while it is being iterated over will not
/// lead to panics, or undefined behaviour --- only possible
/// unexpected results.
///
/// (This is actually a wrapper around a `Cursor`: pointing
/// to the next element to be returned, or `None`.)
pub struct ListIterator<N,S : Selector<Node=N>> (Cursor<N,S>);

/// It is not often necessary to implement this directly.
/// Use `List1`, `Node1` etc. if you can.
/// If your nodes need to a member of multiple lists,
/// use [DlistImplSelector!](../macro.DlistImplSelector.html)
pub trait Selector : Sized + Copy {
    type Node;
    fn link(node : &Self::Node, selector : Self) -> &Link<Self::Node, Self>;
}


/// Should write a suffix suitable for printing after `{:p}`.
/// Used when Pointer is printed with `{:p}`.
pub trait SelectorFmt : Selector {
    fn fmt(&self, f : &mut Formatter) -> Result<(), fmt::Error>;
}

/// `DlistDefineStaticSelector!( `_SELTYPE_`,` _NODE_` [` _MEMBS_ `]);`
///
/// For setting up nodes which can each be a member of multiple lists,
/// witb the link within each node identified at compile time.
///
/// Arranges that _NODE_ can be part of a `List` by virtue of it
/// containing a `Link`.  Defines _SELTYPE_ as an empty struct
/// implementing `Selector` (and `Copy,Default,...`).
///
/// _MEMBS_ is zero or more field selectors (each preceded by
/// the `.`), array indices, etc., to find a `Link` inside _NODE_.
/// _MEMBS_ must be surrounded by literal `[` and `]` for
/// macro parsing reasons.
/// 
/// This macro
/// constructs the expression (_somenode MEMBS_) where
/// _somenode_ is a reference to a _NODE_, and expects that expression
/// to name a `Link<`_NODE,SELTYPE_`>` within _somenode_.
///
/// You will need to implement `SelectorFmt` for _SELTYPE_
/// to be able to debug format `Pointer<`_NODE,SELTYPE_`>`
#[macro_export]
macro_rules! DlistDefineStaticSelector {
    ( $S:ident, $N:ty [ $($x:tt)* ]) => {
        #[derive(Debug,Copy,Clone,PartialEq,Eq,Default)]
        struct $S { }
        DlistImplSelector!($S, $N, _s [ $($x)* ]);
    }
}

/// `DlistImplSelector!( `[ `+(` _TYPEPARAMS_ `)`] _SELTYPE_`,` _NODE_`,` _SELVAR_ `[` _MEMBS_ `]);`
///
/// For setting up nodes which can each be a member of multiple lists,
/// where the link is identified at runtime.
///
/// (Usually when a node wants to potentially be a member of multiple
/// lists, the specific list membership is known at compile time.
/// In that case use `DlistDefineStaticSelector` if possible.)
///
/// Arranges that _NODE_ can be part of a `List` by virtue of it
/// containing a `Link` (or a particular collection of `Link`s).
/// (Implements `Selector` for _SELTYPE_.)
///
/// _SELTYPE_ is a selector
/// type (defined by you) which relates a node to one of its potential list
/// memberships.
///
/// If `+(`_TYPEPARAMS_`)` is specified at the beginning, _TYPEPARAMS_
/// is appended to `impl` in the macro expansion.
///
/// _MEMBS_ is zero or more field selectors (each preceded by
/// the `.`), array indices, etc., to find a `Link` inside _NODE_.
/// In _MEMBS_, _SELVAR_ (conventionally `s`), will be
/// an immutable local variable of type _SELTYPE_.
/// _MEMBS_ must be surrounded by literal `[` and `]` for
/// macro parsing reasons.
///
/// The macro
/// constructs the expression (_somenode MEMBS_) where
/// _somenode_ is a reference to _NODE_, and expects that expression
/// to name a `Link<`_NODE,SELTYPE_`>` within _somenode_.
///  If this is not suitable,
/// you should open-code an impleentation of `Selector` instead.
///
/// See the definition of `List1Selector` (in the source to this
/// module), and its call to
/// `DlistImplSelector!` for an example.
/// 
/// _SELTYPE_ must be `Copy`.  It is useful for it to be
/// `Debug`, `PartialEq`, and `SelectorFmt`.

#[macro_export]
macro_rules! DlistImplSelector {
    ($(+( $($typar:tt)* ))* $S:ty, $N:ty, $s:ident [ $($x:tt)* ])
        => {
        impl $( $($typar)* )* $crate::dlist::Selector for $S {
            type Node = $N;
            fn link(n : &$N, $s : $S) -> &Link<$N,$S> { &( n $($x)* ) }
        }
    }
}

// ----- pn and ht access, using types for (some) correctness-----

// We write a lot of code to work both `forwards' and `backwards'.
// In general in the public API we provide a parameter `rev' or `tail'
// which is a boolean.  In most of our own code we want to talk about
// HEAD and TAIL and PREV and NEXT.  So we write, say, HEAD^rev, to
// mean `HEAD, except if rev then TAIL'.
//
// This is enforced by the following arrangments:
// Each DefinePairArrayIndex defines something like
//    enum HT { HEAD, TAIL }
// The ^ operator can be used with a bool to flip it.  Flipping
// generates a PairArrayIndexGeneralised<HT>, which cannot be
// flipped again.  Array indexing is done with HT::index, which
// only takes a PairArrayIndexGeneralised<HT>.  This ensures
// flipping exactly once, and prevents use of PN instead of HT.
//
// Everyone here who accesses pn or ht should either use ::index,
// or must be vetted to DTRT.  But, usually, accesses are done
// via the macros get! etc.
macro_rules! DefinePairArrayIndex {
    { $Enum:ident; $False:ident; $True:ident } => {
        enum $Enum { $False, $True }
        use self::$Enum::{$False,$True};
        impl std::ops::BitXor<bool> for $Enum {
            type Output = PairArrayIndexGeneralised<$Enum>;
            fn bitxor(self, flip : bool) -> Self::Output {
                PairArrayIndexGeneralised(
                    ((self as usize) != 0) ^ flip,
                    std::marker::PhantomData,
                )
            }
        }
        impl $Enum {
            fn index(s : PairArrayIndexGeneralised<$Enum>) -> usize {
                s.0 as usize
            }
        }
    }
}
struct PairArrayIndexGeneralised<T> (bool, std::marker::PhantomData<T>);

DefinePairArrayIndex!{ HT; HEAD; TAIL }
DefinePairArrayIndex!{ PN; PREV; NEXT }

fn clone_option_cell<T:Clone>(c : &Cell<Option<T>>) -> Option<T> {
    let r = c.replace(None);
    c.set(r.clone());
    r
}

macro_rules! link {
    ($ptr:expr) => (<S as Selector>::link    (&$ptr.node, $ptr.selector))
}
macro_rules! get {
    ($ptr:expr, $pn:expr) => (
        clone_option_cell( &link!($ptr).pn[PN::index($pn)]) )
}
macro_rules! set {
    ($ptr:expr, $pn:expr, $nv:expr) => (
        link!($ptr).pn[PN::index($pn)].set($nv)
    )
}
macro_rules! end {
    ($list:expr, $ht:expr) => ( $list.ht[HT::index($ht)] )
}
macro_rules! setLinkB {
    ($ent:expr, $prev:expr,$next:expr, $rev:expr, $list:expr,) => (
        setLinkB!($ent,$prev,$next,$rev,$list)
    );
    ($ent:expr, $prev:expr,$next:expr, $rev:expr, $list:expr) => (
        set!($ent,PREV^$rev, $prev);
        set!($ent,NEXT^$rev, $next);
        #[cfg(debug_assertions)] { link!($ent).busy.set( Some($list.id) ) };
    )
}
macro_rules! setLinkI {
    ($ent:expr) => (
        set!($ent,PREV^false, None);
        set!($ent,NEXT^false, None);
        #[cfg(debug_assertions)] { link!($ent).busy.set(None) };
    )
}


#[cfg(debug_assertions)]
macro_rules! assert_busy{($p:expr,$i:expr)=>($p.debug_assert_busy(Some($i)) )}
macro_rules! assert_idle{($p:expr        )=>($p.debug_assert_busy(None    ) )}
#[cfg(not(debug_assertions))]
macro_rules! assert_busy{($p:expr,$i:expr)=>() }

// ----- other helpful macros -----

// turns
//   imp!{ N,S, [Trait for,] Type { ... } }
// into
//   impl<N, S : Selector<Node=N>> [Trait for,] Type { ... } }
// which saves typing.  Sadly, note the necessary spurious comma.
macro_rules! imp {
  { $N:ident, $LE:ident, $tr:path, for $T:ident { $($body:tt)* } } =>
  { impl<$N, $LE : Selector<Node=$N>> $tr for $T<$N, $LE> { $($body)* } };
  { $N:ident, $LE:ident, $T:ident { $($body:tt)* } } =>
  { impl<$N, $LE : Selector<Node=$N>>         $T<$N, $LE> { $($body)* } };
}

// ----- actual implementation! -----

imp!{ N,S, Link {
    /// Creates a new blank `Link` (ie one which is not on any list).
    pub fn new() -> Self { Link {
        pn : [ Cell::new(None), Cell::new(None) ],
        #[cfg(debug_assertions)] busy : Cell::new(None)
    } }
}}

imp!{ N,S, Pointer {
    /// Makes a pointer out of a reference to a node.
    ///
    /// Only possible where the selector type has a default value;
    /// eg, when called as `Pointer1::new`, or in other situations
    /// where the relevant link in each node is identified at compile-time.
    pub fn new(p : &Rc<N>) -> Pointer<N, S> where S : Default {
        Pointer::with_selector(p, Default::default())
    }
    /// Makes a pointer, with runtime link selection
    ///
    /// Given a reference `p` to a node, and `selector`,
    /// makes them into a pointer --- that is, a reference
    /// to the node but with respect to that specific possible
    /// list membership.
    pub fn with_selector(p : &Rc<N>, selector : S) -> Pointer<N, S> {
        Pointer { node : p.clone(), selector }
    }
    /// Consumes `data`, and returns a reference ready for use with a
    /// list.
    pub fn from_data(data : N, selector : S) -> Pointer<N, S> {
        Pointer { node : Rc::new(data), selector }
    }
    /// Returns the selector portion of the pointer.
    pub fn selector(&self) -> S { self.selector }

    /// `true` iff the pointers are equal.
    ///
    /// Ie, if they both point to the same node and (with runtime link
    /// selection) have the same selector.  Ie, they both refer to the
    /// same link within the same node.
    pub fn ptr_eq(a : &Pointer<N,S>, b : &Pointer<N,S>) -> bool
        where S : PartialEq
    {
        Rc::ptr_eq(&a.node, &b.node) && a.selector == b.selector
    }

    /// `true` iff both pointers are equal, or both are null (`None`).
    pub fn cursor_eq(a : &Cursor<N,S>, b : &Cursor<N,S>) -> bool
        where S : PartialEq
    {
        match (a, b) {
            (None,        None       ) => true,
            (Some(ref a), Some(ref b)) => Pointer::ptr_eq(a,b),
            _                          => false,
        }
    }

    /// Returns an iterator starting here
    ///
    /// The iterator will process the entry referred to by
    /// `self`, and subsequent entries.
    pub fn iter_at(&self) -> ListIterator<N,S> { ListIterator(
        Some(self.clone())
    )}

    /// Returns a cursor pointing to the next or previous item.
    pub fn get_next_prev(&self, rev : bool) -> Cursor<N,S> {
        get!(self,NEXT^rev)
    }

    #[allow(unused_variables)]
    fn debug_assert_busy(&self, expected : Option<&ListID>) {
        #[cfg(debug_assertions)] {
            let got = link!(self).busy.get();
            debug_assert_eq!(got.as_ref(), expected);
        }
    }
}}

fn set_next_prev<N,S : Selector<Node=N>> (
    of : &Pointer<N,S>,
    to : Cursor<N,S>,
    head : &mut List<N,S>,
    rev : bool
) {
    match get!(of,NEXT^rev) {
        None => {
            end!(head,TAIL^rev) = to;
        },
        Some(ref next) => {
            set!(next,PREV^rev, to);
        },
    }
}

imp!{ N,S, List {
    pub fn new() -> Self {
        List { ht : [ None, None],
               #[cfg(debug_assertions)] id : {
                   use std::cell::Cell;
                   thread_local!{
                       static COUNTER : Cell<usize> = Cell::new(0);
                   }
                   (std::thread::current().id(),
                    COUNTER.with(|p| {
                        let r = p.get();
                        p.set(r + 1);
                        r
                    }))
               }
        }
    }

    pub fn is_empty(&self) -> bool { end!(self,HEAD^false).is_none() }

    /// Get `Some` pointer to the first or last element, or `None`
    /// if the list is empty.
    pub fn first_last(&self, tail : bool) -> Cursor<N,S> {
        end!(self,HEAD^tail).clone()
    }
    pub fn first(&self) -> Cursor<N,S> { self.first_last(false) }
    pub fn last (&self) -> Cursor<N,S> { self.first_last(true ) }

    pub fn iter(&self) -> ListIterator<N,S> {
        ListIterator( self.first_last(false) )
    }

    /// Inserts `new_entry` into `self` before or after `locaation`.
    ///
    /// # Panics, or tangles the list(s):
    ///
    /// `new_entry` must not be on any list.
    ///
    /// `location` must be on `self` (and not on some other list).
    pub fn insert(&mut self,
                  new_entry : &Pointer<N,S>,
                  location : &Pointer<N,S>,
                  after : bool,
    )
    {
        assert_idle!(new_entry);
        assert_busy!(location, &self.id);
        setLinkB!(
            new_entry,
            get!(location, PREV^after),
            Some(location.clone()),
            after,
            self,
        );
        set!(location, PREV^after, Some(new_entry.clone()));
        set_next_prev(new_entry, Some(new_entry.clone()), self, !after);
    }

    /// Inserts `new_entry` at the start or end of the list.
    ///
    /// # Panics, or tangles the list(s):
    ///
    /// `new_entry` must not be on any list.
    pub fn push_at(&mut self, new_entry : &Pointer<N,S>, tail : bool) {
        assert_idle!(new_entry);
        setLinkB!(
            new_entry,
            None,
            end!(self,HEAD^tail).clone(),
            tail,
            self,
        );
        end!(self,HEAD^tail) = Some(new_entry.clone());
        set_next_prev(new_entry, Some(new_entry.clone()), self, tail);
    }
    pub fn push_front(&mut self, n : &Pointer<N,S>) { self.push_at(n,false) }
    pub fn push_back (&mut self, n : &Pointer<N,S>) { self.push_at(n,true ) }

    /// Removes the entry at the start or end of the list,
    /// returning `None` if the list is empty.
    pub fn pop_at(&mut self, tail : bool) -> Cursor<N,S> {
        let was = end!(self,HEAD^tail).clone();
        if let Some(ref node) = was {
            set_next_prev(node, None, self, tail);
            end!(self,HEAD^tail) = None;
            setLinkI!(node);
        }
        was
    }
    pub fn pop_front(&mut self) -> Cursor<N,S> { self.pop_at(false) }
    pub fn pop_back (&mut self) -> Cursor<N,S> { self.pop_at(true ) }

    /// Removes `item`.
    ///
    /// # Panics, or tangles the list:
    ///
    /// `item` must be on `self`.
    pub fn remove(&mut self, item : &Pointer<N,S>) {
        assert_busy!(item, &self.id);
        for &rev in &[false,true] {
            set_next_prev(item, get!(item,PREV^rev), self, rev);
        }
        setLinkI!(item);
    }

    pub fn clear(&mut self) {
        let mut node = end!(self,HEAD^false).clone();
        while node.is_some() {
            let inner = node.unwrap();
            let next_node = get!(inner,NEXT^false);
            setLinkI!(inner);
            node = next_node;
        }
        self.ht = [ None, None ];
    }
}}

imp!{N,S, Drop, for List {
    fn drop(&mut self) { self.clear() }
}}

//----- the iterator -----

imp!{ N,S, ListIterator {
    /// Moves the iterator one step.
    /// If the iterator has already reached the end, is a no-op.
    /// If the iterator's next pointer points at a node which
    /// is not in any list, `walk` will report that node and
    /// leave the iterator finished.
    pub fn walk(&mut self, rev : bool) {
        let c = self.0.as_ref().and_then(
            |p| p.get_next_prev(rev)
        );
        *self = ListIterator(c);
    }

    /// Returns the current node (the next node to be returned),
    /// if any, and then advances (or retards) the iterator.
    pub fn next_prev(&mut self, rev : bool) -> Cursor<N,S> {
        let was = self.0.clone();
        self.walk(rev);
        was
    }

    pub fn cursor(&self) -> Cursor<N,S> { self.0.clone() }

    // Converts an Option<Pointer> into a ListIterator
    pub fn from_cursor(c : Cursor<N,S>) -> Self { ListIterator(c) }
}}

imp!{ N,S, Iterator, for ListIterator {
    type Item = Pointer<N,S>;
    fn next(&mut self) -> Option<Pointer<N,S>> { self.next_prev(false) }
}}

imp!{ N,S, std::ops::Deref   , for ListIterator {
    type Target = Cursor<N,S>;
    fn deref    (&    self) -> &    Cursor<N,S> { &    self.0 }
}}
imp!{ N,S, std::ops::DerefMut, for ListIterator {
    fn deref_mut(&mut self) -> &mut Cursor<N,S> { &mut self.0 }
}}

imp!{ N,S, std::iter::FusedIterator, for ListIterator {
}}

impl<'l, N, S : Selector<Node=N>> IntoIterator for &'l List<N,S> {
    type Item = Pointer<N,S>;
    type IntoIter = ListIterator<N,S>;
    fn into_iter(self) -> ListIterator<N,S> { self.iter() }
}

//----- other convenience traits -----

// derive is too stupid to realise that Pointer is Clone even though
// N may not be.
imp!{ N,S, Clone, for Pointer {
    fn clone(&self) -> Self { Pointer { node : self.node.clone(), ..*self } }
}}

imp!{ N,S, std::ops::Deref, for Pointer {
    type Target = Rc<N>;
    fn deref    (&    self) -> &    Rc<N> { &    self.node }
}}

imp!{ N,S, std::ops::DerefMut, for Pointer {
    fn deref_mut(&mut self) -> &mut Rc<N> { &mut self.node }
}}

imp!{ N,S, Default, for Link   { fn default() -> Self { Link  ::new()  } }}
imp!{ N,S, Default, for List   { fn default() -> Self { List  ::new()  } }}

impl<N,S : Selector<Node=N> + SelectorFmt> fmt::Pointer for Pointer<N,S> {
    fn fmt(&self, f : &mut Formatter) -> Result<(), fmt::Error> {
        write!(f,"{:p}", self.node)?;
        SelectorFmt::fmt(&self.selector, f)?;
        Ok(())
    }
}
impl<N,S : Selector<Node=N> + fmt::Debug> fmt::Debug for Pointer<N,S> {
    fn fmt(&self, f : &mut Formatter) -> Result<(), fmt::Error> {
        write!(f,"Pointer({:p}, {:?})", &self.node, &self.selector)
    }
}

impl<N,S> From<Rc<N>> for Pointer<N,S>
where S : Default + Selector<Node=N> {
    fn from(p : Rc<N>) -> Pointer<N,S> { Pointer {
        node : p,
        selector : Default::default()
    }}
}

impl<'a,N,S> From<&'a Rc<N>> for Pointer<N,S>
where S : Default + Selector<Node=N>
{
    fn from(p : &Rc<N>) -> Pointer<N,S> { Self::from(p.clone()) }
}

impl<N,S : Default + Selector<Node=N>> From<N> for Pointer<N,S> {
    fn from(data : N) -> Pointer<N,S> { From::from( Rc::new( data ))}
}

// ----- convenience List1, Node1, Pointer1 -----

/// Simple list
///  - each node is only on one list
pub type List1<T> = List<Node1<T>,List1Selector<T>>;


/// Node on a simple list.
///
/// For when each node is only on one list.
///
/// `T` is your own data.  You will often want T to be a `Cell` or a
/// `RefCell`, since you won't generally have mutable access to it.
///
/// Normally you will refer to nodes via `Pointer1`,
/// which contains an `Rc<Node1>`, or via `Cursor1`,
/// which is `Option<Pointer1<_>>`
///
/// ```struct Node1<T>```
pub struct Node1<T> {
    data : T,
    ll : Link<
            Node1<T>,
            List1Selector<T>,
        >,
}

pub type Pointer1<T> = Pointer<Node1<T>,List1Selector<T>>;
pub type Cursor1<T> = Option<Pointer1<T>>;

/// Selector type for simple List1/Node1
///
/// You do not need to deal with this type directly.
#[derive(Eq,PartialEq,Debug)]
pub struct List1Selector<T> { marker : PhantomData<T> }
DlistImplSelector!(+(<T>) List1Selector<T>, Node1<T>, _s [ .ll ]);
// The PhantomData is needed because List1Selector is generic
// over the user's node type T.  For a fixed node type,
// and a fixed link entry within it, the selector can be a struct ().

impl<T> Default for List1Selector<T> {
    fn default() -> List1Selector<T> { List1Selector { marker : PhantomData } }
}
impl<T> SelectorFmt for List1Selector<T> {
    fn fmt(&self, _f : &mut Formatter) -> Result<(), fmt::Error> { Ok(()) }
}
impl<T> Copy for List1Selector<T> {
}
impl<T> Clone for List1Selector<T> {
    fn clone(&self) -> Self { *self }
}

impl<T> Node1<T> {
    /// Wraps up `data` into a node struct.
    ///
    /// You'll normally want `pointer` instead.
    pub fn new(data : T) -> Self {
        Node1 { data, ll : Default::default() }
    }
    /// Wraps up `data` into a node and an <code>Rc</code>,
    /// giving a pointer (a reference) ready to be put onto a list.
    pub fn pointer(data : T) -> Pointer1<T> { From::from( data ) }
}

impl<T> Default for Node1<T> where T : Default {
    fn default() -> Node1<T> { Node1::new( T::default() ) }
}

impl<T> std::ops::Deref    for Node1<T> {
    type Target = T;
    fn deref    (&    self) -> &    T { &    self.data }
}
impl<T> std::ops::DerefMut for Node1<T> {
    fn deref_mut(&mut self) -> &mut T { &mut self.data }
}


impl<T> From<T> for Pointer1<T> {
    fn from(data : T) -> Pointer1<T> {
        Pointer::new( &Rc::new( Node1::new( data )))
    }
}

mod test;