mod bst;
pub mod hash_table;
mod sequential_search;
pub use bst::RedBlackBST;
pub use hash_table::{
HashTable, LinearProbingHashTable, SeperateChainingHashTable,
};
pub use sequential_search::SequentialSearch;
pub trait SymbolTable<K, V>: IntoIterator<Item = (K, V)> {
fn put(&mut self, key: K, value: V);
#[must_use]
fn get(&self, key: &K) -> Option<&V>;
fn delete(&mut self, key: &K)
where
K: Clone,
V: Clone;
fn clear(&mut self);
#[must_use]
#[inline(always)]
fn contains(&self, key: &K) -> bool {
self.get(key).is_some()
}
#[must_use]
#[inline(always)]
fn is_empty(&self) -> bool {
self.size() == 0
}
#[must_use]
fn size(&self) -> usize;
}
pub trait OrderedSymbolTable<K: Ord, V>: SymbolTable<K, V> {
#[must_use]
fn min(&self) -> Option<&K>;
#[must_use]
fn max(&self) -> Option<&K>;
#[must_use]
fn floor(&self, key: &K) -> Option<&K>;
#[must_use]
fn ceiling(&self, key: &K) -> Option<&K>;
#[must_use]
fn rank(&self, key: &K) -> usize;
#[must_use]
fn select(&self, rank: usize) -> Option<&K>;
#[must_use]
fn size_betwen(&self, lo: &K, hi: &K) -> usize {
if hi < lo {
0
} else if self.contains(hi) {
self.rank(hi) - self.rank(lo) + 1
} else {
self.rank(hi) - self.rank(lo)
}
}
#[inline]
fn delete_min(&mut self)
where
K: Clone,
V: Clone,
{
let val = self.min();
if let Some(val) = val {
self.delete(&val.clone())
}
}
#[inline]
fn delete_max(&mut self)
where
K: Clone,
V: Clone,
{
let val = self.max();
if let Some(val) = val {
self.delete(&val.clone())
}
}
}
#[derive(Debug, Default, Clone, Copy)]
struct SearchingNode<K, V>(K, Option<V>);
impl<K: PartialEq, V> PartialEq for SearchingNode<K, V> {
fn eq(&self, other: &Self) -> bool {
self.0 == other.0
}
}
impl<K: Eq, V> Eq for SearchingNode<K, V> {}
impl<K: PartialOrd, V> PartialOrd for SearchingNode<K, V> {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
self.0.partial_cmp(&other.0)
}
}
impl<K: Ord, V> Ord for SearchingNode<K, V> {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.0.cmp(&other.0)
}
}