journalmap 0.1.0

use crate::JournalError;
use crate::Tag;
use std::collections::HashSet;
use std::fmt::Debug;
use std::hash::Hash;
use std::ops::Range;

#[cfg(feature = "serde")]
use serde::Deserialize;
#[cfg(feature = "serde")]
use serde::Serialize;
#[cfg(feature = "serde")]
use serde::de::Deserialize as DeserializeTrait;
#[cfg(feature = "serde")]
use serde::de::Deserializer;
#[cfg(feature = "serde")]
use serde::ser::Serialize as SerializeTrait;
#[cfg(feature = "serde")]
use serde::ser::Serializer;

#[derive(Clone, Copy)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
struct Insert<V> {
    pub val: V,
    pub index: usize,
}

impl<V: Clone> Insert<V> {
    pub fn forward(&self, vec: &mut Vec<V>) {
        vec.insert(self.index, self.val.clone());
    }

    pub fn reverse(&self, vec: &mut Vec<V>) {
        vec.remove(self.index);
    }
}

impl<V: Debug> std::fmt::Debug for Insert<V> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "[+] {:?}@{}", self.val, self.index)
    }
}

#[derive(Clone, Copy)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
struct Remove<V> {
    pub val: V,
    pub index: usize,
}

impl<V: Clone> Remove<V> {
    pub fn forward(&self, vec: &mut Vec<V>) {
        vec.remove(self.index);
    }

    pub fn reverse(&self, vec: &mut Vec<V>) {
        vec.insert(self.index, self.val.clone());
    }
}

impl<V: Debug> std::fmt::Debug for Remove<V> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "[-] {:?}@{}", self.val, self.index)
    }
}

#[derive(Clone, Copy)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
struct Push<V> {
    pub val: V,
}

impl<V: Clone> Push<V> {
    pub fn forward(&self, vec: &mut Vec<V>) {
        vec.push(self.val.clone());
    }

    pub fn reverse(&self, vec: &mut Vec<V>) {
        vec.pop();
    }
}

impl<V: Debug> std::fmt::Debug for Push<V> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "[V] {:?}", self.val)
    }
}

#[derive(Clone, Copy)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
struct Pop<V> {
    pub val: V,
}

impl<V: Clone> Pop<V> {
    pub fn forward(&self, vec: &mut Vec<V>) {
        vec.pop();
    }

    pub fn reverse(&self, vec: &mut Vec<V>) {
        vec.push(self.val.clone());
    }
}

impl<V: Debug> std::fmt::Debug for Pop<V> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "[^] {:?}", self.val)
    }
}

#[derive(Clone, Copy)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
enum JournalEntry<V, T> {
    Insert(Insert<V>),
    Remove(Remove<V>),
    Push(Push<V>),
    Pop(Pop<V>),
    Tag(Tag<T>),
}

impl<V: Clone, T: Hash + Eq + Clone> JournalEntry<V, T> {
    pub fn reverse(&self, vec: &mut Vec<V>) {
        match self {
            Self::Insert(entry_data) => entry_data.reverse(vec),
            Self::Remove(entry_data) => entry_data.reverse(vec),
            Self::Push(entry_data) => entry_data.reverse(vec),
            Self::Pop(entry_data) => entry_data.reverse(vec),
            Self::Tag(_) => {}
        }
    }

    pub fn forward(&self, vec: &mut Vec<V>) {
        match self {
            Self::Insert(entry_data) => entry_data.forward(vec),
            Self::Remove(entry_data) => entry_data.forward(vec),
            Self::Push(entry_data) => entry_data.forward(vec),
            Self::Pop(entry_data) => entry_data.forward(vec),
            Self::Tag(_) => {}
        }
    }
}

