deepmerge 0.1.0

//! Kind-specific merge handlers
//!
//! This module provides merge implementations for different kinds of types
//! (collections, options, numbers, maps) based on policy settings.

use crate::policy::{Policy, Condition, NumberMerge, BoolMerge, DeepMergeFrom, OptionMerge, SequenceMerge, MapMerge};
use crate::DeepMerge;

// ============================================================================
// Condition check helpers - inlined for hot paths
// ============================================================================

/// Check if a string merge should proceed based on the condition
#[allow(clippy::inline_always)]
#[inline(always)]
fn should_merge_string<P: Policy>(dst: &str, src: &str, policy: &P) -> bool {
    match policy.when_condition() {
        Condition::NonEmpty | Condition::NonDefault => !src.is_empty(),
        Condition::Always | Condition::Some => true, // Not applicable to strings
        Condition::Changed | Condition::ChangedBy(_) => dst != src,
    }
}

/// Check if a vec merge should proceed based on the condition
#[allow(clippy::inline_always)]
#[inline(always)]
fn should_merge_vec<T, P: Policy>(src: &[T], policy: &P) -> bool {
    match policy.when_condition() {
        Condition::NonEmpty | Condition::NonDefault => !src.is_empty(),
        // Not applicable to vecs
        Condition::Always | Condition::Some | Condition::Changed | Condition::ChangedBy(_) => true, // Can't check without PartialEq
    }
}

/// Check if a number merge should proceed based on the condition
#[allow(clippy::inline_always)]
#[inline(always)]
fn should_merge_number<T: PartialEq + Default, P: Policy>(dst: &T, src: &T, policy: &P) -> bool {
    match policy.when_condition() {
        Condition::Always | Condition::NonEmpty | Condition::Some => true, // Numbers are always "non-empty", Some not applicable
        Condition::NonDefault => *src != T::default(),
        Condition::Changed | Condition::ChangedBy(_) => dst != src,
    }
}

/// Check if a bool merge should proceed based on the condition
#[allow(clippy::inline_always)]
#[inline(always)]
fn should_merge_bool<P: Policy>(dst: bool, src: bool, policy: &P) -> bool {
    match policy.when_condition() {
        Condition::Always | Condition::NonEmpty | Condition::Some => true, // Bools are always "non-empty", Some not applicable
        Condition::NonDefault => src, // false is default, so true for non-false values
        Condition::Changed | Condition::ChangedBy(_) => dst != src,
    }
}

/// Check if a map merge should proceed based on the condition
#[allow(clippy::inline_always)]
#[inline(always)]
fn should_merge_map<K, V, P: Policy>(other: &impl MapLike<K, V>, policy: &P) -> bool {
    match policy.when_condition() {
        Condition::NonEmpty | Condition::NonDefault => !other.is_empty(),
        // Not applicable to maps, can't check efficiently
        Condition::Always | Condition::Some | Condition::Changed | Condition::ChangedBy(_) => true,
    }
}

/// Check if a set merge should proceed based on the condition
#[allow(clippy::inline_always)]
#[inline(always)]
fn should_merge_set<T, P: Policy>(other: &impl SetLike<T>, policy: &P) -> bool {
    match policy.when_condition() {
        Condition::NonEmpty | Condition::NonDefault => !other.is_empty(),
        // Not applicable to sets, can't check efficiently
        Condition::Always | Condition::Some | Condition::Changed | Condition::ChangedBy(_) => true,
    }
}

// Helper traits for generic map/set operations
trait MapLike<K, V> {
    fn is_empty(&self) -> bool;
}

trait SetLike<T> {
    fn is_empty(&self) -> bool;
}

#[cfg(feature = "std")]
impl<K, V> MapLike<K, V> for HashMap<K, V> {
    fn is_empty(&self) -> bool { self.is_empty() }
}

#[cfg(feature = "std")]
impl<K, V> MapLike<K, V> for BTreeMap<K, V> {
    fn is_empty(&self) -> bool { self.is_empty() }
}

#[cfg(feature = "indexmap")]
impl<K, V> MapLike<K, V> for IndexMap<K, V> {
    fn is_empty(&self) -> bool { self.is_empty() }
}

#[cfg(feature = "std")]
impl<T> SetLike<T> for HashSet<T> {
    fn is_empty(&self) -> bool { self.is_empty() }
}

#[cfg(feature = "std")]
impl<T> SetLike<T> for BTreeSet<T> {
    fn is_empty(&self) -> bool { self.is_empty() }
}

