Which data structure should I consider for implementing the following requirements.

[Chan Ag]

Hello,

I need to figure which Collection API implementation is going to be a good choice for implementing the following two requirements.

Req 2 : You have to create a program that simulates the NASDAQ Stock Quotations chart. The chart should maintain those 100 top companies whose stock prices are the highest. The chart displays the name of the company followed by its stock price in dollars, in the descending order of the stock price.

Req 3 : Req 2 + make sure that the companies that are added in the chart are all listed companies.

For req 2, I can't use a TreeMap because a company can have at most one entry so the company name should become the key. But if company name becomes the key, then I don't get any benefit of using a Tree structure cause I'd want to benefit from the sorting and the sorting should be on the stock price. I can't use stock price as the key as two companies can have the same quotes. Any suggestions?

And I have no clue on Req 3 except that I can use enums somewhere but again I can't have company name as the key. Also the problems of Req 2 apply.
Any hints/suggestions?

Thanks,
Chan.

[Chan Ag]

This is resolved. Sorry for the confusion.

I'm going to use a TreeSet with enum type as one of the fields in the elements' class.

enum Company { < the company names> }

class StockPriceEntry{
Company value;
double stockPrice;

}

Thanks,
Chan.

[Bin Smith]

import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;

class CompanyComparator implements Comparator<Company> {

	@Override
	public int compare(Company o1, Company o2) {
		int result = o1.getPrice().compareTo(o2.getPrice());
		if (result == 0) {
			return o1.getName().compareTo(o2.getName());
		}
		return result;
	}
}

class Company {
	private String name;
	private Double price;

	public Company(String name, Double price) {
		super();
		this.name = name;
		this.price = price;
	}

	public String getName() {
		return name;
	}

	public Double getPrice() {
		return price;
	}

	@Override
	public String toString() {
		return name + "=" + price;
	}
}

public class Trial {

	public static void main(String[] args) {
		Company[] companies = { new Company("company1", 100.00),
				new Company("company2", 200.00),
				new Company("company3", 200.00),
				new Company("company4", 200.00),
				new Company("company5", 300.00),
				new Company("company6", 400.00) };
		TreeSet<Company> treeMap = new TreeSet(new CompanyComparator());
		for (Company company : companies) {
			treeMap.add(company);
		}
		Iterator<Company> descendingIterator = treeMap.descendingIterator();
		while (descendingIterator.hasNext()) {
			Company company = (Company) descendingIterator.next();
			System.out.println(company);
		}
	}
}

[Chan Ag]

You know what. Although what was being tested then is probably just if I can use enums properly, but if I think of it now, it's a slightly more complex problem.

If I have to actually simulate this thing of top 100 stock prices' companies, there are couple of other things to look at as well. A remove operation is not quite as simple. Let us assume the minimum stock price entry in the list is IBM, 200 and there is an Amazon, 250 somewhere in the set. Say Amazon entry changes to Amazon 230. So the old Amazon entry has to be definitely removed. So the first check is if the entry is already present in the set, it has to be removed for sure. --> I can do this.

