Asked  7 Months ago    Answers:  5   Viewed   43 times

In Java there are the SortedSet and SortedMap interfaces. Both belong to the Java Collections framework and provide a sorted way to access the elements.

However, in my understanding there is no SortedList in Java. You can use java.util.Collections.sort() to sort a list.

Any idea why it is designed like that?

 Answers

15

List iterators guarantee first and foremost that you get the list's elements in the internal order of the list (aka. insertion order). More specifically it is in the order you've inserted the elements or on how you've manipulated the list. Sorting can be seen as a manipulation of the data structure, and there are several ways to sort the list.

I'll order the ways in the order of usefulness as I personally see it:

1. Consider using Set or Bag collections instead

NOTE: I put this option at the top because this is what you normally want to do anyway.

A sorted set automatically sorts the collection at insertion, meaning that it does the sorting while you add elements into the collection. It also means you don't need to manually sort it.

Furthermore if you are sure that you don't need to worry about (or have) duplicate elements then you can use the TreeSet<T> instead. It implements SortedSet and NavigableSet interfaces and works as you'd probably expect from a list:

TreeSet<String> set = new TreeSet<String>();
set.add("lol");
set.add("cat");
// automatically sorts natural order when adding

for (String s : set) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

If you don't want the natural ordering you can use the constructor parameter that takes a Comparator<T>.

Alternatively, you can use Multisets (also known as Bags), that is a Set that allows duplicate elements, instead and there are third-party implementations of them. Most notably from the Guava libraries there is a TreeMultiset, that works a lot like the TreeSet.

2. Sort your list with Collections.sort()

As mentioned above, sorting of Lists is a manipulation of the data structure. So for situations where you need "one source of truth" that will be sorted in a variety of ways then sorting it manually is the way to go.

You can sort your list with the java.util.Collections.sort() method. Here is a code sample on how:

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

Collections.sort(strings);
for (String s : strings) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

Using comparators

One clear benefit is that you may use Comparator in the sort method. Java also provides some implementations for the Comparator such as the Collator which is useful for locale sensitive sorting strings. Here is one example:

Collator usCollator = Collator.getInstance(Locale.US);
usCollator.setStrength(Collator.PRIMARY); // ignores casing

Collections.sort(strings, usCollator);

Sorting in concurrent environments

Do note though that using the sort method is not friendly in concurrent environments, since the collection instance will be manipulated, and you should consider using immutable collections instead. This is something Guava provides in the Ordering class and is a simple one-liner:

List<string> sorted = Ordering.natural().sortedCopy(strings);

3. Wrap your list with java.util.PriorityQueue

Though there is no sorted list in Java there is however a sorted queue which would probably work just as well for you. It is the java.util.PriorityQueue class.

Nico Haase linked in the comments to a related question that also answers this.

In a sorted collection you most likely don't want to manipulate the internal data structure which is why PriorityQueue doesn't implement the List interface (because that would give you direct access to its elements).

Caveat on the PriorityQueue iterator

The PriorityQueue class implements the Iterable<E> and Collection<E> interfaces so it can be iterated as usual. However, the iterator is not guaranteed to return elements in the sorted order. Instead (as Alderath points out in the comments) you need to poll() the queue until empty.

Note that you can convert a list to a priority queue via the constructor that takes any collection:

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

PriorityQueue<String> sortedStrings = new PriorityQueue(strings);
while(!sortedStrings.isEmpty()) {
    System.out.println(sortedStrings.poll());
}
// Prints out "cat" and "lol"

4. Write your own SortedList class

NOTE: You shouldn't have to do this.

You can write your own List class that sorts each time you add a new element. This can get rather computation heavy depending on your implementation and is pointless, unless you want to do it as an exercise, because of two main reasons:

  1. It breaks the contract that List<E> interface has because the add methods should ensure that the element will reside in the index that the user specifies.
  2. Why reinvent the wheel? You should be using the TreeSet or Multisets instead as pointed out in the first point above.

However, if you want to do it as an exercise here is a code sample to get you started, it uses the AbstractList abstract class:

public class SortedList<E> extends AbstractList<E> {