#[cfg(feature = "indexmap")]
impl<T> SetLike<T> for IndexSet<T> {
    fn is_empty(&self) -> bool { self.is_empty() }
}

// Feature-gated modules for external types
#[cfg(feature = "serde_json")]
mod serde_json;

#[cfg(feature = "toml")]
mod toml_value;

#[cfg(feature = "alloc")]
use alloc::vec::Vec;
#[cfg(feature = "alloc")]
use alloc::string::String;
#[cfg(feature = "alloc")]
use alloc::collections::LinkedList;
#[cfg(feature = "alloc")]
use alloc::collections::VecDeque;

#[cfg(feature = "std")]
use std::collections::{HashMap, HashSet, BTreeMap, BTreeSet};
#[cfg(any(feature = "std", feature = "indexmap"))]
use core::hash::Hash;

#[cfg(feature = "indexmap")]
use indexmap::{IndexMap, IndexSet};

// ============================================================================
// Built-in Merge implementations using Policy
// ============================================================================

// Primitive types - numbers
macro_rules! impl_number_merge {
    ($($t:ty),*) => {
        $(
            impl<P: Policy> DeepMerge<P> for $t {
                fn merge_with_policy(&mut self, other: Self, policy: &P) {
                    if !should_merge_number(self, &other, policy) {
                        return;
                    }
                    
                    // Apply merge
                    match policy.number_merge() {
                        NumberMerge::Replace => *self = other,
                        NumberMerge::Keep => {}, // Keep left value
                        NumberMerge::Max => *self = (*self).max(other),
                        NumberMerge::Min => *self = (*self).min(other),
                        NumberMerge::Sum => *self += other,
                    }
                }
            }
        )*
    }
}

impl_number_merge!(i8, i16, i32, i64, i128, isize);
impl_number_merge!(u8, u16, u32, u64, u128, usize);
impl_number_merge!(f32, f64);

// Bool implementation
impl<P: Policy> DeepMerge<P> for bool {
    fn merge_with_policy(&mut self, other: Self, policy: &P) {
        if !should_merge_bool(*self, other, policy) {
            return;
        }
        
        // Apply merge
        match policy.bool_merge() {
            BoolMerge::Replace => *self = other,
            BoolMerge::Keep => {},
            BoolMerge::TrueWins => {
                if other {
                    *self = true;
                }
            },
            BoolMerge::FalseWins => {
                if !other {
                    *self = false;
                }
            },
        }
    }
}

// String implementation
#[cfg(feature = "alloc")]
impl<P: Policy> DeepMerge<P> for String {
    fn merge_with_policy(&mut self, other: Self, policy: &P) {
        if !should_merge_string(self, &other, policy) {
            return;
        }
        
        // Apply string merge strategy
        match policy.string_merge() {
            crate::policy::StringMerge::Replace => *self = other,
            crate::policy::StringMerge::Keep => {},
            crate::policy::StringMerge::Concat => {
                self.push_str(&other);
            },
            crate::policy::StringMerge::ConcatWithSep(sep) => {
                if !self.is_empty() && !other.is_empty() {
                    self.push_str(sep);
                }
                self.push_str(&other);
            },
        }
    }

    fn merge_ref(&mut self, src: &Self, policy: &P)
    where
        Self: Clone,
    {
        // Check condition first to avoid unnecessary cloning
        if !should_merge_string(self, src, policy) {
            return;
        }
        
        // Apply string merge strategy
        match policy.string_merge() {
            crate::policy::StringMerge::Replace => self.clone_from(src),
            crate::policy::StringMerge::Keep => {},
            crate::policy::StringMerge::Concat => {
                self.push_str(src);
            },
            crate::policy::StringMerge::ConcatWithSep(sep) => {
                if !self.is_empty() && !src.is_empty() {
                    self.push_str(sep);
                }
                self.push_str(src);
            },
        }
    }

    fn merge_with_policy_reporting(&mut self, other: Self, policy: &P) -> crate::policy::MergeOutcome {
        let old_value = self.clone();
        self.merge_with_policy(other, policy);
        if *self == old_value {
            crate::policy::MergeOutcome::Unchanged
        } else {
            crate::policy::MergeOutcome::Changed
        }
    }

