fn new(value: Value, down: LddIndex, right: LddIndex) -> Node {

        Node {

            value,

            down,

            right,

            marked: false,

        }

    }

    pub fn is_valid(&self) -> bool {

        true

    }

    fn eq(&self, other: &Self) -> bool {

        self.value == other.value && self.down == other.down && self.right == other.right

    }

    fn hash<H: Hasher>(&self, state: &mut H) {

        self.value.hash(state);

        self.down.hash(state);

        self.right.hash(state);

    }

    fn default() -> Self {

        Self::new()

    }

    pub fn new() -> Self {

        let shared = Rc::new(RefCell::new(ProtectionSet::new()));

        let mut nodes = IndexedSet::new();

        let empty_set = nodes.insert(Node::new(0, LddIndex::default(), LddIndex::default())).0;

        let empty_vector = nodes.insert(Node::new(1, LddIndex::default(), LddIndex::default())).0;

        Self {

            protection_set: shared.clone(),

            nodes,

            cache: OperationCache::new(Rc::clone(&shared)),

            count_until_collection: 10000,

            enable_garbage_collection: true,

            enable_performance_metrics: false,

            empty_set: Ldd::new(&shared, empty_set),

            empty_vector: Ldd::new(&shared, empty_vector),

        }

    }

    pub fn operation_cache(&mut self) -> &mut OperationCache {

        &mut self.cache

    }

    pub fn insert(&mut self, value: Value, down: &LddRef, right: &LddRef) -> Ldd {

        debug_assert_ne!(down, self.empty_set(), "down node can never be the empty set.");

        debug_assert_ne!(right, self.empty_vector(), "right node can never be the empty vector.");

        debug_assert!(*down.index() < self.nodes.len(), "down node not in table.");

        debug_assert!(*right.index() < self.nodes.len(), "right not not in table.");

        if right != self.empty_set() {

            debug_assert_eq!(

                height(self, down) + 1,

                height(self, right),

            debug_assert!(value < self.value(right), "value should be less than right node value.");

        }

        if self.count_until_collection == 0 {

        }

        let (index, _inserted) = self.nodes.insert(Node::new(value, down.index(), right.index()));

        Ldd::new(&self.protection_set, index)

    }

    pub fn protect(&mut self, ldd: &LddRef) -> Ldd {

        Ldd::new(&self.protection_set, ldd.index())

    }

    pub fn garbage_collect(&mut self) {

        let size_of_cache = self.cache.len();

        self.cache.clear();

        self.cache.limit(self.nodes.len());

        let mut stack: Vec<LddIndex> = Vec::new();

        for (_root, index) in self.protection_set.borrow().iter() {

            mark_node(&mut self.nodes, &mut stack, *index);

        }

        let mut number_of_collections: usize = 0;

        self.nodes.retain_mut(|_, node| {

            if node.marked {

                debug_assert!(node.is_valid(), "Should never mark a node that is not valid.");

                node.marked = false;

                true

                number_of_collections += 1;

                false

        });

        for (_, node) in &self.nodes {

            debug_assert!(

                *node.down == 0 || self.nodes.get(node.down).is_some(),

            debug_assert!(

                *node.right == 0 || self.nodes.get(node.right).is_some(),

        if self.enable_performance_metrics {

        }

    }

    pub fn empty_set(&self) -> &Ldd {

        &self.empty_set

    }

    pub fn empty_vector(&self) -> &Ldd {

        &self.empty_vector

    }

    pub fn value(&self, ldd: &LddRef) -> Value {

        self.verify_ldd(ldd);

        let node = &self.nodes[ldd.index()];

        node.value

    }

    pub fn get(&self, ldd: &LddRef) -> Data {

        self.verify_ldd(ldd);

        let node = &self.nodes[ldd.index()];

        Data(

            node.value,

            Ldd::new(&self.protection_set, node.down),

            Ldd::new(&self.protection_set, node.right),

        )

    }

    pub fn get_ref<'a>(&self, ldd: &'a LddRef) -> DataRef<'a> {

        self.verify_ldd(ldd);

        let node = &self.nodes[ldd.index()];

        DataRef(node.value, LddRef::new(node.down), LddRef::new(node.right))

    }

    fn verify_ldd(&self, ldd: &LddRef) {

        debug_assert_ne!(ldd, self.empty_set(), "Cannot inspect empty set.");

        debug_assert_ne!(ldd, self.empty_vector(), "Cannot inspect empty vector.");

        debug_assert!(

            self.nodes.get(ldd.index()).is_some(),

    }

    fn drop(&mut self) {

        if self.enable_performance_metrics {

        }

    }

fn mark_node(nodes: &mut IndexedSet<Node>, stack: &mut Vec<LddIndex>, root: LddIndex) {

    stack.push(root);

    while let Some(current) = stack.pop() {

        let node = &mut nodes[current];

        debug_assert!(node.is_valid(), "Should never mark a node that is not valid.");

        if node.marked {

            continue;

            node.marked = true;

            if *current != 0 && *current != 1 {

                stack.push(node.down);

                stack.push(node.right);

            }

    debug_assert!(stack.is_empty(), "When marking finishes the stack should be empty.");

}

    fn test_random_garbage_collection_small() {

        random_test(100, |rng| {

            let mut storage = Storage::new();

            {

                // Make sure that this set goes out of scope, but keep a reference to some child ldd.

                let vector = random_vector(rng, 10, 10);

                let ldd = singleton(&mut storage, &vector);

                _child = storage.get(&ldd).1;

                storage.garbage_collect();

            }

            storage.garbage_collect();

        });

    }

    fn test_random_garbage_collection() {

        random_test(20, |rng| {

            let mut storage = Storage::new();

            {

                // Make sure that this set goes out of scope, but keep a reference to some child ldd.

                let vector = random_vector_set(rng, 2000, 10, 2);

                let ldd = from_iter(&mut storage, vector.iter());

                _child = storage.get(&storage.get(&ldd).1).1;

                storage.garbage_collect();

            }

            storage.garbage_collect();

        });

    }