Skip to main content

polars_core/chunked_array/ops/
append.rs

1use polars_error::constants::LENGTH_LIMIT_MSG;
2
3use crate::chunked_array::flags::StatisticsFlags;
4use crate::prelude::*;
5use crate::series::IsSorted;
6
7pub(crate) fn new_chunks(chunks: &mut Vec<ArrayRef>, other: &[ArrayRef], len: usize) {
8    // Replace an empty array.
9    if chunks.len() == 1 && len == 0 {
10        other.clone_into(chunks);
11    } else {
12        for chunk in other {
13            if !chunk.is_empty() {
14                chunks.push(chunk.clone());
15            }
16        }
17    }
18}
19
20pub(crate) fn new_chunks_owned(chunks: &mut Vec<ArrayRef>, other: Vec<ArrayRef>, len: usize) {
21    // Replace an empty array.
22    if chunks.len() == 1 && len == 0 {
23        *chunks = other;
24    } else {
25        chunks.reserve(other.len());
26        chunks.extend(other.into_iter().filter(|c| !c.is_empty()));
27    }
28}
29
30/// Keeps the nesting flags of `ca` only if `other` has them too, as they must hold for every chunk.
31/// This applies to an empty `other` as well, whose chunks replace those of an empty `ca`.
32fn retain_nesting_flags<T: PolarsDataType>(ca: &mut ChunkedArray<T>, other: &ChunkedArray<T>) {
33    let nesting = StatisticsFlags::HAS_TRIMMED_LISTS_TO_NORMALIZED_OFFSETS
34        | StatisticsFlags::HAS_PROPAGATED_NULLS;
35    ca.set_flags(ca.get_flags() - (nesting - other.get_flags()));
36}
37
38/// Unit-length arrays are sorted but don't necessarily carry the flag.
39fn unit_or_sorted_flag<T: PolarsDataType>(ca: &ChunkedArray<T>) -> IsSorted {
40    if ca.len() == 1 {
41        IsSorted::Ascending
42    } else {
43        ca.is_sorted_flag()
44    }
45}
46
47pub(super) fn update_sorted_flag_before_append<T>(ca: &mut ChunkedArray<T>, other: &ChunkedArray<T>)
48where
49    T: PolarsDataType,
50    for<'a> T::Physical<'a>: TotalOrd,
51{
52    // Note: Do not call (first|last)_non_null on an array here before checking
53    // it is sorted, otherwise it will lead to quadratic behavior.
54    let sorted_flag = match (
55        ca.null_count() != ca.len(),
56        other.null_count() != other.len(),
57    ) {
58        (false, false) => IsSorted::Ascending,
59        (false, true) => {
60            if
61            // lhs is empty, just take sorted flag from rhs
62            ca.is_empty()
63                || (
64                    // lhs is non-empty and all-null, so rhs must have nulls ordered first
65                    unit_or_sorted_flag(other) != IsSorted::Not
66                        && 1 + other.last_non_null().unwrap() == other.len()
67                )
68            {
69                unit_or_sorted_flag(other)
70            } else {
71                IsSorted::Not
72            }
73        },
74        (true, false) => {
75            if
76            // rhs is empty, just take sorted flag from lhs
77            other.is_empty()
78                || (
79                    // rhs is non-empty and all-null, so lhs must have nulls ordered last
80                    unit_or_sorted_flag(ca) != IsSorted::Not && ca.first_non_null().unwrap() == 0
81                )
82            {
83                unit_or_sorted_flag(ca)
84            } else {
85                IsSorted::Not
86            }
87        },
88        (true, true) => {
89            // both arrays have non-null values.
90            // for arrays of unit length we can ignore the sorted flag, as it is
91            // not necessarily set.
92            let both_sorted = (ca.is_sorted_any() || ca.len() == 1)
93                && (other.is_sorted_any() || other.len() == 1);
94
95            // We will coerce for a single distinct value, which is sorted in both directions.
96            // Only compare values when the flags differ, as that is relatively expensive.
97            let flags_differ = ca.is_sorted_flag() != other.is_sorted_flag();
98            let is_single_value = |arr: &ChunkedArray<T>| {
99                arr.len() - arr.null_count() == 1
100                    || (both_sorted
101                        && flags_differ
102                        && unsafe {
103                            arr.value_unchecked(arr.first_non_null().unwrap())
104                                .tot_eq(&arr.value_unchecked(arr.last_non_null().unwrap()))
105                        })
106            };
107            let l_single = is_single_value(ca);
108            let r_single = is_single_value(other);
109
110            if !both_sorted || (flags_differ && !(l_single || r_single)) {
111                IsSorted::Not
112            } else {
113                let l_idx = ca.last_non_null().unwrap();
114                let r_idx = other.first_non_null().unwrap();
115
116                let null_pos_check =
117                    // check null positions
118                    // lhs does not end in nulls
119                    (1 + l_idx == ca.len())
120                    // rhs does not start with nulls
121                    && (r_idx == 0)
122                    // if there are nulls, they are all on one end
123                    && !(ca.first_non_null().unwrap() != 0 && 1 + other.last_non_null().unwrap() != other.len());
124
125                if !null_pos_check {
126                    IsSorted::Not
127                } else {
128                    #[allow(unused_assignments)]
129                    let mut out = IsSorted::Not;
130
131                    // This can be relatively expensive because of chunks, so delay as much as possible.
132                    let l_val = unsafe { ca.value_unchecked(l_idx) };
133                    let r_val = unsafe { other.value_unchecked(r_idx) };
134
135                    match (l_single, r_single) {
136                        (true, true) => {
137                            out = [IsSorted::Descending, IsSorted::Ascending]
138                                [l_val.tot_le(&r_val) as usize];
139                            drop(l_val);
140                            drop(r_val);
141                            ca.set_sorted_flag(out);
142                            return;
143                        },
144                        (true, false) => out = other.is_sorted_flag(),
145                        _ => out = ca.is_sorted_flag(),
146                    }
147
148                    debug_assert!(!matches!(out, IsSorted::Not));
149
150                    let check = if matches!(out, IsSorted::Ascending) {
151                        l_val.tot_le(&r_val)
152                    } else {
153                        l_val.tot_ge(&r_val)
154                    };
155
156                    if !check {
157                        out = IsSorted::Not
158                    }
159
160                    out
161                }
162            }
163        },
164    };
165
166    ca.set_sorted_flag(sorted_flag);
167}
168
169impl<T> ChunkedArray<T>
170where
171    T: PolarsDataType<IsNested = FalseT, IsObject = FalseT>,
172    for<'a> T::Physical<'a>: TotalOrd,
173{
174    /// Append in place. This is done by adding the chunks of `other` to this [`ChunkedArray`].
175    ///
176    /// See also [`extend`](Self::extend) for appends to the underlying memory
177    pub fn append(&mut self, other: &Self) -> PolarsResult<()> {
178        update_sorted_flag_before_append::<T>(self, other);
179        let len = self.len();
180        self.length = self
181            .length
182            .checked_add(other.length)
183            .ok_or_else(|| polars_err!(ComputeError: LENGTH_LIMIT_MSG))?;
184        self.null_count += other.null_count;
185        new_chunks(&mut self.chunks, &other.chunks, len);
186        Ok(())
187    }
188
189    /// Append in place. This is done by adding the chunks of `other` to this [`ChunkedArray`].
190    ///
191    /// See also [`extend`](Self::extend) for appends to the underlying memory
192    pub fn append_owned(&mut self, mut other: Self) -> PolarsResult<()> {
193        update_sorted_flag_before_append::<T>(self, &other);
194        let len = self.len();
195        self.length = self
196            .length
197            .checked_add(other.length)
198            .ok_or_else(|| polars_err!(ComputeError: LENGTH_LIMIT_MSG))?;
199        self.null_count += other.null_count;
200        new_chunks_owned(&mut self.chunks, std::mem::take(&mut other.chunks), len);
201        Ok(())
202    }
203}
204
205#[doc(hidden)]
206impl ListChunked {
207    pub fn append(&mut self, other: &Self) -> PolarsResult<()> {
208        self.append_owned(other.clone())
209    }
210
211    pub fn append_owned(&mut self, mut other: Self) -> PolarsResult<()> {
212        let dtype = merge_dtypes(self.dtype(), other.dtype())?;
213        self.field = Arc::new(Field::new(self.name().clone(), dtype));
214
215        let len = self.len();
216        self.length = self
217            .length
218            .checked_add(other.length)
219            .ok_or_else(|| polars_err!(ComputeError: LENGTH_LIMIT_MSG))?;
220        self.null_count += other.null_count;
221        self.set_sorted_flag(IsSorted::Not);
222        if !other.get_fast_explode_list() {
223            self.unset_fast_explode_list()
224        }
225        retain_nesting_flags(self, &other);
226
227        new_chunks_owned(&mut self.chunks, std::mem::take(&mut other.chunks), len);
228        Ok(())
229    }
230}
231
232#[cfg(feature = "dtype-array")]
233#[doc(hidden)]
234impl ArrayChunked {
235    pub fn append(&mut self, other: &Self) -> PolarsResult<()> {
236        self.append_owned(other.clone())
237    }
238
239    pub fn append_owned(&mut self, mut other: Self) -> PolarsResult<()> {
240        let dtype = merge_dtypes(self.dtype(), other.dtype())?;
241        self.field = Arc::new(Field::new(self.name().clone(), dtype));
242
243        let len = self.len();
244
245        self.length = self
246            .length
247            .checked_add(other.length)
248            .ok_or_else(|| polars_err!(ComputeError: LENGTH_LIMIT_MSG))?;
249        self.null_count += other.null_count;
250
251        self.set_sorted_flag(IsSorted::Not);
252        retain_nesting_flags(self, &other);
253
254        new_chunks_owned(&mut self.chunks, std::mem::take(&mut other.chunks), len);
255        Ok(())
256    }
257}
258
259#[cfg(feature = "dtype-struct")]
260#[doc(hidden)]
261impl StructChunked {
262    pub fn append(&mut self, other: &Self) -> PolarsResult<()> {
263        self.append_owned(other.clone())
264    }
265
266    pub fn append_owned(&mut self, mut other: Self) -> PolarsResult<()> {
267        let dtype = merge_dtypes(self.dtype(), other.dtype())?;
268        self.field = Arc::new(Field::new(self.name().clone(), dtype));
269
270        let len = self.len();
271
272        self.length = self
273            .length
274            .checked_add(other.length)
275            .ok_or_else(|| polars_err!(ComputeError: LENGTH_LIMIT_MSG))?;
276        self.null_count += other.null_count;
277
278        self.set_sorted_flag(IsSorted::Not);
279        retain_nesting_flags(self, &other);
280
281        new_chunks_owned(&mut self.chunks, std::mem::take(&mut other.chunks), len);
282        Ok(())
283    }
284}
285
286#[cfg(feature = "dtype-categorical")]
287#[doc(hidden)]
288impl<T: PolarsCategoricalType> CategoricalChunked<T> {
289    pub fn append(&mut self, other: &Self) -> PolarsResult<()> {
290        assert!(self.dtype() == other.dtype());
291        self.phys.append(&other.phys)
292    }
293
294    pub fn append_owned(&mut self, other: Self) -> PolarsResult<()> {
295        assert!(self.dtype() == other.dtype());
296        self.phys.append_owned(other.phys)
297    }
298}
299
300#[cfg(feature = "object")]
301#[doc(hidden)]
302impl<T: PolarsObject> ObjectChunked<T> {
303    pub fn append(&mut self, other: &Self) -> PolarsResult<()> {
304        self.append_owned(other.clone())
305    }
306
307    pub fn append_owned(&mut self, mut other: Self) -> PolarsResult<()> {
308        let len = self.len();
309        self.length = self
310            .length
311            .checked_add(other.length)
312            .ok_or_else(|| polars_err!(ComputeError: LENGTH_LIMIT_MSG))?;
313        self.null_count += other.null_count;
314        self.set_sorted_flag(IsSorted::Not);
315
316        new_chunks_owned(&mut self.chunks, std::mem::take(&mut other.chunks), len);
317        Ok(())
318    }
319}