Preventing code bloat with conceptually similar structures

[Paul]

The below code comes from https://www.geeksforgeeks.org/median-of-stream-of-integers-running-integers/

It's elegant except for the massive code duplication -- MaxHeap and MinHeap are copy-pastes of each other with only a single difference.

Any ideas?

My idea would probably be to make Heap a non-abstract class, and leave out
the inheritance. max and min heaps could then be distinguished by each
other by naming conventions rather than inheritance hierarchies.

Without using inheritance, and with just one non-abstract heap class, we write for example:
Heap *left = new Heap(&Greater);
Heap *right = new Heap(&Smaller);

This way code duplication can be completely avoided.

I'd be interested to hear others' opinions.

Thanks,

Paul


#include <iostream>
using namespace std;

// Heap capacity
#define MAX_HEAP_SIZE (128)
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])

//// Utility functions

// exchange a and b
inline
void Exch(int &a, int &b)
{
int aux = a;
a = b;
b = aux;
}

// Greater and Smaller are used as comparators
bool Greater(int a, int b)
{
return a > b;
}

bool Smaller(int a, int b)
{
return a < b;
}

int Average(int a, int b)
{
return (a + b) / 2;
}

// Signum function
// = 0 if a == b - heaps are balanced
// = -1 if a < b - left contains less elements than right
// = 1 if a > b - left contains more elements than right
int Signum(int a, int b)
{
if( a == b )
return 0;

return a < b ? -1 : 1;
}

// Heap implementation
// The functionality is embedded into
// Heap abstract class to avoid code duplication
class Heap
{
public:
// Initializes heap array and comparator required
// in heapification
Heap(int *b, bool (*c)(int, int)) : A(b), comp(c)
{
heapSize = -1;
}

// Frees up dynamic memory
virtual ~Heap()
{
if( A )
{
delete[] A;
}
}

// We need only these four interfaces of Heap ADT
virtual bool Insert(int e) = 0;
virtual int GetTop() = 0;
virtual int ExtractTop() = 0;
virtual int GetCount() = 0;

protected:

// We are also using location 0 of array
int left(int i)
{
return 2 * i + 1;
}

int right(int i)
{
return 2 * (i + 1);
}

int parent(int i)
{
if( i <= 0 )
{
return -1;
}

return (i - 1)/2;
}

// Heap array
int *A;
// Comparator
bool (*comp)(int, int);
// Heap size
int heapSize;

// Returns top element of heap data structure
int top(void)
{
int max = -1;

if( heapSize >= 0 )
{
max = A[0];
}

return max;
}

// Returns number of elements in heap
int count()
{
return heapSize + 1;
}

// Heapification
// Note that, for the current median tracing problem
// we need to heapify only towards root, always
void heapify(int i)
{
int p = parent(i);

// comp - differentiate MaxHeap and MinHeap
// percolates up
if( p >= 0 && comp(A[i], A[p]) )
{
Exch(A[i], A[p]);
heapify(p);
}
}

// Deletes root of heap
int deleteTop()
{
int del = -1;

if( heapSize > -1)
{
del = A[0];

Exch(A[0], A[heapSize]);
heapSize--;
heapify(parent(heapSize+1));
}

return del;
}

// Helper to insert key into Heap
bool insertHelper(int key)
{
bool ret = false;

if( heapSize < MAX_HEAP_SIZE )
{
ret = true;
heapSize++;
A[heapSize] = key;
heapify(heapSize);
}

return ret;
}
};

// Specilization of Heap to define MaxHeap
class MaxHeap : public Heap
{
private:

public:
MaxHeap() : Heap(new int[MAX_HEAP_SIZE], &Greater) { }

~MaxHeap() { }

// Wrapper to return root of Max Heap
int GetTop()
{
return top();
}

// Wrapper to delete and return root of Max Heap
int ExtractTop()
{
return deleteTop();
}

// Wrapper to return # elements of Max Heap
int GetCount()
{
return count();
}

// Wrapper to insert into Max Heap
bool Insert(int key)
{
return insertHelper(key);
}
};

// Specilization of Heap to define MinHeap
class MinHeap : public Heap
{
private:

public:

MinHeap() : Heap(new int[MAX_HEAP_SIZE], &Smaller) { }

~MinHeap() { }

// Wrapper to return root of Min Heap
int GetTop()
{
return top();
}

// Wrapper to delete and return root of Min Heap
int ExtractTop()
{
return deleteTop();
}

// Wrapper to return # elements of Min Heap
int GetCount()
{
return count();
}

// Wrapper to insert into Min Heap
bool Insert(int key)
{
return insertHelper(key);
}
};