( Another approach with the above - have Enum Company with the stock price as its state. And I'm yet to try what will be the implication of having such a set that would contain these elements and the state of such elements is continuously changing. Quite an interesting thing to try and I will try it till I encounter a blocking issue. Might be a time waste, but still want to give it a try. )

Now after the remove I've got to see if the changed entry should still find a place in the set or it should be some other entry.
Implies - multithreading should be involved, if this was a real project. There should be continuously running threads removing stale entries, adding entries that have changed and so on.

But I'd keep it simple. I would do an add for the same company and it will find its place. Cause I'm sure multi-threading knowledge was not expected for completing this assignment.

Chan.

[Chan Ag]

Req 2 : You have to create a program that simulates the NASDAQ Stock Quotations chart. The chart should maintain those 100 top companies whose stock prices are the highest. The chart displays the name of the company followed by its stock price in dollars, in the descending order of the stock price.

Req 3 : Req 2 + make sure that the companies that are added in the chart are all listed companies.

Please ignore the initial responses on this one. This is actually open. I don't know how to get rid of the circle beside the topic.

This requirement seems like a trick question or something. I think I cannot use even a Set for this requirement because it doesn't take duplicates.
Even though my TreeSet is a set of enums, I have to compare based on stock prices and two companies can have same stock prices. So enum comparator wouldn't work properly for border line cases if I have equal stock quotes.

Should it be a LinkedList then? Do you think some infrequently used Set/Map implementation could come to rescue? Actually with Lists, I cannot benefit from a default ordering. Or can I? So if should be a List, is there a List implementation other than LinkedList that is better suited for this requirement?

Oh and I think multi-threading parts should be fairly easy if I use reentrant locks. So yes, I'd be working on the refinement of having the stock chart updated every time a stock quotation changes.

Considering all of the above, do you think it should be a LinkedList or something else? And if I club requirement 2 and requirement 3, should it be enum elements that I should add to the data structure?

Actually I have done some little rough coding using LinkedList and it seems to work. My code is in rough stage right now. Hence I'm not copying it. But the problem is, I am sorting way too often and the stock quotes must change too often too. Not sure how can I cut down on the number of sorts and if there is a data structure better suited for this sort of a requirement.

Please advise.

Thanks,
Chan.

[Chan Ag]

Thanks, Fred.

Here is what I have coded.

package Sets;

import java.util.*;
import java.util.concurrent.locks.*;

public enum Stocks {

    AMAZON(0),
    APPLE(0),
    AUTODESK(0),
    GENERALELECTRIC(0),
    GENERALMOTORS(0),
    GOLDMANSACHS(0),
    GOOGLE(0),
    IBM(0),
    INFORMATICA(0),
    JPMORGAN(0),
    NETAPP(0),
    ORACLE(0),
    TEXASINSTRUMENTS(0),
    VMWARE(0),
    YAHOO(0);
    
    private int stockPrice;
    private static Lock lock = new ReentrantLock();
    private static volatile boolean changed = false;
    //private static int maxSize = 100;
    private static volatile int maxSize = 5;
    private static final LinkedList<Stocks> topChart = new LinkedList<>();
    private static Comparator<Stocks> order = new Comparator<Stocks>() {

        @Override
        public int compare(Stocks o1, Stocks o2) {
            if (o1 == o2) {
                return 0;
            }
            return Integer.valueOf(o1.getStockPrice()).compareTo(
               Integer.valueOf(o2.getStockPrice()));

        }
    };

    private Stocks(int stockPrice) {
        this.stockPrice = stockPrice;
    }

    public static void setMaxSize(int maxSize) {
        Stocks.maxSize = maxSize;
    }

    private final int getStockPrice() {
        return stockPrice;
    }

    private final void setStockPrice(int stockPrice) {
        this.stockPrice = stockPrice;
    }

    public static final void changeStockPrice(Stocks s, int stockPrice) {
        try {
            lock.lock();
            s.setStockPrice(stockPrice);
            if (topChart.isEmpty()) {
                return;
            }
            boolean present = false;
            present = topChart.contains(s);
            if (present ||
               (topChart.getFirst().getStockPrice() < s.getStockPrice())) {
                if (present) {
                    topChart.remove(s);
                } else {
                    topChart.removeFirst();
                }
                Stocks.setChanged();
            }
        } finally {
            lock.unlock();
        }
    }

    private static final void addStocks(Stocks s) {
        int currentSize = topChart.size();
        if (currentSize < maxSize) {
            if (!topChart.contains(s)) {
                topChart.add(s);
                Collections.sort(topChart, order);
            }
            return;
        } else {
            if (s.getStockPrice() <= topChart.getFirst().getStockPrice()) {
                return;
            } else {
                if (!topChart.contains(s)) {
                    topChart.removeFirst();
                    Stocks.addStocks(s);
                }
            }
            return;
        }
    }

    public static final void updateChart() {
        try {
            lock.lock();
            if (changed) {
                for (Stocks s : Stocks.values()) {
                    Stocks.addStocks(s);
                }
                Stocks.changed = false;
            }

        } finally {
            lock.unlock();
        }

    }

    public static final void getListing() {
        try {
            lock.lock();
            if ( changed ) updateChart();
            System.out.println("Listing Top stocks at time : "
               + System.currentTimeMillis());
            Iterator<Stocks> i = topChart.descendingIterator();
            while (i.hasNext()) {
                Stocks temp = i.next();
                System.out.println(temp + " " + temp.getStockPrice());
            }
        } finally {
            lock.unlock();
        }

    }

    public static void setChanged() {
        try{
            lock.lock();
            changed = true;
        }
        finally{
            lock.unlock();
        }
        
    }
}

package Sets;

public final class StockChart {
    
    private volatile boolean done = false;
    
    public final void setDone(boolean done){
        this.done = done;
    }
    
    public void init(){
        Stocks.changeStockPrice(Stocks.AMAZON, 250);
        Stocks.changeStockPrice(Stocks.APPLE, 120);
        Stocks.changeStockPrice(Stocks.AUTODESK, 50);
        Stocks.changeStockPrice(Stocks.GENERALELECTRIC, 350);
        Stocks.changeStockPrice(Stocks.GENERALMOTORS, 280);
        Stocks.changeStockPrice(Stocks.GOLDMANSACHS, 400);
        Stocks.changeStockPrice(Stocks.GOOGLE, 1000);
        Stocks.changeStockPrice(Stocks.IBM, 240);
        Stocks.changeStockPrice(Stocks.INFORMATICA, 150);
        Stocks.changeStockPrice(Stocks.JPMORGAN, 400);
        Stocks.changeStockPrice(Stocks.NETAPP, 180);
        Stocks.changeStockPrice(Stocks.ORACLE, 220);
        Stocks.changeStockPrice(Stocks.TEXASINSTRUMENTS, 300);
        Stocks.changeStockPrice(Stocks.VMWARE, 85);
        Stocks.changeStockPrice(Stocks.YAHOO, 120);
        Stocks.setChanged();
        Thread updater = new Thread() {

            public void run() {
                while (!done) {
                    Stocks.updateChart();
                    try {
                        Thread.sleep(500);
                    } catch (InterruptedException ex) {
                        ex.printStackTrace();
                    }
                }
            }
        };
        updater.start();
        
    }
    
    
    
    public static void main(String[] args){
        StockChart obj = new StockChart();
        obj.init();
        System.out.println("------------------------------");
        Stocks.getListing();
        System.out.println("------------------------------");
        Stocks.changeStockPrice(Stocks.IBM, 400);
        Stocks.getListing();
        System.out.println("------------------------------");
        Stocks.changeStockPrice(Stocks.GOOGLE, 800);
        Stocks.getListing();
        System.out.println("------------------------------");
        Stocks.changeStockPrice(Stocks.AMAZON, 500);
        Stocks.getListing();
        System.out.println("------------------------------");
        obj.setDone(true);
    }
    
}

Here is the output -

run:
------------------------------
Listing Top stocks at time : 1377059975592
GOOGLE 1000
JPMORGAN 400
GOLDMANSACHS 400
GENERALELECTRIC 350
TEXASINSTRUMENTS 300
------------------------------
Listing Top stocks at time : 1377059975592
GOOGLE 1000
IBM 400
JPMORGAN 400
GOLDMANSACHS 400
GENERALELECTRIC 350
------------------------------
Listing Top stocks at time : 1377059975592
GOOGLE 800
IBM 400
JPMORGAN 400
GOLDMANSACHS 400
GENERALELECTRIC 350
------------------------------
Listing Top stocks at time : 1377059975592
GOOGLE 800
AMAZON 500
IBM 400
JPMORGAN 400
GOLDMANSACHS 400
------------------------------
BUILD SUCCESSFUL (total time: 1 second)

The assumptions I have made are -
1. The updater continuously runs and updates the chart. But it updates the chart only if important change/changes ( the stock quote of a top entry has changed or stock quote of an absent entry has become more than the current minimum quote on the list ) has/have happened.
2. All changes to the chart are via the updater unless a listing is asked for. Even if a listing is asked for, the chart is updated only if there are important changes.
3. The updater always checks if there is an important change, in which case it recreates the list in linear time ( or is it quadratic )?

I think if a LinkedList should be correct for this implementation, I am almost done with it unless someone suggests a bug or an improvement.

This is a practice assignment only for self learning, so it's not really holding up anything. It is something I can work on tomorrow also, day after tomorrow also, and so on ....
But I want to learn how to write efficient and better programs. I have a strong feeling that the idea of updating the list in linear time is not really the best idea considering the present entries are already sorted. A contains would inevitably do a search and then adding an element if the contains is false calls for another sort. Doesn't seem like the best of things to do. What do you say? If yes, then what is the alternative?

Thanks,
Chan.

[Bin Smith]

Hello!

First of all you code looks really cool and reveals new java features to me.

I noticed that you use LinkedList whereas you exactly know how many elements will be kept there. Your method updateChart() shows that you add to LinkedList topChart all constants of enum Stocks. You know exactly number of elements inside topChart and as I see method addStocks(Stocks s) removes the element before inserting new one thus ensures maximum size of topChart.
I am talking that it would be better to use ArrayList here. LinkedList is good when you don't know how many elements to hold and range might be from 1 to 1000.
In your case maximum possible number of elements is 15 which is really small thus create ArrayList as :
new ArrayList(15);
If elements are sorted in ascending order then much better search performance you get by searching with Collections.binarySearch(List<T> list,T key,Comparator c). Because it searches for element dividing collection by two.
You need to sort your elements in descending order that's why Colletions.binarySearch is not option for you because it works only if elements are sorted in ascending order !

[Chan Ag]

Thanks for your response, Volodymyr.

I see that you sort your elements inside list. If elements are sorted then much better search performance you get by searching with Collections.binarySearch(List<T> list,T key,Comparator c). Because it searches for element dividing collection by two. Look at that method at line 370 in java.util.Collections class to understand it.

Oh, yes!!! I am making that change already. Thank you. And somebody suggested in one another post that I should not use autoboxing in compareTo for primitives. So I am changing that too.

I noticed that you use LinkedList whereas you exactly know how many elements will be kept there.

I've used LinkedList and not ArrayList because there are too many insertions and deletions. There are many deletions at the 0th index. LinkedList makes 'em faster.
ArrayList has to update far too many indexes with random insertions and deletions whereas LinkledList has to just change the next and prev of two elements.
Having said that, I am still not sure if this is the right data structure. But I'm sure LinkedList is a better choice than at least ArrayLists or Arrays.

Though the assignment said it should be for 100 top stocks, max_size in my code can change. But that's not the reason why I chose LinkedList. I chose LinkedList because to too many additions and deletions.

In your case maximum possible number of elements is 15

Yeah, I should have coded more than 1000 enum elements possibly but I cut down on the number cause I wanted to get to the meat of the design.

Someone, please review my multi-threading parts too?

Thank you.
Chan.

[Winston Gutkowski]

Chan Ag wrote:Thanks for your response, Volodymyr.

Chan AND Volodymyr,

Please DontWriteLongLines. It makes threads very hard to read. I've broken yours up this time, but for future reference, please remember:
80 characters max.
(the SSCCE page actually recommends 62)
And that includes string literals AND comments.

Thanks.

Winston

[Chan Ag]

Ok, Winston. I will keep that in mind. Thanks for the edit.

[Bin Smith]

I did not notice that you need to remove the first element.

I should have coded more than 1000 enum elements possibly

It does not seem that enum with 1000 elements is good idea.
What will you do when you need to add one more company or remove one company.

By using enum your chart can manipulate only the same 1000 companies forever.

[Winston Gutkowski]

Chan Ag wrote:For req 2, I can't use a TreeMap because a company can have at most one entry so the company name should become the key.

I'm afraid you're leaping to implementation before you've worked out WHAT is being asked for; and I also suspect that you're trying to do this all in a single structure, when the requirements don't appear to ask for it. Indeed, they specifically state that you should "make sure that the companies that are added in the chart are all listed companies".

So: Do you have a list (or actually, probably better, a Set) of Companies? Sure you do: your enums. TBH, it's not the way I would have done it; I'd have maintained a Set (probably a HashSet) of Companies quite separate from my stocks list.

Also: When are you going to update your "top 100" list? Seems to me most likely when you get a price change.

So, what about this:
A List<Stock> whose contents are maintained via a HashMap<Company, Integer>?
where the "Integer" is the index of the Stock for that company in the List?
Then you can use that to maintain a third structure, which is a TreeMap<Price, List<Integer>>, which is the basis for your "top 100" list.

I'll leave you to work out the logistics.

Alternatively, understand that there are, what, maybe 100,000 publicly traded companies on the entire planet? - According to this site, actually 63,000. There are only 7 billion people on the planet, and "going public" is costly.

And how long does it take Java to sort 63,000 entries? It'll be in the fractions of seconds, believe me.

Winston

[Chan Ag]

Why is programming right so difficult!

Thanks for replying, Winston.

A List<Stock> whose contents are maintained via a HashMap<Company, Integer>?
where the "Integer" is the index of the Stock for that company in the List?
Then you can use that to maintain a third structure, which is a TreeMap<Price, List<Integer>>, which is the basis for your "top 100" list.

I don't know if I've understood it right. Following is what I have understood.
I create a Stock class, perhaps with elements String company and int price. Then I add Stock objects to the List<Stock>.
Is this right?
Then I create a HashMap that contains the Stocks.company and it's position in the List<Stock> mappings. I think I have understood this much.
The purpose of HashMap is to only record the position of Stocks in the list and I suppose the HashMap is going to be a constant, reference data structure.

Now after this, the TreeMap<Price, List<Integer>> thing seems difficult.
I think I have understood what the TreeMap contains but I have no clue on the how-tos.
If the stock price changes, we might have to move an Integer from one List to another, or we might need to create another price and List<Integer> mapping.
Do you mean the same thing as I've said? Or have I not understood it right?

If yes, it is way too complex for me. :-) Not sure if it just seems complex, or if it really is. I must try it.
Or may be I should park this assignment aside for laters cause it is way too complex for me right now.
May be I should try out some of the easier things before I come back to it.

