forsyth 1.0.1

#![deny(clippy::all)]
#![forbid(unsafe_code)]

//! This is a clean-room implementation of Tom Forsyth's
//! [`Linear-speed Vertex Cache Optimisation`] in Rust.
//!
//! Two algorithms are provided in this crate.
//! - [`order_triangles_inplace`] and [`order_triangles`] to order triangle indices to maximize data locality.
//! - [`order_vertices`] to order vertex data in such an way, that vertex data locality is maximized when iterating sequentially through index data.
//!
//! Both algorithms can be run independently, but ordering indices first and then ordering vertices provides most benefits.
//!
//! Note that [`Kerbel et al. 2018`] argued that [`GPU caching may not benefit from such ordering`].
//! However, there may be use cases that benefit from improved data locality when sequentially processing index and vertex data,
//! such as when streaming data from persistent storage or when processing geometry with CPUs.
//!
//! Despite the original paper's title, the algorithm is [`not guaranteed to be exactly linear`].
//! There are pathological cases where runtime can be worse, especially when  there are many vertices with many connected edges (ie. high valence).
//! Meshes mostly containing very fine-grained triangle fans are an example. However, one can still expect a throughput of hundreds of thousand indices per second on contemporary CPUs even for these cases.
//!
//! In practice, both algorithms are fast enough to opportunistically apply them to geometry to be processed or read multiple times.
//! Apart from data locality, both algorithms may be useful to improve subsequent compression by producing more contiguous data useful for delta compression and other algorithms.
//!
//! ```rust
//! use forsyth::{order_vertices,order_triangles};
//!
//! let input_vertices = &['a', 'b', 'c', 'd', 'e'];
//! let input_indices = &[0_u32, 1, 2, 0, 1, 3, 0, 3, 4, 2, 1, 4];
//!
//! // order indices first
//! let ordered_indices =
//!     order_triangles(input_indices).unwrap_or_else(|_| input_indices.to_vec());
//!
//! assert_eq!(&ordered_indices, &[0, 3, 4, 0, 1, 3, 2, 1, 4, 0, 1, 2]);
//!
//! // then order vertices and remap indices accordingly
//! let (ordered_vertices, ordered_indices) =
//!     order_vertices(input_vertices, ordered_indices.as_slice())
//!         .unwrap_or_else(|_| (input_vertices.to_vec(), ordered_indices));
//!
//! assert_eq!(&ordered_vertices, &['a', 'd', 'e', 'b', 'c']);
//! assert_eq!(&ordered_indices, &[0, 1, 2, 0, 3, 1, 4, 3, 2, 0, 3, 4]);
//! ```
//!
//! [`Linear-speed Vertex Cache Optimisation`]: https://tomforsyth1000.github.io/papers/fast_vert_cache_opt.html
//! [`Kerbel et al. 2018`]: https://arbook.icg.tugraz.at/schmalstieg/Schmalstieg_351.pdf
//! [`GPU caching may not benefit from such ordering`]: https://www.highperformancegraphics.org/wp-content/uploads/2018/Papers-Session2/HPG2018_RevisitingVertexCache.pdf
//! [`order_triangles_inplace`]: ./fn.order_triangles_inplace.html
//! [`order_triangles`]: ./fn.order_triangles.html
//! [`order_vertices`]: ./fn.order_vertices.html
//! [`not guaranteed to be exactly linear`]: https://kento_asashima.gitlab.io/-/forsyth/-/jobs/1192073834/artifacts/target/criterion/order_triangles/report/index.html

/*
This is a clean-room implementation of Tom Forsyth's
"Linear-speed Vertex Cache Optimisation" into Rust.

Comments and comment blocks starting with "TF:" are
excerpts of the original paper as retrieved from
https://tomforsyth1000.github.io/papers/fast_vert_cache_opt.html
on 5 January 2021.
*/

use std::{
    collections::{HashMap, VecDeque},
    convert::{TryFrom, TryInto},
    fmt::Display,
    u32,
};

const MAX_VERTEX_CACHE_SIZE: u16 = std::u16::MAX - 1;
const NOT_IN_CACHE: u16 = std::u16::MAX;
const NULL_TRI: u32 = std::u32::MAX;

/// The default vertex cache size as suggested by the original paper
pub const DEFAULT_VERTEX_CACHE_SIZE: u16 = 32;

/// An error or invariant violation during an ordering operation
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum Error {
    /// Provided slice of Index cannot represent one or more index triples.
    IndicesNotTriples,
    /// An Index failed to convert to usize.
    IndexToUsizeConversion,
    /// There are more than `limit` triangles involved.
    TooManyTrianglesInTotal { limit: usize },
    /// More than `limit` triangles connect to vertex `vertex_idx`.
    TooManyTrianglesAtVertex { vertex_idx: usize, limit: usize },
    /// The resulting ordered Index draw list was malformed.
    MalformedDrawList,
    /// There was an attempt to refer to an invalid vertex index
    VertexOutOfBounds,
}

