Q: Any ideas for this algorithm???

[Somebody]

I have the following:

struct A
{
int left;
int top;
int right;
int bottom;
};

Thats a rectangle. I have an array of rectangles... say ARR[nCount]... Now,
I've got these elements laid out in rows (not important how), but this
struct has no concept of which row its in...

I'm trying to make every rect in a row equal to the size of the max height
rectangle for that row... I can't seem to come up with a working
algorithm... maybe cuz its late... but my general concept is to first detect
when a new row is hit:

int y = 0;

for (int i = 0; i < nCount; i++)
{
if (ARR.top != y)
{
// NEW ROW
y = ARR.top;
}
else
{
}
}

problem with this right away is that it doesn't hit the NEW ROW part for all
the rectangles... namely the last one... so thats not included in the max
measurement.

any suggestions on how to proceed?

 

[Kai-Uwe Bux]

I have the following:

struct A
{
int left;
int top;
int right;
int bottom;
};

Thats a rectangle. I have an array of rectangles... say ARR[nCount]...
Now, I've got these elements laid out in rows (not important how), but
this struct has no concept of which row its in...

I'm trying to make every rect in a row equal to the size of the max height
rectangle for that row... I can't seem to come up with a working
algorithm... maybe cuz its late... but my general concept is to first
detect when a new row is hit:

int y = 0;

for (int i = 0; i < nCount; i++)
{
if (ARR.top != y)
{
// NEW ROW
y = ARR.top;
}
else
{
}
}

problem with this right away is that it doesn't hit the NEW ROW part for
all the rectangles... namely the last one... so thats not included in the
max measurement.

any suggestions on how to proceed?

Write a comparison functor that ranks rectangles according to their top,
something like:

bool is_higher ( A const & lhs, A const & rhs ) {
return ( lhs.top < rhs.top );
}

Now, you can use std::lower_bound, std::upper_bound, and std::equal_range to
find ranges of rectangles of equal hight in a sequence, provided the
sequence is sorted. Finally, you can operate on those ranges and meddle
with the bottom field at will.


Best

Kai-Uwe Bux

 

[John Harrison]

I have the following:

struct A
{
int left;
int top;
int right;
int bottom;
};

Thats a rectangle. I have an array of rectangles... say ARR[nCount]... Now,
I've got these elements laid out in rows (not important how),

I would say that is important. It seems like the essense of the problem
to me.


but this

struct has no concept of which row its in...

Quite right. So you need something external to the rect which holds
which row a rect is in. Which is why knowing how you've split up the
rects into rows is important, as I said above.

I'm trying to make every rect in a row equal to the size of the max height
rectangle for that row... I can't seem to come up with a working
algorithm... maybe cuz its late... but my general concept is to first detect
when a new row is hit:

int y = 0;

for (int i = 0; i < nCount; i++)
{
if (ARR.top != y)
{
// NEW ROW
y = ARR.top;
}
else
{
}
}

problem with this right away is that it doesn't hit the NEW ROW part for all
the rectangles... namely the last one... so thats not included in the max
measurement.

any suggestions on how to proceed?

So it seems you have all the rects in order, which each rect on a row
having the same value for top, is that right? Presumably you then need
to alter the bottom values so that they are all the same height.

A couple of nested for loops would seem sufficient

for (int i = 0; i < nCount; ++i)
{
if (i == 0 || ARR.top != ARR[i-1].top)
{
// NEW ROW - get max
int max = ARR.bottom;
for (int j = i + 1; j < nCount && ARR[j].top == ARR.top; ++j)
{
if (ARR[j].bottom > max)
max = ARR[j].bottom;
}
// now assign max
for (int j = i; j < nCount && ARR[j].top == ARR.top; ++j)
ARR[j].bottom = max;
}
}

Untested code of course.

john

 

[John Harrison]

A couple of nested for loops would seem sufficient

