/** A mergable dictionary.
 *
 * This dict must contain a `Mergable` value. This determines the semantics on conflict. For example if the value is a `Cell` then last-write-wins semantics will be used. However if the value is a `Bag` then multiple values inserted into the same key will be kept. If the value is a `Counter` than conflicting values will be summed.
 */
#[derive(Clone)]
pub struct Dict<K, V, Seq> {
	live: std::collections::HashMap<K, Value<V, Seq>>,
	removed: std::collections::HashMap<K, Seq>,

	// A key can be in both `live` and `removed` however in that case the live sequence number is always higher than the removed sequence number.
}

pub struct DictDiff<K, V: crate::Mergable, Seq> {
	updates: Vec<(K, Seq, Update<V>)>,
}

impl<
	K: std::fmt::Debug,
	V: crate::Mergable + std::fmt::Debug,
	Seq: std::fmt::Debug
>
	std::fmt::Debug for DictDiff<K, V, Seq>
where V::Diff: std::fmt::Debug
{
	fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
		write!(f, "DictDiff(")?;
		self.updates.fmt(f)?;
		write!(f, ")")
	}
}

#[derive(Debug)]
enum Update<V: crate::Mergable> {
	Removed,
	Diff(V::Diff),
	Value(V),
}

// impl<V: crate::Mergable + std::fmt::Debug> std::fmt::Debug for Update<V>
// where V::Diff: std::fmt::Debug
// {
// 	fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
// 		match self {
// 			Removed => write!(f, "Removed"),
// 			Diff(diff) => {
// 				write!(f, "Diff(")?;
// 				diff.fmt(f)?;
// 				write!(f, ")")
// 			}
// 			Value(value) => {
// 				write!(f, "Value(")?;
// 				value.fmt(f)?;
// 				write!(f, ")")
// 			}
// 		}
// 	}
// }

impl<
	K: Clone + Eq + std::hash::Hash,
	V: crate::Mergable,
	SF: crate::SequenceFactory,
>
	Dict<K, V, crate::Sequence<SF>>
{
	pub fn entry<'a>(&'a mut self, key: K) -> DictEntry<'a, K, V, SF> {
		match self.live.entry(key) {
			std::collections::hash_map::Entry::Occupied(entry) => {
				DictEntry::Occupied(DictOccupiedEntry {
					entry,
					removed: &mut self.removed,
				})
			}
			std::collections::hash_map::Entry::Vacant(entry) => {
				DictEntry::Vacant(DictVacantEntry {
					entry,
				})
			}
		}
	}

	pub fn get<
		Q: std::hash::Hash + Eq>
		(&self, k: &Q) -> Option<&V>
		where K: std::borrow::Borrow<Q>
	{
		self.live.get(k).map(|v| &v.value)
	}

	/** Insert a value into the map.
	 *
	 * Note that if the value is already in the map the two values will be *merged*. If you do not want this to occur `delete` the value first.

	 * Also note that this updates the key's creation time meaning that deletes on the previous key will no longer be respected.

	 * TODO: Weird revival stuff.
	*/
	pub fn insert(&mut self, ctx: &mut crate::Context<SF>, k: K, v: V) {
		self.entry(k).insert(ctx, v);
	}

	/** Remove a value from the map.
	 *
	 * Note that the semantics of this operation can be confusing read the description carefully.
	 *
	 * This removes the *known* version of the element in the map and all older versions. Unknown modifications will not prevent deletion but if the element has been `insert`ed again after the version that we are aware of that insert will be preserved. Also note that due to merging semantics that may result in values from the known version "reappearing".
	 */
	pub fn remove<Q: ?Sized>(&mut self, k: K) -> Option<V>
		where
			K: std::borrow::Borrow<Q>,
			Q: std::hash::Hash + Eq
	{
		if let DictEntry::Occupied(entry) = self.entry(k) {
			Some(entry.remove())
		} else {
			None
		}
	}

	fn apply(&mut self,
		that: impl IntoIterator<Item=(K, crate::Sequence<SF>, Update<V>)>)
		-> Result<(), crate::ApplyError>
	{
		for (k, sequence, value) in that {
			match value {
				Update::Removed => {
					let k = match self.removed.entry(k) {
						std::collections::hash_map::Entry::Occupied(mut entry) => {
							if entry.get() >= &sequence {
								continue
							}
							entry.insert(sequence.clone());
							entry.key().clone()
						}
						std::collections::hash_map::Entry::Vacant(entry) => {
							let k = entry.key().clone();
							entry.insert(sequence.clone());
							k
						}
					};

					let entry = self.live.entry(k);
					if let std::collections::hash_map::Entry::Occupied(entry) = entry {
						if entry.get().sequence <= sequence {
							eprintln!("remove");
							entry.remove();
						}
					}
				}
				value => {
					match self.live.entry(k) {
						std::collections::hash_map::Entry::Occupied(mut entry) => {
							let slot = entry.get_mut();
							if sequence > slot.sequence {
								slot.sequence = sequence;
							}
							match value {
								Update::Removed => unreachable!(),
								Update::Diff(d) => slot.value.apply(d)?,
								Update::Value(v) => slot.value.merge(v),
							}
						}
						std::collections::hash_map::Entry::Vacant(entry) => {
							if let Some(seq) = self.removed.get(entry.key()) {
								if seq >= &sequence {
									continue
								}
							}

							let value = match value {
								Update::Removed => unreachable!(),
								Update::Diff(_) => return Err(crate::ApplyError::Missing("Target doesn't contain base value for diff.".into())),
								Update::Value(v) => v,
							};
							entry.insert(Value{
								sequence,
								value,
							});
						}
					}
				}
			}
		}

		Ok(())
	}
}

