Simplify split function

[kdheepak]

Further simplification of try_split by removing the area element and constraints for that, and using the start and end values directly.

[joshka]

General approval of this change with suggestions that are non blocking.

I think if we're going to do this, then what about if we go one step further and remove Element altogether?

The only variables that we care about are the end of each chunk (as the start is required to be strictly equal to the previous chunk).

I think there's probably even a simple approach where the start and end of the area don't really need to be treated any differently than the start / end of a chunk (using an Vec of the positions and .window(2) to setup every constraint).

A quick and dirty check of this suggests that we delete 18-24 lines of code in the diff

[joshka]

Note - this doesn't have #408 included yet (just merged that)

[codecov]

Codecov Report

Merging #411 (2247ed7) into main (56455e0) will decrease coverage by 0.01%.
The diff coverage is 100.00%.

@@            Coverage Diff             @@
##             main     #411      +/-   ##
==========================================
- Coverage   86.13%   86.13%   -0.01%     
==========================================
  Files          40       40              
  Lines        9240     9239       -1     
==========================================
- Hits         7959     7958       -1     
  Misses       1281     1281              

Files Changed	Coverage Δ
src/layout.rs	96.27% <100.00%> (-0.01%)	⬇️

[kdheepak]

I think if we're going to do this, then what about if we go one step further and remove Element altogether?

The only variables that we care about are the end of each chunk (as the start is required to be strictly equal to the previous chunk).

I think there's probably even a simple approach where the start and end of the area don't really need to be treated any differently than the start / end of a chunk (using an Vec of the positions and .window(2) to setup every constraint).

I'm not sure if I'm following this suggestion. We'll always need two decision variables for each chunk, e.g. start and end OR start and length, right? Maybe I'm just being slow this morning, can you can elaborate further?

Also for consideration, we might want to add this constraint in the future:

    for i in 0..elements.len() {
        for j in (i + 1)..elements.len() {
            solver.add_constraint(elements[j].size() | EQ(WEAK) | (elements[i].size()))?;
        }
    }

Regardless of a possible simplification, I do like that Element is a struct with a size() method that returns an Expression. I think it is pretty clean and the problem set up here maps closely to how I think of the optimization problem and the math.

[kdheepak]

I'm going to go ahead and merge this for now, because I'm not sure how much time I'll have in front of a computer over the weekend. I'm happy to follow up on the further simplification in a separate PR.

[joshka]

I'm not sure if I'm following this suggestion. We'll always need two decision variables for each chunk, e.g. start and end OR start and length, right? Maybe I'm just being slow this morning, can you can elaborate further?

If you have: area = [0..=10], and constraints = [Length(3), Length(4), Length(5)], and setup an array of variables positions = [area_start, end[0], end[1], end[2]], then the constraints can be applied to positions.window(2). There's no need to have variables for start[0..2] as those just strictly equal [area_start, end[0], end[1]] and the size of each is just position[n] - position[n-1].

    let (area_start, area_end, area_size) = match layout.direction {
        Direction::Horizontal => (
            f64::from(inner.left()),
            f64::from(inner.right()),
            f64::from(inner.width),
        ),
        Direction::Vertical => (
            f64::from(inner.top()),
            f64::from(inner.bottom()),
            f64::from(inner.height),
        ),
    };
    // the positions of each chunk. The first variable is the start, and each successive variable is
    // the end of that chunk and the start of the next one
    let positions = std::iter::from_fn(|| Some(Variable::new()))
        .take(layout.constraints.len() + 1)
        .collect_vec();

    // ensure the first element is at the start
    solver.add_constraint(positions[0] | EQ(REQUIRED) | area_start)?;

    // ensure the positions are monotonically increasing
    for &position in positions.iter() {
        solver.add_constraints(&[
            position | GE(REQUIRED) | area_start,
            position | LE(REQUIRED) | area_end,
        ])?;
    }

    // ensure the last element touches the right/bottom edge of the area
    if layout.expand_to_fill {
        if let Some(&last) = positions.last() {
            solver.add_constraint(last | EQ(REQUIRED) | area_end)?;
        }
    }

    let sizes = positions
        .iter()
        .tuple_windows()
        .map(|(&start, &end)| end - start)
        .collect_vec();

    // apply the constraints
    for (size, &constraint) in sizes.iter().cloned().zip(layout.constraints.iter()) {
        solver.add_constraint(size.clone() | GE(REQUIRED) | 0.0)?;
        match constraint {
            Constraint::Percentage(p) => {
                let percent = f64::from(p) / 100.00;
                solver.add_constraint(size | EQ(STRONG) | (area_size * percent))?;
            }
            Constraint::Ratio(n, d) => {
                // avoid division by zero by using 1 when denominator is 0
                let ratio = f64::from(n) / f64::from(d.max(1));
                solver.add_constraint(size | EQ(STRONG) | (area_size * ratio))?;
            }
            Constraint::Length(l) => solver.add_constraint(size | EQ(STRONG) | f64::from(l))?,
            Constraint::Max(m) => {
                solver.add_constraints(&[
                    size.clone() | LE(STRONG) | f64::from(m),
                    size | EQ(WEAK) | f64::from(m),
                ])?;
            }
            Constraint::Min(m) => {
                solver.add_constraints(&[
                    size.clone() | GE(STRONG) | f64::from(m),
                    size | EQ(WEAK) | f64::from(m),
                ])?;
            }
        }
    }

