CODEWITHSUNDEEP
javaarrayssetadditionsortedset
randomizertech
randomizertech

Reputation: 2329

Problem with adding item to array in an Ordered Set

I am having trouble adding an item to my array set, it should be ordered in ascending order and for some reason I just get to add it and it does not order it.

Here is my code:

public boolean add(AnyType x){
    if(this.contains(x))
        return false;
    else if(this.isEmpty()){
        items[theSize]=x;
        theSize++;
        return true;
    }
    else{
    if( theSize == items.length )
        this.grow();
    //Here goes code for adding
    /*AnyType[] newItems = (AnyType[]) new Comparable[items.length];
    newItems = items;
    for(int i=0;i<theSize;i++)
        if(items[i].compareTo(x)>0){
            newItems[i]=x;
            newItems[i+1]=items[i];
            for(int j=i+1;j<theSize;j++)
                newItems[j]=items[i];
            items = newItems;
            theSize++;
            return true;
        }

    //*/
    items[theSize]=x; //*/
    theSize++;
    return true;
    }
}

The method should not allow an item to repeat so if you try to add something that is already in there, it should return false. If the array is empty just add to items[0] and then I tried to create a new array and once you find an item bigger than the one I'm inputing copy everything into a new array, add the new value, and just add the rest and then make items = newItems; but it did not work. I have been trying for a couple hours now so I just decided to ask for help. I have my SortedSet class defined like this:

public class SortedSet<AnyType extends Comparable> implements Set<AnyType>
{
    private AnyType[] items;
    private int theSize;
    public SortedSet(){
        theSize = 0;
        items = (AnyType[]) new Comparable[5];
    }

I know there are other ways to do this like using TreeMap but it has to be done as an array.

Thanks

Upvotes: 1

Views: 526

Answers (3)

Boro
Boro

Reputation: 7943

I do not see where you are writing the previous values?

Try something like this in the last else. 

            theSize++;
            AnyType[] newItems = new AnyType[theSize];
            for(int i = 0; i < theSize-1; i++)
                if(items[i].compareTo(x) > 0)
                {
                    newItems[i] = x;
                    newItems[i + 1] = items[i];
                    for(int j = i + 2; j < theSize; j++)
                        newItems[j] = items[j-1];
                    items = newItems;
                    return true;
                }
                else
                    newItems[i] = items[i];
            newItems[theSize-1] = x;
            items = newItems;
            return true;

Since I already coded it to make sure it works fine, here is a sample working on Strings. I focused here only on correct adding. The other issues important for the OP were omitted.

import java.util.Arrays;

public class OrderingAddTest
{
    static int theSize = 0;
    static String[] items = new String[theSize];
    public static void main(String[] args)
    {
        add("a");
        add("e");
        add("d");
        add("b");
        add("c");

        System.out.println(Arrays.toString(items)+"\n; items.length="+items.length);
    }

    private static boolean add(String x)
    {
        theSize++;
        String[] newItems = new String[theSize];
        for(int i = 0; i < theSize - 1; i++)
            if(items[i].compareTo(x) > 0)
            {
                newItems[i] = x;
                newItems[i + 1] = items[i];
                for(int j = i + 2; j < theSize; j++)
                    newItems[j] = items[j - 1];
                items = newItems;
                return true;
            }
            else
                newItems[i] = items[i];
        newItems[theSize - 1] = x;
        items = newItems;
        return true;
    }
}

Upvotes: 2

TarunG
TarunG

Reputation: 610

Your items is of the same size as of items, it should be Size+1

I guess you got a problem here

for(int j=i+ 1; j < theSize;j++)

newItems[j]=items[i];

here j is incrementing for sure, but there is no increment operation given for i, so all the newitems in this loop are being assigned the same value

EDIT : 

    int i;

    for(i=0; i < theSize+1 ; i++)
    if(items[i].compareTo(x)>0){
    newItems[i]=x;

    for(;i<theSize + 1; i++)
     newItems[i]=items[i-1];

: do whatever next.

EDIT 2 :

U are doing a wrong thing here also,

items = newItems;

and the previous assigning statement (newItems=items)

you can't equate them as they are not of same size, you can do that if you use Pointer, (Using Pointers here will make this task A LOT easier,)

Upvotes: 1

Benoit Courtine
Benoit Courtine

Reputation: 7064

There is already a native Java class that have theses features: java.util.TreeSet.

In a Set, the same element cannot appear twice. The "add" method returns a boolean: true if the item was added, false if it was already in the set.

TreeSet is an implementation of "SortedSet", that maintain an order on the elements. Your items only have to implement "Comparable".

Upvotes: 1

Related Questions