impl Display for Error {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Error::IndicesNotTriples => f.write_str("elements are not all triples"),
            Error::IndexToUsizeConversion => f.write_str("cannot convert Index to usize"),
            Error::TooManyTrianglesInTotal { limit } => f.write_fmt(format_args!(
                "too many triangles in total. {} triangles are supported",
                limit,
            )),
            Error::TooManyTrianglesAtVertex { vertex_idx, limit } => f.write_fmt(format_args!(
                "too many triangles connected to vertex {}. {} triangles are supported",
                vertex_idx, limit,
            )),
            Error::MalformedDrawList => {
                f.write_str("the generated ordered Index draw list is malformed")
            }
            Error::VertexOutOfBounds => f.write_str("the vertex index is out of bounds"),
        }
    }
}

/// A struct holding the parameters controlling the algorithm
///
/// Using Config::default() results in a configuration with
/// the parameters set as suggested by the original paper.
///
/// See the paper for further information.

#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Config {
    pub cache_decay_power: f32,
    pub last_tri_score: f32,
    pub valence_boost_scale: f32,
    pub valence_boost_power: f32,
}

impl Default for Config {
    fn default() -> Self {
        Self {
            cache_decay_power: 1.5,
            last_tri_score: 0.75,
            valence_boost_scale: 2.0,
            valence_boost_power: 0.5,
        }
    }
}

/*
TF: Instead, each vertex holds the following data:

Its position in the modelled cache (-1 if it is not in the cache)
Its current score
The total number of triangles that use it
The number of triangles not yet added that use it
The list of triangle indices that use it
*/
#[derive(Clone, Debug)]
struct VertexInfo {
    score: f32,
    tri_list_ofs: u32,
    cache_pos: u16,
    num_tris_active: u16,
}

impl Default for VertexInfo {
    fn default() -> Self {
        Self {
            cache_pos: NOT_IN_CACHE,
            score: 0.0,
            num_tris_active: 0,
            tri_list_ofs: 0,
        }
    }
}

/*
TF: Each triangle in the mesh also stores the following data:

Whether it has been added to the draw list or not
The triangle’s score (the sum of the scores of its vertices)
The indices to the three vertices
*/
#[derive(Debug)]
struct TriangleInfo<Index> {
    verts: [Index; 3],
    score: f32,
    added_to_draw_list: bool,
}

fn calculate_vertex_score(
    config: &Config,
    num_active_tris: u32,
    cache_pos: u16,
    vertex_cache_size: u16,
) -> f32 {
    if num_active_tris == 0 {
        -1.0f32
    } else {
        // TF: Bonus points for having a low number of tris still to
        // use the vert, so we get rid of lone verts quickly.
        let valence_boost = (num_active_tris as f32).powf(-config.valence_boost_power);

        let pos_score = if cache_pos < 3 {
            // TF: This vertex was used in the last triangle,
            // so it has a fixed score, whichever of the three
            // it's in. Otherwise, you can get very different
            // answers depending on whether you add
            // the triangle 1,2,3 or 3,1,2 - which is silly.
            config.last_tri_score
        } else if cache_pos < vertex_cache_size {
            // TF: Points for being high in the cache.
            let scaler = 1.0 / ((vertex_cache_size - 3) as f32);
            (1.0 - ((cache_pos - 3) as f32) * scaler).powf(config.cache_decay_power)
        } else {
            0.0f32
        };

        pos_score + (config.valence_boost_scale * valence_boost)
    }
}

/// Orders a slice of triangle indices in place.
///
/// The configuration in `config` can be used to tweak the algorithm's parameters.
/// No checks for sanity and/or validity of the provided values is done.
///
/// The slice `indices` is assumed to contain the index triples making
/// up the triangles to be ordered.
///
/// `vertex_cache_size` controls the size of the simulated LRU cache that
/// is used to drive the optimization. A size often used is 32.
///
/// Smaller cache sizes result in faster but worse ordering, whereas larger size
/// increase hit rates at the cost of runtime.
/// [`This size-performance-relationship may be sub-linear`]
/// Cache size is clamped internally to implementation-specific ranges.
///
///
/// Returns a reference to `indices`
///
/// ```
/// use forsyth::{Config, order_triangles_inplace};
///
/// let mut indices = [0_u16, 1, 2, 3, 2, 0, 0, 1, 3, 0, 1, 4, 0, 1, 5];
/// assert!(
///     order_triangles_inplace(Config::default(), &mut indices, 32) ==
///     Ok(&[0_u16, 1, 4, 0, 1, 5, 0, 1, 2, 3, 2, 0, 0, 1, 3])
/// );
/// ```
///
/// [`This size-performance-relationship may be sub-linear`]: https://kento_asashima.gitlab.io/-/forsyth/-/jobs/1192073834/artifacts/target/criterion/caches/report/index.html

