How to implement a sorted table (order by a field of the element) by using java TreeSet?

Question

I used TreeSet for this and it works in a per snapshot style. In other words, sort once displays once.

Now, I want to implement a realtime sorted table.

Whenever there is a value change in any elements, the sorted table will be updated accordingly.

To make the sorting work on a per update style, I tried to remove the element and add it to the TreeSet again.

quotes.remove(quote);
quotes.add(quote);

It doesn't work because I have to implement the sorting logic in compareTo() but it breaks the contract for identifying the object which makes the remove() work. TreeSet never call equals() and hashcode() as described in the Java Doc.

Any idea? Please advise.

code:

import java.util.TreeSet;

public class TreeSetTest {

    public static void main(String args[]) {        
        TreeSetTest test = new TreeSetTest();
        test.onQuoteUpdate("appl", 1000d);
        test.onQuoteUpdate("msft", 2000d);
        test.onQuoteUpdate("face", 3000d);
        test.printTopStocks();
        test.onQuoteUpdate("msft", 5000d);
        test.printTopStocks();
    }

    private Set<Quote> quotes = new TreeSet<Quote>();

    public void onQuoteUpdate(String symbol, double turnover) {
        final Quote quote = new Quote(symbol, turnover);
        quotes.remove(quote);
        quotes.add(quote);
    }

    public void printTopStocks() {
        System.out.println("--Top Stocks By Turnover--");
        for (final Quote quote : quotes) {
            System.out.println(quote);
        }
    }
    public static class Quote implements Comparable<Quote> {

        private String symbol;

        private double turnover;

        public Quote(String symbol, double turnover) {
            this.symbol = symbol;
            this.turnover = turnover;
        }

        @Override
        public int compareTo(Quote o) {
            return Double.compare(o.turnover, turnover);
//          return symbol.compareTo(o.symbol);
        }

    }
}

Update 1:

As proposed I tried this:

public static void main(String args[]) {        
    TreeMapTest test = new TreeMapTest();
    test.onQuoteUpdate("appl", 1000d);
    test.onQuoteUpdate("msft", 2000d);
    test.onQuoteUpdate("face", 3000d);
    test.printTopStocks();
    test.onQuoteUpdate("face", 50d);
    test.printTopStocks();
}

    public int compareTo(Quote o) {
        if(o.symbol.equals(symbol)) return 0;
        return Double.compare(o.turnover, turnover);
    }

The remove() return false which eventually there are four elements (expected 3) in the Set.

--Top Stocks By Turnover--
Quote [symbol=face, turnover=3000.0]
Quote [symbol=msft, turnover=2000.0]
Quote [symbol=appl, turnover=1000.0]
remove symbol face : false
add    symbol face : true
--Top Stocks By Turnover--
Quote [symbol=face, turnover=3000.0]
Quote [symbol=msft, turnover=2000.0]
Quote [symbol=appl, turnover=1000.0]
Quote [symbol=face, turnover=50.0]

Update 2:

I tried PriorityQueue and here is the code: https://code.sololearn.com/cb38Eo036c8y/#java

It doesn't work because PriorityQueue doesn't store elements in order. The ordering only works when you poll element from the Queue.

Update 3:

Tried user54321's suggestion that by using a custom collection(see below answer). However, it doesn't look good if there are two more elements having the same value of 'turnover'.

My requirement is a very ordinary one. It seems that none of a collection from JDK fits my case.

Update 4:

The solution from user54321 fits for my interim need. https://code.sololearn.com/c14Ybab7AOFm/#java

Answer 1

Deleted my previously added answer. Looks like a wrong data structure is being used for the scenario.

Here is why.

When an item is being added or removed, TreeSet does a binary search through the available elements using compareTo().

In your case,

After adding first 3 elements, set looks like this.
[{appl, 1000d}, {msft, 2000d}, {face, 3000d}]

Now when you try to remove the element {face, 50d},

It starts searching at {msft, 2000d}, From compareTo() result it determines {face, 50d} should come before {msft, 2000d}.

