#trait #collection #heap #binary

trait-based-collection

A trait-based collection library that implement different data structures using the same trait

1 unstable release

Uses new Rust 2021

0.1.0 Oct 22, 2022

#1003 in Data structures

MIT/Apache

150KB
2.5K SLoC

Rust Trait-based Collection

This project is a collection of data structures that implement the Collection trait, allowing for a common interface for all the data structures in this crate. This crate is intended to be a proof of concept a common interface for all the data structures in Rust.

Summary

This crate contains three major traits:

  • Collection: A trait that defines the basic operations of a collection.
  • FixedSizeCollection: A trait that defines the basic operations of a collection with a fixed size.
  • Iterators: A trait that encapsulates all the iterators of a collection.

This crate contains the following data structures:

  • Queue: A FIFO data structure based on linked nodes.
  • Deque: A FIFO and LIFO data structure based on linked nodes.
  • CircularDeque: A FIFO and LIFO data structure based on a circular array.
  • Stack: A LIFO data structure based on a linked nodes.
  • ArrayStack: A LIFO data structure based on a fixed size array.
  • BinaryHeap: A PriorityQueue data structure based on a binary heap.

For more information, please refer to the individual documentation of each data structure. This can be generated by running cargo doc --open.

Installation

From crates.io:

[dependencies]
trait-based-collection = "0.1"

Alternatively, you can clone this repository and build it from source:

git clone https://github.com/ferranSanchezLlado/rust-data-structures.git
cd r
cargo install --force --path .

If there are installation errors, ensure that your toolchain is up-to-date. For the latest, run:

rustup update

Example

use trait_based_collection::{import, Queue};
import!();

fn main() {
    let mut q = queue![1, 2, 3, 4, 5];
    println!("Queue: {:?}", q);
    println!("Queue size: {}", q.len());
    println!("Queue is empty: {}", q.is_empty());
    
    q.add(6);
    q.remove();
    for i in q.iter() {
        println!("Queue element: {}", i);
    }
}

Future work

Data Structures to implement:

  • Binary Search Tree
  • AVL Tree
  • Red-Black Tree
  • Fibonacci Heap
  • HashMap
  • HashSet
  • Graph
  • Vector

Dependencies

~290–690KB
~16K SLoC