Is it possible to have a binary heap containing different structs in Rust?

user_14838594 0
Viewed 174

I'm working on an event-driven particle simulation. The code below defines the struct Event and implements the equality traits that are needed for a binary heap. This code is working but the object event built by the second constructor (new_event) has redundant member variables. I want to have a binary heap which works with two different event structs in order to avoid this redundancy and improve my code efficiency which is crucial for my project. Can I achieve this using traits?

pub struct Event
{
    pub time: f64,
    pub event_type: EventType,
    pub particle_index1: usize,
    pub particle_index2: usize,
    pub particle_count1: usize,
    pub particle_count2: usize
}

impl Event
{
    pub fn new_collision(time: f64, particle_index1: usize, particle_index2: usize, 
        particle_count1: usize, particle_count2: usize) -> Self
    {

        Self {
            time,
            particle_index1,
            particle_index2,
            event_type: EventType::EventCollision,
            particle_count1,
            particle_count2
        }
    }

    pub fn new_event(time: f64, event_type: EventType, particle_index1: usize, particle_count1: 
        usize) -> Self
    {
        Self {
            time,
            particle_index1,
            particle_index2: 0, //REDUNDANT
            event_type,
            particle_count1,
            particle_count2: 0  //REDUNDANT
        }
    }
}

impl PartialEq for Event
{
    fn eq(&self, other: &Self) -> bool
    {
        self.time == other.time
    }
}

impl Eq for Event{}

impl PartialOrd for Event
{
    fn partial_cmp(&self, other: &Self) -> Option<Ordering>
    {
        other.time.partial_cmp(&self.time) //reverse order
    }
}

impl Ord for Event
{
    fn cmp(&self, other: &Self) -> Ordering
    {
        self.partial_cmp(other).unwrap()
    }
}
rust binary-heap traits
2 Answers

In this case it would be interesting to use an enum and a combination with a custom trait to avoid cumbersome access to inner enum structs:


use core::cmp::Ordering;
type EventType = String;

trait Timed {
    fn time(&self) -> f64;
}

pub struct CollisionEvent {
    pub time: f64,
    pub particle_index1: usize,
    pub particle_index2: usize,
    pub particle_count1: usize,
    pub particle_count2: usize,
}

pub struct GenericEvent {
    pub time: f64,
    pub event_type: EventType,
    pub particle_index1: usize,
    pub particle_count1: usize,
}

pub enum Event {
    Collision(CollisionEvent),
    Generic(GenericEvent),
}

impl Timed for CollisionEvent {
    fn time(&self) -> f64 {
        self.time
    }
}

impl Timed for GenericEvent {
    fn time(&self) -> f64 {
        self.time
    }
}

impl Timed for Event {
    fn time(&self) -> f64 {
        let event: &dyn Timed = match self {
            Event::Collision(event) => event,
            Event::Generic(event) => event,
        };
        event.time()
    }
}

impl Event {
    pub fn new_collision(
        time: f64,
        particle_index1: usize,
        particle_index2: usize,
        particle_count1: usize,
        particle_count2: usize,
    ) -> Self {
        Self::Collision(CollisionEvent {
            time,
            particle_index1,
            particle_index2,
            particle_count1,
            particle_count2,
        })
    }

    pub fn new_event(
        time: f64,
        event_type: EventType,
        particle_index1: usize,
        particle_count1: usize,
    ) -> Self {
        Self::Generic(GenericEvent {
            time,
            particle_index1,
            event_type,
            particle_count1,
        })
    }
}

impl PartialEq for Event {
    fn eq(&self, other: &Self) -> bool {
        self.time() == other.time()
    }
}

impl Eq for Event {}

impl PartialOrd for Event {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        other.time().partial_cmp(&self.time()) //reverse order
    }
}

impl Ord for Event {
    fn cmp(&self, other: &Self) -> Ordering {
        self.partial_cmp(other).unwrap()
    }
}

Playground

user_16951720

It is possible with enums to have a create a data type which can represent multiple "types".

So you could do something like:

pub struct Event {
    pub time: f64,
    pub event_type: EventType,
    pub particle_index1: usize,
    pub particle_count1: usize,
}

pub struct Collison {
    pub time: f64,
    pub event_type: EventType,
    pub particle_index1: usize,
    pub particle_index2: usize,
    pub particle_count1: usize,
    pub particle_count2: usize
}

pub enum EventOrCollision {
    Event(Event),
    Collision(Collision)
}

So you could now have a BinaryHeap<EventOrCollision>>. However the EventOrCollision would have to implement PartialOrd and the other type constraints on BinaryHeap. You would need to use pattern matching around this type.

However Rust enums are constant width/size (+1 for the discriminant bit) so the binary heap would take up the same space in memory as you have currently. You would avoid initializing the extra usize fields although that is incredible cheap.

user_100487990
Related