pub fn order_triangles_inplace<Index>(
    config: Config,
    indices: &mut [Index],
    vertex_cache_size: u16,
) -> Result<&[Index], Error>
where
    Index: TryInto<usize> + std::default::Default + std::cmp::PartialEq + Copy,
{
    let vertex_cache_size =
        std::cmp::max(4, std::cmp::min(vertex_cache_size, MAX_VERTEX_CACHE_SIZE));

    if indices.is_empty() || (indices.len() % 3) != 0 {
        return Err(Error::IndexToUsizeConversion);
    }

    let num_tris = indices.len() / 3;

    let (mut tris, mut verts, mut vertex_tri_list) = {
        let mut tris: Vec<TriangleInfo<Index>> = Vec::with_capacity(num_tris);
        let mut verts: Vec<VertexInfo> = Vec::with_capacity(indices.len());

        /*
        TF: Initialisation of the data is fairly straightforward, with two passes over the triangle data.
        The first simply increments the counter of the number of triangles that use each vertex,
        the second allocates the lists of triangles for each vertex and fills them in.
        After that, the score of each vertex is found using the above code,
        and then the score of each triangle is found by summing the scores of each vertex the triangle uses.
        These scores are simply cached values of the computed scores, and are updated when necessary as the algorithm runs.
        */

        let mut total_vertex_tris = 0;

        for tri_idx in 0..num_tris {
            let mut tri_verts = [Index::default(), Index::default(), Index::default()];

            for (v, tri_vert) in tri_verts.iter_mut().enumerate() {
                let element = (tri_idx * 3) + v;
                let vertex_idx = indices[element];
                *tri_vert = vertex_idx;

                let vertex_idx: usize = if let Ok(vertex_idx) = vertex_idx.try_into() {
                    vertex_idx
                } else {
                    return Err(Error::IndexToUsizeConversion);
                };

                if verts.len() < vertex_idx + 1 {
                    verts.resize(vertex_idx + 1, VertexInfo::default());
                }
                let vert: &mut VertexInfo = &mut verts[vertex_idx];
                if vert.num_tris_active == std::u16::MAX {
                    return Err(Error::TooManyTrianglesAtVertex {
                        vertex_idx,
                        limit: std::u16::MAX as usize,
                    });
                }
                vert.num_tris_active += 1;

                if total_vertex_tris == std::u32::MAX {
                    return Err(Error::TooManyTrianglesInTotal {
                        limit: std::usize::MAX,
                    });
                }

                total_vertex_tris += 1;
            }

            tris.push(TriangleInfo {
                verts: tri_verts,
                score: 0.0,
                added_to_draw_list: false,
            });
        }

        let mut vertex_tri_list = Vec::with_capacity(total_vertex_tris as usize);

        for vert in &mut verts {
            vert.tri_list_ofs = vertex_tri_list.len() as u32;
            vertex_tri_list.resize(vertex_tri_list.len() + vert.num_tris_active as usize, 0u32);
            vert.num_tris_active = 0;
        }

        for tri_idx in 0..num_tris {
            for v in 0..3 {
                let element = (tri_idx * 3) + v;

                let vertex_idx = indices[element]
                    .try_into()
                    .map_err(|_| Error::IndexToUsizeConversion)?;
                let vert: &mut VertexInfo = &mut verts[vertex_idx];
                let tri_list = &mut vertex_tri_list[vert.tri_list_ofs as usize..];
                tri_list[vert.num_tris_active as usize] = tri_idx as u32;
                // We already checked that this is below u16::MAX
                vert.num_tris_active += 1;
            }
        }

        (tris, verts, vertex_tri_list)
    };

    let mut best_score_tri = (NULL_TRI, 0.0_f32);

    for vert in &mut verts {
        vert.score = calculate_vertex_score(
            &config,
            vert.num_tris_active as u32,
            NOT_IN_CACHE,
            vertex_cache_size,
        );
        for i in 0..vert.num_tris_active {
            let tri_idx = vertex_tri_list[vert.tri_list_ofs as usize + i as usize];
            let mut tri = &mut tris[tri_idx as usize];
            tri.score += vert.score;
            if best_score_tri.0 == NULL_TRI || tri.score > best_score_tri.1 {
                best_score_tri = (tri_idx, tri.score);
            }
        }
    }

    let mut draw_list_cursor = 0;

    /*
    TF: Then comes the main body of the algorithm, which picks one triangle at a time to add to the list of drawn triangles, until there are no more triangles left to draw.
    Usually, the algorithm knows from the previous iteration which triangle has the highest score, and simply picks that one.
    In some cases, for example the first time the algorithm runs, it does not already know the best triangle, or the supposed best triangle has an unusually low score (implying that there may be others in the mesh that are better).
    In those rare circumstances, it runs through all the remaining triangles in the mesh searching for the best score.
    */
    let mut lru_cache: VecDeque<Index> = VecDeque::with_capacity(vertex_cache_size as usize + 3);

    while best_score_tri.0 != NULL_TRI {
        let mut best_tri = &mut tris[best_score_tri.0 as usize];
        if best_tri.added_to_draw_list {
            break;
        }
        best_tri.added_to_draw_list = true;

        for v in &best_tri.verts {
            /*
            TF: The best triangle is then added to the draw list. For each vertex the triangle used,
            the valence of that vertex (the number of triangles not yet drawn that use it) is reduced by one,
            and the list of triangle indices in the vertex is updated appropriately.
            */
            let vertex_idx = *v;
            let vertex_idx_usize: usize = vertex_idx
                .try_into()
                .map_err(|_| Error::IndexToUsizeConversion)?;

            let vert = &mut verts[vertex_idx_usize];

            let tri_list = &mut vertex_tri_list[vert.tri_list_ofs as usize
                ..vert.tri_list_ofs as usize + vert.num_tris_active as usize];

            for (i, ti) in tri_list.iter().enumerate() {
                if *ti == best_score_tri.0 {
                    vert.num_tris_active -= 1;
                    for rot in i..vert.num_tris_active as usize {
                        tri_list[rot] = tri_list[rot + 1];
                    }

                    break;
                }
            }

            // Add vertex to draw list
            if let Some(draw_list_idx) = indices.get_mut(draw_list_cursor) {
                *draw_list_idx = vertex_idx;
                draw_list_cursor += 1;
            } else {
                return Err(Error::MalformedDrawList);
            }

            /*
            TF: The three vertices used by the triangle are either moved to the head of the LRU modelled cache,
            or added to the head if they were not already in it.
            */
            lru_cache.retain(|&i| i != vertex_idx);
            lru_cache.push_front(vertex_idx);
        }

        /*
        TF: The cache is temporarily grown in size by three vertices to include all vertices that were previously in the cache,
        and up to the three new ones of this triangle.
        Then the new positions of the vertices in the cache are updated, their corresponding scores are found using the code given above,
        and the scores of all their still-to-be-added triangles are also updated.
        */
        best_score_tri = (NULL_TRI, 0.0);

        for (cache_pos, vertex_idx) in lru_cache.iter().enumerate() {
            let cache_pos = std::cmp::min(cache_pos, (MAX_VERTEX_CACHE_SIZE - 1) as usize) as u16;
            let (new_score, old_score, tri_list_ofs, num_tris_active) = {
                let vertex_idx: usize = (*vertex_idx)
                    .try_into()
                    .map_err(|_| Error::IndexToUsizeConversion)?;
                let vert: &mut VertexInfo = &mut verts[vertex_idx];
                vert.cache_pos = if cache_pos < vertex_cache_size {
                    cache_pos
                } else {
                    NOT_IN_CACHE
                };
                let old_score = vert.score;
                vert.score = calculate_vertex_score(
                    &config,
                    vert.num_tris_active as u32,
                    cache_pos,
                    vertex_cache_size,
                );

                (
                    vert.score,
                    old_score,
                    vert.tri_list_ofs,
                    vert.num_tris_active,
                )
            };

            for tri_idx in &vertex_tri_list
                [tri_list_ofs as usize..tri_list_ofs as usize + num_tris_active as usize]
            {
                let tri_idx = *tri_idx;
                if tri_idx != NULL_TRI {
                    let tri = &mut tris[tri_idx as usize];

                    tri.score -= old_score;
                    tri.score += new_score;

                    if tri.added_to_draw_list {
                        continue;
                    }

                    //TF: As this is done, the score and index of the highest-scoring triangle so far are noted.
                    if best_score_tri.0 == NULL_TRI || tri.score > best_score_tri.1 {
                        best_score_tri = (tri_idx, tri.score);
                    }
                }
            }
        }

        /*
        TF: Finally, the cache is shrunk back to its normal size, with up to three vertices falling out of it.
        Their cache positions have already been updated appropriately.
        */
        while lru_cache.len() > vertex_cache_size as usize {
            lru_cache.pop_back();
        }

        /*
        TF: The algorithm repeats until there are no triangles left to add.
        */

        if best_score_tri.0 == NULL_TRI {
            if draw_list_cursor >= num_tris * 3 {
                break;
            }

            for (tri_idx, tri) in tris.iter().enumerate() {
                if tri.added_to_draw_list {
                    continue;
                }
                // TF: As this is done, the score and index of the highest-scoring triangle so far are noted.
                if best_score_tri.0 == NULL_TRI || tri.score > best_score_tri.1 {
                    best_score_tri = (tri_idx as u32, tri.score);
                }
            }

            if best_score_tri.0 == NULL_TRI {
                break;
            }
        }
    }

    if draw_list_cursor != num_tris * 3 {
        return Err(Error::MalformedDrawList);
    }

    Ok(&indices[0..draw_list_cursor])
}