    private ArrayList<E> internalList = new ArrayList<E>();

    // Note that add(E e) in AbstractList is calling this one
    @Override 
    public void add(int position, E e) {
        internalList.add(e);
        Collections.sort(internalList, null);
    }

    @Override
    public E get(int i) {
        return internalList.get(i);
    }

    @Override
    public int size() {
        return internalList.size();
    }

}

Note that if you haven't overridden the methods you need, then the default implementations from AbstractList will throw UnsupportedOperationExceptions.

Tuesday, June 1, 2021
 
Bono
answered 7 Months ago
86

Do you see anything wrong with the code?

Yes. Why are you adding the three fields together before you compare them?

I would probably do something like this: (assuming the fields are in the order you wish to sort them in)

@Override public int compare(final Report record1, final Report record2) {
    int c;
    c = record1.getReportKey().compareTo(record2.getReportKey());
    if (c == 0)
       c = record1.getStudentNumber().compareTo(record2.getStudentNumber());
    if (c == 0)
       c = record1.getSchool().compareTo(record2.getSchool());
    return c;
}
Tuesday, June 1, 2021
 
Student
answered 7 Months ago
98

Although nobody can really tell you why there is no SortedList<T>, it is possible to discuss why SortedList takes a key and a value. A dictionary maps keys to values. The typical ways to do this are with a binary tree, a hash table, and a list (array), though hash tables are most common because they are O(1) for most operations.

The primary operation that it doesn't support in O(1) is getting the next key in order. If you want to be able to do that, you typically use a binary tree, giving you a sorted dictionary.

If you decide to implement the map as a list, you would keep the elements sorted by key so that lookup is O(lg n), giving you another sorted dictionary -- in the form of a sorted list. Of course the name SortedDictionary was already taken, but SortedList wasn't. I might have called it SortedListDictionary or SortedDictionaryList, but I didn't get to name it.

Friday, July 23, 2021
 
superhero
answered 5 Months ago
34

As @TomasMikula comments in @eckig's (now-deleted) answer, there probably just is not enough demand for an ObservableQueue. If you have a solid use-case, you should consider submitting a feature request.

In the meantime, it's not too hard to create a quick-and-dirty ObservableQueue implementing Queue and adding "observability" by subclassing ObservableListBase and wrapping a Queue implementation. Subclassing ObservableListBase is the "quick" part, but also the "dirty" part because you expose List methods as well as Queue methods; since an arbitrary Queue doesn't have a get(int index) the only way to implement that (that I can see) is to iterate through up to index. Anything that uses get to iterate through the ObservableQueue, regarding it as a List, will run in O(n^2) time. With that caveat, the following should work pretty well:

import java.util.LinkedList;
import java.util.Queue;

import javafx.collections.ObservableListBase;


public class ObservableQueue<E> extends ObservableListBase<E> implements Queue<E> {

    private final Queue<E> queue ;


    /**
     * Creates an ObservableQueue backed by the supplied Queue. 
     * Note that manipulations of the underlying queue will not result
     * in notification to listeners.
     * 
     * @param queue
     */
    public ObservableQueue(Queue<E> queue) {
        this.queue = queue ;
    }

    /**
     * Creates an ObservableQueue backed by a LinkedList.
     */
    public ObservableQueue() {
        this(new LinkedList<>());
    }

    @Override
    public boolean offer(E e) {
        beginChange();
        boolean result = queue.offer(e);
        if (result) {
            nextAdd(queue.size()-1, queue.size());
        }
        endChange();
        return result ;
    }

    @Override
    public boolean add(E e) {
        beginChange() ;
        try {
            queue.add(e);
            nextAdd(queue.size()-1, queue.size());
            return true ;
        } finally {
            endChange();
        }
    }


    @Override
    public E remove() {
        beginChange();
        try {
            E e = queue.remove();
            nextRemove(0, e);
            return e;
        } finally {
            endChange();
        }
    }

    @Override
    public E poll() {
        beginChange();
        E e = queue.poll();
        if (e != null) {
            nextRemove(0, e);
        }
        endChange();
        return e ;
    }

    @Override
    public E element() {
        return queue.element();
    }

