sort.h File Reference

File containing custom sorting algorithms for expressions. More...

#include "abstract.h"

Include dependency graph for sort.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces
	csl
	Namespace for csl library.

Functions
void	csl::sort (std::vector< Expr > &argument)
	Sorts a container using mergeSort(). More...
void	csl::sort (std::vector< Expr >::iterator first, std::vector< Expr >::iterator last)
	Sorts a container using mergeSort(). More...
void	csl::selectionSort (std::vector< Expr > &argument)
	Applies the selection sort algorithm on a container. More...
void	csl::selectionSort (std::vector< Expr >::iterator first, std::vector< Expr >::iterator last)
	Applies the selection sort algorithm on a container. More...
void	csl::mergeSort (std::vector< Expr > &argument)
	Applies the merge sort algorithm on a container. More...
void	csl::mergeSort (std::vector< Expr >::iterator first, std::vector< Expr >::iterator last)
	Applies the merge sort algorithm on a container. More...

Variables
size_t	csl::minMergeSize = 10
	Minimum size for a container to be sorted with mergeSort(). More...

Detailed Description

File containing custom sorting algorithms for expressions.

The std::sort algorithm is in principle more efficient but needs a perfect total ordering between elements, otherwise it might (and will eventually) crash. Ordering between expressions is indeed well-formed, but only when expressions are cannonical (typically after a csl::DeepRefresh() call). If an expression is not canonical, the ordering may be ill-formed and std::sort() function crashes. We then define here algorithms (selection and merge sorts) that will not crash. For a canonical expression, these sorting algorithms will have the same effect as std::sort(), may be slightly less efficient. For non canonical ones, the sort is ill-defined but may still be performed.

Author

Grégoire Uhlrich

Version

1.3

Date

2020-09-20