/// Creates an ordered triangle index buffer.
///
/// A convenience function that wraps [`order_triangles_in_place`] to return a newly
/// allocated ordered index buffer.
///
/// This is equivalent to calling [`order_triangles_in_place`] with default [`Config`] and `cache_size` of 32.
///
/// ```
/// use forsyth::{Error,order_triangles};
///
/// // a triangle
/// assert_eq!(order_triangles(&[0, 1, 2]), Ok(vec![0, 1, 2]));
/// // a quad
/// assert_eq!(
///     order_triangles(&[0_u32, 1, 2, 0, 2, 3]),
///     Ok(vec![0, 1, 2, 0, 2, 3]),
/// );
///
/// assert_eq!(
///     order_triangles(&Vec::<u32>::new()),
///     Err(Error::IndicesNotTriples)
/// );
/// assert_eq!(
///     order_triangles(&[0, 1]),
///     Err(Error::IndicesNotTriples)
/// );
/// assert_eq!(
///     order_triangles(&[0, 1, 2, 3]),
///     Err(Error::IndicesNotTriples)
/// );
///
/// // Works with all (un-)signed integers
/// assert_eq!(
///     order_triangles(&[0_u8, 1, 2, 3, 4, 5]),
///     Ok(vec![0, 1, 2, 3, 4, 5])
/// );
/// assert_eq!(
///     order_triangles(&[0_i16, 1, 2, 3, 4, 5]),
///     Ok(vec![0, 1, 2, 3, 4, 5])
/// );
/// assert_eq!(
///     order_triangles(&[0_u32, 1, 2, 3, 4, 5]),
///     Ok(vec![0, 1, 2, 3, 4, 5])
/// );
/// assert_eq!(
///     order_triangles(&[0_i64, 1, 2, 3, 4, 5]),
///     Ok(vec![0, 1, 2, 3, 4, 5])
/// );
/// assert_eq!(
///     order_triangles(&[0_usize, 1, 2, 3, 4, 5]),
///     Ok(vec![0, 1, 2, 3, 4, 5])
/// );
///
/// // Indices can be sparse
/// assert_eq!(
///     order_triangles(&[0_i8, 1, 2, 63, 64, 65]),
///     Ok(vec![0, 1, 2, 63, 64, 65])
/// );
///
/// // Indices cannot be negative
/// assert_eq!(
///    order_triangles(&[0_i8, -1, -2, 63, 64, 65]),
///    Err(Error::IndexToUsizeConversion)
/// );
/// ```
///
/// [`order_triangles_in_place`]: ./fn.order_triangles_inplace.html
/// [`Config`]: ./struct.Config.html

