yrs 0.18.8

use crate::block::{BlockCell, BlockRange, ClientID, Item, ItemPtr, GC, ID};
use crate::encoding::read::Error;
use crate::slice::ItemSlice;
use crate::types::TypePtr;
use crate::utils::client_hasher::ClientHasher;
use crate::*;
use std::collections::hash_map::Entry;
use std::collections::HashMap;
use std::hash::BuildHasherDefault;
use std::ops::{Index, IndexMut};
use std::vec::Vec;

/// A resizable list of blocks inserted by a single client.
#[derive(PartialEq, Default)]
pub(crate) struct ClientBlockList {
    list: Vec<BlockCell>,
}

impl ClientBlockList {
    /// Creates a new instance of `ClientBlockList` with the specified capacity.
    ///
    /// This function initializes an internal vector with a capacity
    /// indicated by the `capacity` argument. It attempts to reserve this capacity
    /// upfront. If the reservation is successful, it returns a new `ClientBlockList`
    /// instance. Otherwise, it returns an error if the reservation fails.
    ///
    /// # Arguments
    ///
    /// * `capacity` - The desired capacity for the internal vector of `ClientBlockList`.
    ///
    /// # Returns
    ///
    /// This function returns a `Result` type:
    /// - `Ok(ClientBlockList)` if the capacity reservation is successful.
    /// - `Err(Error)` if the capacity reservation fails, encapsulating the reason for the failure.
    ///
    /// # Errors
    ///
    /// This function will return an error if the memory allocation for the specified capacity fails.
    ///
    pub fn with_capacity(capacity: usize) -> Result<ClientBlockList, Error> {
        let mut list = Vec::new();
        list.try_reserve(capacity)?;
        Ok(ClientBlockList { list })
    }

    pub fn clock(&self) -> u32 {
        let len = self.list.len();
        if len == 0 {
            0
        } else {
            self.list[len - 1].clock_range().1 + 1
        }
    }

    pub(crate) fn get(&self, index: usize) -> Option<&BlockCell> {
        self.list.get(index)
    }

    /// Given a block's identifier clock value, return an offset under which this block could be
    /// found using binary search algorithm, or a index under which this block should be inserted.
    pub(crate) fn find_pivot(&self, clock: u32) -> Option<usize> {
        let mut left = 0;
        let mut right = self.list.len() - 1;
        let mut block = &self[right];
        let (mut start, mut end) = block.clock_range();
        if start == clock {
            Some(right)
        } else {
            let mut mid = ((clock / end) * right as u32) as usize;
            while left <= right {
                block = &self[mid];
                (start, end) = block.clock_range();
                if start <= clock {
                    if clock <= end {
                        return Some(mid);
                    }
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
                mid = (left + right) / 2;
            }

            None
        }
    }

    /// Attempts to find a Block which contains given clock sequence number within current block
    /// list. Clocks are considered to work in left-side inclusive way, meaning that block with
    /// an ID (<client-id>, 0) and length 2, with contain all elements with clock values
    /// corresponding to {0,1} but not 2.
    fn get_block(&self, clock: u32) -> Option<&BlockCell> {
        let idx = self.find_pivot(clock)?;
        Some(&self[idx])
    }

    fn get_block_mut(&mut self, clock: u32) -> Option<&mut BlockCell> {
        let idx = self.find_pivot(clock)?;
        Some(&mut self[idx])
    }

    /// Pushes a new block at the end of this block list.
    fn push(&mut self, cell: BlockCell) {
        self.list.push(cell);
    }

    /// Inserts a new block at a given `index` position within this block list. This method may
    /// panic if `index` is greater than a length of the list.
    pub(crate) fn insert(&mut self, index: usize, cell: BlockCell) {
        self.list.insert(index, cell);
    }

    /// Returns a number of blocks stored within this list.
    pub fn len(&self) -> usize {
        self.list.len()
    }

    pub fn iter(&self) -> ClientBlockListIter<'_> {
        ClientBlockListIter(self.list.iter())
    }

    /// Attempts to squash block at a given `index` with a corresponding block on its left side.
    /// If this succeeds, block under a given `index` will be removed, and its contents will be
    /// squashed into its left neighbor. In such case a squash result will be returned in order to
    /// later on rewire left/right neighbor changes that may have occurred as a result of squashing
    /// and block removal.
    pub(crate) fn squash_left(&mut self, index: usize) {
        let (l, r) = self.list.split_at_mut(index);
        let left = &mut l[index - 1];
        let right = &mut r[0];
        match (left, right) {
            (BlockCell::GC(left), BlockCell::GC(right)) => {
                left.end = right.end;
                self.list.remove(index);
            }
            (BlockCell::Block(left), BlockCell::Block(right)) => {
                let mut left = ItemPtr::from(left);
                let right = ItemPtr::from(right);
                if left.try_squash(right) {
                    if let Some(key) = right.parent_sub.as_deref() {
                        if let TypePtr::Branch(mut parent) = right.parent {
                            if let Some(e) = parent.map.get_mut(key) {
                                if right == *e {
                                    *e = ItemPtr::from(left);
                                }
                            }
                        }
                    }
                    self.list.remove(index);
                }
            }
            _ => { /* cannot squash incompatible types */ }
        }
    }
}