// Function implementing algorithm to find median so far.
int getMedian(int e, int &m, Heap &l, Heap &r)
{
// Are heaps balanced? If yes, sig will be 0
int sig = Signum(l.GetCount(), r.GetCount());
switch(sig)
{
case 1: // There are more elements in left (max) heap

if( e < m ) // current element fits in left (max) heap
{
// Remore top element from left heap and
// insert into right heap
r.Insert(l.ExtractTop());

// current element fits in left (max) heap
l.Insert(e);
}
else
{
// current element fits in right (min) heap
r.Insert(e);
}

// Both heaps are balanced
m = Average(l.GetTop(), r.GetTop());

break;

case 0: // The left and right heaps contain same number of elements

if( e < m ) // current element fits in left (max) heap
{
l.Insert(e);
m = l.GetTop();
}
else
{
// current element fits in right (min) heap
r.Insert(e);
m = r.GetTop();
}

break;

case -1: // There are more elements in right (min) heap

if( e < m ) // current element fits in left (max) heap
{
l.Insert(e);
}
else
{
// Remove top element from right heap and
// insert into left heap
l.Insert(r.ExtractTop());

// current element fits in right (min) heap
r.Insert(e);
}

// Both heaps are balanced
m = Average(l.GetTop(), r.GetTop());

break;
}

// No need to return, m already updated
return m;
}

void printMedian(int A[], int size)
{
int m = 0; // effective median
Heap *left = new MaxHeap();
Heap *right = new MinHeap();

for(int i = 0; i < size; i++)
{
m = getMedian(A[i], m, *left, *right);

cout << m << endl;
}

// C++ more flexible, ensure no leaks
delete left;
delete right;
}
// Driver code
int main()
{
int A[] = {5, 15, 1, 3, 2, 8, 7, 9, 10, 6, 11, 4};
int size = ARRAY_SIZE(A);

// In lieu of A, we can also use data read from a stream
printMedian(A, size);

return 0;
}

[Alf P. Steinbach]

On 07.12.2018 00:23, Paul wrote:
> MaxHeap() : Heap(new int[MAX_HEAP_SIZE], &Greater) { }

The use of `Greater` versus `Smaller` seems to be the only difference
between the two classes `MaxHeap` and `MinHeap`.

You can make that a parameter in at least three ways:

* As a template parameter.
* As a function object constructor argument.
* As a virtual function to be overridden in each class.


Cheers & hth.,

- Alf

[Paul]

Thanks, but is the code duplication approach, as originally posted considered
bad, or is it a fine example to emulate?

Paul

[Alf P. Steinbach]