    fn merge_ref_reporting(&mut self, src: &Self, policy: &P) -> crate::policy::MergeOutcome
    where
        Self: Clone,
    {
        // Check condition first
        if !should_merge_string(self, src, policy) {
            return crate::policy::MergeOutcome::Unchanged;
        }
        
        let will_change = match policy.string_merge() {
            crate::policy::StringMerge::Replace => *self != *src,
            crate::policy::StringMerge::Keep => false,
            crate::policy::StringMerge::Concat => !src.is_empty(),
            crate::policy::StringMerge::ConcatWithSep(sep) => {
                !src.is_empty() && (self.is_empty() || !sep.is_empty())
            },
        };
        
        if will_change {
            match policy.string_merge() {
                crate::policy::StringMerge::Replace => self.clone_from(src),
                crate::policy::StringMerge::Keep => {}, // Won't reach here as will_change is false for Keep
                crate::policy::StringMerge::Concat => {
                    self.push_str(src);
                },
                crate::policy::StringMerge::ConcatWithSep(sep) => {
                    if !self.is_empty() && !src.is_empty() {
                        self.push_str(sep);
                    }
                    self.push_str(src);
                },
            }
            crate::policy::MergeOutcome::Changed
        } else {
            crate::policy::MergeOutcome::Unchanged
        }
    }
}

// DeepMergeFrom implementations for String to avoid unnecessary cloning
#[cfg(feature = "alloc")]
impl<P: Policy> DeepMergeFrom<&str, P> for String {
    fn merge_from_with_policy(&mut self, other: &str, policy: &P) {
        if !should_merge_string(self, other, policy) {
            return;
        }
        
        // Apply string merge strategy
        match policy.string_merge() {
            crate::policy::StringMerge::Replace => {
                self.clear();
                self.push_str(other);
            },
            crate::policy::StringMerge::Keep => {},
            crate::policy::StringMerge::Concat => {
                self.push_str(other);
            },
            crate::policy::StringMerge::ConcatWithSep(sep) => {
                if !self.is_empty() && !other.is_empty() {
                    self.push_str(sep);
                }
                self.push_str(other);
            },
        }
    }

    fn merge_from_with_policy_reporting(&mut self, other: &str, policy: &P) -> crate::policy::MergeOutcome {
        // Check condition first
        if !should_merge_string(self, other, policy) {
            return crate::policy::MergeOutcome::Unchanged;
        }
        
        let will_change = match policy.string_merge() {
            crate::policy::StringMerge::Replace => *self != other,
            crate::policy::StringMerge::Keep => false,
            crate::policy::StringMerge::Concat => !other.is_empty(),
            crate::policy::StringMerge::ConcatWithSep(sep) => {
                !other.is_empty() && (self.is_empty() || !sep.is_empty())
            },
        };
        
        if will_change {
            match policy.string_merge() {
                crate::policy::StringMerge::Replace => {
                    self.clear();
                    self.push_str(other);
                },
                crate::policy::StringMerge::Keep => {}, // Won't reach here as will_change is false for Keep
                crate::policy::StringMerge::Concat => {
                    self.push_str(other);
                },
                crate::policy::StringMerge::ConcatWithSep(sep) => {
                    if !self.is_empty() && !other.is_empty() {
                        self.push_str(sep);
                    }
                    self.push_str(other);
                },
            }
            crate::policy::MergeOutcome::Changed
        } else {
            crate::policy::MergeOutcome::Unchanged
        }
    }
}


// Option implementation
impl<T: DeepMerge<P>, P: Policy> DeepMerge<P> for Option<T> {
    fn merge_with_policy(&mut self, other: Self, policy: &P) {
        // Try to check condition with equality if possible
        if !should_merge_option(self, &other, policy) {
            return;
        }
        
        // Apply merge
        match policy.option_merge() {
            OptionMerge::Take => {
                match (self, other) {
                    (Some(dst), Some(src)) => dst.merge_with_policy(src, policy),
                    (dst, Some(src)) => *dst = Some(src),
                    _ => {},
                }
            },
            OptionMerge::Preserve => {
                // Keep self as-is
            },
            OptionMerge::OrLeft => {
                if self.is_none() {
                    *self = other;
                }
            },
        }
    }
}

// Helper function to check if Option should be merged based on condition
#[allow(clippy::ref_option)]
fn should_merge_option<T, P: Policy>(_dst: &Option<T>, src: &Option<T>, policy: &P) -> bool {
    match policy.when_condition() {
        Condition::Some | Condition::NonEmpty | Condition::NonDefault => {
            // Only merge if source is Some; for Option, Some is non-empty and non-default
            src.is_some()
        },
        // Without PartialEq/key extraction, assume always true for these conditions
        Condition::Always | Condition::Changed | Condition::ChangedBy(_) => true,
    }
}