/// Journaling Vector. Each transaction is recorded to the journal and can be
/// undone and redone.
///
/// **NOTE:** Current implementation makes copies of all data & tags.
/// Memory usage is at least doubled, and if you're using data types which
/// are large there can be a decent performance hit on write.
///
/// ## Usage
///
/// JournalVec are designed to provide a simple interface to implement undo,
/// redo and version control. This is achieved via recording all transactions
/// in a journal and by adding "tags", which are basically just generic markers
/// that can be used as undo checkpoints or version identifiers.
///
/// ```rust
/// use journalmap::JournalVec;
///
/// fn main() {
///    let mut rsvp: JournalVec<&'static str, _> = JournalVec::new();
///
///     // Always add a tag at the start
///     rsvp.append_tag("start").unwrap();
///
///     rsvp.push("Sarah");
///     rsvp.push("John");
///     rsvp.push("Mariah");
///     rsvp.insert(1, "Steve");
///
///     rsvp.append_tag("middle").unwrap();
///
///     rsvp.pop();
///     rsvp.remove(1);
///
///     rsvp.append_tag("end").unwrap();
///
///      // Now let's reverse it and watch our changes be undone...
///     rsvp.reverse_to_next();
///
///     assert_eq!(rsvp.as_slice(), &["Sarah", "Steve", "John", "Mariah"]);
///
///     // We can also redo the chanes we've applied
///     rsvp.forward_to_tag(&"end");
///
///     assert_eq!(rsvp.as_slice(), &["Sarah", "John"]);
///
///     rsvp.reverse_to_next();
///
///     // Inserting a new entry truncates the future so we can no longer
///     // re-do the changes we've undone
///     rsvp.push("Omar");
///     rsvp.append_tag("end").unwrap();
///
///     assert_eq!(rsvp.as_slice(), &["Sarah", "Steve", "John", "Mariah", "Omar"]);
/// }
/// ```
pub struct JournalVec<V, T: Eq + Hash> {
    journal: Vec<JournalEntry<V, T>>,
    tags: HashSet<T>,
    vec: Vec<V>,
    current_tag_index: Option<usize>,
}

impl<V, T: Eq + Hash> JournalVec<V, T> {
    pub fn new() -> Self {
        Self {
            journal: Vec::new(),
            tags: HashSet::new(),
            vec: Vec::new(),
            current_tag_index: None,
        }
    }

    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            journal: Vec::with_capacity(capacity),
            tags: HashSet::with_capacity(capacity),
            vec: Vec::with_capacity(capacity),
            current_tag_index: None,
        }
    }

    #[inline]
    pub fn len(&self) -> usize {
        self.vec.len()
    }

    #[inline]
    pub fn is_empty(&self) -> bool {
        self.vec.is_empty()
    }

    pub fn current_tag(&self) -> Option<&T> {
        let Some(i_tag) = self.current_tag_index else {
            return None;
        };

        let JournalEntry::Tag(tag) = &self.journal[i_tag] else {
            panic!("Tag not at tag index");
        };

        Some(&tag.tag)
    }

    #[inline]
    pub fn as_slice(&self) -> &[V] {
        self.vec.as_slice()
    }

    /// Clears the map and the journal.
    pub fn clear_all(&mut self) {
        self.vec.clear();
        self.journal.clear();
        self.tags.clear();
        self.current_tag_index = None;
    }

    /// Used to prepare for another journal entry. Truncates the journal past
    /// the current tag, and clears the current tag index.
    fn transaction_prep(&mut self) {
        let Some(i_tag) = self.current_tag_index.take() else {
            return;
        };

        let i_trunc = i_tag + 1;

        for entry in self.journal[i_trunc..].iter() {
            if let JournalEntry::Tag(tag) = entry {
                self.tags.remove(&tag.tag);
            }
        }

        self.journal.truncate(i_trunc);
    }

    /// Searches the journal in reverse from the current tag to find a tag
    /// that matches the match function, returning the range to apply the
    /// reverse function to. Also sets the current tag to the tag that matches
    /// the match function.
    fn i_tag_reverse_seek<MatchFn: Fn(&T) -> bool>(
        &mut self,
        match_fn: MatchFn,
    ) -> Option<Range<usize>> {
        let i_reverse_end = self.current_tag_index.unwrap_or(self.journal.len());

        let Some(i_tag_rev_rel) = self.journal[..i_reverse_end]
            .iter()
            .rev()
            .position(|entry| {
                if let JournalEntry::Tag(tag) = entry
                    && match_fn(&tag.tag)
                {
                    true
                } else {
                    false
                }
            })
        else {
            return None;
        };

        let i_tag = i_reverse_end - i_tag_rev_rel - 1;

        self.current_tag_index = Some(i_tag);

        let i_reverse_start = i_tag + 1;

        Some(i_reverse_start..i_reverse_end)
    }

    /// Searches the journal in from the current tag to find a tag
    /// that matches the match function, returning the range to apply the
    /// reverse function to. Also sets the current tag to the tag that matches
    /// the match function.
    fn i_tag_forward_seek<MatchFn: Fn(&T) -> bool>(
        &mut self,
        match_fn: MatchFn,
    ) -> Option<Range<usize>> {
        let Some(i_current_tag) = self.current_tag_index else {
            return None;
        };

        let i_forward_start = i_current_tag + 1;

        let Some(i_next_tag_rel) = self.journal[i_forward_start..].iter().position(|entry| {
            if let JournalEntry::Tag(tag) = entry
                && match_fn(&tag.tag)
            {
                true
            } else {
                false
            }
        }) else {
            return None;
        };

        let i_next_tag = i_forward_start + i_next_tag_rel;

        self.current_tag_index = Some(i_next_tag);

        let i_forward_end = i_next_tag;

        Some(i_forward_start..i_forward_end)
    }
}

