No Duplicates

[stoneJax]

I created two for loops to check for and remove any duplicates string in an array. I feel like the for loops are good and maybe there is something wrong with the way I am using the remove function.

 #include <iostream>
#include <string>
#include <vector>
#include "ArraySet.h"

using std::cout;
using std::endl;
using std::string;

void displaySet(ArraySet<std::string>& set)
{
	cout << "The set contains " << set.getCurrentSize()
		<< " items:" << endl;
	std::vector<string> setItems = set.toVector();
	
	int numberOfEntries = (int)setItems.size();
	for (int i = 0; i < numberOfEntries; i++)
	{
		cout << setItems[i] << " ";
	}  // end for
	cout << endl << endl;
}  // end displayset

void setTester(ArraySet<string>& set)
{
	cout << "isEmpty: returns " << set.isEmpty()
		<< "; should be 1 (true)" << endl;
	displaySet(set);

	std::string items[] = { "one", "two", "three", "two", "five", "six" };
	cout << "Add 6 items to the set: " << endl;
	for (int i = 0; i < 6; i++)
	{
		set.add(items[i]);
	}  // end for

	displaySet(set);
	

//************ Created for loops  ************************************************
	std::string firstItem;
	for (int i = 0; i < 6; i++)
	{
		firstItem = items[i];
		for (int i = 1; i <= 6; i++) 
		{

			if (firstItem == items[i])
				set.remove(items[i]);
		}
	}  // end for
	cout << endl << endl;



	displaySet(set);

	cout << "After clearing the set, ";
	set.clear();
	cout << "isEmpty: returns " << set.isEmpty()
		<< "; should be 1 (true)" << endl;
} // end setTester

int main()
{
	ArraySet<std::string> set;
	cout << "Testing the Array-Based set:" << endl;
	cout << "The initial set is empty." << endl;
	setTester(set);
	cout << "All done!" << endl;

	return 0;
} // end main






template<class ItemType>
class ArraySet : public SetInterface<ItemType>
{
private:
	static const int DEFAULT_CAPACITY = 6; // Small size to test for a full bag
	ItemType items[DEFAULT_CAPACITY];      // Array of bag items
	int itemCount;                         // Current count of bag items 
	int maxItems;                          // Max capacity of the bag

	int getIndexOf(const ItemType& target) const;

public:
	ArraySet();
	int getCurrentSize() const;
	bool isEmpty() const;
	bool add(const ItemType& newEntry);
	bool remove(const ItemType& anEntry);
	void clear();
	bool contains(const ItemType& anEntry) const;
	std::vector<ItemType> toVector() const;
}; // end ArrayBag







bool ArraySet<ItemType>::remove(const ItemType & anEntry)
{
	int locatedIndex = getIndexOf(anEntry);
	bool canRemoveItem = !isEmpty() && (locatedIndex > -1);
	if (canRemoveItem)
	{
		itemCount--;
		items[locatedIndex] = items[itemCount];
	}  // end if

	return canRemoveItem;
}  // end remove

[nuderobmonkey]

At line 45, here you iterate till the 7th element but you only have 6.
And at line 44 you could use a reference, because this assignment forces a copy.

[stoneJax]

I made the changes. The reference I did feels redundant so not sure if i did it right. Also, the program seems to be removing everything in the array.

std::string& firstItem(items[0]);
	for (int i = 0; i < 6; i++)
	{
		firstItem = items[i];
		for (int i = 1; i < 6; i++) 
		{

			if (firstItem == items[i])
				set.remove(items[i]);
		}
	}  // end for
	cout << endl << endl;

[nuderobmonkey]

Try this:

for ( int i = 0; i < 6; i++ )
{
    std::string & firstItem = items[i];
    for (int k = i+1; k < 6; k++ )
    {
        if (firstItem == items[k])
            set.remove(items[k])
    }
}

[stoneJax]

That seems to be working now for the most part, unless I change all the elements in the array so they are the same. Then it removes all of them instead of leaving one.

[nuderobmonkey]

There was a skipping problem at our previous inner iteration. And we have to consider that each remove will shrink the size of the set.
Here the next try:

for ( int i = 0; i < set.size(); i++ )
{
    std::string & firstItem = items[i];
    for (int k = i+1; k < set.size();  /*empty*/ )
    {
        if (firstItem == items[k])
            set.remove(items[k])
        else
            k++;
    }
}

*edited

[dhayden]

One problem here is that you're using a priori knowledge of what's in the set. Try writing a function to remove duplicates WITHOUT using the items vector.

You'll quickly discover that there's no easy way to do it since you have no way to iterate through the items in an ArraySet. You have to use toVector() to create a vector so you can go through them.

Once you have the vector, a simple way to remove duplicates is:

create an empty set S
for each string str in the vector {
    if ( S contains str) {
        remove str from the ArraySet
    } else {
        insert str into S
    }
}

[stoneJax]

I'm sorry. I not following the pseudocode here.

[dhayden]

The idea is to keep a set of the items that you know are in the ArraySet. Then, if you see a string that you know is already in the set, then that means there is a duplicate, so you remove one instance of the string. Does that help?

[stoneJax]

The logic makes sense. I just need to get more grounded in the code.

Thank you.

[dhayden]

Here is a reference for std::set: http://www.cplusplus.com/reference/set/set/
You must #include <set> at the top of your program.

To create a set of strings:
std::set<std::string> myset;

To check if some string is in the set:

if (myset.find(someString) != myset.end()) {
    // It's in the set
} else {
    // it's not in the set
}

To insert some string into the set:
myset.insert(someString);