CODEWITHSUNDEEP
java
Unlikely1879
Unlikely1879

Reputation: 95

Data structure which can be sorted with iterator maintaining insertion order

This is a very generalized question, I'll try to be as clear as I can. let's say I have some collection of objects, for simplicity, make them integers. Now I want to make a class which represents these integers as some data structure. In this class I want to implement

How could I make it so that, even if I add integers in unsorted order, e.g. 

someCollection.add(1);
someCollection.add(3);
someCollection.add(2);

and then call 

Collections.sort(someSortingLogic);

The iterator still traverses in insertion order, after the collection is sorted. Is there a particular data structure I could use for this purpose, or would it be a case of manually tracking which elements are inserted in which order, or something else I can't think of?

Many thanks!

Upvotes: 1

Views: 370

Answers (2)

Edwin Buck
Edwin Buck

Reputation: 70909

Generally, to solve a problem like this, you maintain two indexes to the values. Perhaps one of those indexes contains the actual values, perhaps both indexes contain the actual values, or perhaps the actual values are stored elsewhere.

Then when you want to walk the sorted order, you use the sorted index to the values, and when you want the insertion order, you use the insert index to the values.

An index can be as simple as an array containing the values. Naturally, you can't store two different values into one spot in an array, so a simple solution is to wrap two arrays in an Object, such that calling the Object's sort() method sorts one array, while leaving the insertion order array untouched.

Fancier data structures leverage fancier techniques, but they all basically boil down to maintaining two orders, the insertion order AND the sort order.

public class SomeCollection {
   public void add(int value) {
      insertArray = expandIfNeeded(insertArray);
      insertArray[insertIndex++] = value;
      sortArray = expandIfNeeded(sortArray);
      sortArray[sortIndex++] = value;
      sort(sortArray);
   }
   ...
}

Upvotes: 1

clstrfsck
clstrfsck

Reputation: 14829

I'm not sure you've shown us enough code to give you a good answer, but if you have a class that looks a bit like this:

public class Hand implements Iterator<Card>
{
    private List<Card> cards = new ArrayList<>();

    // Returns iterator for natural ordering of cards
    @Override
    public Iterator<Card> iterator()
    {
        return cards.iterator();
    }

    // Rest of code omitted

Then you can implement a sortedIterator(...) method like this:

    // Returns iterator for sorted ordering by Comparator c
    public Iterator<Card> sortedIterator(Comparator<? super Card> c)
    {
        return cards.stream().sorted(c).iterator();
    }

If you show us some more code for what you have written, there may be better solutions.

Upvotes: 1

Related Questions