Programming Forums > Application Development > C++

Jessehk · Dec 8th, 2006, 9:16 PM

Well, it looks like you took the easy way out. Good luck on the exam, you'll need it.

For what it's worth:

#include <iostream>

struct Span {
    int low;
    int high;

    Span( int low, int high );
};

Span::Span( int low, int high )
    : low( low ), high( high ) {}

int getOverlap( const Span &s1, const Span &s2) {
    int counter = 0;

    for ( int i = s1.low; i != s1.high; i++ )
        if ( i >= s2.low && i < s2.high )
            ++counter;

    return counter;
}

int main() {
    Span s1( -3, 2 );
    Span s2( 1, 3 );

    std::cout << getOverlap( s1, s2 ) << std::endl;
}

Jimbo · Dec 8th, 2006, 9:18 PM

Jessehk - Your method seems inefficient. It has a running time of O(n) compared to the O(1) solution we've already come up with.

aznballerlee · Dec 8th, 2006, 9:19 PM

Wait, how would we do this for an array?

(Toggle Plain Text)

double getOverlap (double span1[], double span2[])

with no struct.
I would think of going through a loop ..

Jimbo · Dec 8th, 2006, 9:23 PM

To do it without the span, you shouldn't need a loop. Unfortunately, you don't know for sure the size of either array. Here is one way it might go:

Assume the arrays each contain two values, a low and a high, in that order. Then do what we already did, just using span1[0] and as span1.low and span1[1] as span1.high. Treat span2 similarly.

If the arrays are in unsorted order, but still a low and high, you'll need to figure out which is the low and high for each.

If the arrays are a list of doubles (with more than 2 in each array) and you need to find the range of them, you're stuck, since you don't know the length of the arrays.

Note that for the first 2 examples, it is dangerous to assume the length is 2. Since this is just a small practice code though, I think you can get away with it.

Jessehk · Dec 8th, 2006, 9:26 PM

Jimbo:

I was about to post an example that showed your method to be wrong, but then I realized I was being an idiot. :p

I included the loop because I assumed he was supposed to have one, but in the end, you're right.

aznballerlee · Dec 8th, 2006, 9:30 PM

I would assume to follow your first example and get this:

(Toggle Plain Text)

double getOverlap (Span span1, Span span2)
{
	if (span1[0]> span2[0])
		low = span1[0];
	else
	{   
		low = span2[0];
	}

	if (span1[0] < span2[0])
		high = span1[0];
	else
	{
		high = span2[0];
	}

	int a = high-low;
	if (a>=0)
		return a;
	else
		return 0;
}

Jimbo · Dec 8th, 2006, 9:32 PM

Looks pretty good, though you still need to declare low and high.

aznballerlee · Dec 8th, 2006, 9:51 PM

Okay, one last question about this topic:

(Toggle Plain Text)

Class Span
{
public:
	Span (int low, int high)
		: m_low(low), m_high(high)
	{
	}

	int low () const
	{
		return m_low;
	}

	int high () const
	{
		return m_high;
	}

	int setLow (int value)
	{
		m_low = value;
	}

	int setHigh (int value)
	{
		m_high = value;
	}

private:
	int m_low;
	int m_high;
};

If the above was the class given,
would using the same logic work?

(Toggle Plain Text)

double getOverlap (Span span1, Span span2)
{
	int m_high, m_low;
	if (span1 -> low() > span2 -> low())
		low = span -> low();
	else
	{   
		low = span2 -> low();
	}

	if (span1 -> high() < span2 -> high())
		high = span1 -> high();
	else
	{
		high = span2 -> high();
	}

	int a = high - low;
	if (a>=0)
		return a;
	else
		return 0;
}

aznballerlee · Dec 8th, 2006, 9:54 PM

Similarly, if we used pointers for the Span parameters, would this apply?

(Toggle Plain Text)

double getOverlap (Span *span1, Span *span2)

(Toggle Plain Text)

double getOverlap (Span *span1, Span *span2)
{
	int m_high, m_low;
	if (this -> low() > this -> low())
		low = this -> low();
	else
	{   
		low = this -> low();
	}

	if (this -> high() < this -> high())
		high = this -> high();
	else
	{
		high =  this -> high();
	}

	int a = high - low;
	if (a>=0)
		return a;
	else
		return 0;
}

