CODEWITHSUNDEEP
rusttraitsbinary-heap
Andrea
Andrea

Reputation: 23

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

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()
    }
}

Upvotes: 2

Views: 674

Answers (2)

Netwave
Netwave

Reputation: 42718

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

Upvotes: 2

Ben
Ben

Reputation: 3654

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.

Upvotes: 2

Related Questions