Список отсортированных массивов в Java

Ответ 1

Минималистическое решение

Вот "минимальное" решение.

class SortedArrayList<T> extends ArrayList<T> {

    @SuppressWarnings("unchecked")
    public void insertSorted(T value) {
        add(value);
        Comparable<T> cmp = (Comparable<T>) value;
        for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--)
            Collections.swap(this, i, i-1);
    }
}

Вставка выполняется в линейном времени, но это будет то, что вы получили бы с помощью ArrayList в любом случае (все элементы справа от вставленного элемента должны были бы сдвинуться так или иначе).

Вставка чего-то несопоставимого результата в ClassCastException. (Это подход, сделанный PriorityQueue: приоритетная очередь, основанная на естественном упорядочении, также не позволяет вставлять несопоставимые объекты ( это может привести к ClassCastException).

Переопределение List.add

Обратите внимание, что переопределение List.add (или List.addAll в этом отношении) для вставки элементов в отсортированном виде будет прямым нарушением спецификации интерфейса. Что вы могли бы сделать, это переопределить этот метод, чтобы выбросить UnsupportedOperationException.

Из документов List.add:

boolean add(E e)
    добавляет указанный элемент в конец этого списка (необязательная операция).

То же рассуждение применяется для обеих версий add, обе версии addAll и set. (Все из них являются необязательными операциями в соответствии с интерфейсом списка.)

Некоторые тесты

SortedArrayList<String> test = new SortedArrayList<String>();

test.insertSorted("ddd");    System.out.println(test);
test.insertSorted("aaa");    System.out.println(test);
test.insertSorted("ccc");    System.out.println(test);
test.insertSorted("bbb");    System.out.println(test);
test.insertSorted("eee");    System.out.println(test);

.... печатает:

[ddd]
[aaa, ddd]
[aaa, ccc, ddd]
[aaa, bbb, ccc, ddd]
[aaa, bbb, ccc, ddd, eee]

Ответ 2

Используйте java.util.PriorityQueue.

Ответ 3

Посмотрите SortedList

Этот класс реализует отсортированный список. Он построен с помощью компаратора, который может сравнивать два объекта и сортировать объекты соответственно. Когда вы добавляете объект в список, он вставлен в нужное место. Объект, равный в соответствии с компаратором, будет в списке в том порядке, в котором они были добавлены в этот список. Добавьте только объекты, которые сравнивает компаратор.

Когда список уже содержит объекты, которые равны в соответствии с компаратором, новый объект будет вставлен сразу после этих других объектов.

Ответ 4

Вы можете попробовать Guava TreeMultiSet.

 Multiset<Integer> ms=TreeMultiset.create(Arrays.asList(1,2,3,1,1,-1,2,4,5,100));
 System.out.println(ms);

Ответ 5

Списки обычно сохраняют порядок добавления элементов. Вам определенно нужен список, или будет отсортированный набор (например, TreeSet<E>) для вас? В принципе, вам нужно сохранить дубликаты?

Ответ 6

Это может быть слишком тяжело для вас, но GlazedLists имеет SortedList, который идеально подходит для использования в качестве модели таблицы или JList

Ответ 7

Aioobe-подход - это путь. Я хотел бы предложить следующее улучшение по сравнению с его решением.

class SortedList<T> extends ArrayList<T> {

    public void insertSorted(T value) {
        int insertPoint = insertPoint(value);
        add(insertPoint, value);
    }

    /**
     * @return The insert point for a new value. If the value is found the insert point can be any
     * of the possible positions that keeps the collection sorted (.33 or 3.3 or 33.).
     */
    private int insertPoint(T key) {
        int low = 0;
        int high = size() - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = (Comparable<T>) get(mid);
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else {
                return mid; // key found
            }
        }

        return low;  // key not found
    }
}

Решение aioobe становится очень медленным при использовании больших списков. Используя то, что список отсортирован, позволяет найти точку вставки для новых значений с помощью двоичного поиска.

Я бы также использовал композицию над наследованием, что-то вроде строк

SortedList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Ответ 8

Вы можете подклассифицировать ArrayList и вызвать Collections.sort(this) после добавления любого элемента - для этого вам нужно будет переопределить две версии add и два addAll.

Производительность не будет такой хорошей, как более разумная реализация, которая вставляла бы элементы в нужное место, но выполняла бы эту работу. Если добавление к списку происходит редко, стоимость, амортизированная по всем операциям в списке, должна быть низкой.

Ответ 9

