Implementing Library Algorithms

hey guys..need some help with a project...im basically to implement the following 5 algorithms for a driver program...

here are the algorithms:

accumulate(b, e, t)

equal(b, e, t)

fill(b, e, t) - is to copies the value t into all the elements in the range [b, e).

lexicographic_compare(b, e, b2, e2) - returns true if each element in the range [b, e) is less than the corresponding element in the range [b2, 2e), and false otherwise.

min_element(b, e) - min_element(b, e) returns an iterator pointing to the smallest element in the range [b, e).

this is what I have so far..

Code:

#ifndef GUARD_myalgorithm_h
#define GUARD_myalgorithm_h

template <class In, class Out>
Out my_copy(In b, In e, Out d)
{
while (b != e)
*d++ = *b++;
return d;
}

template <class In, class Out>
int my_accumulate(In b, In e, Out t)
{
int aaa = *t;
while (b != e) {
aaa = aaa + *b;
b++;
}
return aaa;
}

template <class In>
bool my_equal(In b, In e, In t)
{

return true;
}

template <class In>
void my_fill(In b, In e, In t)
{
while (b != e) {
*b = *t;
b++;
}
}

template <class In>
bool my_lexicographic_compare(In b, In e, In b2, In e2)
{
while (b != e && b2 != e2) {
for (b; b != e; b++)
  if (*b >= *b2)
return false;
if (*b < *b2)
}

template <class In>
iter my_min_element(In b, In e)
{
return;
}

#endif

can you guys go over it and see if there are mistakes, also i'm not sure how to do the min_element and equal functions so any pointers would help..thanks

Please indent your code.

I suggest that you use the standard library names but enclose these function templates in your own namespace.

EDIT:
Consider that std::accumulate does not only work on ints.

ok i indented the code...and I also included the driver program - this should not be touched at all..

Code:

#ifndef GUARD_myalgorithm_h
#define GUARD_myalgorithm_h

template <class In, class Out>
Out my_copy(In b, In e, Out d)
{
    while (b != e) 
        *d++ = *b++;
    return d;
}


template <class In, class Out>
int my_accumulate(In b, In e, Out t)
{
    int aaa = *t;
    while (b != e) {
	aaa = aaa + *b;
	b++;
    }
    return aaa;
}

template <class In>
bool my_equal(In b, In e, In t)
{

    return true;
}

template <class In>
void my_fill(In b, In e, In t)
{
    while (b != e) {
	*b = *t;
	b++;
    }
}

template <class In>
bool my_lexicographic_compare(In b, In e, In b2, In e2)
{
    while (b != e && b2 != e2) {
	for (b; b != e; b++)
	    if (*b >= *b2)
		return false;
	if (*b < *b2)
	    return true;
    }
}
template <class In>
iter my_min_element(In b, In e)
{
    return;
}

#endif

program:

Code:

int main()
{
    // set up some vector and list objects to use 
    int a[] = {1, 2, 3, 4};
    size_t size_a = sizeof(a)/sizeof(*a);

    int b[] = {5, 6, 7};
    size_t size_b = sizeof(b)/sizeof(*b);

    int c[] = {4, 3, 2, 3, 4};
    size_t size_c = sizeof(c)/sizeof(*c);

    vector<int> va(a, a + size_a);
    vector<int> vb(b, b + size_b);
    vector<int> vc(c, c + size_c);

    list<int> la(a, a + size_a);
    list<int> lb(b, b + size_b);

    // test my_accumulate 
    cout << "test my_accumulate:\n";
    cout << "  The sum of the elements in va is "
         << my_accumulate(va.begin(), va.end(), 0) << endl;
    cout << "  The sum of the elements in lb is "
         << my_accumulate(lb.begin(), lb.end(), 0) << endl;

    // test my_equal
    cout << "\ntest my_equal:\n";
    if (my_equal(va.begin(), va.end(), vb.begin()))
        cout << "  va and vb are equal\n";
    else
        cout << "  va and vb are not equal\n";

    if (my_equal(va.begin(), va.end(), va.begin()))
        cout << "  va equals itself\n";
    else
        cout << "  va and lb are not equal\n";

    // test my_fill
    cout << "\ntest my_fill:\n";
    cout << "  original va: " ;
    my_copy(va.begin(), va.end(), ostream_it(cout, " "));
    cout << endl;

    my_fill(va.begin(), va.end(), 30);
    cout << "  modified va: ";
    my_copy(va.begin(), va.end(), ostream_it(cout, " "));
    cout << endl;

    // test my_lexicographic_compare
    cout << "\ntest my_lexicographic_compare:\n";

    if (my_lexicographic_compare(la.begin(), la.end(), lb.begin(), lb.end()))
        cout << "  la is less than lb\n";
    else
        cout << "  la is not less than lb\n";

    if (my_lexicographic_compare(va.begin(), va.end(), vb.begin(), vb.end()))
        cout << "  va is less than vb\n";
    else
        cout << "  va is not less than vb\n";

    // test my_min_element
    cout << "\ntest my_min_element:\n";
    cout << "  the smallest element of vc is "
         << *my_min_element(vc.begin(), vc.end())
         << endl;

    return 0;

}

sorry i need to keep the my_(name) cuz the project description tells me to do it like that...

Download UnitTest++ and write some automated unit tests to verify your code.

Seconded, you definitely need some more unit tests!

Nested loops for an algorithm that is O(n+m) in the standard library should ring warning bells, as should the fact that b2 is never incremened, as should the fact that not all code paths return a value.
In short, delete my_lexicographic_compare and start it over. Also try and do it without using <=, >, or >=. You should only need < to compare the items.
The SC++L source code can show you how it's done.

Originally Posted by iMalc

Seconded, you definitely need some more unit tests!

Nested loops for an algorithm that is O(n+m) in the standard library should ring warning bells, as should the fact that b2 is never incremened, as should the fact that not all code paths return a value.
In short, delete my_lexicographic_compare and start it over. Also try and do it without using <=, >, or >=. You should only need < to compare the items.
The SC++L source code can show you how it's done.

hows this:

Code:

bool my_lexicographic_compare(In b, In e, In b2, In e2)

    while (b != e)
	{
	    if (*b2 < b || b2 == e2)
		return false
		else if (*b < *b2)
		    return true;
	    b++;
	    b2++;
	}
return (b2 != e2);

also i tried the my_equal:

Code:

{
    {
	while (b != t)
	    {
		if (*b != *e)   
		    return false;
		++b; 
		++e;
	    }
	return true;
    }

whats wrong with this piece of code? its giving me a compilation error saying "expected constructor, deconstructer, or type conversion before my_min_element"

Code:

template <class In>
iter my_min_element(In b, In e)
{
    iter lowest = b;
    if (b == e)
	return e;
    while (++b != e)
	if (*b < *lowest)
	    lowest = b;
    return lowest;
}

for the lexicographical compare, its giving me an error for the second line: no match for 'operator< '

Code:

template <class In>
bool my_lexicographic_compare(In b, In e, In b2, In e2)
{
    while (b != e)
	{
	    if (*b2 < b || b2 == e2)
		return false;
		else if (*b < *b2)
		    return true;
	    b++;
	    b2++;
	}
    return (b2 != e2);
}

Code:

template <class In>
In my_min_element(In b, In e)
{
    In lowest = b;
    if (b == e)
        return e;
    while (++b != e)
        if (*b < *lowest)
            lowest = b;
    return lowest;
}

template <class In>
bool my_lexicographic_compare(In b, In e, In b2, In e2)
{
    while (b != e)
    {
        if (*b2 < *b || b2 == e2)
            return false;
        else if (*b < *b2)
            return true;
        b++;
        b2++;
    }
    return (b2 != e2);
}

ok..im just getting a compilation error for just one algorithm

Code:

template <class In>
void my_fill(In b, In e, In t)
{
    while (b != e) 
       *b++ = t;
}

the compiler's complaint is referring to the line where my_fill is called in the main function, it is saying "there is no matching call to my_fill"

Originally Posted by jewelz

ok..im just getting a compilation error for just one algorithm

Code:

template <class In>
void my_fill(In b, In e, In t)
{
    while (b != e) 
       *b++ = t;
}

the compiler's complaint is referring to the line where my_fill is called in the main function, it is saying "there is no matching call to my_fill"

That's because you're telling it that b, e, and t are all the same type. Unless you were to try and fill the container with iterators to that type of container, then it isn't going to work.
You need to either have two template types for that function, or use something like typename In::value_type t.