File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes Custom Vector class with 'sorting' capabilities Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Custom Vector class with Watch "Custom Vector class with New topic
Author

Custom Vector class with 'sorting' capabilities

Alpesh Vesuwala
Greenhorn

Joined: Jan 16, 2008
Posts: 9
Hi guys,

I am not using any default feature/ API to sort collection and creating my own Vector which provides me the sorting capabilities.
What would be the best possible approach?

Is there any solution apart from calling merge/ quick sort for every insertion?

Thanks,
Alpesh


Sun Certified Java Programmer<br />Sun Certified Mobile Application Developer
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4374
    
    8

Calling a full sort routine on every insertion seems like overkill to me (especially quicksort, which is poor at almost sorted sets!). I can think of two approaches that will be better - which I'd prefer would depend on how I was expecting it to be used.

- On each insertion, work out the correct point of insertion and just insert there.

- Have a flag indicating whether the list is currently sorted correctly. On insertion, set it to false. Before any retrieve operation, if the flag is false sort the list before returning anything. After all, when you're not reading from the list you don't care if it's sorted or not.

(That's assuming you don't just want to search for an open source List that already does it)
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19682
    
  20

If you can guarantee that the Vector* is always sorted, you can use a binary search (available in java.util.Collections) to find the location to add to. But note that you shouldn't really extend any List implementation, because you will break the contracts of List.add(E) and List.add(int, E). Both specify where in the List the new element should go, and you are not doing that.

Perhaps you should instead create a new Collection implementation that resembles a List but isn't so strict on the way the add methods should be implemented. Of course you can use a Vector (or ArrayList) internally to do all the hard work.


* Why use Vector as the base class? Why not use ArrayList? Unless you need synchronization ArrayList is always a better fit, and if you need synchronization you can also wrap an ArrayList using Collections.synchronizedList.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Alpesh Vesuwala
Greenhorn

Joined: Jan 16, 2008
Posts: 9
Thanks a lot !!!

On each insertion, work out the correct point of insertion and just insert there


To insert an element at specific location is basically calling a sorting operation. so I have to call that logic for every insertion. Here is the problem.

Have a flag indicating whether the list is currently sorted correctly. On insertion, set it to false. Before any retrieve operation, if the flag is false sort the list before returning anything. After all, when you're not reading from the list you don't care if it's sorted or not.


This is a good idea but Sorted at Insertion and optimizing the insertion operation is what I am looking for.

Why use Vector as the base class?


I am not very specific to any existing Collections class. Vector was just an example. It can be my custom Vector or Arraylist that I want in Sorted.

Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3615
    
  14

Neither List nor Vector are suitable types for this, because they should allow the user to insert elements wherever they want.

You can implement your own SortedSet, or if you want to allow duplicate elements, you should implement your own Collection (SortedCollection maybe?).

If you want to keep the collection sorted at all times, you don't have to perform a sort operation on each insertion. You only have to perform a search operation on each insertion, and then insert the element in that position.

So algorithms like merge sort don't apply, you will need algorithms like binary search.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4374
    
    8

Alpesh Vesuwala wrote:To insert an element at specific location is basically calling a sorting operation. so I have to call that logic for every insertion. Here is the problem.


As Rob says, you can use a binary search. That's much more efficient than calling a full-blooded sort routine. You take advantage of the fact that you know it's already sorted
Alpesh Vesuwala
Greenhorn

Joined: Jan 16, 2008
Posts: 9
Thanks all.

I got it and would implement the best, optimized custom Collections class.


 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Custom Vector class with 'sorting' capabilities