Expand description
This crate contains implementations of different data-structures:
Min Heap
use project::datastructures::heap::Heap;
use project::datastructures::heap::MinH;
let mut heap = MinH::default();
heap.insert(3);
heap.insert(1);
heap.insert(2);
assert_eq!(heap.remove(), Some(1));
assert_eq!(heap.remove(), Some(2));
assert_eq!(heap.remove(), Some(3));
assert_eq!(heap.remove(), None);
Max Heap
use project::datastructures::heap::Heap;
use project::datastructures::heap::MaxH;
let mut heap = MaxH::default();
heap.insert(1);
heap.insert(2);
heap.insert(3);
assert_eq!(heap.remove(), Some(3));
assert_eq!(heap.remove(), Some(2));
assert_eq!(heap.remove(), Some(1));
assert_eq!(heap.remove(), None);
Stack
use project::datastructures::linear::LLStack;
use project::datastructures::linear::LL;
let mut stack = LLStack::default();
stack.push(1);
stack.push(2);
stack.push(3);
assert_eq!(stack.pop(), Some(3));
assert_eq!(stack.pop(), Some(2));
assert_eq!(stack.pop(), Some(1));
assert_eq!(stack.pop(), None);
Queue
use project::datastructures::linear::LLQueue;
use project::datastructures::linear::LL;
let mut stack = LLQueue::default();
stack.push(1);
stack.push(2);
stack.push(3);
assert_eq!(stack.pop(), Some(1));
assert_eq!(stack.pop(), Some(2));
assert_eq!(stack.pop(), Some(3));
assert_eq!(stack.pop(), None);
Doubly Linked List
use project::datastructures::linear::DLL;
use project::datastructures::linear::LL;
let mut ll = DLL::default();
ll.insert_head(1);
ll.insert(2, 1);
ll.insert_sorted(3);
let mut iter = ll.iter();
assert_eq!(iter.next(), Some(&1)); // Get current, move cursor forward
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next_back(), Some(&3)); // Get current, move cursor back
assert_eq!(iter.next_back(), Some(&2)); // Get current, move cursor back
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), None);
Singly Linked List
use project::datastructures::linear::LL;
use project::datastructures::linear::SLL;
let mut ll = SLL::default();
ll.insert_head(1);
ll.insert(2, 1);
ll.insert_sorted(3);
let mut iter = ll.iter();
assert_eq!(iter.next(), Some(&1)); // Get current, move cursor forward
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), None);
Circular Doubly Linked List
use project::datastructures::linear::CDLL;
use project::datastructures::linear::LL;
let mut ll = CDLL::default();
ll.insert_head(1);
ll.insert(2, 1);
ll.insert_sorted(3);
let mut iter = ll.iter();
assert_eq!(iter.next(), Some(&1)); // Get current, move cursor forward
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next_back(), Some(&3)); // Get current, move cursor back
assert_eq!(iter.next_back(), Some(&2)); // Get current, move cursor back
assert_eq!(iter.next_back(), Some(&1)); // Get current, move cursor back
assert_eq!(iter.next_back(), Some(&3)); // Get current, move cursor back
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), Some(&1));
Circular Singly Linked List
use project::datastructures::linear::CSLL;
use project::datastructures::linear::LL;
let mut ll = CSLL::default();
ll.insert_head(1);
ll.insert(2, 1);
ll.insert_sorted(3);
let mut iter = ll.iter();
assert_eq!(iter.next(), Some(&1)); // Get current, move cursor forward
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), Some(&1));
Binary Search Tree
use project::datastructures::trees::BST;
let mut tree = BST::default();
tree.insert(3);
tree.insert(2);
tree.insert(4);
tree.insert(1);
// 3
// / \
// 2 4
// /
// 1
assert_eq!(tree.traverse_in_order(), [&1, &2, &3, &4]);
assert_eq!(tree.traverse_breadth_first(), [&3, &2, &4, &1]);
assert_eq!(tree.delete(&4), Some(4));
// 3
// /
// 2
// /
// 1
assert_eq!(tree.traverse_in_order(), [&1, &2, &3]);
assert_eq!(tree.traverse_breadth_first(), [&3, &2, &1]);
assert_eq!(tree.search(&0), None);
assert_eq!(tree.search(&2), Some(&2));
Adelson-Velsky and Landis (AVL) Tree
use project::datastructures::trees::AVL;
let mut tree = AVL::default();
tree.insert(3);
tree.insert(2);
tree.insert(4);
tree.insert(1);
// 3
// / \
// 2 4
// /
// 1
assert_eq!(tree.traverse_in_order(), [&1, &2, &3, &4]);
assert_eq!(tree.traverse_breadth_first(), [&3, &2, &4, &1]);
assert_eq!(tree.delete(&4), Some(4));
// 2
// / \
// 1 3
assert_eq!(tree.traverse_in_order(), [&1, &2, &3]);
assert_eq!(tree.traverse_breadth_first(), [&2, &1, &3]);
assert_eq!(tree.search(&0), None);
assert_eq!(tree.search(&2), Some(&2));
Modules
Collection of data-structures.