uniform_nested_coords_plotters/

lib.rs

#![doc = include_str!("../README.md")]

use core::iter;

use plotters::coord::{
    combinators::NestedValue,
    ranged1d::{AsRangedCoord, DiscreteRanged, NoDefaultFormatting, Ranged, ValueFormatter},
};

/// Like [`plotters::coord::combinators::NestedValue`], but for
#[derive(Debug, PartialEq, Eq, Clone)]
pub enum UniformNestedValue<C, V> {
    /// Caregory value - outer coordinate system only!
    ///
    /// Primarily used for rendering key points, and avoids issues when the inner coordinate system
    /// might not produce key points in the correct location.
    Category(C),
    /// Exact value - typically, this is what you'd actually use when providing values.
    Value(C, V),
}

impl<C, V> UniformNestedValue<C, V> {
    /// Obtain the category of this uniform nested value.
    ///
    /// Analogous to [`plotters::coord::combinators::NestedValue::category`]
    pub fn category(&self) -> &C {
        match self {
            UniformNestedValue::Category(c) => c,
            UniformNestedValue::Value(c, _) => c,
        }
    }

    /// Obtain the nested value of this, if it is a value that actually refers to a single,
    /// concrete nested value.
    ///
    /// Analogous to [`plotters::coord::combinators::NestedValue::nested_value`]
    pub fn nested_value(&self) -> Option<&V> {
        match self {
            UniformNestedValue::Category(_) => None,
            UniformNestedValue::Value(_, v) => Some(v),
        }
    }

    /// Turn this into a tuple, if it is [`UniformNestedValue::Value`]
    pub fn maybe_into_tuple(self) -> Option<(C, V)> {
        match self {
            UniformNestedValue::Category(_) => None,
            UniformNestedValue::Value(c, v) => Some((c, v)),
        }
    }
}

impl<C, V> From<(C, V)> for UniformNestedValue<C, V> {
    #[inline]
    fn from((c, v): (C, V)) -> Self {
        Self::Value(c, v)
    }
}

// A significant amount of code is taken from [`plotters::coord::combinators::NestedRange`]
//
// They are essentially the same concept after all, just one of them does not have individual
// systems for each outer coordinate.
/// Like [`plotters::coord::combinators::NestedRange`], except the nested coordinate system is the
/// same for every item in the outer coordinate system.
///
/// That is, each value in the discrete ranged coordinate system has an associated secondary
/// coordinate system. The value type is [`UniformNestedValue`] - most of the time, you just want
/// [`UniformNestedValue::Value`] - and a [`From`] implementation for tuples is provided as such.
///
/// Because of this uniformity, this can be used very efficiently, even recursively, and even with
/// large `Primary` coordinate systems - including both as a primary coordinate system itself, or
/// as a secondary coordinate system. This is because it lacks the need to scan all the
/// potentially-variadic coordinate systems when doing discrete value indexing.
///
/// Important to note here - The coordinate ranges produced by coordinate systems are typically
/// [inclusive, exclusive) style - they include the lower value and exclude the upper value. This
/// remains true for this coordinate system. However, when working with both [`UniformNestedRange`]
/// and [`plotters::coord::combinators::NestedRange`], typically the final value of the *primary*
/// coordinate system is actually included, and it's only the last value of the secondary
/// coordinate systems that is excluded. This means that it may extend one-further within the
/// primary coordinate system than is expected.
pub struct UniformNestedRange<Primary: DiscreteRanged, Secondary: Ranged> {
    primary_coordinate_system: Primary,
    secondary_coordinate_system: Secondary,
}

// Basically taken directly from the normal implementation.
impl<PCoordType, SCoordType, P, S> ValueFormatter<NestedValue<PCoordType, SCoordType>>
    for UniformNestedRange<P, S>
where
    P: Ranged<ValueType = PCoordType> + DiscreteRanged,
    S: Ranged<ValueType = SCoordType>,
    P: ValueFormatter<PCoordType>,
    S: ValueFormatter<SCoordType>,
{
    fn format(value: &NestedValue<PCoordType, SCoordType>) -> String {
        match value {
            NestedValue::Category(c) => P::format(c),
            NestedValue::Value(_, v) => S::format(v),
        }
    }
}

impl<P: DiscreteRanged, S: Ranged> Ranged for UniformNestedRange<P, S> {
    type FormatOption = NoDefaultFormatting;

    type ValueType = UniformNestedValue<P::ValueType, S::ValueType>;