impl Index<usize> for ClientBlockList {
    type Output = BlockCell;

    fn index(&self, index: usize) -> &Self::Output {
        &self.list[index]
    }
}

impl IndexMut<usize> for ClientBlockList {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        &mut self.list[index]
    }
}

pub(crate) struct ClientBlockListIter<'a>(std::slice::Iter<'a, BlockCell>);

impl<'a> Iterator for ClientBlockListIter<'a> {
    type Item = &'a BlockCell;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.next()
    }
}

/// Block store is a collection of all blocks known to a document owning instance of this type.
/// Blocks are organized per client ID and contain a resizable list of all blocks inserted by that
/// client.
#[derive(PartialEq, Default)]
pub(crate) struct BlockStore {
    clients: HashMap<ClientID, ClientBlockList, BuildHasherDefault<ClientHasher>>,
}

pub(crate) type Iter<'a> = std::collections::hash_map::Iter<'a, ClientID, ClientBlockList>;

impl BlockStore {
    /// Checks if block store is empty. Empty block store doesn't contain any blocks, neither active
    /// nor tombstoned.
    pub fn is_empty(&self) -> bool {
        self.clients.is_empty()
    }

    pub fn contains(&self, id: &ID) -> bool {
        if let Some(clients) = self.clients.get(&id.client) {
            id.clock < clients.clock()
        } else {
            false
        }
    }

    pub fn push_block(&mut self, block: Box<Item>) {
        let id = block.id();
        match self.clients.entry(id.client) {
            Entry::Occupied(mut e) => {
                let list = e.get_mut();
                list.push(block.into());
            }
            Entry::Vacant(e) => {
                let list = e.insert(ClientBlockList::default());
                list.push(block.into());
            }
        }
    }

    pub fn push_gc(&mut self, gc: BlockRange) {
        let id = gc.id;
        let gc: BlockCell = GC::from(gc).into();
        match self.clients.entry(id.client) {
            Entry::Occupied(mut e) => {
                let list = e.get_mut();
                list.push(gc);
            }
            Entry::Vacant(e) => {
                let list = e.insert(ClientBlockList::default());
                list.push(gc);
            }
        }
    }

