use std::{cell::UnsafeCell, cmp::Ordering, hash::Hash, rc::Rc};
use crate::{
io::SrcID,
mem_use::{MemUsage, MemUser},
ops::OpID,
};
#[derive(Clone, PartialEq, Eq, Hash)]
pub struct SparseMonotonicVector<T: Clone> {
runs: im::OrdMap<u32, ImAppendOnlyVec<T>>,
}
impl<T: Clone> SparseMonotonicVector<T> {
pub fn get(&self, idx: u32) -> Option<&T> {
self.runs
.get_prev(&idx)
.and_then(|(run_start, run)| run.get((idx - run_start) as usize))
}
pub fn insert(&mut self, idx: u32, val: T) {
if let Some((run_start, run)) = self.runs.get_prev_mut(&idx) {
match idx.cmp(&(run_start + run.len() as u32)) {
Ordering::Less => {
panic!("Cannot insert in middle of existing run")
}
Ordering::Equal => {
run.push(val);
}
Ordering::Greater => {
self.runs.insert(idx, ImAppendOnlyVec::unit(val));
}
}
} else {
self.runs.insert(idx, ImAppendOnlyVec::unit(val));
}
}
pub fn has_idx(&self, idx: u32) -> bool {
self.runs
.get_prev(&idx)
.filter(|(run_start, run)| idx < *run_start + run.len() as u32)
.is_some()
}
pub fn to_vec(&self) -> Vec<(u32, T)> {
let mut vec = Vec::new();
for (run_start, run) in self.runs.iter() {
for (i, val) in run.as_slice().iter().enumerate() {
vec.push((*run_start + i as u32, val.clone()));
}
}
vec
}
}
impl<T: Clone> Default for SparseMonotonicVector<T> {
fn default() -> Self {
Self {
runs: im::OrdMap::new(),
}
}
}
impl<T: MemUser + Clone> MemUser for SparseMonotonicVector<T> {
fn mem_use(&self) -> MemUsage {
MemUsage::Struct {
name: "SparseMonotonicVector",
fields: vec![("runs", self.runs.mem_use())],
}
}
}
#[derive(Default, Clone, PartialEq, Eq, Hash)]
pub struct SparseMonotonicIntSet {
runs: im::OrdMap<u32, u32>,
}
impl SparseMonotonicIntSet {
pub fn insert(&mut self, idx: u32) {
if let Some((run_start, run_len)) = self.runs.get_prev_mut(&idx) {
match idx.cmp(&(run_start + *run_len)) {
Ordering::Less => {
panic!("Cannot insert in middle of existing run")
}
Ordering::Equal => {
*run_len += 1;
}
Ordering::Greater => {
self.runs.insert(idx, 1);
}
}
} else {
self.runs.insert(idx, 1);
}
}
pub fn has(&self, idx: u32) -> bool {
self.runs
.get_prev(&idx)
.filter(|(run_start, run_len)| idx < *run_start + *run_len)
.is_some()
}
pub fn to_vec(&self) -> Vec<u32> {
let mut ints = Vec::new();
for (run_start, run_len) in self.runs.iter() {
for i in 0..*run_len {
ints.push(*run_start + i);
}
}
ints
}
}
impl MemUser for SparseMonotonicIntSet {
fn mem_use(&self) -> MemUsage {
MemUsage::Struct {
name: "SparseMonotonicIntSet",
fields: vec![("runs", self.runs.mem_use())],
}
}
}
#[derive(Clone, Default, PartialEq, Eq, Hash)]
pub struct SparseOpIDSet(im::HashMap<SrcID, SparseMonotonicIntSet>);
impl SparseOpIDSet {
pub fn insert(&mut self, op_id: OpID) {
self.0
.entry(op_id.0)
.or_default()
.insert(op_id.1);
}
pub fn contains(&self, op_id: &OpID) -> bool {
if let Some(per_node) = self.0.get(&op_id.0) {
per_node.has(op_id.1)
} else {
false
}
}
pub fn to_vec(&self) -> Vec<OpID> {
let mut ops = Vec::new();
for (src_id, per_node) in self.0.iter() {
for sequence_idx in per_node.to_vec() {
ops.push(OpID (*src_id,
sequence_idx,
));
}
}
ops
}
}
impl std::fmt::Debug for SparseOpIDSet {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "SparseOpIDSet({:?})", self.to_vec())
}
}
impl MemUser for SparseOpIDSet {
fn mem_use(&self) -> MemUsage {
self.0.mem_use()
}
}
#[derive(Clone, Default, Debug)]
pub struct ImAppendOnlyVec<T> {
this_len: u32,
data: Rc<UnsafeCell<Vec<T>>>,
}
impl<T> ImAppendOnlyVec<T> {
pub fn unit(item: T) -> ImAppendOnlyVec<T> {
ImAppendOnlyVec {
this_len: 1,
data: Rc::new(UnsafeCell::new(vec![item])),
}
}
pub fn push(&mut self, item: T) {
let data = self.data.get();
unsafe {
if self.this_len as usize != (*data).len() {
panic!("Can only append onto the latest ImAppendOnlyVec reference")
}
(*data).push(item);
}
self.this_len += 1;
}
pub fn get(&self, at: usize) -> Option<&T> {
if at < self.this_len as usize {
unsafe { (*self.data.get()).get(at) }
} else {
None
}
}
pub fn len(&self) -> usize {
self.this_len as usize
}
pub fn as_slice(&self) -> &[T] {
unsafe { &(*self.data.get())[0..self.this_len as usize] }
}
}
impl<T: Hash> Hash for ImAppendOnlyVec<T> {
fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
self.as_slice().hash(state)
}
}
impl<T: PartialEq> PartialEq for ImAppendOnlyVec<T> {
fn eq(&self, other: &Self) -> bool {
self.as_slice() == other.as_slice()
}
}
impl<T: Eq> Eq for ImAppendOnlyVec<T> {}
impl<T: MemUser> MemUser for ImAppendOnlyVec<T> {
fn mem_use(&self) -> MemUsage {
MemUsage::Struct {
name: "ImAppendOnlyVec",
fields: vec![
("this_len", self.this_len.mem_use()),
("data", self.data.mem_use()),
],
}
}
}