for (int i = 0; i < nCount; ++i)
{
if (i == 0 || ARR.top != ARR[i-1].top)
{
// NEW ROW - get max
int max = ARR.bottom;
for (int j = i + 1; j < nCount && ARR[j].top == ARR.top; ++j)
{
if (ARR[j].bottom > max)
max = ARR[j].bottom;
}
// now assign max
for (int j = i; j < nCount && ARR[j].top == ARR.top; ++j)
ARR[j].bottom = max;
}
}

Untested code of course.

Replace last loop with

// now assign max
int k = i;
for (; k < nCount && ARR[k].top == ARR.top; ++k)
ARR[k].bottom = max;
i = k - 1;

Any further bugs I'll leave to you.

john

 

[James Kanze]

I have the following:
struct A
{
int left;
int top;
int right;
int bottom;
};
Thats a rectangle. I have an array of rectangles... say
ARR[nCount]... Now, I've got these elements laid out in rows
(not important how),

I would say that is important. It seems like the essense of the problem
to me.

Me too.

[...]

So it seems you have all the rects in order, which each rect
on a row having the same value for top, is that right?

I'd probably tend to use a two dimentional structure. If I
couldn't change the basic structure, something like the
following should be able to handle all cases (supposing that
"top" can be used to identify the row).

std::map< int, int > maxPerRow ;
for ( A* curr = begin ; curr != end ; ++ curr ) {
int& maxBottom = maxPerRow[ curr->top ] ;
maxBottom = std::max( maxBottom, curr->bottom ) ;
}
for ( A* curr = begin ; curr != end ; ++ curr ) {
curr->bottom = maxBottom[ curr->top ] ;
}

Obviously, if you can manage order, or use a two dimensional
structure, the code can be made more efficient. But anyway you
do it, you'll need two passes over each row.

 

[Somebody]

I have the following:

struct A
{
int left;
int top;
int right;
int bottom;
};

Thats a rectangle. I have an array of rectangles... say ARR[nCount]...
Now, I've got these elements laid out in rows (not important how),

I would say that is important. It seems like the essense of the problem to
me.

I meant the array of rects holds the rectangles *after* they've been laid
out. Thats a GUI issue and I know how you CLC++ guys hate OS specific
questions .

Anyways, they are the rectangles of GUI elements that have been laid out on
the screen... I end up with something like:

0 -> 23 0->40
40->50

etc.

So the 0 -> 23 needs to get changed to 0 -> 40 to match the other item in
the row.

A "row" is all rectangles with the same top.

but this

struct has no concept of which row its in...

Quite right. So you need something external to the rect which holds which
row a rect is in. Which is why knowing how you've split up the rects into
rows is important, as I said above.

I'm trying to make every rect in a row equal to the size of the max
height rectangle for that row... I can't seem to come up with a working
algorithm... maybe cuz its late... but my general concept is to first
detect when a new row is hit:

int y = 0;

for (int i = 0; i < nCount; i++)
{
if (ARR.top != y)
{
// NEW ROW
y = ARR.top;
}
else
{
}
}

problem with this right away is that it doesn't hit the NEW ROW part for
all the rectangles... namely the last one... so thats not included in the
max measurement.

any suggestions on how to proceed?

So it seems you have all the rects in order, which each rect on a row
having the same value for top, is that right? Presumably you then need to
alter the bottom values so that they are all the same height.

A couple of nested for loops would seem sufficient

for (int i = 0; i < nCount; ++i)
{
if (i == 0 || ARR.top != ARR[i-1].top)
{
// NEW ROW - get max
int max = ARR.bottom;
for (int j = i + 1; j < nCount && ARR[j].top == ARR.top; ++j)
{
if (ARR[j].bottom > max)
max = ARR[j].bottom;
}
// now assign max
for (int j = i; j < nCount && ARR[j].top == ARR.top; ++j)
ARR[j].bottom = max;
}
}

Untested code of course.

john

I was trying to do it in a single pass... but it seems like its pretty
straight forward to do it in 2 passes. I guess I'll go with that... its a
small number of rectangles, so the performance should be ok.