polars_arrow/array/boolean/
mutable.rs

1use std::sync::Arc;
2
3use polars_error::{polars_bail, PolarsResult};
4
5use super::BooleanArray;
6use crate::array::physical_binary::extend_validity;
7use crate::array::{Array, MutableArray, TryExtend, TryExtendFromSelf, TryPush};
8use crate::bitmap::MutableBitmap;
9use crate::datatypes::{ArrowDataType, PhysicalType};
10use crate::trusted_len::TrustedLen;
11
12/// The Arrow's equivalent to `Vec<Option<bool>>`, but with `1/16` of its size.
13/// Converting a [`MutableBooleanArray`] into a [`BooleanArray`] is `O(1)`.
14/// # Implementation
15/// This struct does not allocate a validity until one is required (i.e. push a null to it).
16#[derive(Debug, Clone)]
17pub struct MutableBooleanArray {
18    dtype: ArrowDataType,
19    values: MutableBitmap,
20    validity: Option<MutableBitmap>,
21}
22
23impl From<MutableBooleanArray> for BooleanArray {
24    fn from(other: MutableBooleanArray) -> Self {
25        BooleanArray::new(
26            other.dtype,
27            other.values.into(),
28            other.validity.map(|x| x.into()),
29        )
30    }
31}
32
33impl<P: AsRef<[Option<bool>]>> From<P> for MutableBooleanArray {
34    /// Creates a new [`MutableBooleanArray`] out of a slice of Optional `bool`.
35    fn from(slice: P) -> Self {
36        Self::from_trusted_len_iter(slice.as_ref().iter().map(|x| x.as_ref()))
37    }
38}
39
40impl Default for MutableBooleanArray {
41    fn default() -> Self {
42        Self::new()
43    }
44}
45
46impl MutableBooleanArray {
47    /// Creates an new empty [`MutableBooleanArray`].
48    pub fn new() -> Self {
49        Self::with_capacity(0)
50    }
51
52    /// The canonical method to create a [`MutableBooleanArray`] out of low-end APIs.
53    /// # Errors
54    /// This function errors iff:
55    /// * The validity is not `None` and its length is different from `values`'s length
56    /// * The `dtype`'s [`PhysicalType`] is not equal to [`PhysicalType::Boolean`].
57    pub fn try_new(
58        dtype: ArrowDataType,
59        values: MutableBitmap,
60        validity: Option<MutableBitmap>,
61    ) -> PolarsResult<Self> {
62        if validity
63            .as_ref()
64            .is_some_and(|validity| validity.len() != values.len())
65        {
66            polars_bail!(ComputeError:
67                "validity mask length must match the number of values",
68            )
69        }
70
71        if dtype.to_physical_type() != PhysicalType::Boolean {
72            polars_bail!(oos =
73                "MutableBooleanArray can only be initialized with a DataType whose physical type is Boolean",
74            )
75        }
76
77        Ok(Self {
78            dtype,
79            values,
80            validity,
81        })
82    }
83
84    /// Creates an new [`MutableBooleanArray`] with a capacity of values.
85    pub fn with_capacity(capacity: usize) -> Self {
86        Self {
87            dtype: ArrowDataType::Boolean,
88            values: MutableBitmap::with_capacity(capacity),
89            validity: None,
90        }
91    }
92
93    /// Reserves `additional` slots.
94    pub fn reserve(&mut self, additional: usize) {
95        self.values.reserve(additional);
96        if let Some(x) = self.validity.as_mut() {
97            x.reserve(additional)
98        }
99    }
100
101    #[inline]
102    pub fn push_value(&mut self, value: bool) {
103        self.values.push(value);
104        if let Some(validity) = &mut self.validity {
105            validity.push(true)
106        }
107    }
108
109    #[inline]
110    pub fn push_null(&mut self) {
111        self.values.push(false);
112        match &mut self.validity {
113            Some(validity) => validity.push(false),
114            None => self.init_validity(),
115        }
116    }
117
118    /// Pushes a new entry to [`MutableBooleanArray`].
119    #[inline]
120    pub fn push(&mut self, value: Option<bool>) {
121        match value {
122            Some(value) => self.push_value(value),
123            None => self.push_null(),
124        }
125    }
126
127    /// Pop an entry from [`MutableBooleanArray`].
128    /// Note If the values is empty, this method will return None.
129    pub fn pop(&mut self) -> Option<bool> {
130        let value = self.values.pop()?;
131        self.validity
132            .as_mut()
133            .map(|x| x.pop()?.then(|| value))
134            .unwrap_or_else(|| Some(value))
135    }
136
137    /// Extends the [`MutableBooleanArray`] from an iterator of values of trusted len.
138    /// This differs from `extend_trusted_len` which accepts in iterator of optional values.
139    #[inline]
140    pub fn extend_trusted_len_values<I>(&mut self, iterator: I)
141    where
142        I: TrustedLen<Item = bool>,
143    {
144        // SAFETY: `I` is `TrustedLen`
145        unsafe { self.extend_trusted_len_values_unchecked(iterator) }
146    }
147
148    /// Extends the [`MutableBooleanArray`] from an iterator of values of trusted len.
149    /// This differs from `extend_trusted_len_unchecked`, which accepts in iterator of optional values.
150    ///
151    /// # Safety
152    /// The iterator must be trusted len.
153    #[inline]
154    pub unsafe fn extend_trusted_len_values_unchecked<I>(&mut self, iterator: I)
155    where
156        I: Iterator<Item = bool>,
157    {
158        let (_, upper) = iterator.size_hint();
159        let additional =
160            upper.expect("extend_trusted_len_values_unchecked requires an upper limit");
161
162        if let Some(validity) = self.validity.as_mut() {
163            validity.extend_constant(additional, true);
164        }
165
166        self.values.extend_from_trusted_len_iter_unchecked(iterator)
167    }
168
169    /// Extends the [`MutableBooleanArray`] from an iterator of trusted len.
170    #[inline]
171    pub fn extend_trusted_len<I, P>(&mut self, iterator: I)
172    where
173        P: std::borrow::Borrow<bool>,
174        I: TrustedLen<Item = Option<P>>,
175    {
176        // SAFETY: `I` is `TrustedLen`
177        unsafe { self.extend_trusted_len_unchecked(iterator) }
178    }
179
180    /// Extends the [`MutableBooleanArray`] from an iterator of trusted len.
181    ///
182    /// # Safety
183    /// The iterator must be trusted len.
184    #[inline]
185    pub unsafe fn extend_trusted_len_unchecked<I, P>(&mut self, iterator: I)
186    where
187        P: std::borrow::Borrow<bool>,
188        I: Iterator<Item = Option<P>>,
189    {
190        if let Some(validity) = self.validity.as_mut() {
191            extend_trusted_len_unzip(iterator, validity, &mut self.values);
192        } else {
193            let mut validity = MutableBitmap::new();
194            validity.extend_constant(self.len(), true);
195
196            extend_trusted_len_unzip(iterator, &mut validity, &mut self.values);
197
198            if validity.unset_bits() > 0 {
199                self.validity = Some(validity);
200            }
201        }
202    }
203
204    /// Extends `MutableBooleanArray` by additional values of constant value.
205    #[inline]
206    pub fn extend_constant(&mut self, additional: usize, value: Option<bool>) {
207        match value {
208            Some(value) => {
209                self.values.extend_constant(additional, value);
210                if let Some(validity) = self.validity.as_mut() {
211                    validity.extend_constant(additional, true);
212                }
213            },
214            None => {
215                self.values.extend_constant(additional, false);
216                if let Some(validity) = self.validity.as_mut() {
217                    validity.extend_constant(additional, false)
218                } else {
219                    self.init_validity();
220                    self.validity
221                        .as_mut()
222                        .unwrap()
223                        .extend_constant(additional, false)
224                };
225            },
226        };
227    }
228
229    fn init_validity(&mut self) {
230        let mut validity = MutableBitmap::with_capacity(self.values.capacity());
231        validity.extend_constant(self.len(), true);
232        validity.set(self.len() - 1, false);
233        self.validity = Some(validity)
234    }
235
236    /// Converts itself into an [`Array`].
237    pub fn into_arc(self) -> Arc<dyn Array> {
238        let a: BooleanArray = self.into();
239        Arc::new(a)
240    }
241
242    pub fn freeze(self) -> BooleanArray {
243        self.into()
244    }
245}
246
247/// Getters
248impl MutableBooleanArray {
249    /// Returns its values.
250    pub fn values(&self) -> &MutableBitmap {
251        &self.values
252    }
253}
254
255/// Setters
256impl MutableBooleanArray {
257    /// Sets position `index` to `value`.
258    /// Note that if it is the first time a null appears in this array,
259    /// this initializes the validity bitmap (`O(N)`).
260    /// # Panic
261    /// Panics iff index is larger than `self.len()`.
262    pub fn set(&mut self, index: usize, value: Option<bool>) {
263        self.values.set(index, value.unwrap_or_default());
264
265        if value.is_none() && self.validity.is_none() {
266            // When the validity is None, all elements so far are valid. When one of the elements is set of null,
267            // the validity must be initialized.
268            self.validity = Some(MutableBitmap::from_trusted_len_iter(
269                std::iter::repeat(true).take(self.len()),
270            ));
271        }
272        if let Some(x) = self.validity.as_mut() {
273            x.set(index, value.is_some())
274        }
275    }
276}
277
278/// From implementations
279impl MutableBooleanArray {
280    /// Creates a new [`MutableBooleanArray`] from an [`TrustedLen`] of `bool`.
281    #[inline]
282    pub fn from_trusted_len_values_iter<I: TrustedLen<Item = bool>>(iterator: I) -> Self {
283        Self::try_new(
284            ArrowDataType::Boolean,
285            MutableBitmap::from_trusted_len_iter(iterator),
286            None,
287        )
288        .unwrap()
289    }
290
291    /// Creates a new [`MutableBooleanArray`] from an [`TrustedLen`] of `bool`.
292    /// Use this over [`BooleanArray::from_trusted_len_iter`] when the iterator is trusted len
293    /// but this crate does not mark it as such.
294    ///
295    /// # Safety
296    /// The iterator must be [`TrustedLen`](https://doc.rust-lang.org/std/iter/trait.TrustedLen.html).
297    /// I.e. that `size_hint().1` correctly reports its length.
298    #[inline]
299    pub unsafe fn from_trusted_len_values_iter_unchecked<I: Iterator<Item = bool>>(
300        iterator: I,
301    ) -> Self {
302        let mut mutable = MutableBitmap::new();
303        mutable.extend_from_trusted_len_iter_unchecked(iterator);
304        MutableBooleanArray::try_new(ArrowDataType::Boolean, mutable, None).unwrap()
305    }
306
307    /// Creates a new [`MutableBooleanArray`] from a slice of `bool`.
308    #[inline]
309    pub fn from_slice<P: AsRef<[bool]>>(slice: P) -> Self {
310        Self::from_trusted_len_values_iter(slice.as_ref().iter().copied())
311    }
312
313    /// Creates a [`BooleanArray`] from an iterator of trusted length.
314    /// Use this over [`BooleanArray::from_trusted_len_iter`] when the iterator is trusted len
315    /// but this crate does not mark it as such.
316    ///
317    /// # Safety
318    /// The iterator must be [`TrustedLen`](https://doc.rust-lang.org/std/iter/trait.TrustedLen.html).
319    /// I.e. that `size_hint().1` correctly reports its length.
320    #[inline]
321    pub unsafe fn from_trusted_len_iter_unchecked<I, P>(iterator: I) -> Self
322    where
323        P: std::borrow::Borrow<bool>,
324        I: Iterator<Item = Option<P>>,
325    {
326        let (validity, values) = trusted_len_unzip(iterator);
327
328        Self::try_new(ArrowDataType::Boolean, values, validity).unwrap()
329    }
330
331    /// Creates a [`BooleanArray`] from a [`TrustedLen`].
332    #[inline]
333    pub fn from_trusted_len_iter<I, P>(iterator: I) -> Self
334    where
335        P: std::borrow::Borrow<bool>,
336        I: TrustedLen<Item = Option<P>>,
337    {
338        // SAFETY: `I` is `TrustedLen`
339        unsafe { Self::from_trusted_len_iter_unchecked(iterator) }
340    }
341
342    /// Creates a [`BooleanArray`] from an falible iterator of trusted length.
343    ///
344    /// # Safety
345    /// The iterator must be [`TrustedLen`](https://doc.rust-lang.org/std/iter/trait.TrustedLen.html).
346    /// I.e. that `size_hint().1` correctly reports its length.
347    #[inline]
348    pub unsafe fn try_from_trusted_len_iter_unchecked<E, I, P>(
349        iterator: I,
350    ) -> std::result::Result<Self, E>
351    where
352        P: std::borrow::Borrow<bool>,
353        I: Iterator<Item = std::result::Result<Option<P>, E>>,
354    {
355        let (validity, values) = try_trusted_len_unzip(iterator)?;
356
357        let validity = if validity.unset_bits() > 0 {
358            Some(validity)
359        } else {
360            None
361        };
362
363        Ok(Self::try_new(ArrowDataType::Boolean, values, validity).unwrap())
364    }
365
366    /// Creates a [`BooleanArray`] from a [`TrustedLen`].
367    #[inline]
368    pub fn try_from_trusted_len_iter<E, I, P>(iterator: I) -> std::result::Result<Self, E>
369    where
370        P: std::borrow::Borrow<bool>,
371        I: TrustedLen<Item = std::result::Result<Option<P>, E>>,
372    {
373        // SAFETY: `I` is `TrustedLen`
374        unsafe { Self::try_from_trusted_len_iter_unchecked(iterator) }
375    }
376
377    /// Shrinks the capacity of the [`MutableBooleanArray`] to fit its current length.
378    pub fn shrink_to_fit(&mut self) {
379        self.values.shrink_to_fit();
380        if let Some(validity) = &mut self.validity {
381            validity.shrink_to_fit()
382        }
383    }
384}
385
386/// Creates a Bitmap and an optional [`MutableBitmap`] from an iterator of `Option<bool>`.
387/// The first buffer corresponds to a bitmap buffer, the second one
388/// corresponds to a values buffer.
389/// # Safety
390/// The caller must ensure that `iterator` is `TrustedLen`.
391#[inline]
392pub(crate) unsafe fn trusted_len_unzip<I, P>(iterator: I) -> (Option<MutableBitmap>, MutableBitmap)
393where
394    P: std::borrow::Borrow<bool>,
395    I: Iterator<Item = Option<P>>,
396{
397    let mut validity = MutableBitmap::new();
398    let mut values = MutableBitmap::new();
399
400    extend_trusted_len_unzip(iterator, &mut validity, &mut values);
401
402    let validity = if validity.unset_bits() > 0 {
403        Some(validity)
404    } else {
405        None
406    };
407
408    (validity, values)
409}
410
411/// Extends validity [`MutableBitmap`] and values [`MutableBitmap`] from an iterator of `Option`.
412/// # Safety
413/// The caller must ensure that `iterator` is `TrustedLen`.
414#[inline]
415pub(crate) unsafe fn extend_trusted_len_unzip<I, P>(
416    iterator: I,
417    validity: &mut MutableBitmap,
418    values: &mut MutableBitmap,
419) where
420    P: std::borrow::Borrow<bool>,
421    I: Iterator<Item = Option<P>>,
422{
423    let (_, upper) = iterator.size_hint();
424    let additional = upper.expect("extend_trusted_len_unzip requires an upper limit");
425
426    // Length of the array before new values are pushed,
427    // variable created for assertion post operation
428    let pre_length = values.len();
429
430    validity.reserve(additional);
431    values.reserve(additional);
432
433    for item in iterator {
434        let item = if let Some(item) = item {
435            validity.push_unchecked(true);
436            *item.borrow()
437        } else {
438            validity.push_unchecked(false);
439            bool::default()
440        };
441        values.push_unchecked(item);
442    }
443
444    debug_assert_eq!(
445        values.len(),
446        pre_length + additional,
447        "Trusted iterator length was not accurately reported"
448    );
449}
450
451/// # Safety
452/// The caller must ensure that `iterator` is `TrustedLen`.
453#[inline]
454pub(crate) unsafe fn try_trusted_len_unzip<E, I, P>(
455    iterator: I,
456) -> std::result::Result<(MutableBitmap, MutableBitmap), E>
457where
458    P: std::borrow::Borrow<bool>,
459    I: Iterator<Item = std::result::Result<Option<P>, E>>,
460{
461    let (_, upper) = iterator.size_hint();
462    let len = upper.expect("trusted_len_unzip requires an upper limit");
463
464    let mut null = MutableBitmap::with_capacity(len);
465    let mut values = MutableBitmap::with_capacity(len);
466
467    for item in iterator {
468        let item = if let Some(item) = item? {
469            null.push(true);
470            *item.borrow()
471        } else {
472            null.push(false);
473            false
474        };
475        values.push(item);
476    }
477    assert_eq!(
478        values.len(),
479        len,
480        "Trusted iterator length was not accurately reported"
481    );
482    values.set_len(len);
483    null.set_len(len);
484
485    Ok((null, values))
486}
487
488impl<Ptr: std::borrow::Borrow<Option<bool>>> FromIterator<Ptr> for MutableBooleanArray {
489    fn from_iter<I: IntoIterator<Item = Ptr>>(iter: I) -> Self {
490        let iter = iter.into_iter();
491        let (lower, _) = iter.size_hint();
492
493        let mut validity = MutableBitmap::with_capacity(lower);
494
495        let values: MutableBitmap = iter
496            .map(|item| {
497                if let Some(a) = item.borrow() {
498                    validity.push(true);
499                    *a
500                } else {
501                    validity.push(false);
502                    false
503                }
504            })
505            .collect();
506
507        let validity = if validity.unset_bits() > 0 {
508            Some(validity)
509        } else {
510            None
511        };
512
513        MutableBooleanArray::try_new(ArrowDataType::Boolean, values, validity).unwrap()
514    }
515}
516
517impl MutableArray for MutableBooleanArray {
518    fn len(&self) -> usize {
519        self.values.len()
520    }
521
522    fn validity(&self) -> Option<&MutableBitmap> {
523        self.validity.as_ref()
524    }
525
526    fn as_box(&mut self) -> Box<dyn Array> {
527        let array: BooleanArray = std::mem::take(self).into();
528        array.boxed()
529    }
530
531    fn as_arc(&mut self) -> Arc<dyn Array> {
532        let array: BooleanArray = std::mem::take(self).into();
533        array.arced()
534    }
535
536    fn dtype(&self) -> &ArrowDataType {
537        &self.dtype
538    }
539
540    fn as_any(&self) -> &dyn std::any::Any {
541        self
542    }
543
544    fn as_mut_any(&mut self) -> &mut dyn std::any::Any {
545        self
546    }
547
548    #[inline]
549    fn push_null(&mut self) {
550        self.push(None)
551    }
552
553    fn reserve(&mut self, additional: usize) {
554        self.reserve(additional)
555    }
556
557    fn shrink_to_fit(&mut self) {
558        self.shrink_to_fit()
559    }
560}
561
562impl Extend<Option<bool>> for MutableBooleanArray {
563    fn extend<I: IntoIterator<Item = Option<bool>>>(&mut self, iter: I) {
564        let iter = iter.into_iter();
565        self.reserve(iter.size_hint().0);
566        iter.for_each(|x| self.push(x))
567    }
568}
569
570impl TryExtend<Option<bool>> for MutableBooleanArray {
571    /// This is infalible and is implemented for consistency with all other types
572    fn try_extend<I: IntoIterator<Item = Option<bool>>>(&mut self, iter: I) -> PolarsResult<()> {
573        self.extend(iter);
574        Ok(())
575    }
576}
577
578impl TryPush<Option<bool>> for MutableBooleanArray {
579    /// This is infalible and is implemented for consistency with all other types
580    fn try_push(&mut self, item: Option<bool>) -> PolarsResult<()> {
581        self.push(item);
582        Ok(())
583    }
584}
585
586impl PartialEq for MutableBooleanArray {
587    fn eq(&self, other: &Self) -> bool {
588        self.iter().eq(other.iter())
589    }
590}
591
592impl TryExtendFromSelf for MutableBooleanArray {
593    fn try_extend_from_self(&mut self, other: &Self) -> PolarsResult<()> {
594        extend_validity(self.len(), &mut self.validity, &other.validity);
595
596        let slice = other.values.as_slice();
597        // SAFETY: invariant offset + length <= slice.len()
598        unsafe {
599            self.values
600                .extend_from_slice_unchecked(slice, 0, other.values.len());
601        }
602        Ok(())
603    }
604}
polars_arrow/array/boolean/mutable.rs

polars_arrow/array/boolean/
mutable.rs