impl<V: Clone, T: Eq + Hash + Clone> JournalVec<V, T> {
    pub fn insert(&mut self, index: usize, val: V) {
        self.transaction_prep();

        self.vec.insert(index, val.clone());

        self.journal
            .push(JournalEntry::Insert(Insert { val, index }));
    }

    pub fn get(&self, index: usize) -> Option<&V> {
        self.vec.get(index)
    }

    /// **NOTE:** non-panicing vs. the original vec implementation of `.remove()`,
    /// instead returns Some if the index is in bounds and None if it is out of
    /// bounds.
    pub fn remove(&mut self, index: usize) -> Option<V> {
        if self.vec.len() <= index {
            return None;
        }

        self.transaction_prep();

        let val = self.vec.remove(index);

        self.journal.push(JournalEntry::Remove(Remove {
            val: val.clone(),
            index,
        }));

        Some(val)
    }

    /// **NOTE:** Does not clear journal. Performs repeated pop operations on
    /// the vec, recording each. If you want to clear the map and the journal,
    /// use `clear_all()`
    pub fn clear(&mut self) {
        self.transaction_prep();

        while self.pop().is_some() {}
    }

    pub fn push(&mut self, val: V) {
        self.transaction_prep();
        self.vec.push(val.clone());
        self.journal.push(JournalEntry::Push(Push { val }));
    }

    pub fn pop(&mut self) -> Option<V> {
        let Some(val) = self.vec.pop() else {
            return None;
        };

        self.transaction_prep();

        self.journal
            .push(JournalEntry::Pop(Pop { val: val.clone() }));

        Some(val)
    }

    /// Insert a tag at the current journal index. If the tag already exists,
    /// return an error.
    pub fn append_tag(&mut self, tag: T) -> Result<(), JournalError<T>> {
        if self.tags.contains(&tag) {
            return Err(JournalError::TagExists { tag });
        }

        self.current_tag_index = Some(self.journal.len());
        self.journal
            .push(JournalEntry::Tag(Tag { tag: tag.clone() }));
        self.tags.insert(tag);

        Ok(())
    }

    /// Replays the journal in reverse till the next tag is found. If no
    /// tag is found, nothing happens.
    pub fn reverse_to_next(&mut self) -> bool {
        let Some(range) = self.i_tag_reverse_seek(|_| true) else {
            return false;
        };

        if range.is_empty() {
            return false;
        }

        self.reverse_range(range);

        true
    }

    /// Replays the journal in reverse till the specified tag is found. If the
    /// tag isn't found, nothing happens.
    pub fn reverse_to_tag(&mut self, tag: &T) -> bool {
        let Some(range) = self.i_tag_reverse_seek(|other_tag| other_tag == tag) else {
            return false;
        };

        if range.is_empty() {
            return false;
        }

        self.reverse_range(range);

        true
    }

    /// Replays the journal till the next tag is found. If no
    /// tag is found, nothing happens.
    pub fn forward_to_next(&mut self) -> bool {
        let Some(range) = self.i_tag_forward_seek(|_| true) else {
            return false;
        };

        if range.is_empty() {
            return false;
        }

        self.forward_range(range);

        true
    }