impl<
	K: Clone + Eq + std::hash::Hash,
	V: Clone + crate::Mergable,
	SF: crate::SequenceFactory,
>
	crate::Mergable for Dict<K, V, crate::Sequence<SF>>
{
	type Diff = DictDiff<K, V, crate::Sequence<SF>>;

	fn merge(&mut self, that: Self) {
		let removed = that.removed.into_iter()
			.map(|(k, sequence)| (k, sequence, Update::Removed));
		let live = that.live.into_iter()
			.map(|(k, Value{sequence, value})| (k, sequence, Update::Value(value)));
		self.apply(removed.chain(live)).unwrap()
	}

	fn diff(&self, that: &Self) -> Self::Diff {
		let mut updates = Vec::new();
		for (k, seq) in &self.removed {
			if let Some(that_seq) = that.removed.get(k) {
				if that_seq == seq {
					continue
				}
			}

			updates.push((k.clone(), seq.clone(), Update::Removed));
		}
		for (k, v) in &self.live {
			if let Some(sequence) = that.removed.get(k) {
				if sequence >= &v.sequence {
					continue
				}
			}
			updates.push((
				k.clone(),
				v.sequence.clone(),
				match that.get(k) {
					Some(known) => Update::Diff(v.value.diff(known)),
					None => Update::Value(v.value.clone()),
				}));
		}

		DictDiff { updates }
	}

	fn apply(&mut self, diff: Self::Diff) -> Result<(), crate::ApplyError> {
		self.apply(diff.updates)
	}
}

impl<
	K,
	V,
	SF,
>
  Default for Dict<K, V, SF>
{
	fn default() -> Self {
		Dict {
			live: Default::default(),
			removed: Default::default(),
		}
	}
}

impl<K: Eq + std::hash::Hash, V: PartialEq, Seq> PartialEq for Dict<K, V, Seq> {
	fn eq(&self, that: &Self) -> bool {
		self.live == that.live
	}
}

impl<K: std::fmt::Debug, V: std::fmt::Debug, Seq> std::fmt::Debug for Dict<K, V, Seq> {
	fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
		self.live.fmt(f)
	}
}

#[derive(Clone)]
struct Value<V, Seq> {
	sequence: Seq,
	value: V,
}

impl<V: PartialEq, Seq> PartialEq for Value<V, Seq> {
	fn eq(&self, that: &Self) -> bool {
		self.value == that.value
	}
}

impl<V: std::fmt::Debug, Seq> std::fmt::Debug for Value<V, Seq> {
	fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
		// write!(f, "{:?} @ {:?}", self.value, self.sequence)
		self.value.fmt(f)
	}
}

pub enum DictEntry<'a, K: 'a, V: 'a, SF: crate::SequenceFactory> {
	Occupied(DictOccupiedEntry<'a, K, V, SF>),
	Vacant(DictVacantEntry<'a, K, V, SF>),
}

impl<'a,
	K: 'a + Eq + std::hash::Hash,
	V: 'a + crate::Mergable,
	SF: crate::SequenceFactory
>
	DictEntry<'a, K, V, SF>
{
	pub fn insert(self, ctx: &'a mut crate::Context<SF>, v: V) -> &'a mut V {
		match self {
			DictEntry::Occupied(mut entry) => {
				entry.insert(ctx, v);
				entry.into_mut()
			}
			DictEntry::Vacant(entry) => entry.insert(ctx, v),
		}
	}

	pub fn or_insert(self, ctx: &'a mut crate::Context<SF>, v: V) -> &'a mut V {
		match self {
			DictEntry::Occupied(mut entry) => {
				entry.insert(ctx, v);
				entry.into_mut()
			}
			DictEntry::Vacant(entry) => entry.insert(ctx, v),
		}
	}
}

pub struct DictOccupiedEntry<'a, K: 'a, V: 'a, SF: crate::SequenceFactory> {
	entry: std::collections::hash_map::OccupiedEntry<'a, K, Value<V, crate::Sequence<SF>>>,
	removed: &'a mut std::collections::HashMap<K, crate::Sequence<SF>>,
}

impl<'a,
	K: 'a + Eq + std::hash::Hash,
	V: 'a + crate::Mergable,
	SF: crate::SequenceFactory
>
	DictOccupiedEntry<'a, K, V, SF>
{
	pub fn into_mut(self) -> &'a mut V {
		&mut self.entry.into_mut().value
	}

	pub fn insert(&mut self, ctx: &'a mut crate::Context<SF>, v: V) {
		self.entry.get_mut().sequence = ctx.next_sequence();
		self.entry.get_mut().value.merge(v);
	}

	pub fn remove(self) -> V {
		let (k, Value{sequence, value}) = self.entry.remove_entry();
		self.removed.insert(k, sequence);
		value
	}
}

pub struct DictVacantEntry<'a, K: 'a, V: 'a, SF: crate::SequenceFactory> {
	entry: std::collections::hash_map::VacantEntry<'a, K, Value<V, crate::Sequence<SF>>>,
}