    /// Returns an iterator over the client and block lists pairs known to a current block store.
    pub fn iter(&self) -> Iter<'_> {
        self.clients.iter()
    }

    /// Returns a state vector, which is a compact representation of the state of blocks integrated
    /// into a current block store. This state vector can later be encoded and send to a remote
    /// peers in order to calculate differences between two stored and produce a compact update,
    /// that can be applied in order to fill missing update information.
    pub fn get_state_vector(&self) -> StateVector {
        let map = self
            .clients
            .iter()
            .map(|(client_id, list)| (*client_id, list.clock()))
            .collect();
        StateVector::new(map)
    }

    pub(crate) fn get_client(&self, client_id: &ClientID) -> Option<&ClientBlockList> {
        self.clients.get(client_id)
    }

    pub(crate) fn get_client_mut(&mut self, client_id: &ClientID) -> Option<&mut ClientBlockList> {
        self.clients.get_mut(client_id)
    }

    /// Returns immutable reference to a block, given its pointer. Returns `None` if not such
    /// block could be found.
    pub(crate) fn get_block(&self, id: &ID) -> Option<&BlockCell> {
        let clients = self.clients.get(&id.client)?;
        clients.get_block(id.clock)
    }

    pub(crate) fn get_block_mut(&mut self, id: &ID) -> Option<&mut BlockCell> {
        let clients = self.clients.get_mut(&id.client)?;
        clients.get_block_mut(id.clock)
    }

    pub(crate) fn get_item(&self, id: &ID) -> Option<ItemPtr> {
        let cell = self.get_block(id)?;
        if let BlockCell::Block(item) = cell {
            Some(ItemPtr::from(item))
        } else {
            None
        }
    }

    /// Returns a block slice that represents a range of data within a particular block containing
    /// provided [ID], starting from that [ID] until the end of the block.
    ///
    /// Example: *for a block `A:1..=5` and id `A:3`, the returned slice will represent `A:3..=5`*.
    pub(crate) fn get_item_clean_start(&self, id: &ID) -> Option<ItemSlice> {
        let ptr = self.get_item(id)?;
        let offset = id.clock - ptr.id().clock;
        Some(ItemSlice::new(ptr, offset, ptr.len() - 1))
    }

    /// Returns a block slice that represents a range of data within a particular block containing
    /// provided [ID], starting from the beginning of the block until the that [ID] (inclusive).
    ///
    /// Example: *for a block `A:1..=5` and id `A:3`, the returned slice will represent `A:1..=3`*.
    pub(crate) fn get_item_clean_end(&self, id: &ID) -> Option<ItemSlice> {
        let ptr = self.get_item(id)?;
        let block_id = ptr.id();
        let offset = id.clock - block_id.clock;
        Some(ItemSlice::new(ptr, 0, offset))
    }

    /// Returns the last observed clock sequence number for a given `client`. This is exclusive
    /// value meaning it describes a clock value of the beginning of the next block that's about
    /// to be inserted. You cannot use that clock value to find any existing block content.
    pub fn get_clock(&self, client: &ClientID) -> u32 {
        if let Some(list) = self.clients.get(client) {
            list.clock()
        } else {
            0
        }
    }

    /// Returns a mutable reference to block list for the given `client`. In case when no such list
    /// existed, a new one will be created and returned.
    pub(crate) fn get_client_blocks_mut(&mut self, client: ClientID) -> &mut ClientBlockList {
        self.clients
            .entry(client)
            .or_insert_with(ClientBlockList::default)
    }

    /// Returns a mutable reference to block list for the given `client`. In case when no such list
    /// existed, a new one will be created with predefined `capacity` and returned.
    pub(crate) fn get_client_blocks_with_capacity_mut(
        &mut self,
        client: ClientID,
        capacity: usize,
    ) -> Result<&mut ClientBlockList, Error> {
        match self.clients.entry(client) {
            Entry::Occupied(e) => Ok(e.into_mut()),
            Entry::Vacant(e) => {
                let list = ClientBlockList::with_capacity(capacity)?;
                Ok(e.insert(list))
            }
        }
    }

    /// Given block pointer, tries to split it, returning a true, if block was split in result of
    /// calling this action, and false otherwise.
    pub fn split_block(
        &mut self,
        mut block: ItemPtr,
        offset: u32,
        encoding: OffsetKind,
    ) -> Option<ItemPtr> {
        let id = block.id().clone();
        let blocks = self.clients.get_mut(&id.client)?;
        let index = blocks.find_pivot(id.clock)?;
        let mut right = block.splice(offset, encoding)?;
        let right_ptr = ItemPtr::from(&mut right);
        blocks.insert(index + 1, right.into());

        Some(right_ptr)
    }

    pub(crate) fn split_block_inner(&mut self, block: ItemPtr, offset: u32) -> Option<ItemPtr> {
        self.split_block(block, offset, OffsetKind::Utf16)
    }
}

impl std::fmt::Debug for ClientBlockList {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        std::fmt::Display::fmt(self, f)
    }
}

impl std::fmt::Display for ClientBlockList {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_list().entries(self.list.iter()).finish()
    }
}

impl std::fmt::Debug for BlockStore {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        std::fmt::Display::fmt(self, f)
    }
}

impl std::fmt::Display for BlockStore {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let mut s = f.debug_struct("");
        for (k, v) in self.clients.iter() {
            s.field(&k.to_string(), v);
        }
        s.finish()
    }
}

pub(crate) struct Blocks<'a> {
    current_client: std::vec::IntoIter<(&'a ClientID, &'a ClientBlockList)>,
    current_block: Option<ClientBlockListIter<'a>>,
}

impl<'a> Blocks<'a> {
    fn new(update: &'a BlockStore) -> Self {
        let mut client_blocks: Vec<(&'a ClientID, &'a ClientBlockList)> =
            update.clients.iter().collect();
        // sorting to return higher client ids first
        client_blocks.sort_by(|a, b| b.0.cmp(a.0));
        let mut current_client = client_blocks.into_iter();

        let current_block = current_client.next().map(|(_, v)| v.iter());
        Blocks {
            current_client,
            current_block,
        }
    }
}

impl<'a> Iterator for Blocks<'a> {
    type Item = &'a BlockCell;

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(blocks) = self.current_block.as_mut() {
            let block = blocks.next();
            if block.is_some() {
                return block;
            }
        }

        if let Some(entry) = self.current_client.next() {
            self.current_block = Some(entry.1.iter());
            self.next()
        } else {
            None
        }
    }
}