C++ programming

[TheeeGod 3]

to all the c++ gurus: I need some help with this code.

This is concerned with sorted lists of type UpLists.

Write two user functions (not members or friends) called GetIntersection and

GetUnion which performs the following:

L1: 8,12,38,41,84,101.

L2: 4,12,38,39,42,84,99,101,348.

Then a call like GetIntersection(L1, L2) returns a new sorted list UpList which

contains 12,38,84,101.

A call like GetUnion(L1, L2) returns a new sorted list UpList which contains

4,8,12,38,39,41,42,84,99,101,348.

Write a test program called Test_UpList.cc which contains these two functions

and a main program that uses these functions.



any help would be appreciated...thnx in advance

[khp]

How is the uplist defined ?

Why do you need us to help you with your homework ?

[TheeeGod 3]

i'm trying to figure out myself how the uplisyt is defined. my professor didnt say anything.

and as for the second question, if u dont want to help that is fine. i said any help would be "APPRECIATED", implying that your help on this is not "REQUIRED"

[khp]

OK I guess I can help you out a little bit

I have implemented GetIntersection, and made a small test function. You should be able to implement GetUnion easily. I have defined uplist to be a stl list of intergers.


#include <stdio.h>
#include <list>

using namespace std;

#define uplist list<int>

uplist* GetIntersection(uplist L1,uplist L2)
{
uplist* results_list= new uplist();
while ((!L1.empty()) && (!L2.empty()))
{
if (L1.front()==L2.front()) {
results_list->push_back(L1.front());
L1.pop_front();
L2.pop_front();
} else {
if (L1.front()>L2.front())
L2.pop_front();
else
L1.pop_front();
}
}
return results_list;
}

int main(int argc, char* argv[])
{
uplist mylistL1;
uplist mylistL2;
uplist* results;
mylistL1.push_back(1);
mylistL1.push_back(2);
mylistL1.push_back(5);
mylistL2.push_back(2);
mylistL2.push_back(5);
results = GetIntersection(mylistL1,mylistL2);
printf("Results:\n");
while (!results->empty()) {
printf("%d \n",results->front());
results->pop_front();
}
return 0;
}

[TheeeGod 3]

wow man...thank you...i will test this code out and check it with what i have...i will report back if i have any problems...thanks again in tons

[khp]

Originally posted by TheeeGod 3
wow man...thank you...

No problem, in the above code I used call by value on the arguments of GetIntersection in order to avoid modifying the argument lists.
If the arguments for GetIntersection are huge this will be an expensive operation, because complete copies of the argument lists are constructed when calling GetIntersection.

If instead we use call by reference the program only passes, a pointer to the argumentlist, to GetIntersection. But then we must not modify the arguments in GetIntersection. To make sure this happens we declare the arguments to be const and use iterators to work through the lists. This should be about twice as fast on large examples.

The code should then look something like this.


#include <stdio.h>
#include <list>

using namespace std;

#define uplist list<int>

uplist* GetIntersection(const uplist *L1,const uplist *L2)
{
uplist::const_iterator L1pos=L1->begin();
uplist::const_iterator L2pos=L2->begin();
uplist* results_list= new uplist();
while ((L1pos!=L1->end()) && (L2pos!=L2->end()))
{
if (*L1pos==*L2pos) {
results_list->push_back(*L1pos);
L1pos++;
L2pos++;
} else {
if (*L1pos>*L2pos)
L2pos++;
else
L1pos++;
}
}
return results_list;
}

int main(int argc, char* argv[])
{
uplist mylistL1;
uplist mylistL2;
uplist* results;
mylistL1.push_back(1);
mylistL1.push_back(2);
mylistL1.push_back(5);
mylistL2.push_back(2);
mylistL2.push_back(5);
results = GetIntersection(&mylistL1,&mylistL2);
printf("Results:\n");
while (!results->empty()) {
printf("%d \n",results->front());
results->pop_front();
}
return 0;
}


But I think you need to be carefull with this stl (standard template library) stuff, somehow I don't think this was what your professor had in mind.

[ChristianHJW]

khp,

you seem to have some nice C++ skills :D ...

Any plans to contribute to some of the projects here ? MCF, the new A/V format could need some help .. check http://mcf.sourceforge.net technical section to read more about the specs, a good example what MCF could do for the community is this thread here : http://forum.doom9.org/showthread.php?s=&threadid=8317 ... getting 800 MB of data on a 700 MB CD ....

You're also welcome on our IRC channel, #mcf on the openprojects server. MCF project is on sourceforge https://sourceforge.net/projects/mcf/ , if you want to join as coder please PM me here with email adress mentioned somewhere ...

[Nic]

Shouldn't you:
delete results;

