pub trait NVec<D: Dim, T>: NVecCore<D, T> {
Show 14 methods
// Required methods
fn at(&self, idx: impl IntoIdx<D>) -> T;
fn child(&self, i: D::ChildIdx) -> impl NVec<D::PrevDim, T>;
fn all(&self) -> impl Iterator<Item = T>;
// Provided methods
fn num_children(&self) -> usize { ... }
fn card(&self, idx: impl Into<D::CardIdx>) -> usize { ... }
fn is_bounded(&self) -> bool { ... }
fn is_rectangular(&self) -> bool { ... }
fn is_unbounded(&self) -> bool { ... }
fn in_bounds(&self, idx: impl Into<D::LeqIdx>) -> bool { ... }
fn card_equality(&self, other: &impl NVec<D, T>) -> CardEquality<D> { ... }
fn try_at(&self, idx: impl IntoIdx<D>) -> Option<T> { ... }
fn equality(&self, other: &impl NVec<D, T>) -> Equality<D>
where T: PartialEq { ... }
fn children(&self) -> impl Iterator<Item = impl NVec<D::PrevDim, T>> { ... }
fn all_in(
&self,
indices: impl Iterator<Item = impl IntoIdx<D>>,
) -> impl Iterator<Item = T> { ... }
}Expand description
A D dimensional vector.
The objective of this trait to enable polymorphism over containers that are or that are capable of behaving as contagious data structures with efficient random access by indices of its elements.
V1, V2, etc. are type aliases for NVec<D1, T>, NVec<D2, T>, and so on.
§Motivation
The NVec trait mainly aims to support algorithms.
The goal is to implement the algorithm once without considering the underlying
type of the vectors, and it works for all inputs that behave like a multi-dimensional
vector without any loss of performance.
The most straightforward example is the standard Vec<T> or &[T]; they both
implement V1<T>.
And consequently, Vec<Vec<T>> implements V2<T>.
Actually, inner type can vary since Vec<X> implements V2<T> provided that X
implements V1<T>.
This might be the first example of polymorphism.
This trait aims at enabling any type that makes sense to implement the vector trait
with the corresponding dimension.
To elaborate the idea of polymorphism, consider an algorithm that requires a distance matrix as its input such that the (i,j)-th element of the matrix represents the distance from location i to location j. Our goal is to implement this algorithm once, which works with different distance matrix representations without any loss of performance.
Say our distance unit is u32, so our input distance matrix is impl V2<u32>.
fn algorithm(distance_matrix: impl V2<u32>) { ... }We want to be able to call algorithm with any input that makes sense as a distance
matrix.
Let’s think about what can implement V2<u32>?
§Dense
We can store all distances in a 2-dimensional structure, Vec<Vec<u32>> for instance.
As mentioned above, Vec<Vec<u32>> implements V2<u32>, so this works.
let dense_matrix = vec![vec![0, 2, 3], vec![3, 0, 7], vec![2, 2, 0]];
algorithm(&dense_matrix);§Flattened Dense
Sometimes it is advantageous to flatten matrices and treat the 1-dimensional structure as a 2-dimensional structure.
We can also treat a V1<T> as a jagged V2<T> by providing the additional information
about the column lengths which can be any V1<usize>.
let flat_storage = vec![0, 2, 3, 3, 0, 7, 2, 2, 0];
let row_end_indices = V.d1().fun(|[i]| 3 * (i + 1)).bounded(3);
let flat_dense_matrix = flat_storage.as_jagged(&row_end_indices);
algorithm(&flat_dense_matrix);§Constant
Sometimes we have scenarios where all entries of the matrix are identical to some value. This is often very handy in input polymorphism.
- Consider the shortest distance problem.
When, all distances are equal to 1 (
d[i, j] = 1, for all i, j), solution of the same problem represents the minimum number of arcs to reach the destination. - Consider the minimum cost flow problem.
When all edges have infinite capacity (
cap[i, j] = INF, for all i, j), and when we send one unit of flow from s to t, the solution represents the shortest path from s to t.
In order to use the algorithm, should we create an n-by-n storage of the same values?
Not necessarily.
let all_ones = V.d2().constant(1).with_rectangular_bounds([3, 3]);
algorithm(&all_ones);§Sparse
Quite often, we run into a situation where our vector is sparse and we are worried about
the wasted memory. Consider, for instance, that only certain locations are reachable from
one location, and hence, only those pairs have distance values. We assume that the distances
between all other locations are u32::MAX.
Should we fill an n-by-n storage where almost all elements are equal to u32::MAX?
Not necessarily.
let mut sparse_matrix = V.d2().sparse(u32::MAX);
*sparse_matrix.at_mut([0, 1]) = 10;
*sparse_matrix.at_mut([1, 2]) = 7;
*sparse_matrix.at_mut([1, 3]) = 5;
*sparse_matrix.at_mut([3, 8]) = 60;
assert_eq!(sparse_matrix.lookup_len(), 4);
algorithm(&sparse_matrix);§Functional
Sometimes, we do not prefer to store any distances at all. The reasons might vary. For instance,
- computing the element might be so cheap that it doesn’t make sense to store and look up,
- the size of the matrix is critically large given the hardware, we prefer to pay the computational price of re-calculating the element every time it is requested.
In these cases, we can simply provide the function that computes the element.
struct Location(u32, u32);
fn euclidean(a: &Location, b: &Location) -> u32 {
(((a.0 - b.0) * (a.0 - b.0) + (a.1 - b.1) * (a.1 - b.1)) as f64).sqrt() as u32
}
let locations = vec![Location(0, 3), Location(3, 2), Location(4, 1)];
let euclidean_matrix = V.d2().fun(|[i, j]| euclidean(&locations[i], &locations[j]));
algorithm(&euclidean_matrix);§Cached
Sometimes, we do not prefer to store distances but due to a different reason.
- The matrix might be huge, while the algorithm accesses only a small subset of elements.
- But we don’t necessarily know ahead of time which elements will be accessed.
- Instead of pre-computing the entire matrix, we can compute elements on demand.
- However, unlike the Euclidean example above, the computation of the element might be relatively expensive.
- In order to avoid repeating the computation of the element on repeated accesses, we cache the computed elements.
We can achieve this by simply calling into_cached on a functional vector.
struct Address(/* coordinates */);
fn distance_api(a: &Address, b: &Address) -> u32 {
todo!("make an api call to get the shortest distance wrt routing on the road network")
}
let addresses = vec![Address(), Address(), Address()];
let cached_distances = V
.d2()
.fun(|[i, j]| distance_api(&addresses[i], &addresses[j]))
.into_cached();
assert_eq!(cached_distances.cache_len(), 0); // cache is initially empty
algorithm(&cached_distances);Required Methods§
Sourcefn at(&self, idx: impl IntoIdx<D>) -> T
fn at(&self, idx: impl IntoIdx<D>) -> T
Returns the element at the idx-th position of the vector.
Note that the dimensions of the vector and the index are equal; and hence, the result is the scalar.
§Panics
Panics if the idx is not in_bounds.
§Examples
use orx_v::*;
let vec = vec![
vec![0, 1, 2],
vec![3],
vec![4, 5],
];
assert_eq!(vec.at([0, 1]), 1);
assert_eq!(vec.at([1, 0]), 3);
assert_eq!(vec.at([2, 1]), 5);
// vec.at([1, 1]); // panics!
assert_eq!(vec.try_at([1, 1]), None);Sourcefn child(&self, i: D::ChildIdx) -> impl NVec<D::PrevDim, T>
fn child(&self, i: D::ChildIdx) -> impl NVec<D::PrevDim, T>
Returns the i-th child of the vector.
Note that child has a dimension that is one less than the dimension of this vector.
§Panics
Panics if i is out of bounds; i.e., i >= vec.num_children().
§Examples
use orx_v::*;
// D2
let vec = vec![
vec![0, 1, 2],
vec![3],
vec![4, 5],
];
// child is a D1 vec
let child = vec.child(2);
assert_eq!(child.num_children(), 2);
assert_eq!(child.at([0]), 4);
assert_eq!(child.at([1]), 5);Sourcefn all(&self) -> impl Iterator<Item = T>
fn all(&self) -> impl Iterator<Item = T>
Returns a flattened iterator over all scalar (D0) elements of the vector.
In this sense, all can be considered similar to recursively
called flat map on higher dimensional collections.
See all_in for creating an iterator over a given domain.
§Examples
use orx_v::*;
let vec = vec![
vec![0, 1],
vec![],
vec![2],
];
let mut all = vec.all();
assert_eq!(all.next(), Some(0));
assert_eq!(all.next(), Some(1));
assert_eq!(all.next(), Some(2));
assert_eq!(all.next(), None);§Panics
Panics if the vector is_unbounded as this will lead to an infinite loop.
The following are examples for unbounded vectors:
ConstantVec=>V.d1().constant(42)SparseVec=>V.d2().sparse(42)FunVec=>V.d2().fun(|[i, j]| i + 42 * j)
Finite domain of these vectors can be set by calling:
boundedforD1vectors,with_rectangular_boundsorwith_variable_boundsfor higher dimensional vectors.
§Examples
use orx_v::*;
let v1 = V.d1().constant(42).bounded(4);
assert_eq!(
v1.all().collect::<Vec<_>>(),
vec![42, 42, 42, 42],
);
let mut v2 = V.d2().sparse(0).with_rectangular_bounds([2, 3]);
*v2.at_mut([0, 2]) = 42;
assert_eq!(
v2.all().collect::<Vec<_>>(),
vec![0, 0, 42, 0, 0, 0],
);
let num_cols = [1, 0, 2, 1];
let v2 = V.d2().fun(|[i, j]| 10 * i + j).with_variable_bounds(&num_cols);
assert_eq!(
v2.equality(&[vec![0], vec![], vec![20, 21], vec![30]]),
Equality::Equal,
);
assert_eq!(
v2.all().collect::<Vec<_>>(),
vec![0, 20, 21, 30],
);Provided Methods§
Sourcefn num_children(&self) -> usize
fn num_children(&self) -> usize
Returns the number of children of the vector; i.e., number of elements of the one lower dimension.
If this vector is of dimension D2; num_children returns the
number of D1 children (V1) of this vector.
§Examples
use orx_v::*;
let vec = vec![
vec![0, 1, 2],
vec![3],
vec![4, 5],
];
assert_eq!(vec.num_children(), 3);
assert_eq!(vec.child(2).num_children(), 2);Sourcefn card(&self, idx: impl Into<D::CardIdx>) -> usize
fn card(&self, idx: impl Into<D::CardIdx>) -> usize
Returns the cardinality of the vec in any of the lower dimensions.
§Examples
use orx_v::*;
let v2 = [
vec![0, 2, 3],
vec![1, 7],
vec![],
vec![10, 3, 4, 8],
];
// outer-most cardinality
assert_eq!(v2.card([]), 4);
// cardinality of the first-degree child
assert_eq!(v2.card([3]), 4);
// equivalent to:
assert_eq!(v2.child(3).card([]), 4);This logic works similarly for higher dimensions.
use orx_v::*;
let v4 = [
vec![ // 0
vec![ // 0, 0
vec![3], // 0, 0, 0
vec![1, 2], // 0, 0, 1
],
vec![ // 0, 1
vec![6, 7, 8], // 0, 1, 0
vec![], // 0, 1, 1
vec![9], // 0, 1, 2
],
]
];
assert_eq!(v4.card([]), 1);
assert_eq!(v4.card([0]), 2);
assert_eq!(v4.card([0, 0]), 2);
assert_eq!(v4.card([0, 0, 0]), 1);
assert_eq!(v4.card([0, 0, 1]), 2);
assert_eq!(v4.card([0, 1]), 3);
assert_eq!(v4.card([0, 1, 0]), 3);
assert_eq!(v4.card([0, 1, 1]), 0);
assert_eq!(v4.card([0, 1, 2]), 1);Sourcefn is_bounded(&self) -> bool
fn is_bounded(&self) -> bool
Returns whether or not the vector is bounded.
The following are examples for unbounded vectors:
ConstantVec=>V.d1().constant(42)SparseVec=>V.d2().sparse(42)FunVec=>V.d2().fun(|[i, j]| i + 42 * j)
Finite domain of these vectors can be set by calling:
boundedforD1vectors,with_rectangular_boundsorwith_variable_boundsfor higher dimensional vectors.
§Example
use orx_v::*;
let v2 = vec![
vec![0, 1],
vec![],
vec![2],
];
assert!(v2.is_bounded());
let v1: &[usize] = v2[0].as_slice();
assert!(v1.is_bounded());
// constant
let v1 = V.d1().constant(42);
assert!(v1.is_unbounded());
let v1 = V.d1().constant(42).bounded(10);
assert!(v1.is_bounded());
// sparse
let mut v2 = V.d2().sparse(0);
*v2.at_mut([0, 2]) = 42;
assert!(v2.is_unbounded());
let mut v2 = V.d2().sparse(0).with_rectangular_bounds([2, 3]);
*v2.at_mut([0, 2]) = 42;
assert!(v2.is_bounded());
// fun
let v2 = V.d2().fun(|[i, j]| 10 * i + j);
assert!(v2.is_unbounded());
let num_cols = [1, 0, 2, 1];
let v2 = V.d2().fun(|[i, j]| 10 * i + j).with_variable_bounds(&num_cols);
assert!(v2.is_bounded());Sourcefn is_rectangular(&self) -> bool
fn is_rectangular(&self) -> bool
Returns whether or not the cardinalities of the vector are rectangular.
A rectangular vector of dimension D has the same number of children
at a given lower dimension for all indices.
- All empty vectors are rectangular.
- All
D1vectors are dimensional. - Two and higher dimensional matrices are rectangular.
§Examples
You may see examples of rectangular vectors below.
use orx_v::*;
let vec = V.d3().empty::<i64>();
assert!(vec.is_rectangular());
let vec = vec![1, 3, 4];
assert!(vec.is_rectangular());
let vec = V.d4().constant(42).with_rectangular_bounds([1, 3, 2, 7]);
assert!(vec.is_rectangular());
let vec = vec![
vec![1, 2, 3],
vec![4, 5, 6],
];
assert!(vec.is_rectangular());
let vec = vec![
vec![
vec![1, 2, 3],
],
vec![
vec![4, 5, 6],
],
];
assert!(vec.is_rectangular());
let flat_vec = vec![0, 1, 2, 3, 4, 5, 6, 7];
let row_end_indices = V.d1().fun(|[i]| 4 * (i + 1)).bounded(2);
let vec = flat_vec.as_jagged(&row_end_indices);
assert!(vec.is_rectangular());
let vec = V.d2().fun(|[i, j]| i + j).with_rectangular_bounds([4, 2]);
assert!(vec.is_rectangular());And below are examples for the non-rectangular or jagged vectors.
use orx_v::*;
let lengths = vec![3, 2, 3];
let vec = V.d2().constant(42).with_variable_bounds(lengths);
assert!(!vec.is_rectangular());
let vec = vec![
vec![1, 2, 3],
vec![4, 5, 6, 7],
];
assert!(!vec.is_rectangular());
let vec = vec![
vec![
vec![1, 2, 3],
],
vec![
vec![4, 5, 6, 7],
],
];
assert!(!vec.is_rectangular());
let vec = vec![
vec![
vec![1, 2, 3],
],
vec![
vec![4, 5, 6],
vec![7, 8, 9],
],
];
assert!(!vec.is_rectangular());
let flat_vec = vec![0, 1, 2, 3, 4, 5, 6, 7];
let row_end_indices = vec![2, 5, 8];
let vec = flat_vec.as_jagged(&row_end_indices);
assert!(!vec.is_rectangular());
let card = vec![3, 2, 3];
let vec = V.d2().fun(|[i, j]| i + j).with_variable_bounds(card);
assert!(!vec.is_rectangular());Sourcefn is_unbounded(&self) -> bool
fn is_unbounded(&self) -> bool
Returns whether or not the vector is unbounded.
The following are examples for unbounded vectors:
ConstantVec=>V.d1().constant(42)SparseVec=>V.d2().sparse(42)FunVec=>V.d2().fun(|[i, j]| i + 42 * j)
Finite domain of these vectors can be set by calling:
boundedforD1vectors,with_rectangular_boundsorwith_variable_boundsfor higher dimensional vectors.
§Example
use orx_v::*;
let v2 = vec![
vec![0, 1],
vec![],
vec![2],
];
assert!(v2.is_bounded());
let v1: &[usize] = v2[0].as_slice();
assert!(v1.is_bounded());
// constant
let v1 = V.d1().constant(42);
assert!(v1.is_unbounded());
let v1 = V.d1().constant(42).bounded(10);
assert!(v1.is_bounded());
// sparse
let mut v2 = V.d2().sparse(0);
*v2.at_mut([0, 2]) = 42;
assert!(v2.is_unbounded());
let mut v2 = V.d2().sparse(0).with_rectangular_bounds([2, 3]);
*v2.at_mut([0, 2]) = 42;
assert!(v2.is_bounded());
// fun
let v2 = V.d2().fun(|[i, j]| 10 * i + j);
assert!(v2.is_unbounded());
let num_cols = [1, 0, 2, 1];
let v2 = V.d2().fun(|[i, j]| 10 * i + j).with_variable_bounds(&num_cols);
assert!(v2.is_bounded());Sourcefn in_bounds(&self, idx: impl Into<D::LeqIdx>) -> bool
fn in_bounds(&self, idx: impl Into<D::LeqIdx>) -> bool
Returns whether or not the given idx is in bounds.
Note that the index can be the same dimension as the vector or any of the lower dimensions.
§Examples
use orx_v::*;
let vec = vec![
vec![1, 2, 3],
vec![4]
];
// d2
assert_eq!(vec.in_bounds([0, 2]), true); // element 3
assert_eq!(vec.in_bounds([1, 0]), true); // element 4
assert_eq!(vec.in_bounds([1, 1]), false); // X
assert_eq!(vec.in_bounds([2, 0]), false); // X
// d1
assert_eq!(vec.in_bounds([0]), true); // V1 [1, 2, 3]
assert_eq!(vec.in_bounds([1]), true); // V1 [4]
assert_eq!(vec.in_bounds([2]), false); // X
// d0
assert_eq!(vec.in_bounds([]), true); // V2 [[1, 2, 3], [4]]Sourcefn card_equality(&self, other: &impl NVec<D, T>) -> CardEquality<D>
fn card_equality(&self, other: &impl NVec<D, T>) -> CardEquality<D>
Returns the cardinality equality of this vec with the other:
- Returns
CardEquality::Equaliff the cardinality of the structures and all their corresponding children have equal cardinalities. - Returns
CardEquality::Unequalif cardinalities do not agree at at least one level. The tuple(idx, card1, card2)represents the following:idxis the place the inequality in cardinalities are observed;card1andcard2are the unequal cardinalities at the givenidxin the first and second vectors, respectively.
§Examples
use orx_v::*;
let a = vec![
vec![0, 1, 2],
vec![3, 4, 5, 6],
];
let b1 = vec![
vec![7, 0, 3],
vec![5, 2, 9, 5],
];
let b2 = vec![
vec![7, 0, 3],
vec![5, 2, 9, 5, 42],
];
let b3 = vec![
vec![7, 0, 3],
vec![5, 2, 9, 5],
vec![],
];
// cardinalities are equal
assert_eq!(a.card_equality(&b1), CardEquality::Equal);
// cardinalities of the 1-st-level children with index 1
// (`a.child(1)`) are different (4 != 5)
assert_eq!(
a.card_equality(&b2),
CardEquality::Unequal(IdxLeqD1::IdxD1([1]), 4, 5)
);
// outer-most cardinalities are different (2 != 3)
assert_eq!(
a.card_equality(&b3),
CardEquality::Unequal(IdxLeqD1::IdxD0([]), 2, 3)
);Sourcefn try_at(&self, idx: impl IntoIdx<D>) -> Option<T>
fn try_at(&self, idx: impl IntoIdx<D>) -> Option<T>
Returns the element at the idx-th position of the vector if the
index is in_bounds; returns None otherwise.
§Examples
use orx_v::*;
let vec = vec![
vec![0, 1, 2],
vec![3],
vec![4, 5],
];
assert_eq!(vec.try_at([0, 1]), Some(1));
assert_eq!(vec.try_at([1, 0]), Some(3));
assert_eq!(vec.try_at([2, 1]), Some(5));
// vec.at([1, 1]); // panics!
assert_eq!(vec.try_at([1, 1]), None);Sourcefn equality(&self, other: &impl NVec<D, T>) -> Equality<D>where
T: PartialEq,
fn equality(&self, other: &impl NVec<D, T>) -> Equality<D>where
T: PartialEq,
Returns the equality of this vec with the other:
- Returns
Equality::Equaliff the cardinality of the structures as well as all values at corresponding positions are equal. - Returns
Equality::UnequalCardif cardinalities do not agree at at least one level. The tuple(idx, card1, card2)represents the following:idxis the place the inequality in cardinalities are observed;card1andcard2are the unequal cardinalities at the givenidxin the first and second vectors, respectively.
- Returns
Equality::UnequalValueif any of the values are different. The(idx)represents the index where the value inequality is observed.
§Examples
use orx_v::*;
let a = vec![
vec![0, 1, 2],
vec![3, 4, 5, 6],
];
let b1 = vec![
vec![0, 1, 2],
vec![3, 4, 5, 6],
];
let b2 = vec![
vec![0, 1, 2],
vec![3, 4, 42, 6],
];
let b3 = vec![
vec![0, 1, 2],
vec![3, 4, 5, 6, 42],
];
let b4 = vec![
vec![0, 1, 2],
vec![3, 4, 5, 6],
vec![42],
];
// vectors are equal
assert_eq!(a.equality(&b1), Equality::Equal);
// values at [1, 2] are different
assert_eq!(a.equality(&b2), Equality::UnequalValue([1, 2]));
// cardinalities of the 1-st-level children with index 1
// (`a.child(1)`) are different (3 != 4)
assert_eq!(
a.equality(&b3),
Equality::UnequalCard(IdxLeqD1::IdxD1([1]), 4, 5)
);
// outer-most cardinalities are different (2 != 3)
assert_eq!(
a.equality(&b4),
Equality::UnequalCard(IdxLeqD1::IdxD0([]), 2, 3)
);Sourcefn children(&self) -> impl Iterator<Item = impl NVec<D::PrevDim, T>>
fn children(&self) -> impl Iterator<Item = impl NVec<D::PrevDim, T>>
Returns an iterator of all children of the vector.
Note that child has a dimension that is one less than the dimension of this vector.
use orx_v::*;
// D2
let vec = vec![
vec![0, 1, 2],
vec![3],
vec![4, 5],
];
let mut children = vec.children();
assert_eq!(children.next().unwrap().equality(&[0, 1, 2]), Equality::Equal);
assert_eq!(children.next().unwrap().equality(&[3]), Equality::Equal);
assert_eq!(children.next().unwrap().equality(&[4, 5]), Equality::Equal);
assert!(children.next().is_none());Sourcefn all_in(
&self,
indices: impl Iterator<Item = impl IntoIdx<D>>,
) -> impl Iterator<Item = T>
fn all_in( &self, indices: impl Iterator<Item = impl IntoIdx<D>>, ) -> impl Iterator<Item = T>
Returns an iterator of elements for the given indices.
This method is useful especially when the vector is_unbounded and we would
like to iterate only over the given indices.
§Panics
Panics if any of the indices that indices iterator yields is out of bounds.
§Examples
use orx_v::*;
let vec = V.d1().constant(42);
assert!(vec.is_unbounded());
let mut all = vec.all_in(0..3);
assert_eq!(all.next(), Some(42));
assert_eq!(all.next(), Some(42));
assert_eq!(all.next(), Some(42));
assert_eq!(all.next(), None);
let vec = vec![
vec![0, 1],
vec![],
vec![2],
];
let mut all = vec.all_in([[0, 1], [2, 0]].into_iter());
assert_eq!(all.next(), Some(1));
assert_eq!(all.next(), Some(2));
assert_eq!(all.next(), None);Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.