grumpy · Dec 8th, 2006, 10:20 PM

Quote:

Originally Posted by aznballerlee

Okay, one last question about this topic:
If the above was the class given,
would using the same logic work?

(Toggle Plain Text)

double getOverlap (Span span1, Span span2)
{
    int m_high, m_low;
    if (span1 -> low() > span2 -> low())
        low = span -> low();
    else
    {   
        low = span2 -> low();
    }

    if (span1 -> high() < span2 -> high())
        high = span1 -> high();
    else
    {
        high = span2 -> high();
    }

    int a = high - low;
    if (a>=0)
        return a;
    else
        return 0;
}

Not quite. The -> syntax works with pointers, not objects. Either use the . (dot) syntax for accessing members of the class/struct, or have the function accept two pointer arguments.

Dec 8th, 2006, 9:16 PM	#11
Jessehk The Oblivious One Join Date: May 2005 Location: Ontario, Canada Posts: 639 Rep Power: 4	Well, it looks like you took the easy way out. Good luck on the exam, you'll need it. For what it's worth: (Toggle Plain Text) #include <iostream> struct Span { int low; int high; Span( int low, int high ); }; Span::Span( int low, int high ) : low( low ), high( high ) {} int getOverlap( const Span &s1, const Span &s2) { int counter = 0; for ( int i = s1.low; i != s1.high; i++ ) if ( i >= s2.low && i < s2.high ) ++counter; return counter; } int main() { Span s1( -3, 2 ); Span s2( 1, 3 ); std::cout << getOverlap( s1, s2 ) << std::endl; } #include <iostream> struct Span { int low; int high; Span( int low, int high ); }; Span::Span( int low, int high ) : low( low ), high( high ) {} int getOverlap( const Span &s1, const Span &s2) { int counter = 0; for ( int i = s1.low; i != s1.high; i++ ) if ( i >= s2.low && i < s2.high ) ++counter; return counter; } int main() { Span s1( -3, 2 ); Span s2( 1, 3 ); std::cout << getOverlap( s1, s2 ) << std::endl; } __________________ Dr. Zoidberg: [ecstatic] I'm going to a movie... with FRIENDS!

Dec 8th, 2006, 9:18 PM	#12
Jimbo Battle Programmer Join Date: Feb 2006 Location: Bellevue, WA, USA Posts: 751 Rep Power: 3	Jessehk - Your method seems inefficient. It has a running time of O(n) compared to the O(1) solution we've already come up with. __________________ <insert disclaimer here> <insert shameless plug for Visual Studio here>

Dec 8th, 2006, 9:19 PM	#13
aznballerlee Hobbyist Programmer Join Date: Nov 2006 Posts: 111 Rep Power: 2	Wait, how would we do this for an array? (Toggle Plain Text) double getOverlap (double span1[], double span2[]) double getOverlap (double span1[], double span2[]) with no struct. I would think of going through a loop ..

Dec 8th, 2006, 9:23 PM	#14
Jimbo Battle Programmer Join Date: Feb 2006 Location: Bellevue, WA, USA Posts: 751 Rep Power: 3	To do it without the span, you shouldn't need a loop. Unfortunately, you don't know for sure the size of either array. Here is one way it might go: Assume the arrays each contain two values, a low and a high, in that order. Then do what we already did, just using span1[0] and as span1.low and span1[1] as span1.high. Treat span2 similarly. If the arrays are in unsorted order, but still a low and high, you'll need to figure out which is the low and high for each. If the arrays are a list of doubles (with more than 2 in each array) and you need to find the range of them, you're stuck, since you don't know the length of the arrays. Note that for the first 2 examples, it is dangerous to assume the length is 2. Since this is just a small practice code though, I think you can get away with it. __________________ <insert disclaimer here> <insert shameless plug for Visual Studio here>

Dec 8th, 2006, 9:26 PM	#15
Jessehk The Oblivious One Join Date: May 2005 Location: Ontario, Canada Posts: 639 Rep Power: 4	Jimbo: I was about to post an example that showed your method to be wrong, but then I realized I was being an idiot. :p I included the loop because I assumed he was supposed to have one, but in the end, you're right. __________________ Dr. Zoidberg: [ecstatic] I'm going to a movie... with FRIENDS!