// Public helper functions for Option merging with change detection

/// Merges two Options only if they are different (requires `PartialEq`)
/// 
/// # Example
/// ```
/// use deepmerge::prelude::*;
/// use deepmerge::option_merge_if_changed;
/// 
/// let mut dst = Some(42);
/// let src = Some(42);
/// option_merge_if_changed(&mut dst, src, &DefaultPolicy);
/// assert_eq!(dst, Some(42)); // Unchanged because values are equal
/// 
/// let mut dst = Some(42);
/// let src = Some(100);
/// option_merge_if_changed(&mut dst, src, &DefaultPolicy);
/// assert_eq!(dst, Some(100)); // Changed because values differ
/// ```
pub fn option_merge_if_changed<T, P>(dst: &mut Option<T>, src: Option<T>, policy: &P)
where
    T: DeepMerge<P> + PartialEq,
    P: Policy,
{
    // Check if values are different
    if dst != &src {
        // Values differ, proceed with merge
        match policy.option_merge() {
            OptionMerge::Take => {
                match (dst, src) {
                    (Some(d), Some(s)) => d.merge_with_policy(s, policy),
                    (d, Some(s)) => *d = Some(s),
                    (d, None) => *d = None,  // Take None when src is None
                }
            },
            OptionMerge::Preserve => {
                // Keep dst as-is
            },
            OptionMerge::OrLeft => {
                if dst.is_none() {
                    *dst = src;
                }
            },
        }
    }
}

/// Merges two Options based on a key extractor function
/// Only merges if the extracted keys differ
/// 
/// # Example
/// ```
/// use deepmerge::prelude::*;
/// use deepmerge::option_merge_with_key;
/// 
/// #[derive(Clone, PartialEq, Debug)]
/// struct User {
///     id: u32,
///     name: String,
/// }
/// 
/// impl deepmerge::DeepMerge<DefaultPolicy> for User {
///     fn merge_with_policy(&mut self, other: Self, _policy: &DefaultPolicy) {
///         *self = other;
///     }
/// }
/// 
/// let mut dst = Some(User { id: 1, name: "Alice".to_string() });
/// let src = Some(User { id: 1, name: "Alice Updated".to_string() });
/// 
/// // Extract ID for comparison
/// fn get_id(user: &User) -> u32 { user.id }
/// 
/// option_merge_with_key(&mut dst, src.clone(), &DefaultPolicy, get_id);
/// assert_eq!(dst.as_ref().unwrap().name, "Alice"); // Unchanged, same ID
/// 
/// let src = Some(User { id: 2, name: "Bob".to_string() });
/// option_merge_with_key(&mut dst, src, &DefaultPolicy, get_id);
/// assert_eq!(dst.as_ref().unwrap().name, "Bob"); // Changed, different ID
/// ```
pub fn option_merge_with_key<T, P, K, F>(dst: &mut Option<T>, src: Option<T>, policy: &P, key_fn: F)
where
    T: DeepMerge<P>,
    P: Policy,
    K: PartialEq,
    F: for<'a> Fn(&'a T) -> K,
{
    // Check if keys differ
    let should_merge = match (dst.as_ref(), src.as_ref()) {
        (Some(d), Some(s)) => key_fn(d) != key_fn(s),
        (None, Some(_)) | (Some(_), None) => true,
        (None, None) => false,
    };
    
    if should_merge {
        match policy.option_merge() {
            OptionMerge::Take => {
                match (dst, src) {
                    (Some(d), Some(s)) => d.merge_with_policy(s, policy),
                    (d, Some(s)) => *d = Some(s),
                    (d, None) => *d = None,  // Take None when src is None
                }
            },
            OptionMerge::Preserve => {
                // Keep dst as-is
            },
            OptionMerge::OrLeft => {
                if dst.is_none() {
                    *dst = src;
                }
            },
        }
    }
}