pub fn order_triangles<Index>(indices: &[Index]) -> Result<Vec<Index>, Error>
where
    Index: std::convert::TryInto<usize> + std::default::Default + std::cmp::PartialEq + Copy,
{
    if indices.is_empty() || (indices.len() % 3) != 0 {
        return Err(Error::IndicesNotTriples);
    }

    let vertex_cache_size = DEFAULT_VERTEX_CACHE_SIZE;

    let buffer = {
        let mut buffer = Vec::with_capacity(indices.len());
        buffer.extend_from_slice(indices);

        order_triangles_inplace(Config::default(), buffer.as_mut_slice(), vertex_cache_size)?;

        buffer
    };
    Ok(buffer)
}

/// Orders a vertex buffer to maximize data locality.
///
/// The returned vertex buffer contains the referenced vertices from `vertices` and is ordered to maximize data locality when being read sequentially.
/// The accompanying index buffer contains the mapped `indices` to match the new vertex ordering.
///
/// This function can also be used to consolidate sparse index and vertex data as unreferenced vertices are not copied.
/// ```
/// use forsyth::{Error,order_vertices};
///
/// assert_eq!(
///     order_vertices(&['d', 'c', 'b', 'a'], &[3, 2, 0, 2, 1, 0]),
///     Ok((vec!['a', 'b', 'd', 'c'], vec![0, 1, 2, 1, 3, 2]))
/// );
///
/// // Vertices not referenced by any index are removed
/// assert_eq!(
///     order_vertices(&['x', 'x', 'a', 'b', 'y', 'c'], &[2, 3, 5]),
///     Ok((vec!['a', 'b', 'c'], vec![0, 1, 2]))
/// );
///
/// // Indices must be in valid range
/// assert_eq!(
///     order_vertices(&['a', 'b', 'c'], &[0_i8, 1, 99]),
///     Err(Error::VertexOutOfBounds)
/// );
/// assert_eq!(
///     order_vertices(&['a', 'b', 'c'], &[0_i8, -1, 2]),
///     Err(Error::IndexToUsizeConversion)
/// );

