use crate::Error;
#[derive(Debug, Clone)]
pub struct DynamicArray<T> {
data: Vec<T>,
}
impl<T> DynamicArray<T> {
pub fn with_capacity(capacity: usize) -> Self {
Self {
data: Vec::with_capacity(capacity),
}
}
pub fn new() -> Self {
Self::with_capacity(10)
}
pub fn len(&self) -> usize {
self.data.len()
}
pub fn is_empty(&self) -> bool {
self.data.is_empty()
}
pub fn append(&mut self, value: T) {
self.data.push(value);
}
pub fn insert(&mut self, index: usize, value: T) -> Result<(), Error> {
if index > self.data.len() {
return Err(Error::OutOfBounds);
}
self.data.insert(index, value);
Ok(())
}
pub fn remove(&mut self, value: &T) -> Result<(), Error>
where
T: PartialEq,
{
if let Some(index) = self.data.iter().position(|x| x == value) {
self.data.remove(index);
Ok(())
} else {
Err(Error::NotFound)
}
}
pub fn pop(&mut self, index: Option<usize>) -> Result<T, Error> {
if self.data.is_empty() {
return Err(Error::Empty);
}
let idx = index.unwrap_or(self.data.len() - 1);
if idx >= self.data.len() {
return Err(Error::OutOfBounds);
}
Ok(self.data.remove(idx))
}
pub fn get(&self, index: usize) -> Result<&T, Error> {
self.data.get(index).ok_or(Error::OutOfBounds)
}
pub fn set(&mut self, index: usize, value: T) -> Result<(), Error> {
if index >= self.data.len() {
return Err(Error::OutOfBounds);
}
self.data[index] = value;
Ok(())
}
pub fn to_vec(&self) -> Vec<T>
where
T: Clone,
{
self.data.clone()
}
}
impl<T> Default for DynamicArray<T> {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
struct SNode<T> {
value: Option<T>,
next: Option<usize>,
}
#[derive(Debug)]
pub struct SinglyLinkedList<T> {
nodes: Vec<SNode<T>>,
head: Option<usize>,
free: Vec<usize>,
len: usize,
}
impl<T> SinglyLinkedList<T> {
pub fn new() -> Self {
Self {
nodes: Vec::new(),
head: None,
free: Vec::new(),
len: 0,
}
}
pub fn len(&self) -> usize {
self.len
}
pub fn is_empty(&self) -> bool {
self.len == 0
}
fn alloc(&mut self, value: T) -> usize {
if let Some(index) = self.free.pop() {
self.nodes[index] = SNode {
value: Some(value),
next: None,
};
index
} else {
self.nodes.push(SNode {
value: Some(value),
next: None,
});
self.nodes.len() - 1
}
}
fn free_node(&mut self, index: usize) {
self.nodes[index].value = None;
self.nodes[index].next = None;
self.free.push(index);
}
fn node_at(&self, index: usize) -> Result<usize, Error> {
if index >= self.len {
return Err(Error::OutOfBounds);
}
let mut current = self.head.unwrap();
for _ in 0..index {
current = self.nodes[current].next.unwrap();
}
Ok(current)
}
pub fn append(&mut self, value: T) {
let index = self.alloc(value);
if let Some(tail_index) = self.tail() {
self.nodes[tail_index].next = Some(index);
} else {
self.head = Some(index);
}
self.len += 1;
}
fn tail(&self) -> Option<usize> {
let mut current = self.head?;
while let Some(next) = self.nodes[current].next {
current = next;
}
Some(current)
}
pub fn prepend(&mut self, value: T) {
let index = self.alloc(value);
self.nodes[index].next = self.head;
self.head = Some(index);
self.len += 1;
}
pub fn insert(&mut self, index: usize, value: T) -> Result<(), Error> {
if index > self.len {
return Err(Error::OutOfBounds);
}
if index == 0 {
self.prepend(value);
return Ok(());
}
let prev = self.node_at(index - 1)?;
let new_index = self.alloc(value);
self.nodes[new_index].next = self.nodes[prev].next;
self.nodes[prev].next = Some(new_index);
self.len += 1;
Ok(())
}
pub fn remove(&mut self, value: &T) -> Result<(), Error>
where
T: PartialEq,
{
let head = self.head.ok_or(Error::NotFound)?;
if self.nodes[head].value.as_ref() == Some(value) {
let next = self.nodes[head].next;
self.free_node(head);
self.head = next;
self.len -= 1;
return Ok(());
}
let mut current = head;
while let Some(next) = self.nodes[current].next {
if self.nodes[next].value.as_ref() == Some(value) {
self.nodes[current].next = self.nodes[next].next;
self.free_node(next);
self.len -= 1;
return Ok(());
}
current = next;
}
Err(Error::NotFound)
}
pub fn pop(&mut self, index: Option<usize>) -> Result<T, Error> {
if self.is_empty() {
return Err(Error::Empty);
}
let idx = index.unwrap_or(self.len - 1);
if idx >= self.len {
return Err(Error::OutOfBounds);
}
if idx == 0 {
let head = self.head.unwrap();
let value = self.nodes[head].value.take().unwrap();
let next = self.nodes[head].next;
self.free_node(head);
self.head = next;
self.len -= 1;
return Ok(value);
}
let prev = self.node_at(idx - 1)?;
let current = self.nodes[prev].next.unwrap();
let value = self.nodes[current].value.take().unwrap();
self.nodes[prev].next = self.nodes[current].next;
self.free_node(current);
self.len -= 1;
Ok(value)
}
pub fn get(&self, index: usize) -> Result<&T, Error> {
let node = self.node_at(index)?;
Ok(self.nodes[node].value.as_ref().unwrap())
}
pub fn get_mut(&mut self, index: usize) -> Result<&mut T, Error> {
let node = self.node_at(index)?;
Ok(self.nodes[node].value.as_mut().unwrap())
}
pub fn find(&self, value: &T) -> Result<usize, Error>
where
T: PartialEq,
{
let mut current = self.head;
let mut i = 0;
while let Some(idx) = current {
if self.nodes[idx].value.as_ref() == Some(value) {
return Ok(i);
}
current = self.nodes[idx].next;
i += 1;
}
Err(Error::NotFound)
}
pub fn to_vec(&self) -> Vec<T>
where
T: Clone,
{
let mut result = Vec::with_capacity(self.len);
let mut current = self.head;
while let Some(idx) = current {
result.push(self.nodes[idx].value.as_ref().unwrap().clone());
current = self.nodes[idx].next;
}
result
}
}
impl<T> Default for SinglyLinkedList<T> {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
struct DNode<T> {
value: Option<T>,
prev: Option<usize>,
next: Option<usize>,
}
#[derive(Debug)]
pub struct DoublyLinkedList<T> {
nodes: Vec<DNode<T>>,
head: Option<usize>,
tail: Option<usize>,
free: Vec<usize>,
len: usize,
}
impl<T> DoublyLinkedList<T> {
pub fn new() -> Self {
Self {
nodes: Vec::new(),
head: None,
tail: None,
free: Vec::new(),
len: 0,
}
}
pub fn len(&self) -> usize {
self.len
}
pub fn is_empty(&self) -> bool {
self.len == 0
}
fn alloc(&mut self, value: T) -> usize {
if let Some(index) = self.free.pop() {
self.nodes[index] = DNode {
value: Some(value),
prev: None,
next: None,
};
index
} else {
self.nodes.push(DNode {
value: Some(value),
prev: None,
next: None,
});
self.nodes.len() - 1
}
}
fn free_node(&mut self, index: usize) {
self.nodes[index].value = None;
self.nodes[index].prev = None;
self.nodes[index].next = None;
self.free.push(index);
}
fn node_at(&self, index: usize) -> Result<usize, Error> {
if index >= self.len {
return Err(Error::OutOfBounds);
}
if index <= self.len / 2 {
let mut current = self.head.unwrap();
for _ in 0..index {
current = self.nodes[current].next.unwrap();
}
Ok(current)
} else {
let mut current = self.tail.unwrap();
for _ in 0..self.len - index - 1 {
current = self.nodes[current].prev.unwrap();
}
Ok(current)
}
}
pub fn append(&mut self, value: T) {
let index = self.alloc(value);
if let Some(tail) = self.tail {
self.nodes[tail].next = Some(index);
self.nodes[index].prev = Some(tail);
self.tail = Some(index);
} else {
self.head = Some(index);
self.tail = Some(index);
}
self.len += 1;
}
pub fn prepend(&mut self, value: T) {
let index = self.alloc(value);
if let Some(head) = self.head {
self.nodes[head].prev = Some(index);
self.nodes[index].next = Some(head);
self.head = Some(index);
} else {
self.head = Some(index);
self.tail = Some(index);
}
self.len += 1;
}
pub fn insert(&mut self, index: usize, value: T) -> Result<(), Error> {
if index > self.len {
return Err(Error::OutOfBounds);
}
if index == 0 {
self.prepend(value);
return Ok(());
}
if index == self.len {
self.append(value);
return Ok(());
}
let next = self.node_at(index)?;
let prev = self.nodes[next].prev.unwrap();
let new_index = self.alloc(value);
self.nodes[new_index].prev = Some(prev);
self.nodes[new_index].next = Some(next);
self.nodes[prev].next = Some(new_index);
self.nodes[next].prev = Some(new_index);
self.len += 1;
Ok(())
}
pub fn remove(&mut self, value: &T) -> Result<(), Error>
where
T: PartialEq,
{
let mut current = self.head;
while let Some(idx) = current {
if self.nodes[idx].value.as_ref() == Some(value) {
self.remove_node(idx);
return Ok(());
}
current = self.nodes[idx].next;
}
Err(Error::NotFound)
}
fn remove_node(&mut self, index: usize) {
let prev = self.nodes[index].prev;
let next = self.nodes[index].next;
if let Some(p) = prev {
self.nodes[p].next = next;
} else {
self.head = next;
}
if let Some(n) = next {
self.nodes[n].prev = prev;
} else {
self.tail = prev;
}
self.free_node(index);
self.len -= 1;
}
pub fn pop(&mut self, index: Option<usize>) -> Result<T, Error> {
if self.is_empty() {
return Err(Error::Empty);
}
let idx = index.unwrap_or(self.len - 1);
if idx >= self.len {
return Err(Error::OutOfBounds);
}
let node = self.node_at(idx)?;
let value = self.nodes[node].value.take().unwrap();
self.remove_node(node);
Ok(value)
}
pub fn get(&self, index: usize) -> Result<&T, Error> {
let node = self.node_at(index)?;
Ok(self.nodes[node].value.as_ref().unwrap())
}
pub fn get_mut(&mut self, index: usize) -> Result<&mut T, Error> {
let node = self.node_at(index)?;
Ok(self.nodes[node].value.as_mut().unwrap())
}
pub fn to_vec(&self) -> Vec<T>
where
T: Clone,
{
let mut result = Vec::with_capacity(self.len);
let mut current = self.head;
while let Some(idx) = current {
result.push(self.nodes[idx].value.as_ref().unwrap().clone());
current = self.nodes[idx].next;
}
result
}
}
impl<T> Default for DoublyLinkedList<T> {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
struct CNode<T> {
value: Option<T>,
next: Option<usize>,
}
#[derive(Debug)]
pub struct CircularLinkedList<T> {
nodes: Vec<CNode<T>>,
tail: Option<usize>,
free: Vec<usize>,
len: usize,
}
impl<T> CircularLinkedList<T> {
pub fn new() -> Self {
Self {
nodes: Vec::new(),
tail: None,
free: Vec::new(),
len: 0,
}
}
pub fn len(&self) -> usize {
self.len
}
pub fn is_empty(&self) -> bool {
self.len == 0
}
fn alloc(&mut self, value: T) -> usize {
if let Some(index) = self.free.pop() {
self.nodes[index] = CNode {
value: Some(value),
next: None,
};
index
} else {
self.nodes.push(CNode {
value: Some(value),
next: None,
});
self.nodes.len() - 1
}
}
fn free_node(&mut self, index: usize) {
self.nodes[index].value = None;
self.nodes[index].next = None;
self.free.push(index);
}
pub fn append(&mut self, value: T) {
let index = self.alloc(value);
if let Some(tail) = self.tail {
let head = self.nodes[tail].next.unwrap();
self.nodes[tail].next = Some(index);
self.nodes[index].next = Some(head);
self.tail = Some(index);
} else {
self.nodes[index].next = Some(index);
self.tail = Some(index);
}
self.len += 1;
}
pub fn prepend(&mut self, value: T) {
let index = self.alloc(value);
if let Some(tail) = self.tail {
let head = self.nodes[tail].next.unwrap();
self.nodes[tail].next = Some(index);
self.nodes[index].next = Some(head);
} else {
self.nodes[index].next = Some(index);
self.tail = Some(index);
}
self.len += 1;
}
pub fn remove(&mut self, value: &T) -> Result<(), Error>
where
T: PartialEq,
{
let tail = self.tail.ok_or(Error::NotFound)?;
let head = self.nodes[tail].next.unwrap();
if self.nodes[head].value.as_ref() == Some(value) {
if head == tail {
self.tail = None;
} else {
self.nodes[tail].next = self.nodes[head].next;
}
self.free_node(head);
self.len -= 1;
return Ok(());
}
let mut current = head;
for _ in 0..self.len - 1 {
let next = self.nodes[current].next.unwrap();
if self.nodes[next].value.as_ref() == Some(value) {
let after = self.nodes[next].next;
self.nodes[current].next = after;
if next == tail {
self.tail = Some(current);
}
self.free_node(next);
self.len -= 1;
return Ok(());
}
current = next;
}
Err(Error::NotFound)
}
pub fn to_vec(&self) -> Vec<T>
where
T: Clone,
{
if self.is_empty() {
return Vec::new();
}
let mut result = Vec::with_capacity(self.len);
let tail = self.tail.unwrap();
let start = self.nodes[tail].next.unwrap();
let mut current = start;
loop {
result.push(self.nodes[current].value.as_ref().unwrap().clone());
current = self.nodes[current].next.unwrap();
if current == start {
break;
}
}
result
}
}
impl<T> Default for CircularLinkedList<T> {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct Stack<T> {
items: Vec<T>,
}
impl<T> Stack<T> {
pub fn new() -> Self {
Self { items: Vec::new() }
}
pub fn len(&self) -> usize {
self.items.len()
}
pub fn is_empty(&self) -> bool {
self.items.is_empty()
}
pub fn push(&mut self, value: T) {
self.items.push(value);
}
pub fn pop(&mut self) -> Result<T, Error> {
self.items.pop().ok_or(Error::Empty)
}
pub fn peek(&self) -> Result<&T, Error> {
self.items.last().ok_or(Error::Empty)
}
pub fn to_vec(&self) -> Vec<T>
where
T: Clone,
{
self.items.iter().rev().cloned().collect()
}
}
impl<T> Default for Stack<T> {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct Queue<T> {
items: std::collections::VecDeque<T>,
}
impl<T> Queue<T> {
pub fn new() -> Self {
Self {
items: std::collections::VecDeque::new(),
}
}
pub fn len(&self) -> usize {
self.items.len()
}
pub fn is_empty(&self) -> bool {
self.items.is_empty()
}
pub fn enqueue(&mut self, value: T) {
self.items.push_back(value);
}
pub fn dequeue(&mut self) -> Result<T, Error> {
self.items.pop_front().ok_or(Error::Empty)
}
pub fn peek(&self) -> Result<&T, Error> {
self.items.front().ok_or(Error::Empty)
}
pub fn to_vec(&self) -> Vec<T>
where
T: Clone,
{
self.items.iter().cloned().collect()
}
}
impl<T> Default for Queue<T> {
fn default() -> Self {
Self::new()
}
}