// Vec implementation
#[cfg(feature = "alloc")]
impl<T, P: Policy> DeepMerge<P> for Vec<T> {
    fn merge_with_policy(&mut self, other: Self, policy: &P) {
        if !should_merge_vec(&other, policy) {
            return;
        }
        
        // Apply merge
        match policy.sequence_merge() {
            SequenceMerge::Append | SequenceMerge::Extend => {
                // No generic dedupe; use explicit helpers for Eq+Hash
                self.reserve(other.len());
                self.extend(other);
            },
            SequenceMerge::Prepend => {
                // No generic dedupe; use explicit helpers for Eq+Hash
                let mut result = other;
                result.reserve(self.len());
                result.extend(core::mem::take(self));
                *self = result;
            },
            // Without bounds, Union/Intersect fall back to append-like behavior
            SequenceMerge::Union | SequenceMerge::Intersect => {
                self.reserve(other.len());
                self.extend(other);
            },
        }
    }
}

// VecDeque implementation (mirrors Vec behavior)
#[cfg(feature = "alloc")]
impl<T, P: Policy> DeepMerge<P> for VecDeque<T> {
    fn merge_with_policy(&mut self, other: Self, policy: &P) {
        let proceed = match policy.when_condition() {
            Condition::NonEmpty | Condition::NonDefault => !other.is_empty(),
            Condition::Always | Condition::Some | Condition::Changed | Condition::ChangedBy(_) => true,
        };
        if !proceed { return; }
        match policy.sequence_merge() {
            SequenceMerge::Append | SequenceMerge::Extend | SequenceMerge::Union | SequenceMerge::Intersect => {
                let mut other = other;
                self.append(&mut other);
            },
            SequenceMerge::Prepend => {
                let mut result = other;
                result.append(self);
                *self = result;
            },
        }
    }
}

// LinkedList implementation (order-preserving; no capacity hints)
#[cfg(feature = "alloc")]
impl<T, P: Policy> DeepMerge<P> for LinkedList<T> {
    fn merge_with_policy(&mut self, mut other: Self, policy: &P) {
        let proceed = match policy.when_condition() {
            Condition::NonEmpty | Condition::NonDefault => !other.is_empty(),
            Condition::Always | Condition::Some | Condition::Changed | Condition::ChangedBy(_) => true,
        };
        if !proceed { return; }
        match policy.sequence_merge() {
            SequenceMerge::Append | SequenceMerge::Extend | SequenceMerge::Union | SequenceMerge::Intersect => {
                self.append(&mut other);
            },
            SequenceMerge::Prepend => {
                other.append(self);
                *self = other;
            },
        }
    }
}

// Helper functions for deduplication that are called based on sequence_dedupe policy

/// Performs an append operation with optional deduplication if type supports it
/// This is an internal function used by the Vec `DeepMerge` implementation
#[cfg(all(feature = "std", feature = "alloc"))]
pub fn vec_append_with_dedupe<T: Clone + Eq + Hash>(vec: &mut Vec<T>, other: Vec<T>) {
    use std::collections::HashSet;
    
    let mut seen: HashSet<T> = HashSet::with_capacity(vec.len() + other.len());
    let mut result = Vec::with_capacity(vec.len() + other.len());
    
    // First, dedupe existing elements in vec
    for item in core::mem::take(vec) {
        if seen.insert(item.clone()) {
            result.push(item);
        }
    }
    
    // Then add new items from other, skipping duplicates
    for item in other {
        if seen.insert(item.clone()) {
            result.push(item);
        }
    }
    
    *vec = result;
}

/// Performs a prepend operation with optional deduplication if type supports it
#[cfg(all(feature = "std", feature = "alloc"))]
pub fn vec_prepend_with_dedupe<T: Clone + Eq + Hash>(vec: &mut Vec<T>, other: Vec<T>) {
    use std::collections::HashSet;
    
    let mut seen: HashSet<T> = HashSet::with_capacity(vec.len() + other.len());
    let mut result = Vec::with_capacity(vec.len() + other.len());
    
    // First add items from other, deduping
    for item in other {
        if seen.insert(item.clone()) {
            result.push(item);
        }
    }
    
    // Then add items from self, skipping duplicates
    for item in core::mem::take(vec) {
        if seen.insert(item.clone()) {
            result.push(item);
        }
    }
    
    *vec = result;
}

// Note: Generic Vec<T> merging never deduplicates. Use the public helpers
// (e.g., vec_append_with_dedupe / vec_prepend_with_dedupe) which require
// T: Eq + Hash, or the Ord variants, to get real deduplication.

// Public helper functions for Vec operations that require additional bounds