Also for consideration, we might want to add this constraint in the future (equal sizes):

This can be written as:

for (left, right) in sizes.iter().tuple_window() {
  solver.add_constraint(left | EQ(WEAK) | right)?;
}

It's probably not necessary to add all the comparisons as [a=b, b=c] implies [a=c]. I'm not sure what the constraint solver does though for constraints that can't be satisfied.

[kdheepak]

Okay, that makes sense. Thanks for explaining and the code examples. I do find it more confusing to read though, but maybe I should think about it more.

It's probably not necessary to add all the comparisons as [a=b, b=c] implies [a=c]. I'm not sure what the constraint solver does though for constraints that can't be satisfied.

I think it is necessary to add all combinations because you can have one of the chunks be smaller because of a higher priority constraint. For example take a case like [Percentage(50), Length(10), Percentage(50)], we want b to be close to 10 units but the rest to be spread equally between the Percentage(50)s. I haven't tested this case specifically but I can imagine corner cases like this popping up.

[joshka]

You're right. I tried that and found that I was wrong. Your explanation of why makes a lot of sense - I couldn't quite get there. I replaced tuple_window() with tuple_combinations() and works well.

Percentage shouldn't grow / shrink any more than length should, as it's based on a percentage of the total not a percentage of the amount after length is taken out. 50%/10/50% should render (these would be good tests in the other PR):

• size = 10: 5/10/5 => [2.5, 7.5, 2.5] => [3, 5, 2]
• size = 20: 10/10/10 => [6.67, 6.67, 6.67] => [7, 6, 7]
• size = 40: 20/10/20 => [16, 8, 16]
• size = 100: 50/10/50 => [45.4, 9.1, 45.4] => [45, 10, 45]

I do find it more confusing to read though, but maybe I should think about it more.

I thought the same when I initially read it from the perspective of coming from thinking in terms of Elements with start / end / size. Perhaps it needs a small diagram to make the algorithm clear? E.g.:

positions: [start  end0  end1  end2 ]
positions: [ 0.0   1.0   3.0   10.0 ]
sizes:     [    1.0   2.0   7.0     ]
sizes:     [   size0 size1 size2    ]

[kdheepak]

A diagram like this certainly helps:

positions: [start  end0  end1  end2 ]
positions: [ 0.0   1.0   3.0   10.0 ]
sizes:     [    1.0   2.0   7.0     ]
sizes:     [   size0 size1 size2    ]

I'm not convinced it is worth it for the extra simplification in this case. If we really wanted to remove Element we could create start and end variables in the function.

But I do like the way it is written right now with Element and with element.size() returning an Expression. It makes it very easy for me at a glance to understand exactly what is going on.