Real time sorted by value, auto-discarding, bounde

Question

I spent some time to try to make a collection that:
1) is sorted by value (not by key)
2) is sorted each time an element is added or modified
3) is fixed size and discard automatically smallest/biggest element depending of the sort way
4) is safe thread

So 3) and 4) I think it is quite ok. For 1) and 2) it was a bit more tricky. I spent quite a long time on this thread, experimenting the different sample, but one big issue is that the collection are sorted only once when object are inserted.

Anyway, I try to implement my own collection, which is working (shouldn't be used for huge data as it is sorted quite often) but I'm not so happy with the design. Especially in the fact that my value objects are constrained to be Observable (which is good) but not comparable so I had to use a dirty instanceof + exception for this.

Any sugestion to improve this ?

Here is the code:

    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    import java.util.Observable;
    import java.util.Observer;

    public class SortedDiscardingSyncArray<K, V extends Observable> implements Observer {

        // Comparison way (ascendent or descendant)
        public static enum ComparisonWay
        {
            DESC,
            ASC;
        }

        // this is backed by a List (and ArrayList impl)
        private List<ArrayElement> array;

        // Capacity, configurable, over this limit, an item will be discarded
        private int MAX_CAPACITY = 200;

        // default is descending comparison
        private ComparisonWay compareWay = ComparisonWay.DESC;

        public SortedDiscardingSyncArray(ComparisonWay compareWay, int mAX_CAPACITY) {
            super();
            this.compareWay = compareWay;
            MAX_CAPACITY = mAX_CAPACITY;
            array = new ArrayList <ArrayElement>(MAX_CAPACITY);
        }

        public SortedDiscardingSyncArray(int mAX_CAPACITY) {
            super();
            MAX_CAPACITY = mAX_CAPACITY;
            array = new ArrayList<ArrayElement>(MAX_CAPACITY);
        }

        public SortedDiscardingSyncArray() {
            super();
            array = new ArrayList <ArrayElement>(MAX_CAPACITY);
        }

        public boolean put(K key, V value)
        {
            try {
                return put (new ArrayElement(key, value, this));
            } catch (Exception e) {
                e.printStackTrace();
                return false;
            } 
            finally
            {
                sortArray();
            }

        }

        private synchronized boolean put(ArrayElement ae)
        {
            if (array.size() < MAX_CAPACITY)
            {
                return array.add(ae);
            }
            // check if last one is greater/smaller than current value to insert
            else if (ae.compareTo(array.get(MAX_CAPACITY-1)) < 0)
            {
                array.remove(MAX_CAPACITY - 1);
                return array.add(ae);
            }
            // else we don't insert
            return false;
        }

        public V getValue (int index)
        {
            return array.get(index).getValue();
        }

        public V getValue (K key)
        {
            for (ArrayElement ae : array)
            {
                if (ae.getKey().equals(key)) return ae.getValue();
            }
            return null;
        }

        public K getKey (int index)
        {
            return array.get(index).getKey();
        }

        private void sortArray()
        {
            Collections.sort(array);
        }

        public synchronized void setValue(K key, V newValue) {
            for (ArrayElement ae : array)
            {
                if (ae.getKey().equals(key)) 
                {
                    ae.setValue(newValue);
                    return;
                }
            }
        }
        public int size() {
            return array.size();
        }

        @Override
        public void update(java.util.Observable arg0, Object arg1) {
            sortArray();        
        }

        public static void main(String[] args) {

            //  some test on the class
            SortedDiscardingSyncArray<String, ObservableSample> myData = new SortedDiscardingSyncArray<String, ObservableSample>(ComparisonWay.DESC, 20);

            String Ka = "Ka";
            String Kb = "Kb";
            String Kc = "Kc";
            String Kd = "Kd";
            myData.put(Ka, new ObservableSample(0));
            myData.put(Kb, new ObservableSample(3));
            myData.put(Kc, new ObservableSample(1));
            myData.put(Kd, new ObservableSample(2));


            for (int i=0; i < myData.size(); i++)
            {
                System.out.println(myData.getKey(i).toString() + " - " + myData.getValue(i).toString());
            }
            System.out.println("Modifying data...");
            myData.getValue(Kb).setValue(12);
            myData.getValue(Ka).setValue(34);
            myData.getValue(Kd).setValue(9);
            myData.getValue(Kc).setValue(19);
            for (int i=0; i < myData.size(); i++)
            {
                System.out.println(myData.getKey(i).toString() + " - " + myData.getValue(i).toString());
            }
        }

        private class ArrayElement implements Comparable <ArrayElement> {

            public ArrayElement(K key, V value, Observer obs) throws Exception {
                super();
                // don't know how to handle that case
                // maybe multiple inheritance would have helped here ?
                if (! (value instanceof Comparable)) throw new Exception("Object must be 'Comparable'");
                this.key = key;
                this.value = value;
                value.addObserver(obs);
            }

            public String toString()
            {
                StringBuffer sb = new StringBuffer();
                sb.append(key);
                sb.append(" - ");
                sb.append(value);
                return sb.toString();
            }

            private K key;
            private V value;

            public K getKey() {
                return key;
            }

            public V getValue() {
                return value;
            }

            public synchronized void setValue(V value) {
                this.value = value;
            }

            @SuppressWarnings("unchecked")
            @Override
            public int compareTo(ArrayElement o) {

                int c;
                if (compareWay == ComparisonWay.DESC) c = ((Comparable<V>) o.getValue()).compareTo(this.getValue());
                else c = ((Comparable<V>) this.getValue()).compareTo(o.getValue());
                if (c != 0) {
                    return c;
                }
                Integer hashCode1 = o.getValue().hashCode();
                Integer hashCode2 = this.getValue().hashCode();
                // we don't check the compare way for hash code (useless ?)
                return hashCode1.compareTo(hashCode2);
            }

        }
    }

And the other class for testing purpose:

    import java.util.Observable;

    public class ObservableSample extends Observable implements Comparable <ObservableSample>
    {
        private Integer value = 0;

        public ObservableSample(int value) {
            this.value = value;
            setChanged();   
            notifyObservers();
        }

        public String toString()
        {
            return String.valueOf(this.value);
        }

        public void setValue(Integer value) {
            this.value = value;
            setChanged();   
            notifyObservers();
        }

        public Integer getValue() {
            return value;
        }

        @Override
        public int compareTo(ObservableSample o) {
            int c;
            c = (this.getValue()).compareTo(o.getValue());
            if (c != 0) {
                return c;
            }
            Integer hashCode1 = o.getValue().hashCode();
            Integer hashCode2 = this.getValue().hashCode();
            // we don't check the compare way for hash code (useless ?)
            return hashCode1.compareTo(hashCode2);
        }
    }

Answer 1

You can have a marker interface

public interface ComparableObservable extends Observable, Comparable {
}

and then change

SortedDiscardingSyncArray<K, V extends Observable>

to

SortedDiscardingSyncArray<K, V extends ComparableObservable>

to avoid the explicit cast.

Other than that the code is quite verbose and I didn't follow it completely. I would also suggest having a look at guava or (apache) commons-collections library to explore if you can find something reusable.

Answer 2

You can write generic wildcards with multiple bounds. So change your declaration of <K, V extends Observable> to <K, V extends Observable & Comparable<V>> and then you can treat V as if it implements both interfaces, without an otherwise empty and useless interface.

Another few things: Pick a naming convention, and stick with it. The one I use is that a name such as MAX_CAPACITY would be used for a static final field (i.e. a constant, such as a default) and that the equivalent instance field would be maxCapacity Names such as mAX_CAPACITY would be right out of the question.

See: Oracle's naming conventions for Java

Instead of using a ComparisonWay enum, I would take a custom Comparator. Much more flexible, and doesn't replicate something that already exists.

See: the Comparator API docs

Your code, as written, is not thread safe. In particular an observed element calling the unsynchronized update method may thus invoke sortArray without obtaining the proper lock. FindBugs is a great tool that catches a lot of problems like this.

Your ObservableSample does not really follow good practices with regards to how it implements Comparable, in that it does not really compare data values but instead the hashCode. The hashCode is essentially arbitrary and collisions are quite possible. Additionally, the Comparable interface requests that usually you should be "consistent with Equals", for which you also might want to take a look at the documentation for the Object class's equals method

Yes, it sounds like a lot of work, but if you go through it and do it right you will save yourself astounding amounts of debugging effort down the road. If you do not do these properly and to the spec, you will find that when you place it in Sets or Maps your keys or values strangely disappear, reappear, or get clobbered. And it will depend on which version of Java you run, potentially!

Answer 3

Here is a version updated. Still not completly sure it is safe thread but findbugs tool didn't give so usefull tips. Also for the comparisonWay, I don't want to constraint the user to develop its own comparator, I want to keep the things simple.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Observable;
import java.util.Observer;

public class SortedDiscardingSyncArray<K, V extends Observable & Comparable<V>> implements Observer {

    // Comparison way (ascendent or descendant)
    public static enum ComparisonWay { DESC, ASC; }

    // this is backed by a List (and ArrayList)
    private List<ArrayElement> array;

    // Capacity, configurable, over this limit, an item will be discarded
    private int maxCapacity = 200;

    // default is descending comparison
    private ComparisonWay compareWay = ComparisonWay.DESC;

    public SortedDiscardingSyncArray(ComparisonWay compareWay, int maxCapacity) {
        super();
        this.compareWay = compareWay;
        this.maxCapacity = maxCapacity;
        array = new ArrayList <ArrayElement>(maxCapacity);
    }

    public SortedDiscardingSyncArray(int maxCapacity) {
        super();
        this.maxCapacity = maxCapacity;
        array = new ArrayList<ArrayElement>(maxCapacity);
    }

    public SortedDiscardingSyncArray() {
        super();
        array = new ArrayList <ArrayElement>(maxCapacity);
    }

    // not synchronized, but calling internal sync put command
    public boolean put(K key, V value)
    {
        try {
            return put (new ArrayElement(key, value, this));
        } catch (Exception e) {
            e.printStackTrace();
            return false;
        } 
        finally
        {
            sortArray();
        }
    }

    private synchronized boolean put(ArrayElement ae)
    {
        if (array.size() < maxCapacity) return array.add(ae);
        // check if last one is greater/smaller than current value to insert
        else if (ae.compareTo(array.get(maxCapacity-1)) < 0)
        {
            array.remove(maxCapacity - 1);
            return array.add(ae);
        }
        // else we don't insert and return false
        return false;
    }

    public V getValue (int index)
    {
        return array.get(index).getValue();
    }

    public V getValue (K key)
    {
        for (ArrayElement ae : array)
        {
            if (ae.getKey().equals(key)) return ae.getValue();
        }
        return null;
    }

    public K getKey (int index)
    {
        return array.get(index).getKey();
    }

    private synchronized void sortArray()
    {
        Collections.sort(array);
    }

    public synchronized void setValue(K key, V newValue) {
        for (ArrayElement ae : array)
        {
            if (ae.getKey().equals(key)) 
            {
                ae.setValue(newValue);
                return;
            }
        }
    }

    public int size() {
        return array.size();
    }

    @Override
    public void update(java.util.Observable arg0, Object arg1) {
        sortArray();        
    }

    public static void main(String[] args) {
        //  some test on the class
        SortedDiscardingSyncArray<String, ObservableSample> myData = new SortedDiscardingSyncArray<String, ObservableSample>(ComparisonWay.DESC, 20);

        String Ka = "Ka";
        String Kb = "Kb";
        String Kc = "Kc";
        String Kd = "Kd";
        myData.put(Ka, new ObservableSample(0));
        myData.put(Kb, new ObservableSample(3));
        myData.put(Kc, new ObservableSample(1));
        myData.put(Kd, new ObservableSample(2));


        for (int i=0; i < myData.size(); i++)
        {
            System.out.println(myData.getKey(i).toString() + " - " + myData.getValue(i).toString());
        }
        System.out.println("Modifying data...");
        myData.getValue(Kb).setValue(12);
        myData.getValue(Ka).setValue(34);
        myData.getValue(Kd).setValue(9);
        myData.getValue(Kc).setValue(19);
        for (int i=0; i < myData.size(); i++)
        {
            System.out.println(myData.getKey(i).toString() + " - " + myData.getValue(i).toString());
        }
    }

    private class ArrayElement implements Comparable <ArrayElement> {

        public ArrayElement(K key, V value, Observer obs) throws Exception {
            super();
            this.key = key;
            this.value = value;
            value.addObserver(obs);
        }

        public String toString()
        {
            StringBuffer sb = new StringBuffer();
            sb.append(key);
            sb.append(" - ");
            sb.append(value);
            return sb.toString();
        }

        private K key;
        private V value;

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public synchronized void setValue(V value) {
            this.value = value;
        }

        @Override
        public int compareTo(ArrayElement o) {

            int c;
            if (compareWay == ComparisonWay.DESC) c = o.getValue().compareTo(this.getValue());
            else c = this.getValue().compareTo(o.getValue());
            if (c != 0) {
                return c;
            }
            Integer hashCode1 = o.getValue().hashCode();
            Integer hashCode2 = this.getValue().hashCode();
            // we don't check the compare way for hash code (useless ?)
            return hashCode1.compareTo(hashCode2);
        }

    }
}

Answer 4

Collections are difficult to write, maybe you should look for an existing implementation.

Try checking out ImmutableSortedSet from Guava.