是否有可能在 Rust 中有一个包含不同结构的二进制堆？

Question

我正在研究事件驱动的粒子模拟。下面的代码定义了 struct Event 并实现了二叉堆所需的相等性特征。此代码有效，但第二个构造函数 (new_event) 构建的对象事件具有冗余成员变量。我想要一个二进制堆，它与两个不同的事件结构一起工作，以避免这种冗余并提高我的代码效率，这对我的项目至关重要。我可以使用特征来实现吗？

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

Answer 1

在这种情况下，使用 enum 以及与自定义特征的组合以避免对内部枚举结构的繁琐访问会很有趣：


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

Answer 2

使用 enums 可以创建一个可以表示多个“类型”的数据类型。

所以你可以这样做：

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

所以您现在可以拥有 BinaryHeap<EventOrCollision>>。然而 EventOrCollision 必须在 BinaryHeap 上实现 PartialOrd 和其他类型约束。您需要围绕此类型使用 pattern matching。

但是 Rust 枚举是常量 width/size（判别位为 +1），因此二进制堆将占用与当前相同的 space 内存。你会避免初始化额外的 usize 字段，尽管这非常便宜。

是否有可能在 Rust 中有一个包含不同结构的二进制堆？

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

traits

binary-heap

rust