/// ```
/// [`This size-performance-relationship may be sub-linear`]: https://kento_asashima.gitlab.io/-/forsyth/-/jobs/1192073834/artifacts/target/criterion/caches/report/index.html

pub fn order_vertices<Index, Vertex>(
    vertices: &[Vertex],
    indices: &[Index],
) -> Result<(Vec<Vertex>, Vec<Index>), Error>
where
    Index: Copy + Eq + TryInto<usize> + TryFrom<usize> + std::hash::Hash,
    Vertex: Copy,
{
    let mut ordered_vertices = Vec::with_capacity(vertices.len());
    let mut ordered_indices = Vec::with_capacity(indices.len());
    let mut index_map: HashMap<Index, Index> = HashMap::with_capacity(indices.len());

    for index in indices {
        let mapped_idx = match index_map.entry(*index) {
            std::collections::hash_map::Entry::Occupied(mapped) => *mapped.get(),
            std::collections::hash_map::Entry::Vacant(vacant) => {
                let index = (*index)
                    .try_into()
                    .map_err(|_| Error::IndexToUsizeConversion)?;
                if let Some(vertex) = vertices.get(index) {
                    ordered_vertices.push(*vertex);
                    let mapped = (ordered_vertices.len() - 1)
                        .try_into()
                        .map_err(|_| Error::IndexToUsizeConversion)?;
                    *vacant.insert(mapped)
                } else {
                    return Err(Error::VertexOutOfBounds);
                }
            }
        };
        ordered_indices.push(mapped_idx);
    }

    Ok((ordered_vertices, ordered_indices))
}

#[cfg(test)]
mod tests {

    use super::*;

    use proptest::collection::vec;
    use proptest::prelude::*;

    #[test]
    fn error_formatting() {
        for e in [
            Error::IndexToUsizeConversion,
            Error::IndicesNotTriples,
            Error::TooManyTrianglesAtVertex {
                vertex_idx: 123,
                limit: 42,
            },
            Error::TooManyTrianglesInTotal { limit: 42 },
            Error::MalformedDrawList,
            Error::VertexOutOfBounds,
        ] {
            assert_eq!(
                format!("{}", e),
                match e {
                    Error::IndicesNotTriples => "elements are not all triples",
                    Error::IndexToUsizeConversion => "cannot convert Index to usize",
                    Error::TooManyTrianglesInTotal { .. } =>
                        "too many triangles in total. 42 triangles are supported",
                    Error::TooManyTrianglesAtVertex { .. } =>
                        "too many triangles connected to vertex 123. 42 triangles are supported",
                    Error::MalformedDrawList =>
                        "the generated ordered Index draw list is malformed",
                    Error::VertexOutOfBounds => "the vertex index is out of bounds",
                }
                .to_string()
            );
        }
    }

    #[test]
    fn config() {
        assert_eq!(
            Config {
                cache_decay_power: 1.5,
                last_tri_score: 0.75,
                valence_boost_scale: 2.0,
                valence_boost_power: 0.5,
            },
            Config::default()
        );
    }

    #[test]
    fn combined() {
        let input_vertices = &['a', 'b', 'c', 'd', 'e'];
        let input_indices = &[0_u32, 1, 2, 0, 1, 3, 0, 3, 4, 2, 1, 4];

        // order indices first
        let ordered_indices =
            order_triangles(input_indices).unwrap_or_else(|_| input_indices.to_vec());

        assert_eq!(&ordered_indices, &[0, 3, 4, 0, 1, 3, 2, 1, 4, 0, 1, 2]);

        // then order vertices and remap indices accordingly
        let (ordered_vertices, ordered_indices) =
            order_vertices(&input_vertices[..], ordered_indices.as_slice())
                .unwrap_or_else(|_| (input_vertices.to_vec(), ordered_indices));

        assert_eq!(&ordered_vertices, &['a', 'd', 'e', 'b', 'c']);
        assert_eq!(&ordered_indices, &[0, 1, 2, 0, 3, 1, 4, 3, 2, 0, 3, 4]);
    }

