Struct hilbert::normalize::IntegerDataRange

pub struct IntegerDataRange {
    pub low: i64,
    pub high: i64,
    pub bits_required: usize,
}

Holds the observed range of values seen in a set of points whose coordinates are 32-bit integers (signed or unsigned).

From this information we can determine how to translate the coordinates so that their normalized range has a low of zero. This permits us to use the fewest number of bits to represent them when constructing a Hilbert index.

• Use the normalize method to adjust a coordinate value into range such that the full precision of the number is preserved.
• Use the compress method to both normalize and shrink the coordinate value, to reduce the number of bits used per coordinate, at the expense of less precision.

Motivation.

1. The Hilbert Curve transformation requires non-negative numbers, so all values must be translated until the lowest is zero. That means that if the lowest value is negative, we shift to the positive direction, or contrariwise to the negative direction.
2. The execution time of the Hilbert transformation is directly proportional to the number of bits used to represent each value. Thus if we can sacrifice some precision, each value can be right-shifted by the same number of bits if we wish to compress the range.

Fields

low: i64

Lowest value of any coordinate of any point in a collection of points.

high: i64

Highest value of any coordinate of any point in a collection of points.

bits_required: usize

Minimum number of bits required to represent a normalized value without loss of information.

Examples:

• If low is -10 and high is 24 then the range is 34 so 6 bits are required to represent all values in that range.
• If low is 50 and high is 67 then the range is 17 so 5 bits are required to represent all values in that range.

Methods

impl IntegerDataRange

pub fn new<I>(low_i: I, high_i: I) -> Self where
    I: Into<i64>, 

Create an IntegerDataRange without reference to particular data.

pub fn from_i32<I>(points: &[I]) -> Self where
    &'a I: IntoIterator<Item = &'a i32>, 

Study all i32 coordinates in all points to find the minimum and maximum values.

pub fn from_u32<I>(points: &[I]) -> Self where
    &'a I: IntoIterator<Item = &'a u32>, 

Study all u32 coordinates in all points to find the minimum and maximum values.

pub fn range(&self) -> u32

Range from low to high value.

pub fn normalize<I>(&self, coordinate: I) -> u32 where
    I: Into<i64>, 

Normalize an integer convertible to an i64, shifting it enough so that the minimum value found in any point is shifted to zero and the maximum value is shifted to range, and using the full number of bits required for the range.

pub fn compress<I>(&self, coordinate: I, bits_allocated: usize) -> u32 where
    I: Into<i64>, 

Normalize a coordinate value, shifting it enough so that the minimum value found in any point is shifted to zero and the maximum value is shifted to range, then optionally compressing the range by bit shifting such that no more than the given number of bits are required for the largest value.

Trait Implementations

impl Clone for IntegerDataRange

fn clone(&self) -> IntegerDataRange

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl PartialEq<IntegerDataRange> for IntegerDataRange

fn eq(&self, other: &IntegerDataRange) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &IntegerDataRange) -> bool

This method tests for !=.

impl Debug for IntegerDataRange

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl StructuralPartialEq for IntegerDataRange