use crate::*;
use alloc::vec;
#[derive(Clone, Debug)]
pub struct SortedVec<T> {
vec: Vec<T>,
}
enum Branch {
A, B, None
}
impl<T: Ord> Static for SortedVec<T> {
fn len(&self) -> usize {
self.vec.len()
}
fn merge_with(self, other: Self) -> Self {
let a = self.vec;
let b = other.vec;
let mut vec: Vec<T> = Vec::with_capacity(a.len() + b.len());
let vec_ptr = vec.as_mut_ptr();
let mut i = 0;
let mut a = a.into_iter();
let mut b = b.into_iter();
let mut maybe_x = a.next();
let mut maybe_y = b.next();
let branch;
loop {
match (maybe_x, maybe_y) {
(Some(x), Some(y)) => {
if x < y {
unsafe { vec_ptr.add(i).write(x); }
maybe_x = a.next();
maybe_y = Some(y);
} else {
unsafe { vec_ptr.add(i).write(y); }
maybe_x = Some(x);
maybe_y = b.next();
}
i += 1;
}
(Some(x), None) => {
unsafe { vec_ptr.add(i).write(x); }
i += 1;
branch = Branch::A;
break;
}
(None, Some(y)) => {
unsafe { vec_ptr.add(i).write(y); }
i += 1;
branch = Branch::B;
break;
}
(None, None) => {
branch = Branch::None;
break;
}
}
}
match branch {
Branch::A => {
for x in a {
unsafe { vec_ptr.add(i).write(x); }
i += 1;
}
}
Branch::B => {
for x in b {
unsafe { vec_ptr.add(i).write(x); }
i += 1;
}
}
Branch::None => {}
}
assert!(i == vec.capacity());
unsafe { vec.set_len(i); }
SortedVec { vec }
}
}
impl<T> Singleton for SortedVec<T> {
type Item = T;
fn singleton(item: Self::Item) -> Self {
SortedVec { vec: vec![item] }
}
}
impl<T: Ord> core::iter::FromIterator<T> for SortedVec<T> {
fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> Self {
let mut vec = iter.into_iter().collect::<Vec<_>>();
vec.sort();
SortedVec { vec }
}
}
#[derive(Clone, Debug)]
pub struct SVQueue<T, S = strategy::Binary> {
dynamic: Dynamic<SortedVec<T>, S>,
len: usize,
}
impl<T: Ord> SVQueue<T> {
pub fn new() -> Self {
SVQueue {
dynamic: Dynamic::new(),
len: 0,
}
}
pub fn with_strategy<S: Strategy>() -> SVQueue<T, S> {
SVQueue {
dynamic: Dynamic::new(),
len: 0,
}
}
}
impl<T: Ord, S: Strategy> SVQueue<T, S> {
pub fn len(&self) -> usize {
self.len
}
pub fn is_empty(&self) -> bool {
self.len == 0
}
pub fn push(&mut self, item: T) {
self.dynamic.insert(item);
self.len += 1;
}
pub fn peek(&self) -> Option<&T> {
self.dynamic.units()
.filter_map(|unit| unit.vec.last())
.max()
}
pub fn peek_mut(&mut self) -> Option<&mut T> {
self.dynamic.units_mut()
.filter_map(|unit| unit.vec.last_mut())
.max()
}
pub fn pop(&mut self) -> Option<T> {
let best_unit = self.dynamic.units_mut()
.max_by(|u1, u2| {
u1.vec.last().cmp(&u2.vec.last())
});
match best_unit {
None => None,
Some(unit) => {
match unit.vec.pop() {
None => None,
Some(x) => {
self.len -= 1;
Some(x)
}
}
}
}
}
}
#[test]
fn test_svqueue_len() {
let some_numbers = vec![1,4,6,2,1,5,7,4,3,2,7,8];
let mut pqueue = SVQueue::new();
let mut counter = 0;
for x in some_numbers {
pqueue.push(x);
counter += 1;
assert_eq!(pqueue.len(), counter);
assert_eq!(pqueue.len(), pqueue.dynamic.len());
}
while !pqueue.is_empty() {
pqueue.pop();
counter -= 1;
assert_eq!(pqueue.len(), counter);
assert_eq!(pqueue.len(), pqueue.dynamic.len());
}
}
#[derive(Clone, Debug)]
pub struct SVMap<K, V, S = strategy::Binary> {
dynamic: Dynamic<SortedVec<SVPair<K, V>>, S>,
len: usize,
free_count: usize,
}
#[derive(Clone, Debug)]
struct SVPair<K, V>(K, Option<V>);
impl<K: Ord, V> Ord for SVPair<K, V> {
fn cmp(&self, other: &Self) -> core::cmp::Ordering {
self.0.cmp(&other.0)
}
}
impl<K: Ord, V> PartialOrd for SVPair<K, V> {
fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
Some(self.cmp(other))
}
}
impl<K: Ord, V> PartialEq for SVPair<K, V> {
fn eq(&self, other: &Self) -> bool {
self.0 == other.0
}
}
impl<K: Ord, V> Eq for SVPair<K, V> {}
impl<K: Ord, V> SVMap<K, V> {
pub fn new() -> Self {
SVMap {
dynamic: Dynamic::new(),
len: 0,
free_count: 0,
}
}
pub fn with_strategy<S: Strategy>() -> SVMap<K, V, S> {
SVMap {
dynamic: Dynamic::new(),
len: 0,
free_count: 0,
}
}
}
impl<K: Ord, V, S: Strategy> SVMap<K, V, S> {
pub fn len(&self) -> usize {
self.len
}
pub fn is_empty(&self) -> bool {
self.len == 0
}
fn search<Q: Ord + ?Sized>(&self, key: &Q) -> Option<&SVPair<K, V>> where
K: core::borrow::Borrow<Q>
{
for unit in self.dynamic.units() {
let vec = &unit.vec;
if let Ok(index) = vec.binary_search_by(|entry| {
entry.0.borrow().cmp(key)
}) {
return unsafe { Some(vec.get_unchecked(index)) }
}
}
None
}
fn search_mut<Q: Ord + ?Sized>(&mut self, key: &Q) -> Option<&mut SVPair<K, V>> where
K: core::borrow::Borrow<Q>
{
for unit in self.dynamic.units_mut() {
let vec = &mut unit.vec;
if let Ok(index) = vec.binary_search_by(|entry| {
entry.0.borrow().cmp(key)
}) {
return unsafe { Some(vec.get_unchecked_mut(index)) }
}
}
None
}
pub fn contains_key<Q: Ord + ?Sized>(&self, key: &Q) -> bool where
K: core::borrow::Borrow<Q>
{
self.search(key).is_some()
}
pub fn get<Q: Ord + ?Sized>(&self, key: &Q) -> Option<&V> where
K: core::borrow::Borrow<Q>
{
self.search(key).map(|entry| entry.1.as_ref()).flatten()
}
pub fn get_key_value<Q: Ord + ?Sized>(&self, key: &Q) -> Option<(&K, &V)> where
K: core::borrow::Borrow<Q>
{
self.search(key).map(|entry| {
match &entry.1 {
Some(v) => { Some( (&entry.0, v) ) }
None => { None }
}
}).flatten()
}
pub fn get_mut<Q: Ord + ?Sized>(&mut self, key: &Q) -> Option<&mut V> where
K: core::borrow::Borrow<Q>
{
self.search_mut(key).map(|entry| entry.1.as_mut()).flatten()
}
pub fn insert(&mut self, key: K, value: V) -> Option<V> {
if let Some(entry) = self.search_mut(&key) {
let result = core::mem::replace(&mut entry.1, Some(value));
if let None = result {
self.len += 1;
self.free_count -= 1;
}
result
} else {
self.dynamic.insert(SVPair(key, Some(value)));
self.len += 1;
None
}
}
const REBUILD_THRESHOLD: usize = 16;
pub fn remove<Q: Ord + ?Sized>(&mut self, key: &Q) -> Option<V> where
K: core::borrow::Borrow<Q>
{
if let Some(entry) = self.search_mut(&key) {
let result = core::mem::replace(&mut entry.1, None);
if let Some(_) = result {
self.len -= 1;
self.free_count += 1;
}
if self.free_count > self.len && self.len > Self::REBUILD_THRESHOLD {
let mut tmp = SVMap::<K, V>::with_strategy::<S>();
core::mem::swap(self, &mut tmp);
*self = tmp.into_iter().collect();
}
result
} else { None }
}
pub fn clear(&mut self) {
self.dynamic.clear();
self.len = 0;
self.free_count = 0;
}
}
impl<K: Ord, V, S: Strategy> core::iter::FromIterator<(K, V)> for SVMap<K, V, S> {
fn from_iter<I: IntoIterator<Item=(K, V)>>(iter: I) -> Self {
let sv = iter
.into_iter()
.map(|(k,v)| SVPair(k, Some(v)))
.collect::<SortedVec<_>>();
let mut dynamic = Dynamic::new();
let len = sv.len();
dynamic.add_unit(sv);
Self {
dynamic,
len,
free_count: 0,
}
}
}
pub struct SVMapKV<K, V> {
unit_iter: DynamicIntoIter<SortedVec<SVPair<K, V>>>,
opt_kv_iter: Option<alloc::vec::IntoIter<SVPair<K, V>>>,
}
impl<K, V> Iterator for SVMapKV<K, V> {
type Item = (K, V);
fn next(&mut self) -> Option<Self::Item> {
loop {
if let Some(kv_iter) = &mut self.opt_kv_iter {
while let Some(sv_pair) = kv_iter.next() {
if let Some(value) = sv_pair.1 {
return Some( (sv_pair.0, value) );
}
}
}
self.opt_kv_iter =
self.unit_iter.next().map(|sv| sv.vec.into_iter());
if let None = self.opt_kv_iter { return None; }
}
}
}
impl<K: Ord, V, S> core::iter::IntoIterator for SVMap<K, V, S> {
type Item = (K, V);
type IntoIter = SVMapKV<K, V>;
fn into_iter(self) -> Self::IntoIter {
SVMapKV {
unit_iter: self.dynamic.into_iter(),
opt_kv_iter: None,
}
}
}