    #[test]
    fn fuzz_regressions() {
        {
            assert_eq!(
                order_triangles(&[i16::from_be_bytes([130_u8, 246])]),
                Err(Error::IndicesNotTriples)
            );
        }
    }

    #[test]
    fn sanity_checks() {
        let mut cache = VecDeque::new();
        cache.push_back(0);
        cache.push_back(1);
        cache.push_back(2);
        cache.push_back(3);
        cache.retain(|i| *i != 3);
        assert_eq!(cache.len(), 3);
        cache.push_front(3);
        assert_eq!(cache, [3, 0, 1, 2]);
    }

    #[test]
    fn test_vertex_score() {
        const MAX_VERTEX_CACHE_SIZE: u16 = 32;

        let config = Config::default();

        for (cache_pos, ref_score) in [
            (-2, config.valence_boost_scale),
            (-1, config.valence_boost_scale),
            (0, config.last_tri_score + config.valence_boost_scale),
            (1, config.last_tri_score + config.valence_boost_scale),
            (2, config.last_tri_score + config.valence_boost_scale),
            (3, 3.0),
            (4, 2.9487243),
            (5, 2.8983564),
            (6, 2.8489127),
            (MAX_VERTEX_CACHE_SIZE as i32 - 1, 2.0064032),
            (MAX_VERTEX_CACHE_SIZE as i32, config.valence_boost_scale),
            (2 * MAX_VERTEX_CACHE_SIZE as i32, config.valence_boost_scale),
        ]
        .iter()
        {
            let score = calculate_vertex_score(
                &config,
                1,
                if *cache_pos < 0 {
                    MAX_VERTEX_CACHE_SIZE + 1
                } else {
                    *cache_pos as u16
                },
                MAX_VERTEX_CACHE_SIZE,
            );
            assert!(
                (score - ref_score).abs() <= f32::EPSILON,
                "Score ({},{}) != ({},{})",
                &cache_pos,
                score,
                &cache_pos,
                &ref_score
            );
        }
    }

    #[test]
    fn basic_triangle_ordering() {
        {
            let mut indices = [0_u16, 1, 2, 3, 2, 0, 0, 1, 3, 0, 1, 4, 0, 1, 5];
            assert_eq!(
                order_triangles_inplace(Config::default(), &mut indices, 32).unwrap(),
                &[0, 1, 4, 0, 1, 5, 0, 1, 2, 3, 2, 0, 0, 1, 3]
            );
        }

        assert_eq!(
            order_triangles_inplace::<u32>(Config::default(), &mut [], 32),
            Err(Error::IndexToUsizeConversion)
        );

        assert_eq!(
            order_triangles_inplace(Config::default(), &mut [-1_i32, 0, 2], 32),
            Err(Error::IndexToUsizeConversion)
        );

        // 1 shared edge - quad
        assert_eq!(
            order_triangles(&[0_u32, 1, 2, 0, 2, 3]).unwrap(),
            [0, 1, 2, 0, 2, 3]
        );

        assert_eq!(
            order_triangles(&Vec::<u32>::new()),
            Err(Error::IndicesNotTriples)
        );
        assert_eq!(order_triangles(&[0]), Err(Error::IndicesNotTriples));
        assert_eq!(order_triangles(&[0, 1]), Err(Error::IndicesNotTriples));
        assert_eq!(order_triangles(&[0, 1, 2]).unwrap(), [0, 1, 2]);
        assert_eq!(
            order_triangles(&[0, 1, 2, 3]),
            Err(Error::IndicesNotTriples)
        );

        // Two disjunctive tris in multiple types
        assert_eq!(
            order_triangles(&[0_u32, 1, 2, 3, 4, 5]).unwrap(),
            [0, 1, 2, 3, 4, 5]
        );
        assert_eq!(
            order_triangles(&[0_u16, 1, 2, 3, 4, 5]).unwrap(),
            [0, 1, 2, 3, 4, 5]
        );
        assert_eq!(
            order_triangles(&[0_u8, 1, 2, 3, 4, 5]).unwrap(),
            [0, 1, 2, 3, 4, 5]
        );
        assert_eq!(
            order_triangles(&[0_u64, 1, 2, 3, 4, 5]).unwrap(),
            [0, 1, 2, 3, 4, 5]
        );

        assert_eq!(
            order_triangles(&[0_i32, 1, 2, 3, 4, 5]).unwrap(),
            [0, 1, 2, 3, 4, 5]
        );
        assert_eq!(
            order_triangles(&[0_i16, 1, 2, 3, 4, 5]).unwrap(),
            [0, 1, 2, 3, 4, 5]
        );
        assert_eq!(
            order_triangles(&[0_i8, 1, 2, 3, 4, 5]).unwrap(),
            [0, 1, 2, 3, 4, 5]
        );
        assert_eq!(
            order_triangles(&[0_i64, 1, 2, 3, 4, 5]).unwrap(),
            [0, 1, 2, 3, 4, 5]
        );
        assert_eq!(
            order_triangles(&[0_usize, 1, 2, 3, 4, 5]).unwrap(),
            [0, 1, 2, 3, 4, 5]
        );
        assert_eq!(
            order_triangles(&[0_isize, 1, 2, 3, 4, 5]).unwrap(),
            [0, 1, 2, 3, 4, 5]
        );
        assert_eq!(
            order_triangles(&[0_u128, 1, 2, 3, 4, 5]).unwrap(),
            [0, 1, 2, 3, 4, 5]
        );
        assert_eq!(
            order_triangles(&[0_i128, 1, 2, 3, 4, 5]).unwrap(),
            [0, 1, 2, 3, 4, 5]
        );

        // Indices are sparse
        assert_eq!(
            order_triangles(&[0_i8, 1, 2, 63, 64, 65]).unwrap(),
            [0, 1, 2, 63, 64, 65]
        );

        // Indices are negative
        assert_eq!(
            order_triangles(&[0_i8, -1, -2, 63, 64, 65]),
            Err(Error::IndexToUsizeConversion)
        );

        {
            let num_indices = 3 * 256;
            let mut indices = Vec::with_capacity(num_indices);
            for _ in 0..num_indices {
                indices.push(indices.len());
            }

            for cs in [
                0,
                1,
                2,
                3,
                4,
                8,
                16,
                32,
                64,
                128,
                256,
                257,
                std::u16::MAX - 1,
                std::u16::MAX,
            ] {
                let mut indices = indices.clone();
                let result = order_triangles_inplace(Config::default(), indices.as_mut_slice(), cs);
                assert!(result.is_ok(), "result is {:?}", result);
            }
        }

        {
            let mut indices = Vec::with_capacity((std::u16::MAX as usize) + 1);
            for _ in 0..(std::u16::MAX as usize) + 1 {
                indices.push(0);
                indices.push(1);
                indices.push(2);
            }

            assert_eq!(
                order_triangles(indices.as_slice()),
                Err(Error::TooManyTrianglesAtVertex {
                    vertex_idx: 0,
                    limit: 65535
                })
            );
        }
    }