At the end there? even though you've removed all the members, the class should be deleted. Just nitpicking :D

@Chris:
Still making your army? :D

-Nic

[BlackSun]

Originally posted by Nic

@Chris:
Still making your army? :D

-Nic

ROTFL !! :D :D He's like that...hiring everybody !!

[khp]

@ChristianHJW:

Thank you for the invite, I have thought about getting into some of this stuff, but I find it hard to step into the middle of a project.

Edit: OK, I have joined the devel and cvs mailinglists at the sourceforge, I will probably be lurking for a while.

I am working on a small project of my own, trying to compare a set of avi files against a reference avi file, in other words I am making a tool that will try to measure how close different codecs matches the original picture quality.



Shouldn't you:
delete results;


Yes ofcause, I'am pretty much a, do as little as possible person, writing a happy ending to my programs usually has a very low priority

[avih]

Originally posted by khp
..Yes ofcause, I'am pretty much a, do as little as possible person, writing a happy ending to my programs usually has a very low priority

:D but ofcourse :) that's my kind of attitude :)

don't get surprised by the possible consequences though :)

[ChristianHJW]

Originally posted by khp @ChristianHJW: Thank you for the invite, I have thought about getting into some of this stuff, but I find it hard to step into the middle of a project.
Edit: OK, I have joined the devel and cvs mailinglists at the sourceforge, I will probably be lurking for a while. .. Great !! Thanks for your interest in MCF .. and dont forget to join our #mcf channel on IRC openprojects server by time ... right now all our devs are there and chatting about stupid things instead of coding :D !! ( just joking .. )

[TheeeGod 3]

@KHP...i found out what the uplist is defined as....

// file name: Uplist.h

#ifndef UPLIST_H
#define UPLIST_H

#include "SLIST.h"

template <class T> class UpList {
private:
SList<T> list;
public:
void Insert (const T& item) {
if (list.IsEmpty())
list.AddFirst (item) ;
else if (list.ShowFirst() >= item)
list.AddFirst(item);
else {
SList<T>: :Iterator cur = list.Begin(), prev;
while (cur != list.End() && *cur < item)
prev = cur++;
if (cur ==list.End())
list.AddLast(item) ;
else
list.AddAfter(prev, item);
}
}

void Delete() {
assert(!list.IsEmpty());
list.RemoveFirst();
}

bool IsEmpty() { return list.IsEmpty() ; }

const T& ShowFirst() { return list.ShowFirst() ; }

class Iterator {
private:
SList<T>: :Iterator i;
public:
Iterator() {}

Iterator (SList<T>: :Iterator it) { i = it;}

T& operator*() {return *i;}

Iterator& operator++() { // prefix
++i;
return *this;
}

Iterator operator++ (int) { // postfix
Iterator r(*this);
++i ;
return r;
}

bool operator==(Iterator r) { return i == r.i; }
bool operator!=(Iterator r) {return i != r.i; }
};

Iterator Begin() {
SList<T>: :Iterator it = list.Begin();
return Iterator(it) ; }

Iterator End() {
SList<T>: :Iterator it = list.End() ;
return Iterator(it) ; }
} ;
#endif

wha would be next?

[khp]

OK then your Test_UpList.cc file should contain something like this. Again I'll leave it to you, to write the GetUnion function.

Edit: OK I have changed GetIntersection to work with any element class for which the == and > operators are defined.

#include <stdio.h>
#include "Uplist.h"

template <class T>

UpList<T>* GetIntersection(UpList<T> *L1, UpList<T> *L2)
{
UpList<T>::iterator L1pos=L1->Begin();
UpList<T>::iterator L2pos=L2->Begin();

UpList<t>* results_list= new UpList<T>();
while ((L1pos!=L1->End()) && (L2pos!=L2->End()))
{
if (*L1pos==*L2pos) {
results_list->Insert(*L1pos);
L1pos++;
L2pos++;
} else {
if (*L1pos>*L2pos)
L2pos++;
else
L1pos++;
}
}
return results_list;
}

int main(int argc, char* argv[])
{
UpList<int> mylistL1;
UpList<int> mylistL2;
UpList<int>* results;
mylistL1.Insert(1);
mylistL1.Insert(2);
mylistL1.Insert(5);
mylistL2.Insert(2);
mylistL2.Insert(5);
results = GetIntersection(&mylistL1,&mylistL2);
printf("Results:\n");
while (!results->IsEmpty()) {
printf("%d \n",results->ShowFirst());
results->Delete();
}
delete results;
return 0;
}



Unfortunatly I have been unable to test this because I don't have the file SLIST.h included by Uplist.h, so you might get a few syntax errors. Which platform / compiler are you using for this ?.

[TheeeGod 3]

unix