Efficient if nesting.

[Gaminic]

Hello,

My current project uses a MAX Heap to keep a number of things organized. It's a simple Binary Heap (implemented as an array), mainly using:
-Insert(NODE n)
-Delete(NODE at index T)
-Update(NODE at index T with new value NVAL)

The number of Elements in constant and are saved in a vector of Elements. Only the Elements with a value above a certain threshold are in the Heap. This changes nothing for Insert and Delete, but results in the following cases for Update:

-Old Value < LIMIT:
--New Value < LIMIT: update value, stop.
--New Value > LIMIT: update value, Insert into Heap, stop.
-Old Value > LIMIT:
--New Value < LIMIT: Delete from Heap, update value, stop.
--New Value > Limit:
---New Value < Old Value: update value, Downsift, stop.
---New Value > Old Value: update value, Upsift, stop.

I used that flow table quite literally for the code:

void HEAP::HUpdate(CNODE ij, VALUE nval) {
	if (index(ij) == UNHEAPED) {  // Same as val(ij) < LIMIT
		val(ij) = nval;
		if (nval > limit) HInsert(ij);
	}
	else {
		if (nval < limit) { 
			HDelete(index(ij));
			val(ij) = nval;
		}
		else {
			if (nval > val(ij)) {
				val(ij) = nval;
				upsift(index(ij));
			}
			else {
				val(ij) = nval;
				downsift(index(ij));
			}
		}
	}
}

It works, but I'm not satisfied with it. It looks inefficient. It might all be in my head, but when I see multiple nestings I become unhappy.

Is there a more efficient way of doing this? I can artificially reduce the nesting by replace the "else" with a "return" in the related "if" code, but I'm not sure if that's better.

Any and all tips are welcome in regards to nesting, even if they're not directly applicable to this specific problem!

[ne555]

>It might all be in my head,
Yes

> but when I see multiple nestings I become unhappy.
Then don't nest

Also val(ij) = nval; is in all paths.

[AleaIactaEst]

I don't think you can make this any more efficient than now by changing the way you do the if nesting, since you really do need to check for all these informations, if the old value is below limit or not and so on.

I also would not artificially remove the nesting by placing return at the end of every if statement, because this won't change overall performance at all and the code will only be more difficult to read in my opinion.

All i know how to prevent if-statements are techniques like the following:

Imagine you want to run a loop and always toggle an integer value from 1 to 2 and from 2 to 1. Instead of writing

for(whatever) {
    if (value==1) value = 2
    else          value = 1
    //...
}

you could simply write value = 3-value;, so sometimes you can replace if-else statements by arithmetic expressions. This doesn't help in your specific problem of course :/

By the way in the case where old_value is below limit and the new_value is above the limit, you do not delete the old value from the vector, is this what you intended?

[coder777]

it's not nesting (except line 4). It's cascading.

Don't worry about if, since this is one of the fastest commands at all. So I don't think that there're really faster alternatives

[Gaminic]

Thanks for the responses, everyone. I figured I was overthinking things again.

@ne555:

Also val(ij) = nval; is in all paths.

Yes, but I can't put it outside of any of the checks with the current cascade sequence:

a) HDelete() works by changing val, therefore it must be set to nval after the delete.
b) In the "deepest" ifs, I need to check compare val and nval. If I place val = nval; outside, I lose the old value.

@AleaIactaEst

By the way in the case where old_value is below limit and the new_value is above the limit, you do not delete the old value from the vector, is this what you intended?

The old and new value belong to the same element. I'm not replacing one with the other; I'm updating one. The relation of the two values determines what update steps are required (Nothing, Insert, Delete, or Reposition). If the old value is below LIMIT, then the Element is not Heaped.

[edit]

Just realized that a) is not true with this Heap. Left-over logic of the Fibonacci Heap implementation. Still, I need the old value for the deepest if, so I can't update any sooner. I'll look at other possible sequences to see if I can reduce code doubling.

[doug4]

As @coder777 said, it's cascading ifs. Many people would write this as

void HEAP::HUpdate(CNODE ij, VALUE nval) {
	if (index(ij) == UNHEAPED) {  // Same as val(ij) < LIMIT
		val(ij) = nval;
		if (nval > limit) HInsert(ij);
	}
	else if (nval < limit) { 
		HDelete(index(ij));
		val(ij) = nval;
	}
	else if (nval > val(ij)) {
		val(ij) = nval;
		upsift(index(ij));
	}
	else {
		val(ij) = nval;
		downsift(index(ij));
	}
}

This hides the actual nesting that occurs in the code and makes it more easier for the user to see that the different options are all really at the same level in the decision tree. There is no logical difference between this code and your original post.

It is strictly a matter of style preference as to which way to go.

[Gaminic]

The way I drew my decision table made it seem like nesting. Thanks for clarifying, everyone!