creating java generic data structure

Question

I am building a data structure to learn more about java. I understand this program might be useless.

Here's what I want. I want to create a data structure that store smallest 3 values. if value is high, then ignore it. When storing values than I also want to put them in correct place so I don't have to sort them later. I can enter values by calling the add method.

so let's say I want to add 20, 10, 40, 30 than the result will be [10,20,30]. note I can only hold 3 smallest values and it store them as I place them.

I also understand that there are a lot of better ways for doing this but again this is just for learning purposes.

Question: I need help creating add method. I wrote some code but I am getting stuck with add method. Please help.

My Thinking: we might have to use a Iterator in add method?

public class MyJavaApp {
    public static void main(String[] args){
        MyClass<Integer> m = new MyClass<Integer>(3);

        m.add(10);
        m.add(20);
        m.add(30);
        m.add(40);

    }
}


public class MyClass<V extends Comparable<V>> {

    private V v[];

    public MyClass(int s){
        this.v = (V[])new Object[s];
    }


    public void add(V a){

    }
}

tharindu_DG · Accepted Answer · 2015-11-13 07:27:03Z

Here is a rough sketch of the add method you have to implement. You have to use the appropriate implementation of the compareTo method when comparing elements.

public void add(V a){
    V temp = null;
    if(a.compareTo( v[0]) == -1 ){
        /*
           keeping the v[0] in a temp variable since, v[0] could be the second 
           smallest value or the third smallest value.
           Therefore call add method again to assign it to the correct
           position.
        */
        temp = v[0];  
        v[0] = a;
        add(temp);
    }else if(a.compareTo(v[0]) == 1 && a.compareTo(v[1]) == -1){
        temp = v[1];
        v[1] = a;
        add(temp);
    }else if(a.compareTo(v[1]) == 1 && a.compareTo(v[2]) == -1){
        temp = v[2];
        v[2] = a;
        add(temp);
    }
}

Therefore the v array will contain the lowerest elements.

Hope this helps.

dave · Accepted Answer · 2015-11-13 05:22:09Z

A naive, inefficient approach would be (as you suggest) to iterate through the values and add / remove based on what you find:

public void add(Integer a)
{
    // If fewer than 3 elements in the list, add and we're done.
    if (m.size() < 3)
    {
        m.add(a);
        return;
    }
    // If there's 3 elements, find the maximum.
    int max = Integer.MIN_VALUE;
    int index = -1;
    for (int i=0; i<3; i++) {
        int v = m.get(i);
        if (v > max) {
            max = v;
            index = i;
        }
    }
    // If a is less than the max, we need to add it and remove the existing max.
    if (a < max) {
        m.remove(index);
        m.add(a);
    }
}

Note: this has been written for Integer, not a generic type V. You'll need to generalise. It also doesn't keep the list sorted - another of your requirements.

mprivat · Accepted Answer · 2015-11-13 08:08:30Z

Here's an implementation of that algorithm. It consists of looking for the right place to insert. Then it can be optimized for your requirements:

Don't bother looking past the size you want
Don't add more items than necessary

Here's the code. I added the toString() method for convenience. Only the add() method is interesting. Also this implementation is a bit more flexible as it respects the size you give to the constructor and doesn't assume 3.

I used a List rather than an array because it makes dealing with generics a lot easier. You'll find that using an array of generics makes using your class a bit more ugly (i.e. you have to deal with type erasure by providing a Class<V>).

import java.util.*;

public class MyClass<V extends Comparable<V>> {

    private int s;
    private List<V> v;

    public MyClass(int s) {
        this.s = s;
        this.v = new ArrayList<V>(s);
    }


    public void add(V a) {
        int i=0;
        int l = v.size();

        // Find the right index
        while(i<l && v.get(i).compareTo(a) < 0) i++;

        if(i<s) {
            v.add(i, a);

            // Truncate the list to make sure we don't store more values than needed
            if(v.size() > s) v.remove(v.size()-1);
        }
    }

    public String toString() {
        StringBuilder result = new StringBuilder();
        for(V item : v) {
            result.append(item).append(',');
        }

        return result.toString();
    }
}

Collectives™ on Stack Overflow

creating java generic data structure

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related