Dec 8th, 2006, 9:30 PM	#16
aznballerlee Hobbyist Programmer Join Date: Nov 2006 Posts: 111 Rep Power: 2	I would assume to follow your first example and get this: (Toggle Plain Text) double getOverlap (Span span1, Span span2) { if (span1[0]> span2[0]) low = span1[0]; else { low = span2[0]; } if (span1[0] < span2[0]) high = span1[0]; else { high = span2[0]; } int a = high-low; if (a>=0) return a; else return 0; } double getOverlap (Span span1, Span span2) { if (span1[0]> span2[0]) low = span1[0]; else { low = span2[0]; } if (span1[0] < span2[0]) high = span1[0]; else { high = span2[0]; } int a = high-low; if (a>=0) return a; else return 0; }

Dec 8th, 2006, 9:32 PM	#17
Jimbo Battle Programmer Join Date: Feb 2006 Location: Bellevue, WA, USA Posts: 751 Rep Power: 3	Looks pretty good, though you still need to declare low and high. __________________ <insert disclaimer here> <insert shameless plug for Visual Studio here>

Dec 8th, 2006, 9:51 PM	#18
aznballerlee Hobbyist Programmer Join Date: Nov 2006 Posts: 111 Rep Power: 2	Okay, one last question about this topic: (Toggle Plain Text) Class Span { public: Span (int low, int high) : m_low(low), m_high(high) { } int low () const { return m_low; } int high () const { return m_high; } int setLow (int value) { m_low = value; } int setHigh (int value) { m_high = value; } private: int m_low; int m_high; }; Class Span { public: Span (int low, int high) : m_low(low), m_high(high) { } int low () const { return m_low; } int high () const { return m_high; } int setLow (int value) { m_low = value; } int setHigh (int value) { m_high = value; } private: int m_low; int m_high; }; If the above was the class given, would using the same logic work? (Toggle Plain Text) double getOverlap (Span span1, Span span2) { int m_high, m_low; if (span1 -> low() > span2 -> low()) low = span -> low(); else { low = span2 -> low(); } if (span1 -> high() < span2 -> high()) high = span1 -> high(); else { high = span2 -> high(); } int a = high - low; if (a>=0) return a; else return 0; } double getOverlap (Span span1, Span span2) { int m_high, m_low; if (span1 -> low() > span2 -> low()) low = span -> low(); else { low = span2 -> low(); } if (span1 -> high() < span2 -> high()) high = span1 -> high(); else { high = span2 -> high(); } int a = high - low; if (a>=0) return a; else return 0; } Last edited by aznballerlee; Dec 8th, 2006 at 10:06 PM.

Dec 8th, 2006, 9:54 PM	#19
aznballerlee Hobbyist Programmer Join Date: Nov 2006 Posts: 111 Rep Power: 2	Similarly, if we used pointers for the Span parameters, would this apply? (Toggle Plain Text) double getOverlap (Span span1, Span span2) double getOverlap (Span span1, Span span2) (Toggle Plain Text) double getOverlap (Span span1, Span span2) { int m_high, m_low; if (this -> low() > this -> low()) low = this -> low(); else { low = this -> low(); } if (this -> high() < this -> high()) high = this -> high(); else { high = this -> high(); } int a = high - low; if (a>=0) return a; else return 0; } double getOverlap (Span span1, Span span2) { int m_high, m_low; if (this -> low() > this -> low()) low = this -> low(); else { low = this -> low(); } if (this -> high() < this -> high()) high = this -> high(); else { high = this -> high(); } int a = high - low; if (a>=0) return a; else return 0; } Last edited by aznballerlee; Dec 8th, 2006 at 10:06 PM.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
How to create struct containing variable array struct	shoeyfighter	C	14	Nov 6th, 2006 3:26 AM
Casting a struct to s aimilar struct	shoeyfighter	C	6	Oct 27th, 2006 2:59 PM
struct question	n00b	C++	9	Oct 15th, 2006 11:26 AM
Appreciate comments on some linked list code	Jessehk	C	5	Jul 20th, 2006 7:59 PM
confusing question from assignment	silvia	C++	1	Jul 29th, 2005 4:29 AM

Programming Forums > Application Development > C++

Struct Question