    fn map(&self, value: &Self::ValueType, limit: (i32, i32)) -> i32 {
        // This uses the same behaviour as the NestedRange in case the outer coordinate system is
        // not compatible.
        let index_in_primary = self
            .primary_coordinate_system
            .index_of(value.category())
            .unwrap_or(0);
        // This is # of values in the primary discrete coordinate system.
        let total_primary_buckets = self.primary_coordinate_system.size();

        // Each bucket is allocated to [secondary start, secondary end), from the [primary value,
        // primary_value.next) region of the resulting i32 coordinate system.
        //
        // This is rounded down, and is also signed.
        let uniform_real_coordinates_buckets_delta =
            (limit.1 - limit.0) / total_primary_buckets as i32;
        let mut residual_extra_buckets_delta = (limit.1 - limit.0) % total_primary_buckets as i32;

        // The output coordinate system delta was negative in this case, so the modulo will be too.
        // Move it up one full modulo chunk
        if residual_extra_buckets_delta < 0 {
            residual_extra_buckets_delta += uniform_real_coordinates_buckets_delta;
        }

        // Left part of the bucket to construct the final output in.
        //
        // The `residual stuff . min` part allocates the non-exactly-divided chunks spread across
        // the output buckets - adding "one-extra" until the residual indivisible bucket delta is
        // fully distributed.
        let secondary_bucket_left = limit.0
            + uniform_real_coordinates_buckets_delta * index_in_primary as i32
            + residual_extra_buckets_delta.min(index_in_primary as i32);

        // Right part of the bucket.
        //
        // The residual stuff again accounts for the allocation of extra space. This is taken from
        // the NestedRange implementation as this kind of thing gives me a headache lol, but it
        // seems to be doing the same thing of allocating exactly enough total extra to fill up the
        // remaining non-exactly-divisible bucket space evenly across the output coordinate space.
        let secondary_bucket_right = secondary_bucket_left
            + uniform_real_coordinates_buckets_delta
            + if (residual_extra_buckets_delta as usize) < index_in_primary {
                1
            } else {
                0
            };

        // Perform the mapping of the inner secondary coordinate system. Unlike the original
        // implementation we don't need to perform any indexing due to uniformity of secondary
        // coordinate system.
        match value.nested_value() {
            Some(v) => self
                .secondary_coordinate_system
                .map(v, (secondary_bucket_left, secondary_bucket_right)),
            // In this case - category only -  map to the midpoint
            None => (secondary_bucket_left + secondary_bucket_right) / 2,
        }
    }

    fn key_points<Hint: plotters::coord::ranged1d::KeyPointHint>(
        &self,
        hint: Hint,
    ) -> Vec<Self::ValueType> {
        // This is taken mostly directly from the default implementation.

        // Either there are no light points, or we have insufficient points allowed to do anything
        // with secondary coordinate systems inside the buckets (i.e. not enough to put at least
        // one non-primary key point there, which requires at least one extra available key point
        // for every primary axis point).
        if !hint.weight().allow_light_points()
            || hint.max_num_points() < self.primary_coordinate_system.size() * 2
        {
            self.primary_coordinate_system
                .key_points(hint)
                .into_iter()
                .map(UniformNestedValue::Category)
                .collect()
        } else {
            // extra points we have available for each secondary bucket after allocating them to
            // the primary category values.
            //
            // This automatically discards any "extra" indivisible key points.
            let per_secondary_size = (hint.max_num_points()
                - self.primary_coordinate_system.size())
                / self.primary_coordinate_system.size();
            self.primary_coordinate_system
                .values()
                .enumerate()
                .flat_map(|(category_idx, value)| {
                    // The key point at the category value
                    iter::once(UniformNestedValue::Category(value)).chain(
                        self.secondary_coordinate_system
                            .key_points(per_secondary_size)
                            .into_iter()
                            .map(move |secondary_value| {
                                (
                                    self.primary_coordinate_system
                                        .from_index(category_idx)
                                        .expect(
                                        "Invalid index even though we iterated over allowed values",
                                    ),
                                    secondary_value,
                                )
                                    .into()
                            }),
                    )
                })
                .collect()
        }
    }

    fn range(&self) -> core::ops::Range<Self::ValueType> {
        // We have a uniform pair of ranges here.
        let primary_range = self.primary_coordinate_system.range();
        let secondary_range = self.secondary_coordinate_system.range();

        (primary_range.start, secondary_range.start).into()
            ..(primary_range.end, secondary_range.end).into()
    }
}

