Remove TreeMap entries less than x

Question

I have the following TreeMap:

private Map<Date,WeekSchedule> weeks = new TreeMap<Date,WeekSchedule>();

And I need to remove all entries, whose date is before a given value.

What is the most efficient way to do this?

This is what I have so far:

public void removeWeeksBefore(Date monDate){
    for (Map.Entry<Date, WeekSchedule> entry : weeks.entrySet()){
        if(entry.getKey().before(monDate)){
            weeks.remove(entry.getKey());   //This will destroy the iterator
        }else{
            return;
        }
    }
}

Mariano

Is Date comparable? Can you store this as a NavigableMap? – Disinherit

@LouisWasserman Yes, Java.util.Date is compareable – Mariano

Answer 1

The most efficient way is probably storing this as a SortedMap and then using the one line

map.headMap(monDate).clear();

Disinherit

You could store it as TreeMap, sure, but the OP stored it as a Map, which doesn't support headMap. The performance is going to depend on the implementation, and there are certainly tree implementations which could support this in O(log n); I can readily believe that the current implementation doesn't support this faster, though. I don't know why you'd expect iterating to be more efficient in memory, though, and I absolutely do claim that this is specifically intended as a way to use the SortedMap view types and the intended solution to the problem. – Disinherit

Answer 2

Since you don't care about the map values, you only need to iterate over the keySet:

Iterator<Date> iter = weeks.keySet().iterator();

while (iter.hasNext()) {
    if (iter.next().before(monDate))
        iter.remove();
    else
        return;  // since TreeMap is sorted by key
}

Senility

Is there a reason, why you removed the return-statement in the else-branch? – Mariano

@Mariano Because we don't want to return as soon as we find an element that doesn't need to be removed. We want to traverse the entire map. – Senility

Yes, by natural order. – Johnsonian

@AnubianNoob Good point, I forgot we were dealing with a TreeMap. I guess we can use return after all. – Senility

Answer 3

You can use the iterator instead of for-each loop, if you are modifying the Iterable.

    for (Iterator<Entry<Date, WeekSchedule>> i = weeks.entrySet().iterator() ; i.hasNext(); ){
        Entry<Date, WeekSchedule> entry = i.next();
        if(entry.getKey().before(monDate)){
            i.remove();
        }else{
            return;
        }
    }

Uriel