Generally code duplication is frowned on, regarded as ungood, hence the
common advice to keep it DRY (Don't Repeat Yourself).

A main reason why it's ungood in the ideal, is that roughly 80% of
development is maintenance, and maintenance can easily introduce
unintenteded differences in a set of code duplications. This then
increases work involved in further maintenance and bug-hunting.

However, especially (in my experience) in the defense industry, code
like whole files is very often duplicated, and then some minor changes
are made. It's in practice necessary because the original code is at a
low level of abstraction with no support for e.g. overriding behavior.
And it generates a source of income for the developer, a kind of job
security, as well making the developer seem productive in terms of
number of lines produced per time period, the infamous SLOC metric.

Job security: it would cost much more to let some other developer try to
make sense of the spaghetti.

Productivity: defense industry people are a very conservative lot in
peace time. During WWII this industry invented the whole field of
logistics and the underlying math of what's now dynamic programming, and
the ideas now underlying ISO certification (as I recall that originated
with ungood quality of bombs made in English factories with mostly
female workers), and much else. But since then it's not progressed
beyond e.g. counting lines of code as a metric of productivity.

Of course the defense industry thing is a /management issue/, that it's
too easy for a manager to benefit from taking the short view and passing
the cost on to someone who later gets responsibility for this, and
ultimately it's an issue of people being paid just to conform. But. In
practice it means that for what's “best practice” in C++ one should
better consider the outer context, like who pays, very carefully.


Cheers!,

- Alf

[Vir Campestris]

On 07/12/2018 08:19, Paul wrote:
> Thanks, but is the code duplication approach, as originally posted considered
> bad, or is it a fine example to emulate?

I've just spent a few days removing some duplication, and I expect to be
doing some more. I'm having to untangle the spaghetti before I dare add
anything new.

I found at least one case where some bugs had been fixed in one of the
copies, but not in the other.

Then on further examination I found that none of the build
configurations could actually access the second copy. So I've deleted it.

Andy

[Shobe, Martin]

On 12/7/2018 3:20 AM, Alf P. Steinbach wrote:
[snip]

> Productivity: defense industry people are a very conservative lot in
> peace time. During WWII this industry invented the whole field of
> logistics and the underlying math of what's now dynamic programming, and
> the ideas now underlying ISO certification (as I recall that originated
> with ungood quality of bombs made in English factories with mostly
> female workers), and much else. But since then it's not progressed
> beyond e.g. counting lines of code as a metric of productivity.

Since the ISO was a re-organization of the ISA and the ISA begin in
1926, this misogynous "history" is fake. Please don't continue to spread it.

http://www.sis.pitt.edu/mbsclass/standards/martincic/isohistr.htm

Martin Shobe

[Alf P. Steinbach]

On 08.12.2018 00:59, Shobe, Martin wrote:
> On 12/7/2018 3:20 AM, Alf P. Steinbach wrote:
> [snip]
>
>> Productivity: defense industry people are a very conservative lot in
>> peace time. During WWII this industry invented the whole field of
>> logistics and the underlying math of what's now dynamic programming,
>> and the ideas now underlying ISO certification (as I recall that
>> originated with ungood quality of bombs made in English factories with
>> mostly female workers), and much else. But since then it's not
>> progressed beyond e.g. counting lines of code as a metric of
>> productivity.
>
> Since the ISO was a re-organization of the ISA and the ISA begin in
> 1926,

That's irrelevant to anything.


> this misogynous "history"

Did you latch on to the word “female” and fail to apply any rational
thinking, or was this a more purely random choice of derogatory
adjective, a shot in the dark hoping to maybe hit something?


> is fake.

That conclusion doesn't follow from any premise or logic of yours.

> Please don't continue to spread it.

You could have looked it up, you know.

You were so close:


> http://www.sis.pitt.edu/mbsclass/standards/martincic/isohistr.htm

The site you refer to here traces the history to the US in WWII, with
further development in Britain after the war.

[quote]
The history behind this series of standards can be traced to the USA
during World War II. From the USA, the concept of quality assurance
spread to Europe via NATO where it evolved into the Allied Quality
Assurance Publication (AQAP). This series of docu ments discussed
everything from production efficiency to selection of suppliers. The
AQAP series were adopted by the UK Ministry of Defense for the British
Armed Forces. This series had a trickle down effect as organizations
began to require quality ass urance programs from their suppliers. The
problem was that there was much diversity in the requirements for
different organizations
[/quote]

I've read a review of computing history in the American publication
Scientific American, where the author, a renowned US professor, failed
to make any mention of George Boole, Augustus de Morgan, Charles Babbage
and Ada Lovelace. He started with Napoleon I think it was, skipped
England and later Konrad Zuse, I'm not sure but it's possible he also
skipped Alan Turing, made it appear that Johannes von Neumann was an
American, and that modern computing was invented in the US. That's one
example of why I'm a bit skeptical of American history writing. But I
fail now to google up a reference more in the direction of England, I'm
not sure where I got that from. However, the role of women in production
is apparently much less controversial than the very high defect rate of
English bombs; googling found any number of references for that.


> Martin Shobe

Cheers!, & hth.,

- Alf

[Manfred]

I have also witnessed the damage of code duplication - indeed it was a
maintenance problem where a fix was implemented in one place and
forgotten in another, a very common scenario.

But, when it comes to projects with very strict quality requirements,
one has to consider that coding "best practices" are not the highest
priority - although this may superficially seem a paradox.

By "very strict quality requirements" I mean e.g. systems where a
failure can actually physically harm people.
In these environments system validation becomes of utmost relevance,
hence the conservative attitude towards a system that has already been
validated.
When introducing a change in code, it is therefore understandable that
the modified code be deployed only for the specific targets that do need
it, and leave the code untouched for other targets - which results in
code duplication.
Obviously this introduces some extra maintenance burden, but depending
on the level of maturity of the project this burden can be evaluated to
be less harmful than the risk of introducing a bug in systems that have
already been validated, and that in the end would need no change - i.e.
an unjustified risk.

By no means I advocate that this is good practice from a software design
point of view. My point is that at a higher level it may be considered
preferable based on considerations on the whole system lifecycle, beyond
the rationale of software design only.

>
>
> Cheers!,
>
> - Alf

[Jorgen Grahn]

I haven't tried to understand the code, but it looks pretty bad.
Unrelated to what you're asking about:

- uses new for no obvious reason
- doesn't use const
- has comments, but they are useless:

// Specilization of Heap to define MaxHeap
class MaxHeap : public Heap

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[Shobe, Martin]

On 12/7/2018 7:46 PM, Alf P. Steinbach wrote:
> On 08.12.2018 00:59, Shobe, Martin wrote:
>> On 12/7/2018 3:20 AM, Alf P. Steinbach wrote:
>> [snip]
>>
>>> Productivity: defense industry people are a very conservative lot in
>>> peace time. During WWII this industry invented the whole field of
>>> logistics and the underlying math of what's now dynamic programming,
>>> and the ideas now underlying ISO certification (as I recall that
>>> originated with ungood quality of bombs made in English factories
>>> with mostly female workers), and much else. But since then it's not
>>> progressed beyond e.g. counting lines of code as a metric of
>>> productivity.
>>
>> Since the ISO was a re-organization of the ISA and the ISA begin in 1926,
>
> That's irrelevant to anything.

Since 1926 is before WW2, the ideas underlying ISO predate WW2 and
couldn't have come from bomb quality during WW2.

>> this misogynous "history"
>
> Did you latch on to the word “female” and fail to apply any rational
> thinking, or was this a more purely random choice of derogatory
> adjective, a shot in the dark hoping to maybe hit something?

It's a result of you blaming the quality of the output on the gender.
That's what rational thinking makes of what you said.

>> is fake.
>
> That conclusion doesn't follow from any premise or logic of yours.

It most certainly does because it would require the effect to come
before the cause.

>> Please don't continue to spread it.
>
> You could have looked it up, you know.

I did.

>
> You were so close:
>
>
>> http://www.sis.pitt.edu/mbsclass/standards/martincic/isohistr.htm
>
> The site you refer to here traces the history to the US in WWII, with
> further development in Britain after the war.
>
> [quote]
> The history behind this series of standards can be traced to the USA
> during World War II. From the USA, the concept of quality assurance
> spread to Europe via NATO where it evolved into the Allied Quality
> Assurance Publication (AQAP). This series of docu ments discussed
> everything from production efficiency to selection of suppliers. The
> AQAP series were adopted by the UK Ministry of Defense for the British
> Armed Forces. This series had a trickle down effect as organizations
> began to require quality ass urance programs from their suppliers. The
> problem was that there was much diversity in the requirements for
> different organizations
> [/quote]

There's nothing there about your supposed cause. It's also about a
particular standard, ISO 9000, published in 1987.

Martin Shobe

[Alf P. Steinbach]

On 11.12.2018 05:30, Shobe, Martin wrote:
> On 12/7/2018 7:46 PM, Alf P. Steinbach wrote:
>> On 08.12.2018 00:59, Shobe, Martin wrote:
>>> On 12/7/2018 3:20 AM, Alf P. Steinbach wrote:
>>> [snip]
>>>
>>>> Productivity: defense industry people are a very conservative lot in
>>>> peace time. During WWII this industry invented the whole field of
>>>> logistics and the underlying math of what's now dynamic programming,
>>>> and the ideas now underlying ISO certification (as I recall that
>>>> originated with ungood quality of bombs made in English factories
>>>> with mostly female workers), and much else. But since then it's not
>>>> progressed beyond e.g. counting lines of code as a metric of
>>>> productivity.
>>>
>>> Since the ISO was a re-organization of the ISA and the ISA begin in
>>> 1926,
>>
>> That's irrelevant to anything.
>
> Since 1926 is before WW2, the ideas underlying ISO predate WW2 and
> couldn't have come from bomb quality during WW2.

You're still irrelevant to anything.

With the number of irrelevancies piling up now, it begins to sound not
sound of mind.

>>> this misogynous "history"
>>
>> Did you latch on to the word “female” and fail to apply any rational
>> thinking, or was this a more purely random choice of derogatory
>> adjective, a shot in the dark hoping to maybe hit something?
>
> It's a result of you blaming the quality of the output on the gender.

That would be a lie for someone with a good grasp of reality right in
front of the nose, namely the quoted material.

> That's what rational thinking makes of what you said.
>
>>> is fake.
>>
>> That conclusion doesn't follow from any premise or logic of yours.
>
> It most certainly does because it would require the effect to come
> before the cause.

Jeez.

>>> Please don't continue to spread it.
>>
>> You could have looked it up, you know.
>
> I did.

No, you failed:

>> You were so close:
>>
>>
>>> http://www.sis.pitt.edu/mbsclass/standards/martincic/isohistr.htm
>>
>> The site you refer to here traces the history to the US in WWII, with
>> further development in Britain after the war.
>>
>> [quote]
>> The history behind this series of standards can be traced to the USA
>> during World War II. From the USA, the concept of quality assurance
>> spread to Europe via NATO where it evolved into the Allied Quality
>> Assurance Publication (AQAP). This series of docu ments discussed
>> everything from production efficiency to selection of suppliers. The
>> AQAP series were adopted by the UK Ministry of Defense for the British
>> Armed Forces. This series had a trickle down effect as organizations
>> began to require quality ass urance programs from their suppliers. The
>> problem was that there was much diversity in the requirements for
>> different organizations
>> [/quote]
>
> There's nothing there about your supposed cause.

Again, it seems you're unable to relate to what you read, and instead
prefer to relate to idiotic ideas in your mind.

> It's also about a
> particular standard, ISO 9000, published in 1987.

Yes it is.


Cheers & quite a bit annoyed having to respond to idiocy,

- Alf