# README

![Yaambo](./yaambo.svg)

*Yaambo* is a library that contains an implementation of a concurrent skip list.

A concurrent skip list is a multithreaded implementation of the skip list data structure.
It is a probabilistic data structure that allows for fast insertion, deletion, and lookup of
elements. It is also efficient in terms of space usage.

A skip list is a linked list with a number of levels. Each level is a linked list of nodes,
where each node contains a key and a value. The keys are sorted in ascending order. The higher
levels of the skip list skip over a large number of nodes, which makes lookup operations very
efficient.

A concurrent skip list uses hand-over-hand locking to protect the nodes in the skip list.
This means that only one thread can be modifying a node at a time. However, multiple threads
can be reading the nodes at the same time.

The concurrent skip list is a good choice for applications that need to be able to handle a
large number of concurrent operations. It is also a good choice for applications that need to
be able to perform fast lookup operations.

Here are some of the benefits of using a concurrent skip list:

- Fast insertion, deletion, and lookup of elements
- Efficient in terms of space usage
- Scalable to handle a large number of concurrent operations
- Good for applications that need to perform fast lookup operations

Here are some of the limitations of using a concurrent skip list:

Can be more complex to implement than other data structures

- May not be as efficient as other data structures for some operations, such as range queries
- May not be as scalable as other data structures for some applications

This implementation is based on the on documented in William Pugh's 1989, paper
["Concurrent Maintenance of Skip Lists"](https://15721.courses.cs.cmu.edu/spring2018/papers/08-oltpindexes1/pugh-skiplists-cacm1990.pdf).

## Examples

The following examples are adapted from the examples in the Rust standard library
documentation for [`HashMap`].

```rust
use yaambo::ConcurrentSkipList;

let mut movie_reviews: ConcurrentSkipList<String, String> = ConcurrentSkipList::new();

// Review some movies.
movie_reviews.set(
    "The Matrix".to_string(),
    "My favorite movie.".to_string(),
);
movie_reviews.set(
    "Liquorice Pizza".to_string(),
    "Not for me.".to_string(),
);
movie_reviews.set(
    "Moulin Rouge".to_string(),
    "A guilty pleasure.".to_string(),
);
movie_reviews.set(
    "The Power of the Dog".to_string(),
    "Underroted.".to_string(),
);

// Check for a specific one.
// When collections store owned values (String), they can still be
// queried using references (&str).
if !movie_reviews.contains("Les Misérables") {
    println!("We've got {} reviews, but Les Misérables ain't one.",
             movie_reviews.iter().count());
}

// oops, this review has a lot of spelling mistakes, let's delete it.
movie_reviews.remove("The Power of the Dog");

// Look up the values associated with some keys.
let to_find = ["Moulin Rouge", "Alice's Adventure in Wonderland"];
for &movie in &to_find {
    match movie_reviews.get(movie) {
        Some(review) => println!("{movie}: {review}"),
        None => println!("{movie} is un-reviewed.")
    }
}

// Iterate over everything.
for (movie, review) in &movie_reviews {
    println!("{movie}: \"{review}\"");
}
```

A `ConcurrentSkipList` with a known list of items can be initialized
from an array:

```rust
use yaambo::ConcurrentSkipList;

let solar_distance: ConcurrentSkipList<String, f32> = ConcurrentSkipList::from([
    ("Mercury", 0.4),
    ("Venus", 0.7),
    ("Earth", 1.0),
    ("Mars", 1.5),
]);
```

The easiest way to use `ConcurrentSkipList` with a custom key type is
to derive [`Ord`]. This requires that the key derive [`PartialEq`],
[`Eq`], and [`PartialOrd`] as well.

```rust
use yaambo::ConcurrentSkipList;

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct StreetFighter {
    name: String,
    country: String,
}

impl StreetFighter {
    Creates a new Street Fighter.
    fn new(name: &str, country: &str) -> StreetFighter {
        StreetFighter { name: name.to_string(), country: country.to_string() }
    }
}

// Use a ConcurrentSkipList to store the fighters' health points.
let fighters: ConcurrentSkipList<StreetFighter, usize> = ConcurrentSkipList::from([
    (StreetFighter::new("Akuma", "Japan"), 900_usize),
    (StreetFighter::new("Zangief", "Russia"), 1075_usize),
    (StreetFighter::new("Chun Li", "China"), 975_usize),
]);

// Use derived implementation to print the status of the fighters.
for (fighter, health) in &fighters {
    println!("{fighter:?} has {health} hp");
}
```

## License

This library uses the [MIT License](https://en.wikipedia.org/wiki/MIT_License).
If you find it helpful, I’d love to hear about it!

<!-- TODO(OMEGA-1333): The following need to be addressed:

  - Add badges to this README.
  - Add a section on how to install the this once it has been uploaded to Crates.io.
  - Add a section on how to contribute to this library. -->