/// Performs a union operation on a Vec, removing duplicates.
/// Preserves the order of elements from the first vec.
/// 
/// # Example
/// ```
/// use deepmerge::prelude::*;
/// use deepmerge::vec_union_dedup;
/// 
/// let mut vec1 = vec![1, 2, 3, 2];
/// let vec2 = vec![3, 4, 5];
/// vec_union_dedup(&mut vec1, vec2);
/// assert_eq!(vec1, vec![1, 2, 3, 4, 5]);
/// ```
#[cfg(all(feature = "std", feature = "alloc"))]
pub fn vec_union_dedup<T: Clone + Eq + Hash>(vec: &mut Vec<T>, other: Vec<T>) {
    use std::collections::HashSet;
    
    let mut seen: HashSet<T> = HashSet::with_capacity(vec.len() + other.len());
    let mut result = Vec::with_capacity(vec.len() + other.len());
    
    // Preserve order from vec first
    for item in core::mem::take(vec) {
        if seen.insert(item.clone()) {
            result.push(item);
        }
    }
    
    // Then add new items from other
    for item in other {
        if seen.insert(item.clone()) {
            result.push(item);
        }
    }
    
    *vec = result;
}

/// Performs an intersection operation on a Vec.
/// Keeps only elements that exist in both vecs and removes duplicates.
/// 
/// # Example
/// ```
/// use deepmerge::prelude::*;
/// use deepmerge::vec_intersect_dedup;
/// 
/// let mut vec1 = vec![1, 2, 3, 4, 2];
/// let vec2 = vec![2, 3, 5];
/// vec_intersect_dedup(&mut vec1, vec2);
/// assert_eq!(vec1, vec![2, 3]);
/// ```
#[cfg(all(feature = "std", feature = "alloc"))]
pub fn vec_intersect_dedup<T: Clone + Eq + Hash>(vec: &mut Vec<T>, other: Vec<T>) {
    use std::collections::HashSet;
    
    let other_set: HashSet<T> = other.into_iter().collect();
    let mut seen = HashSet::new();
    let mut result = Vec::new();
    
    // Keep only elements in both, deduplicating in the process
    for item in core::mem::take(vec) {
        if other_set.contains(&item) && seen.insert(item.clone()) {
            result.push(item);
        }
    }
    
    *vec = result;
}

/// Performs a union operation on a Vec using `BTreeSet` for deduplication.
/// Useful for types that implement Ord but not Hash.
/// 
/// # Example
/// ```
/// use deepmerge::prelude::*;
/// use deepmerge::vec_union_dedup_ord;
/// 
/// let mut vec1 = vec![1, 2, 3, 2];
/// let vec2 = vec![3, 4, 5];
/// vec_union_dedup_ord(&mut vec1, vec2);
/// assert_eq!(vec1, vec![1, 2, 3, 4, 5]);
/// ```
#[cfg(feature = "alloc")]
pub fn vec_union_dedup_ord<T: Clone + Ord>(vec: &mut Vec<T>, other: Vec<T>) {
    use alloc::collections::BTreeSet;
    
    let mut seen = BTreeSet::new();
    let mut result = Vec::with_capacity(vec.len() + other.len());
    
    // Preserve order from vec first
    for item in core::mem::take(vec) {
        if seen.insert(item.clone()) {
            result.push(item);
        }
    }
    
    // Then add new items from other
    for item in other {
        if seen.insert(item.clone()) {
            result.push(item);
        }
    }
    
    *vec = result;
}

/// Performs an intersection operation on a Vec using `BTreeSet`.
/// Useful for types that implement Ord but not Hash.
/// Removes duplicates in the process.
/// 
/// # Example
/// ```
/// use deepmerge::prelude::*;
/// use deepmerge::vec_intersect_dedup_ord;
/// 
/// let mut vec1 = vec![1, 2, 3, 4, 2];
/// let vec2 = vec![2, 3, 5];
/// vec_intersect_dedup_ord(&mut vec1, vec2);
/// assert_eq!(vec1, vec![2, 3]);
/// ```
#[cfg(feature = "alloc")]
pub fn vec_intersect_dedup_ord<T: Clone + Ord>(vec: &mut Vec<T>, other: Vec<T>) {
    use alloc::collections::BTreeSet;
    
    let other_set: BTreeSet<T> = other.into_iter().collect();
    let mut seen = BTreeSet::new();
    let mut result = Vec::new();
    
    // Keep only elements in both, deduplicating in the process
    for item in core::mem::take(vec) {
        if other_set.contains(&item) && seen.insert(item.clone()) {
            result.push(item);
        }
    }
    
    *vec = result;
}