Don't think that your suggestion was a wasted effort. I greatly appreciate it.
I will come back to it. But at a later time, when I am more equipped to implement it.

Thank you so much.
Chan.

[Bin Smith]

Hello!

Then you can use that to maintain a third structure, which is a TreeMap<Price, List<Integer>>, which is the basis for your "top 100" list.

All @Winston suggestions make my head ache.
But this one in qoutes means that two or more different companies can have the same price. You can't have the same keys, but your price can be the same for different companies. That's why List<Integer> indicates indices of Stocks which have the same Price in List<Stock>.
But this all is painful.
I do not see why TreeSet<Company> with custom Comparator proposed by me in first reply is bad idea.

Sorry but I made a mistake before. Collections.binarySearch is used only if you have your elements sorted in ascending order which is not your case.
This is extract from your code:

present = topChart.contains(s);  
            if (present ||  
               (topChart.getFirst().getStockPrice() < s.getStockPrice())) {  
                if (present) {  
                    topChart.remove(s); 

It is bad. Because you do the same comparison(by equals) in contains(s) and remove(s) twice. The better would be to use indexOf(s) instead of contains(s) because it returns to you index of s. Then you can remove by obtained index much quicker then you do that with remove(s). Why? Because you do not do equals for the second time as you do in remove(s) but you only traverse LinkedList without any equals in remove(index). And method remove(index) always knows at which end your index is closer to and thus it starts search from the tail or the head therefore search is very quick in remove(index). Look at remove(index) and remove(s) methods in LinkedList to understand them better.

[Winston Gutkowski]

Volodymyr Levytskyi wrote:All @Winston suggestions make my head ache.

But this one in qoutes means that two or more different companies can have the same price. You can't have the same keys, but your price can be the same for different companies. That's why List<Integer> indicates indices of Stocks which have the same Price in List<Stock>.

Correct.

I do not see why TreeSet<Company> with custom Comparator proposed by me in first reply is bad idea.

Did I say it was a bad idea? I was offering an alternative to Chan's implementation. But now that you mention it, iteration of TreeSet or TreeMap entries is not as fast as a List, and since, in order to get your entries in "Top 100" sequence, they need to be ordered by price first, you will necessarily have to search for the correct stock.

Also, you both seem to be assuming that a Company and its Stock are the same thing, when the requirements - and actually real life too - suggest otherwise.

Perhaps if I illustrate my idea with names and more specific structures it might help:
HashMap<Company, Integer> companies;
ArrayList<Stock> stocks;
TreeMap<Price, List<Integer>> stocksByPrice; ('Price' in this case would probably be an Integer or a Double).

The first table is your stock exchange, which is the driver for your other two structures. Since it is a Map, it does not allow the same Company to be entered twice. As it stands, there is a 1:1 correlation between a Company and its Stock, which is the entity that contains the "current price", but there is nothing that would stop you turning that 'Integer' into a List<Integer>, and thus allowing a Company to have (as in fact they do) more than 1 quoted Stock.

The list contains a list of each Stock quoted on the exchange. Now, you could use a HashSet<Stock>, but do you really need all that extra complexity and space? Hashed collections are very wasteful of space.

The final structure is the one used to maintain our "S&P 100" list, and is basically a dynamic index. It is NOT required for the normal functioning of the market, simply to keep that list current.

Now let's take a "Change price" function. This requires a Company and a new price; and the procedure would go something like this:
1. Get the Company's Stock index.
2. Get the Stock with that index and from it, its "current price".
3. Get the "Stocks by price" entry for the "current price" and remove our Stock index from its List.
4. Add the new price and index to "Stocks by price".
5. Update the Stock's "current price".
(Note: Step 5 could be done before, or synchronous with, Steps 3 and 4)

Note that I wasn't even thinking about how I was going to do this when I came up with the structures; simply what was required of them.
Also, it holds with the actual relationship between a Company and its Stock (or Stocks), which is that a Company "has" a Stock; it isn't the same thing as a Stock.
Actually, in information terms, it's far more likely that a Stock "is listed for" a Company: ie, A Company doesn't require a Stock in order to exist, but a Stock sure as hell better be associated with a Company.

I should also add that there are MANY ways of doing this, and you could certainly use HashSets or Maps instead of Lists. You could also drive all of this from your Stock table rather than your Company one, but the requirements suggest that there is a 1:1 correlation between Company and Stock which would be more difficult to enforce via a Stock entity.

I've also presumed that there aren't likely to be too many Stocks with the same price, but if there are, we simply change the structure of the index (ie, stocksByPrice). Nothing else has to change.

HIH

Winston

[Chan Ag]

Thanks, Winston.

[Chan Ag]

Heya, Volodymyr.

I do not see why TreeSet<Company> with custom Comparator proposed by me in first reply is bad idea.

No, it's not. In fact it was my first choice too. Also my first version of code had a TreeSet too. Yes, my elements were enum elements but my comparator was similar - I used ordinal function when the stock price was same. But there was a problem I encountered when I had too many records with the same stock price. It turned out so that because they had an order based on the ordinal too, the border line cases were behaving incorrectly if there were three or more records with the same stock price. I was getting a lower price in the set while a higher price was out of the set. I was too quick to discard the TreeSet structure because of this. I shouldn't have. May be the root cause was not the comparator, but incorrect logic somewhere else. I should have checked better.

Like the current case, I was actually adding a new entry to the set only if
1. The stock price of an existing entry had changed - in which case I'd delete that entry first - add the first entry in the stock exchange to the set without any comparisons so the set had 100 elements, check one by one if all the stocks in the exchange had a price higher than the minimum price in the top 100 - add it to the set if yes and it would find it's place.
2. The stock price of an absent entry had changed such that it was greater than the lowest price in the top 100, in which case I would delete the first element from the set and add this changed entry and it would find its place in the set.

May be for case 1, I should have just added all the elements to the set without any less than or greater than comparisons. It didn't work correctly may be because I was doing selective comparisons which were inconsistent from a total order perspective ( I also believe that it should have still worked cause even with selective adds it should have worked correctly eventually. But just cause I encountered this case, I should test it. ). Or may be some if then else logic elsewhere else was incorrect. These are just may be's and I have to work on this assignment again to get my answers.
I don't have the code now cause I changed the same piece into a List implementation. But I will try it again sometime next week to make sure it works or to ascertain that it wouldn't work.
This is still open.

And by the way, binary search would work cause the list is sorted.

I'd try Winston's suggestion too. Cause with it we'd not have any problems. But I'm not yet sure if I've understood it correctly. But I must do some findings on my own before posting further questions.

So, this is just FYI that I'm working on it. Just it may take some time. Thanks for your help.

Chan.