Реальное время отсортировано по значению, автоматическое удаление, ограниченная коллекция?

Question

Я потратил некоторое время, чтобы попытаться сделать коллекцию, которая:
1) отсортировано по значению (не по ключу)
2) сортируется при каждом добавлении или изменении элемента
3) имеет фиксированный размер и автоматически отбрасывает самый маленький / самый большой элемент в зависимости от способа сортировки
4) безопасная нить

Так что 3) и 4) я думаю, что это вполне нормально. Для 1) и 2) это было немного сложнее. Я потратил довольно много времени на этот поток , экспериментируя с другим образцом, но одна большая проблема заключается в том, что коллекция сортируется только один раз при вставке объекта.

В любом случае, я пытаюсь реализовать свою собственную коллекцию, которая работает (не следует использовать для больших данных, поскольку они сортируются довольно часто), но я не очень доволен дизайном. Особенно в том факте, что мои объекты-значения ограничены быть Observable (что хорошо), но не сопоставимы, поэтому мне пришлось использовать для этого грязный экземпляр instanceof +.

Любое предложение, чтобы улучшить это?

Вот код:

    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);
            }

        }
    }

И другой класс для тестирования:

    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

Вот обновленная версия. Все еще не совсем уверен, что это безопасная тема, но инструмент findbugs не дал столь полезных советов. Также для сравнения: я не хочу ограничивать пользователя в разработке собственного компаратора, я хочу, чтобы все было просто.

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 2

Вы можете иметь интерфейс маркера

public interface ComparableObservable extends Observable, Comparable {
}

, а затем изменить

SortedDiscardingSyncArray<K, V extends Observable>

до

SortedDiscardingSyncArray<K, V extends ComparableObservable>

, чтобы избежать явного приведения.

Кроме этого, код довольно многословен, и я не следовал ему полностью. Я также предложил бы взглянуть на библиотеку гуавы или (apache) commons-collection, чтобы узнать, сможете ли вы найти что-то повторно используемое.

Answer 3

Вы можете написать общие шаблоны с несколькими границами. Поэтому измените ваше объявление <K, V extends Observable> на <K, V extends Observable & Comparable<V>>, и тогда вы сможете рассматривать V так, как будто он реализует оба интерфейса, без в противном случае пустого и бесполезного интерфейса.

Еще несколько вещей: выберите соглашение об именах и придерживайтесь его. Я использую то, что имя, такое как MAX_CAPACITY, будет использоваться для поля static final (то есть константа, такая как значение по умолчанию), и что эквивалентное поле экземпляра будет maxCapacity Имена, такие как mAX_CAPACITY, будут быть прямо вне вопроса.

См .: Соглашения Oracle о присвоении имен для Java

Вместо использования перечисления ComparisonWay я бы взял пользовательский Comparator. Гораздо более гибок и не воспроизводит то, что уже существует.

См .: Документация API Comparator

Ваш код, как написано, не является потокобезопасным. В частности, наблюдаемый элемент, вызывающий несинхронизированный метод update, может, таким образом, вызывать sortArray без получения надлежащей блокировки. FindBugs - отличный инструмент, который улавливает множество подобных проблем.

Ваш ObservableSample на самом деле не следует передовым методам в отношении того, как он реализует Comparable, в том смысле, что он действительно не сравнивает значения данных, а вместо этого hashCode. Хэш-код является по существу произвольным, и коллизии вполне возможны. Кроме того, интерфейс Comparable запрашивает, чтобы вы, как правило, были «согласованы с Equals», для чего вам также может потребоваться взглянуть на документацию для метода equals класса Object

Да, это звучит как большая работа, но если вы пройдете через это и сделаете это правильно, вы сэкономите изумительное количество усилий по отладке в будущем. Если вы не сделаете это должным образом и в соответствии со спецификацией, вы обнаружите, что, когда вы помещаете это в Set s или Map s, ваши ключи или значения странным образом исчезают, появляются вновь или ударяются. И это будет зависеть от того, какую версию Java вы используете, потенциально!

Answer 4

Коллекции сложно написать, возможно, вам стоит поискать существующую реализацию.

Попробуйте проверить ImmutableSortedSet из Гуавы.