// In-place deduplication helpers

/// Deduplicate a Vec in-place, preserving the first occurrence order. Requires T: Eq + Hash.
#[cfg(all(feature = "std", feature = "alloc"))]
pub fn vec_dedupe_in_place<T: Clone + Eq + Hash>(vec: &mut Vec<T>) {
    use std::collections::HashSet;
    let mut seen: HashSet<T> = HashSet::with_capacity(vec.len());
    let mut result = Vec::with_capacity(vec.len());
    for item in core::mem::take(vec) {
        if seen.insert(item.clone()) {
            result.push(item);
        }
    }
    *vec = result;
}

/// Deduplicate a Vec in-place by key, preserving the first occurrence order of each key.
#[cfg(all(feature = "std", feature = "alloc"))]
pub fn vec_dedupe_in_place_by_key<T: Clone, K: Eq + Hash, F>(vec: &mut Vec<T>, key_fn: F)
where
    F: for<'a> Fn(&'a T) -> K,
{
    use std::collections::HashSet;
    let mut seen: HashSet<K> = HashSet::with_capacity(vec.len());
    let mut result = Vec::with_capacity(vec.len());
    for item in core::mem::take(vec) {
        let key = key_fn(&item);
        if seen.insert(key) {
            result.push(item);
        }
    }
    *vec = result;
}

/// Append with by-key deduplication, keeping first occurrences from `vec`, then unique items from `other`.
#[cfg(all(feature = "std", feature = "alloc"))]
pub fn vec_append_dedup_by_key<T: Clone, K: Eq + Hash, F>(vec: &mut Vec<T>, other: Vec<T>, key_fn: F)
where
    F: for<'a> Fn(&'a T) -> K,
{
    use std::collections::HashSet;
    let mut seen: HashSet<K> = HashSet::with_capacity(vec.len() + other.len());
    let mut result = Vec::with_capacity(vec.len() + other.len());

    for item in core::mem::take(vec) {
        let key = key_fn(&item);
        if seen.insert(key) {
            result.push(item);
        }
    }
    for item in other {
        let key = key_fn(&item);
        if seen.insert(key) {
            result.push(item);
        }
    }
    *vec = result;
}

/// Prepend with by-key deduplication, keeping first occurrences from `other`, then unique items from original `vec`.
#[cfg(all(feature = "std", feature = "alloc"))]
pub fn vec_prepend_dedup_by_key<T: Clone, K: Eq + Hash, F>(vec: &mut Vec<T>, other: Vec<T>, key_fn: F)
where
    F: for<'a> Fn(&'a T) -> K,
{
    use std::collections::HashSet;
    let mut seen: HashSet<K> = HashSet::with_capacity(vec.len() + other.len());
    let mut result = Vec::with_capacity(vec.len() + other.len());

    for item in other {
        let key = key_fn(&item);
        if seen.insert(key) {
            result.push(item);
        }
    }
    for item in core::mem::take(vec) {
        let key = key_fn(&item);
        if seen.insert(key) {
            result.push(item);
        }
    }
    *vec = result;
}


// HashMap implementation
#[cfg(feature = "std")]
#[allow(clippy::implicit_hasher)]
impl<K: Eq + Hash, V: DeepMerge<P>, P: Policy> DeepMerge<P> for HashMap<K, V> {
    fn merge_with_policy(&mut self, other: Self, policy: &P) {
        use std::collections::hash_map::Entry;
        
        if !should_merge_map(&other, policy) {
            return;
        }
        
        // Apply merge
        match policy.map_merge() {
            MapMerge::Overlay => {
                for (k, v) in other {
                    match self.entry(k) {
                        Entry::Occupied(mut e) => {
                            e.get_mut().merge_with_policy(v, policy);
                        },
                        Entry::Vacant(e) => {
                            e.insert(v);
                        },
                    }
                }
            },
            MapMerge::Union => {
                self.extend(other);
            },
            MapMerge::Left => {
                // Keep self as-is
            },
            MapMerge::Right => {
                *self = other;
            },
        }
    }
}