And continues to search towards start of the elements ( checking with {appl, 1000d} next).

Since the search doesn't find {face, 3000d}, that element remains without being removed.

Next when you add the element {face,50}, similar search happens and since the search does not find {face, 3000}, It adds {face, 50} to the beginning.

Now the set looks like this.
[{face, 50}, {appl, 1000d}, {msft, 2000d}, {face, 3000d}]

Now the problem here is that compareTo() isn't capable of considering both symbol and turnover for a sensible sorting. TreeSet can be used for getting a sorted collection of unique elements.

If you need to get a sorted collection of different objects with a particular sorting criteria, in this case turnover value, you can use a PriorityQueue

Update: Using a List and a Set in custom data structure

The problem here is that we have to maintain two conditions. 1. Symbol has to be unique 2. Collection should be sorted by turnover value

compareTo() in Quote can check one at a time and not both. So in this case we may have to go for a custom data structure.

First use only turnover in compareTo();

    @Override
    public int compareTo(Quote o) {
        return Double.compare(o.turnover, turnover);
    }

Then implement the custom data structure. Note that we are using a HashSet to keep track of the symbol alone. Using a list so that duplicate turnover values can be kept.

static class QuoteCollection {
    Set<String> symbols = new HashSet<>();
    List<Quote> quotes = new LinkedList<>();

    public void onQuoteUpdate(Quote q) {

        if (symbols.contains(q.getSymbol())) {
            // this requires quotes.equals() to be implemented
            quotes.remove(q);
        } else {
            symbols.add(q.getSymbol());
        }
        insertToCollection(q);
    }

    // inserting at correct position to remain sorted
    private void insertToCollection(Quote q) {
        int index = Collections.binarySearch(quotes, q);
        if (index < 0)
            index = ~index; // bitwise compliment to find insert position if it is not available in the list
        quotes.add(index, q);
    }

    public List<Quote> getQuotes() {
        return quotes;
    }
}

Then use it in the main(). Note that printTopStocks() has been changed a little.

public static void main(String args[]) {
    Main test = new Main();
    QuoteCollection quoteCollection = new QuoteCollection();
    quoteCollection.onQuoteUpdate(new Quote("appl", 1000d));
    quoteCollection.onQuoteUpdate(new Quote("msft", 2000d));
    quoteCollection.onQuoteUpdate(new Quote("face", 3000d));
    test.printTopStocks(quoteCollection.getQuotes());
    quoteCollection.onQuoteUpdate(new Quote("face", 50d));
    test.printTopStocks(quoteCollection.getQuotes());
}
public void printTopStocks(List<Quote> quotes) {
    System.out.println("--Top Stocks By Turnover--");
    for (final Quote quote : quotes) {
        System.out.println(quote);
    }
}

This approach does involve data duplication. However a sorted collection can be maintained at linear time complexity(since it uses 'List.remove()')

Answer 2

Couple of points :

1. Trying to remove elements even when you are adding it first time.

2. While updating you are trying to remove new element which does not exist in TreeSet. final Quote quote = new Quote(symbol, turnover); here you are building new element which is Quote("face","50d") which does not exist when you are calling quotes.remove(quote);

Below is the one of the way to solve it, I am hard coding oldQuote to keep it short but you can update it:

   public void onAdd(String symbol, double turnover) {
            final Quote quote = new Quote(symbol, turnover);

            quotes.remove(quote);
            quotes.add(quote);
        }

     public void onQuoteUpdate(String symbol, double turnover) {
                final Quote newQuote = new Quote(symbol, turnover);
                final Quote oldQuote = new Quote("face", 3000d);
                quotes.remove(oldQuote);
                quotes.add(quote);
            } 

     public static void main(String args[]) {        
                TreeSetTest test = new TreeSetTest();
                test.onAdd("appl", 1000d);
                test.onAdd("msft", 2000d);
                test.onAdd("face", 3000d);
                test.printTopStocks();
                test.onQuoteUpdate("face", 50d);
                test.printTopStocks();
            }