    @Override
    public E peek() {
        return queue.peek();
    }

    @Override
    public E get(int index) {
        Iterator<E> iterator = queue.iterator();
        for (int i = 0; i < index; i++) iterator.next();
        return iterator.next();
    }

    @Override
    public int size() {
        return queue.size();
    }

}

You can register ListChangeListeners with this to be notified of modifications to the queue. (Note that if you want to support extractors and update notifications, you'd need to do quite a bit more work...).

import javafx.collections.ListChangeListener.Change;

public class ObservableQueueTest {
    public static void main(String[] args) {
        ObservableQueue<String> oq = new ObservableQueue<>();
        oq.addListener((Change<? extends String> change) -> {
            while (change.next()) {
                if (change.wasAdded()) {
                    System.out.println("Added: "+change.getAddedSubList());
                }
                if (change.wasRemoved()) {
                    System.out.println("Removed: "+change.getRemoved());
                }
                if (change.wasUpdated()) {
                    System.out.println("Updated: "+oq.subList(change.getFrom(), change.getTo()));
                }
                if (change.wasReplaced()) {
                    System.out.println("Replaced");
                }
            }
        });

        oq.offer("One");
        oq.offer("Two");
        oq.offer("Three");

        System.out.println("Peek: "+oq.peek());
        System.out.println("Remove...");
        System.out.println(oq.remove());

        System.out.println("Element:");
        System.out.println(oq.element());

        System.out.println("get(1): "+oq.get(1));

        System.out.println("Poll: ");
        System.out.println(oq.poll());

        System.out.println("Poll again:");
        System.out.println(oq.poll());

        System.out.println("Poll should return null:");
        System.out.println(oq.poll());

        System.out.println("Element should throw exception:");
        System.out.println(oq.element());
    }

}
Monday, August 16, 2021
 
Daveel
answered 4 Months ago
59

You should start by reading the JavaDoc of Comparator.compare() to understand what that "contract" is:

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y.

In normal terms it says that if "x is greater than y, y must be smaller than x". Sounds obvious, but is not the case in your comparator:

  • In your case you violate it when two Users have checkMatchConditions false, in which case compare(u1, u2) and compare(u2, u1) both return 1. Hence, there are cases where u1 is greater than u2, and u2 is greater than u1, which is a violation.
  • Similarely, if both Users have checkMatchConditions true, and their lastMatchDates are both null, they will also violate the contract.
  • In addition, because you manually try to compare the dates with isBefore, you also return -1 in both cases when two Users have checkMatchConditions true and their lastMatchDates are both equal.

In order to fix this, you should first add a natural language description of how you want the Users to be ordered. Then you can work out the comparator logic.

The error has nothing to do with the Boolean.valueOf() by the way.


Now that you explained how you want to order, have a look at this comparator:

public int compare(MiniUser u1, MiniUser u2)
{
    // order by match
    boolean u1Matches = checkMatchConditions(u1, user);
    boolean u2Matches = checkMatchConditions(u2, user);

    if (u1Matches != u2Matches)
    {
        // put matching ones first
        return u1Matches ? -1 : 1;
    }
    else if (u1Matches)
    {
        // order by dates
        boolean u1HasDate = u1.getLastMatchDate() != null;
        boolean u2HasDate = u2.getLastMatchDate() != null;

        if (u1HasDate != u2HasDate)
        {
            // put the ones without date first
            return u1HasDate ? 1 : -1;
        }
        else if (u1HasDate)
        {
            // order chronologically
            return u1.getLastMatchDate().compareTo(u2.getLastMatchDate());
        }
        else
        {
            // no dates, no order possible
            return 0;
        }
    }
    else
    {
        // both don't match, no order possible
        return 0;
    }
}

If I understood your requirements correctly, this should impose a consistent order to your elements. Note how I use Date's compareTo for the date ordering instead of doing it myself, and how I return 0 in case they are "equal" in regards to the order instead of "randomly" returning 1 or -1.

Friday, September 3, 2021
 
innovation
answered 3 Months ago
Only authorized users can answer the question. Please sign in first, or register a free account.
Not the answer you're looking for? Browse other questions tagged :  
Share