Я думаю, что выбор между SortedSets/Lists и "нормальными" сортируемыми коллекциями зависит от того, нужна ли вам сортировка только для целей презентации или почти во всех точках во время выполнения. Использование сортированной коллекции может быть намного дороже, потому что сортировка выполняется каждый раз, когда вы вставляете элемент.

Если вы не можете выбрать коллекцию в JDK, вы можете взглянуть на Коллекции сообщества Apache

Ответ 10

Поскольку предлагаемые в настоящее время реализации, которые реализуют отсортированный список, разбивая API Collection, имеют собственную реализацию дерева или что-то подобное, я был любопытным, как будет выполняться реализация на основе TreeMap. (Especialy, поскольку TreeSet также работает на TreeMap)

Если кто-то заинтересован в этом, он также может свободно смотреть в него:

TreeList

Его часть основной библиотеки, вы можете добавить ее через зависимость от Maven, конечно. (Лицензия Apache)

В настоящее время реализация, похоже, довольно хорошо сравнивается с тем же уровнем, что и для класса Guava SortedMultiSet и для TreeList библиотеки Apache Commons.

Но я был бы счастлив, если бы не только меня проверили реализацию, чтобы убедиться, что я не пропустил что-то важное.

С уважением!

Ответ 11

У меня была та же проблема. Поэтому я взял исходный код java.util.TreeMap и написал IndexedTreeMap. Он реализует мою собственную IndexedNavigableMap:

public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
   K exactKey(int index);
   Entry<K, V> exactEntry(int index);
   int keyIndex(K k);
}

Реализация основана на обновлении весов node в красно-черном дереве при его изменении. Вес - это число дочерних узлов ниже заданного node, плюс один. Например, когда дерево поворачивается влево:

    private void rotateLeft(Entry<K, V> p) {
    if (p != null) {
        Entry<K, V> r = p.right;

        int delta = getWeight(r.left) - getWeight(p.right);
        p.right = r.left;
        p.updateWeight(delta);

        if (r.left != null) {
            r.left.parent = p;
        }

        r.parent = p.parent;


        if (p.parent == null) {
            root = r;
        } else if (p.parent.left == p) {
            delta = getWeight(r) - getWeight(p.parent.left);
            p.parent.left = r;
            p.parent.updateWeight(delta);
        } else {
            delta = getWeight(r) - getWeight(p.parent.right);
            p.parent.right = r;
            p.parent.updateWeight(delta);
        }

        delta = getWeight(p) - getWeight(r.left);
        r.left = p;
        r.updateWeight(delta);

        p.parent = r;
    }
  }

updateWeight просто обновляет весы до корня:

   void updateWeight(int delta) {
        weight += delta;
        Entry<K, V> p = parent;
        while (p != null) {
            p.weight += delta;
            p = p.parent;
        }
    }

И когда нам нужно найти элемент по индексу, это реализация, использующая вес:

public K exactKey(int index) {
    if (index < 0 || index > size() - 1) {
        throw new ArrayIndexOutOfBoundsException();
    }
    return getExactKey(root, index);
}

private K getExactKey(Entry<K, V> e, int index) {
    if (e.left == null && index == 0) {
        return e.key;
    }
    if (e.left == null && e.right == null) {
        return e.key;
    }
    if (e.left != null && e.left.weight > index) {
        return getExactKey(e.left, index);
    }
    if (e.left != null && e.left.weight == index) {
        return e.key;
    }
    return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1);
}

Также очень удобно найти индекс ключа:

    public int keyIndex(K key) {
    if (key == null) {
        throw new NullPointerException();
    }
    Entry<K, V> e = getEntry(key);
    if (e == null) {
        throw new NullPointerException();
    }
    if (e == root) {
        return getWeight(e) - getWeight(e.right) - 1;//index to return
    }
    int index = 0;
    int cmp;
    index += getWeight(e.left);

    Entry<K, V> p = e.parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        while (p != null) {
            cmp = cpr.compare(key, p.key);
            if (cmp > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    } else {
        Comparable<? super K> k = (Comparable<? super K>) key;
        while (p != null) {
            if (k.compareTo(p.key) > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    }
    return index;
}

Результат этой работы можно найти в http://code.google.com/p/indexed-tree-map/

TreeSet/TreeMap (а также их индексированные копии из проекта с индексированной древовидной картой) не позволяют дублировать ключи, вы можете использовать 1 ключ для массива значений. Если вам нужен SortedSet с дубликатами, используйте TreeMap со значениями в виде массивов. Я бы это сделал.