Info
Disclaimer: I'm not a professional programmer, so apologies in advance if I misuse terms of art.
The gist of this little component of a program I'm writing is as follows: I have a structure which maintains some data corresponding to points in a fixed grid, along with a queue of “commands” which instruct it to do certain operations on those data. Each “command” can be of several flavors—corresponding to various different operations on the data—and specifies one of several shapes, which determine particular subsets of points in the grid on which the given operation is to be performed.
Here’s a version of the code that I believe captures all of the important functionality:
use std::{
fmt::{self, Display, Formatter},
mem,
ops::{Add, AddAssign},
collections::VecDeque,
};
// ---------- Individual grid points ----------
#[derive(Debug, Copy, Clone)]
pub struct Point { x: u32, y: u32, }
impl Display for Point {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
write!(f, "({}, {})", self.x, self.y)
}
}
impl Add for Point {
type Output = Self;
fn add(self, other: Self) -> Self {
Self {
x: self.x + other.x,
y: self.y + other.y,
}
}
}
impl AddAssign for Point {
fn add_assign(&mut self, other: Self) {
*self = Self {
x: self.x + other.x,
y: self.y + other.y,
}
}
}
// ---------- Shapes ----------
// Generic newtype for shapes
#[derive(Debug, Copy, Clone)]
struct Shape<S>(S);
impl<S: Display> Display for Shape<S> {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
write!(f, "{}", self.0)
}
}
#[derive(Debug, Copy, Clone)]
struct Triangle { origin: Point, side_len: u32 }
impl Display for Triangle {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
write!(f, "triangle at {} with side length {}", self.origin, self.side_len)
}
}
#[derive(Debug, Copy, Clone)]
struct Rect { origin: Point, width: u32, height: u32 }
impl Display for Rect {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
write!(f, "rectangle at {} with width {} and height {}", self.origin, self.width, self.height)
}
}
// Monomorphizer for shapes
#[derive(Debug, Copy, Clone)]
enum Shapes { Triangle(Shape<Triangle>), Rect(Shape<Rect>) }
impl Shapes {
fn triangle(origin: Point, side_len: u32) -> Self {
Shapes::Triangle( Shape(
Triangle { origin, side_len }
) )
}
fn rect(origin: Point, width: u32, height: u32) -> Self {
Shapes::Rect( Shape(
Rect { origin, width, height }
) )
}
}
// Used to get the "first point" in a shape when constructing an iterator
trait Origin {
fn origin(&self) -> Point;
fn set_origin(&mut self, new_origin: Point);
}
// delegating origin to inner shape
impl<S: Origin> Origin for Shape<S> {
fn origin(&self) -> Point {
self.0.origin()
}
fn set_origin(&mut self, new_origin: Point) {
self.0.set_origin(new_origin);
}
}
impl<S: Origin> AddAssign<Point> for Shape<S> {
fn add_assign(&mut self, other: Point) {
self.set_origin(self.origin() + other);
}
}
// ---------- Iterating over points in a shape ----------
// The core of iteration over a shape: knowing how to get the next point
trait PointIncr {
fn succ(&self, point: &Point) -> Option<Point>;
}
// An actual iterator over points in a shape simply needs to know the shape
// and track a single point in that shape
pub struct PointIterator<S> {
shape: S,
next_point: Option<Point>
}
impl<S: PointIncr> Iterator for PointIterator<S> {
type Item = Point;
fn next(&mut self) -> Option<Point> {
let nextnext = self.shape.succ(&self.next_point?);
mem::replace(&mut self.next_point, nextnext)
}
}
impl<S: PointIncr + Origin> IntoIterator for Shape<S> {
type Item = Point;
type IntoIter = PointIterator<S>;
fn into_iter(self) -> PointIterator<S> {
PointIterator {
next_point: Some( self.0.origin() ),
shape: self.0,
}
}
}
impl Origin for Triangle {
fn origin(&self) -> Point {
self.origin
}
fn set_origin(&mut self, new_origin: Point) {
self.origin = new_origin;
}
}
impl PointIncr for Triangle {
fn succ(&self, point: &Point) -> Option<Point> {
if point.x + point.y + 1 < self.origin.x + self.origin.y + self.side_len {
Some(Point {
x: point.x + 1,
y: point.y,
})
} else if point.y + 1 < self.origin.y + self.side_len {
Some(Point {
x: self.origin.x,
y: point.y + 1,
})
} else {
None
}
}
}
impl Origin for Rect {
fn origin(&self) -> Point {
self.origin
}
fn set_origin(&mut self, new_origin: Point) {
self.origin = new_origin;
}
}
impl PointIncr for Rect {
fn succ(&self, point: &Point) -> Option<Point> {
if point.x + 1 < self.origin.x + self.width {
Some( Point {
x: point.x + 1,
y: point.y
})
} else if point.y + 1 < self.origin.y + self.height {
Some( Point {
x: self.origin.x,
y: point.y + 1
})
} else {
None
}
}
}
// ---------- Commands that can be queued in the "command-processor" ----------
#[derive(Debug, Copy, Clone)]
enum ProcessShape {
CommandA(Shapes),
CommandB(Shapes)
}
impl ProcessShape {
fn triangle_cmd_A(origin: Point, side_len: u32) -> Self {
ProcessShape::CommandA(
Shapes::triangle(origin, side_len)
)
}
fn rect_cmd_A(origin: Point, width: u32, height: u32) -> Self {
ProcessShape::CommandA(
Shapes::rect(origin, width, height)
)
}
fn triangle_cmd_B(origin: Point, side_len: u32) -> Self {
ProcessShape::CommandB(
Shapes::triangle(origin, side_len)
)
}
fn rect_cmd_B(origin: Point, width: u32, height: u32) -> Self {
ProcessShape::CommandB(
Shapes::rect(origin, width, height)
)
}
}
// ---------- The "command-processor" ----------
#[derive(Debug, Copy, Clone)]
struct PointData;
struct GridProcessor {
shape: Shape<Rect>,
grid_data: Vec<PointData>,
processing_queue: VecDeque<ProcessShape>,
}
impl GridProcessor {
fn new(width: u32, height: u32) -> Self {
Self {
shape: Shape( Rect {
origin: Point { x: 0, y: 0 },
width,
height
} ),
grid_data: vec![PointData; (width as usize) * (height as usize)],
processing_queue: VecDeque::<ProcessShape>::new(),
}
}
#[inline]
fn queue_command(&mut self, command: ProcessShape) {
self.processing_queue.push_back(command);
}
fn process_queued_commands(&mut self) {
let commands: VecDeque<_> = self.processing_queue.drain(..).collect();
for cmd in commands {
match cmd {
ProcessShape::CommandA(shape) => self.dispatch_command_A(shape),
ProcessShape::CommandB(shape) => self.dispatch_command_B(shape),
}
}
}
fn dispatch_command_A(&mut self, shape: Shapes) {
match shape {
Shapes::Triangle(triangle) => self.process_command_A(triangle),
Shapes::Rect(rect) => self.process_command_A(rect)
}
}
fn dispatch_command_B(&mut self, shape: Shapes) {
match shape {
Shapes::Triangle(triangle) => self.process_command_B(triangle),
Shapes::Rect(rect) => self.process_command_B(rect)
}
}
fn process_command_A<S: PointIncr + Origin + Display + Copy>(&mut self, shape: Shape<S>) {
for point in shape {
println!("Executing command A at coordinates {} in a {}.", point, shape);
}
}
fn process_command_B<S: PointIncr + Origin + Display + Copy>(&mut self, shape: Shape<S>) {
for point in shape {
println!("Executing command B at coordinates {} in a {}.", point, shape);
}
}
}
fn main() {
let mut grid_processor = GridProcessor::new(10, 10);
let pt1 = Point { x: 2, y: 1 };
let pt2 = Point { x: 1, y: 3 };
let cmd1 = ProcessShape::rect_cmd_A(pt1, 2, 3);
grid_processor.queue_command(cmd1);
let cmd2 = ProcessShape::triangle_cmd_B(pt2, 3);
grid_processor.queue_command(cmd2);
grid_processor.process_queued_commands();
}
It should be noted that there are a few things in there which aren’t really “used” but are left as placeholders to give a sense of some of the other components of the program whose precise details I don’t think are relevant here. The main() function at the bottom is just to confirm that the logic all works as desired.
In my implementation, I am trying to satisfy the following constraints (I’m reasonably confident these are the only important ones for this post):
Iterator should also not involve branching on the shape type in each call to next().The traits Origin and PointIncr, together with the generic implementations of Iterator for PointIterator<S> and IntoIterator for Shape<S>, are my attempt to satisfy (1)-(3) – these things, together, reduce the implementation of iteration over points in any specific shape to merely specifying an initial point (i.e. implementing Origin) and a successor function on points in that shape (i.e. implmenting PointIncr). To satisfy (3), it is necessary that the signature of the IntoIter type associated to a shape actually depend on the type of shape (as opposed to having a single shape-insensitive iterator type which stores a variant in a shape enum and branches on that variant in every next call). However, the orphan rules force me (as far as I can tell) to use a newtype wrapper Shape<S> for all the shapes in order to actually implement IntoIterator generically.
On the other hand, in order to be able to queue arbitrary commands together, I have to use a monomorphizer for the shapes (the Shapes enum), which means I’m ultimately stuck (unless there’s a nicer design pattern I’m unaware of) with two layers of indirection just for shapes themselves.
One other small wrinkle: in the process_queued_commands function, I found that I was forced to drain the queue into a separate one in order to be able to iterate over it, since the actual process_command_X functions (where X is A or B) will, in reality, alter the data in self.grid_data, and thus requires a mutable borrow on self (which would be impossible if I were just iterating directly over self.processing_queue.drain(..) directly). My understanding is that what the borrowing rules are theoretically guarding against here is a scenario where e.g. the process_command_X actually modify self.processing_queue, since that is already borrowed in the loop over self.processing_queue.drain(..). Of course, my implementation of those functions will never do that, but I’m not sure how to design things in a way that actually expresses that fact so that the borrow checker is happy. I’m guessing this particular quandary is probably one of the more common ones and probably has at least one fairly standard resolution, but I’m not sure what that is.
Thanks in advance for any feedback!
3 posts - 2 participants
🏷️ Rust_feed