impl<'a, K: 'a, V: 'a, SF: crate::SequenceFactory> DictVacantEntry<'a, K, V, SF> {
	pub fn insert(self, ctx: &'a mut crate::Context<SF>, value: V) -> &'a mut V {
		&mut self.entry.insert(
			Value {
				sequence: ctx.next_sequence(),
				value,
			})
			.value
	}
}

#[test]
fn test_dict() {
	let mut ctx = crate::Context::default();

	let one = crate::Cell::new(&mut ctx, "one");
	let two = crate::Cell::new(&mut ctx, "two");

	let result = crate::test::test_merge(&mut [one.clone(), two.clone()]);
	assert_eq!(*result, "two");

	let mut parent_l = Dict::default();
	parent_l.insert(&mut ctx, 0, two.clone());

	let mut parent_r = Dict::default();
	parent_r.insert(&mut ctx, 0, one.clone());

	let merged = crate::test::test_merge(&mut [parent_l.clone(), parent_r.clone()]);
	assert_eq!(merged, parent_l);

	let mut child_l = merged.clone();
	child_l.insert(&mut ctx, 1, one.clone());

	let mut child_r = merged;
	child_r.insert(&mut ctx, 2, two.clone());

	let merged = crate::test::test_merge(&mut [parent_l, parent_r, child_l, child_r]);
	let mut expected = Dict::default();
	expected.insert(&mut ctx, 0, two.clone());
	expected.insert(&mut ctx, 1, one.clone());
	expected.insert(&mut ctx, 2, two.clone());
	assert_eq!(merged, expected);
}

#[test]
fn test_dict_remove_old() {
	let mut ctx = crate::Context::default();

	let one = crate::Cell::new(&mut ctx, "one");
	let two = crate::Cell::new(&mut ctx, "two");

	let mut parent_l = Dict::default();
	parent_l.insert(&mut ctx, 0, two.clone());

	let mut parent_r = Dict::default();
	parent_r.insert(&mut ctx, 0, one.clone());

	// We remove the left entry. However the right is created after this.
	parent_l.remove(0);

	let merged = crate::test::test_merge(&mut [parent_l.clone(), parent_r.clone()]);
	assert_eq!(merged, parent_r);
}

#[test]
fn test_dict_remove_new() {
	let mut ctx = crate::Context::default();

	let one = crate::Cell::new(&mut ctx, "one");
	let two = crate::Cell::new(&mut ctx, "two");

	let mut parent_l = Dict::default();
	parent_l.insert(&mut ctx, 0, two.clone());

	let mut parent_r = Dict::default();
	parent_r.insert(&mut ctx, 0, one.clone());

	// We remove the right entry. Since this was created later the removal wins.
	parent_r.remove(0);

	let merged = crate::test::test_merge(&mut [parent_l.clone(), parent_r.clone()]);
	assert_eq!(merged, parent_r);
}

#[test]
fn test_dict_remove_merge_revive() {
	let mut ctx = crate::Context::default();

	let one = crate::Cell::new(&mut ctx, "one");
	let two = crate::Cell::new(&mut ctx, "two");

	let mut root = Dict::default();
	root.insert(&mut ctx, 0, two.clone());

	// Note that this "insert" actually merges the cells, resulting in "two" winning because it is newer (even though the insert happened earlier.
	let mut child_insert = root.clone();
	child_insert.insert(&mut ctx, 0, one.clone());

	// This removes the value. However since it doesn't know about child_insert's insertion that is preserved and the "two" value is "revived".
	let mut child_remove = root.clone();
	child_remove.remove(0);

	let merged = crate::test::test_merge(&mut [child_remove, child_insert.clone()]);
	assert_eq!(merged, child_insert);
}