// BTreeMap implementation
#[cfg(feature = "std")]
impl<K: Ord, V: DeepMerge<P>, P: Policy> DeepMerge<P> for BTreeMap<K, V> {
    fn merge_with_policy(&mut self, other: Self, policy: &P) {
        use std::collections::btree_map::Entry;
        
        if !should_merge_map(&other, policy) {
            return;
        }
        
        // Apply merge
        match policy.map_merge() {
            MapMerge::Overlay => {
                for (k, v) in other {
                    match self.entry(k) {
                        Entry::Occupied(mut e) => {
                            e.get_mut().merge_with_policy(v, policy);
                        },
                        Entry::Vacant(e) => {
                            e.insert(v);
                        },
                    }
                }
            },
            MapMerge::Union => {
                self.extend(other);
            },
            MapMerge::Left => {
                // Keep self as-is
            },
            MapMerge::Right => {
                *self = other;
            },
        }
    }
}

// HashSet implementation - no Clone required
#[cfg(feature = "std")]
#[allow(clippy::implicit_hasher)]
impl<T: Eq + Hash, P: Policy> DeepMerge<P> for HashSet<T> {
    fn merge_with_policy(&mut self, other: Self, policy: &P) {
        use core::mem;
        
        if !should_merge_set(&other, policy) {
            return;
        }
        
        // Apply merge - no Clone required
        match policy.sequence_merge() {
            SequenceMerge::Append | SequenceMerge::Extend | SequenceMerge::Union => {
                self.extend(other);
            },
            SequenceMerge::Prepend => {
                // For sets, prepend doesn't really make sense, but we can swap and extend
                let mut result = other;
                result.extend(mem::take(self));
                *self = result;
            },
            SequenceMerge::Intersect => {
                // Use retain to keep only elements in both sets
                let other_ref = &other;
                self.retain(|item| other_ref.contains(item));
            },
        }
    }
}

// BTreeSet implementation - no Clone required
#[cfg(feature = "std")]
impl<T: Ord, P: Policy> DeepMerge<P> for BTreeSet<T> {
    fn merge_with_policy(&mut self, other: Self, policy: &P) {
        use core::mem;
        
        if !should_merge_set(&other, policy) {
            return;
        }
        
        // Apply merge - no Clone required
        match policy.sequence_merge() {
            SequenceMerge::Append | SequenceMerge::Extend | SequenceMerge::Union => {
                self.extend(other);
            },
            SequenceMerge::Prepend => {
                // For sets, prepend doesn't really make sense, but we can swap and extend
                let mut result = other;
                result.extend(mem::take(self));
                *self = result;
            },
            SequenceMerge::Intersect => {
                // Use retain to keep only elements in both sets
                let other_ref = &other;
                self.retain(|item| other_ref.contains(item));
            },
        }
    }
}

// IndexMap implementation
#[cfg(feature = "indexmap")]
impl<K: Eq + Hash, V: DeepMerge<P>, P: Policy> DeepMerge<P> for IndexMap<K, V> {
    fn merge_with_policy(&mut self, other: Self, policy: &P) {
        use indexmap::map::Entry;
        
        if !should_merge_map(&other, policy) {
            return;
        }
        
        // Apply merge
        match policy.map_merge() {
            MapMerge::Overlay => {
                for (k, v) in other {
                    match self.entry(k) {
                        Entry::Occupied(mut e) => {
                            e.get_mut().merge_with_policy(v, policy);
                        },
                        Entry::Vacant(e) => {
                            e.insert(v);
                        },
                    }
                }
            },
            MapMerge::Union => {
                self.extend(other);
            },
            MapMerge::Left => {
                // Keep self as-is
            },
            MapMerge::Right => {
                *self = other;
            },
        }
    }
}

// IndexSet implementation - no Clone required
#[cfg(feature = "indexmap")]
impl<T: Eq + Hash, P: Policy> DeepMerge<P> for IndexSet<T> {
    fn merge_with_policy(&mut self, other: Self, policy: &P) {
        use core::mem;
        
        if !should_merge_set(&other, policy) {
            return;
        }
        
        // Apply merge - no Clone required
        match policy.sequence_merge() {
            SequenceMerge::Append | SequenceMerge::Extend | SequenceMerge::Union => {
                self.extend(other);
            },
            SequenceMerge::Prepend => {
                // For sets, prepend doesn't really make sense, but we can swap and extend
                let mut result = other;
                result.extend(mem::take(self));
                *self = result;
            },
            SequenceMerge::Intersect => {
                // Use retain to keep only elements in both sets
                let other_ref = &other;
                self.retain(|item| other_ref.contains(item));
            },
        }
    }
}