    /// Replays the journal till the specified tag is found. If the
    /// tag isn't found, nothing happens.
    pub fn forward_to_tag(&mut self, tag: &T) -> bool {
        let Some(range) = self.i_tag_forward_seek(|other_tag| other_tag == tag) else {
            return false;
        };

        if range.is_empty() {
            return false;
        }

        self.forward_range(range);

        true
    }

    /// Replays the journal entries in the specified range in reverse
    fn reverse_range(&mut self, range: Range<usize>) {
        for entry in self.journal[range].iter().rev() {
            entry.reverse(&mut self.vec);
        }
    }

    /// Replays the journal entries in the specified range
    fn forward_range(&mut self, range: Range<usize>) {
        for entry in self.journal[range].iter() {
            entry.forward(&mut self.vec);
        }
    }

    /// Generates a journal struct based on the current state of the JournalVec.
    ///
    /// ### Flags:
    /// * `truncate_future` - remove all journal entries past the currently
    /// selected tag.
    pub fn generate_journal(&self, truncate_future: bool) -> JournalVecJournal<V, T> {
        let i_copy_start = 0;
        let i_copy_end = if truncate_future && let Some(i_tag) = self.current_tag_index {
            i_tag + 1
        } else {
            self.journal.len()
        };

        let journal_src = &self.journal[i_copy_start..i_copy_end];

        let journal = journal_src.to_vec();

        JournalVecJournal { journal }
    }

    /// Generated a JournalVec by replaying a JournalVecJournal from start to
    /// finish.
    pub fn from_journal(val: &JournalVecJournal<V, T>) -> Self {
        let capacity = val.journal.len();
        let vec = Vec::with_capacity(capacity);
        let tags = HashSet::with_capacity(capacity);
        let mut journal_vec = Self {
            vec,
            tags,
            journal: val.journal.clone(),
            current_tag_index: None,
        };

        for entry in journal_vec.journal.iter() {
            entry.forward(&mut journal_vec.vec);

            if let JournalEntry::Tag(tag) = entry {
                journal_vec.tags.insert(tag.tag.clone());
            }
        }

        journal_vec
    }
}

impl<V, T: Eq + Hash> std::ops::Index<usize> for JournalVec<V, T> {
    type Output = V;

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

impl<V: Debug, T: Debug + Eq + Hash> std::fmt::Debug for JournalVec<V, T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let alternate = f.alternate();
        write!(f, "{{")?;
        for (i_entry, entry) in self.journal.iter().enumerate() {
            if alternate {
                write!(f, "\n\t")?;
            }
            match entry {
                JournalEntry::Insert(entry) => {
                    write!(f, "{:?}", entry)?;
                }
                JournalEntry::Remove(entry) => {
                    write!(f, "{:?}", entry)?;
                }
                JournalEntry::Push(entry) => {
                    write!(f, "{:?}", entry)?;
                }
                JournalEntry::Pop(entry) => {
                    write!(f, "{:?}", entry)?;
                }
                JournalEntry::Tag(tag) => {
                    if let Some(i_tag) = self.current_tag_index
                        && i_tag == i_entry
                    {
                        {
                            write!(f, "@ [T] {:?}", tag.tag)?;
                        }
                    } else {
                        {
                            write!(f, "[T] {:?}", tag.tag)?;
                        }
                    }
                }
            }

            write!(f, ",")?;
        }

        if alternate {
            write!(f, "\n")?;
        }

        write!(f, "}}")?;

        Ok(())
    }
}

/// An extracted journal from a JournalVec. Used for storage purposes: if you
/// want to serialize a JournalVec for later, you want to extract a
/// JournalVecJournal and then serialize said journal.
pub struct JournalVecJournal<V, T> {
    journal: Vec<JournalEntry<V, T>>,
}

#[cfg(feature = "serde")]
impl<V: SerializeTrait, T: SerializeTrait + Eq + Hash> SerializeTrait for JournalVecJournal<V, T> {
    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
        self.journal.serialize(serializer)
    }
}

#[cfg(feature = "serde")]
impl<'de, V: DeserializeTrait<'de>, T: DeserializeTrait<'de> + Eq + Hash> DeserializeTrait<'de>
    for JournalVecJournal<V, T>
{
    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
        Ok(Self {
            journal: Vec::deserialize(deserializer)?,
        })
    }
}