/// Efficient implementation of uniformly-nested [`DiscreteRanged`]. Even in uses which require
/// very large amounts of indexing operations, this should be significantly more efficient than
/// [`plotters::coord::combinators::NestedRange`], because of the lack of a need to traverse
/// linearly through dynamic secondary coordinate systems.
impl<Primary: DiscreteRanged, Secondary: DiscreteRanged> DiscreteRanged
    for UniformNestedRange<Primary, Secondary>
{
    #[inline]
    fn size(&self) -> usize {
        // This coordinate system has the slightly surprising behaviour of including values from
        // the "end part" of the primary coordinate system. However, this is accounted for just
        // fine by .size().
        self.primary_coordinate_system.size() * self.secondary_coordinate_system.size()
    }

    // We - like the normal implementation - do not allow getting the index of pure-category
    // [`UniformNestedValue`]
    fn index_of(&self, value: &Self::ValueType) -> Option<usize> {
        let primary_index = self.primary_coordinate_system.index_of(value.category())?;
        let secondary_size = self.secondary_coordinate_system.size();
        let secondary_index = self
            .secondary_coordinate_system
            .index_of(value.nested_value()?)?;
        Some(secondary_size * primary_index + secondary_index)
    }

    fn from_index(&self, index: usize) -> Option<Self::ValueType> {
        let secondary_size = self.secondary_coordinate_system.size();
        let primary_index = index / secondary_size;
        let secondary_index = index % secondary_size;
        let category = self.primary_coordinate_system.from_index(primary_index)?;
        let value = self
            .secondary_coordinate_system
            .from_index(secondary_index)?;
        Some((category, value).into())
    }
}

/// Used to build a uniform-nested coordinate system ([`UniformNestedRange`])
pub trait BuildUniformNestedCoord: AsRangedCoord
where
    Self::CoordDescType: DiscreteRanged,
{
    /// Builds a uniform nested coordinate system.
    ///
    /// Provide a function to generate the single coordinate system you want to nest uniformly
    /// inside this outer coordinate system.
    ///
    /// Will panic if this coordinate system has a [`DiscreteRanged::size`] of zero.
    fn uniform_nested_coord_with<Secondary: AsRangedCoord>(
        self,
        make_secondary: impl FnOnce() -> Secondary,
    ) -> UniformNestedRange<Self::CoordDescType, Secondary::CoordDescType> {
        let primary: Self::CoordDescType = self.into();
        assert!(primary.size() > 0);

        let secondary: Secondary::CoordDescType = make_secondary().into();

        UniformNestedRange {
            primary_coordinate_system: primary,
            secondary_coordinate_system: secondary,
        }
    }

    /// Builds a uniform nested coordinate system that has been directly provided without an
    /// intermediary function call.
    ///
    /// Will panic if this coordinate system has a [`DiscreteRanged::size`] of zero
    fn uniform_nested_coord<Secondary: AsRangedCoord>(
        self,
        secondary: Secondary,
    ) -> UniformNestedRange<Self::CoordDescType, Secondary::CoordDescType> {
        let primary: Self::CoordDescType = self.into();
        assert!(primary.size() > 0);

        let secondary: Secondary::CoordDescType = secondary.into();
        UniformNestedRange {
            primary_coordinate_system: primary,
            secondary_coordinate_system: secondary,
        }
    }
}

impl<T: AsRangedCoord> BuildUniformNestedCoord for T where T::CoordDescType: DiscreteRanged {}

/// Some basic tests taken approximately from the same module in
/// [`plotters::coord::combinators::NestedRange`]
#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_uniform_nested_coord() {
        let coord = (0..10).uniform_nested_coord(0..39);
        let range = coord.range();
        assert_eq!((0, 0).into()..(10, 39).into(), range);
        assert_eq!(coord.size(), 11 * 40);
        // 0th category spans [0 -> 100), as the size of the start range is 11
        // Midpoint should be 50
        assert_eq!(coord.map(&UniformNestedValue::Category(0), (0, 1100)), 50);
        assert_eq!(coord.map(&(0, 0).into(), (0, 1100)), 0);
        // zero-based:
        // 2/40 => 2/40 => 1/20
        // 0 + 1/20 * (1100/11) => 5
        assert_eq!(coord.map(&(0, 2).into(), (0, 1100)), 5);
        // (19 + 1)/40 = 0.5
        // 0.5 * (1100/11) + 5 *(1100/11) => 50 + 500 => 550 -> -1 for 0-based
        assert_eq!(coord.map(&(5, 19).into(), (0, 1100)), 549);

        // '0'th value is zero, '1'st value is 1, ..., '8'th value is 8
        assert_eq!(coord.from_index(40 * 3 + 8).unwrap(), (3, 8).into());
        // 10 * 40 = 400, 39 is 0-based->39th value, => 439
        assert_eq!(coord.index_of(&(10, 39).into()).unwrap(), 439);
    }
}

/// Useful includes suitable for performing `uniform_nested_coords_plotters::prelude::*`
pub mod prelude {
    pub use super::{BuildUniformNestedCoord, UniformNestedRange, UniformNestedValue};
}

// uniform-nested-coords-plotters - NestedRange but uniform
// Copyright (C) 2024  Matti <mattibryce at protonmail dot com>
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.