    #[test]
    fn basic_vertex_ordering() {
        assert_eq!(
            order_vertices(&['a', 'b', 'c'], &[0, 1, 2]),
            Ok((vec!['a', 'b', 'c'], vec![0, 1, 2]))
        );

        assert_eq!(
            order_vertices(&['x', 'x', 'a', 'b', 'y', 'c'], &[2, 3, 5]),
            Ok((vec!['a', 'b', 'c'], vec![0, 1, 2]))
        );

        assert_eq!(
            order_vertices(&['a', 'b', 'c'], &[-1, 0, 2]),
            Err(Error::IndexToUsizeConversion)
        );

        assert_eq!(
            order_vertices(&['a', 'b', 'c'], &[0, 1, 3]),
            Err(Error::VertexOutOfBounds)
        );
    }

    #[test]
    fn readme_test() {
        let input_vertices = &['a', 'b', 'c', 'd', 'e'];
        let input_indices = &[0_u32, 1, 2, 0, 1, 3, 0, 3, 4, 2, 1, 4];

        // order indices first
        let ordered_indices =
            order_triangles(input_indices).unwrap_or_else(|_| input_indices.to_vec());

        assert_eq!(&ordered_indices, &[0, 3, 4, 0, 1, 3, 2, 1, 4, 0, 1, 2]);

        // then order vertices and remap indices accordingly
        let (ordered_vertices, ordered_indices) =
            order_vertices(input_vertices, ordered_indices.as_slice())
                .unwrap_or_else(|_| (input_vertices.to_vec(), ordered_indices));

        assert_eq!(&ordered_vertices, &['a', 'd', 'e', 'b', 'c']);
        assert_eq!(&ordered_indices, &[0, 1, 2, 0, 3, 1, 4, 3, 2, 0, 3, 4]);
    }

    proptest! {

        #![proptest_config(ProptestConfig::with_cases(20000))]
        #[test]
        fn fuzz_order_triangles(mut indices in vec(0u8..32,3..32))
        {
            while indices.len() < 3 || indices.len() % 3 != 0 {
                indices.push(0);
            }

            let mut ordered = order_triangles(&indices).expect("does not panic!");
            assert_eq!(indices.len(),ordered.len());
            indices.sort_unstable();
            ordered.sort_unstable();
            assert_eq!(indices,ordered);
        }
    }
}