Java: autofiltering list?

Question

I have a series of items arriving which are used in one of my data structures, and I need a way to keep track of those items that are retained.

interface Item {}
class Foo implements Item { ... }
class Baz implements Item { ... }

class StateManager
{
    List<Foo> fooList;
    Map<Integer, Baz> bazMap;

    public List<Item> getItems();
}

What I want is that if I do the following:

for (int i = 0; i < SOME_LARGE_NUMBER; ++i)
{
    /* randomly do one of the following:
     * 1) put a new Foo somewhere in the fooList
     * 2) delete one or more members from the fooList
     * 3) put a new Baz somewhere in the bazMap
     * 4) delete one or more members from the bazMap
     */
}

then if I make a call to StateManager.getItems(), I want to return a list of those Foo and Baz items, which are found in the fooList and the bazMap, in the order they were added. Items that were deleted or displaced from fooList and bazMap should not be in the returned list.

How could I implement this? SOME_LARGE_NUMBER is large enough that I don't have the memory available to retain all the Foo and Baz items, and then filter them.

---

edit: this seems hard to me, because I don't really want class Foo or class Baz to have any awareness of an insertion index, and I want the approach to be scalable so that I don't have to have StateManager be aware of it either.

I was thinking maybe of using decorators for the List<> and Map<> used in fooList and bazMap, with the decorators each having a reference to the master List<> returned in getItems(), so that the decorators would silently do all the legwork.

Also just for clarity, let's say the operations on fooList and bazMap are:

 fooList.add(foo1);
 bazMap.put(3, baz1);
 fooList.add(foo2);     
 fooList.add(foo3);
 bazMap.put(10, baz2);
 bazMap.put(4, baz3);
 fooList.set(1, foo4);
 bazMap.put(7, baz4);
 bazMap.put(3, baz5);
 fooList.add(foo5);
 bazMap.put(7, baz6);
 fooList.set(0, foo6);
 bazMap.put(4, baz7);
 fooList.add(foo1);

then the list returned by getItems should be

 [foo3, baz2, foo4, baz5, foo5, baz6, foo6, baz7, foo1]

since the end fooList = [foo6, foo4, foo3, foo5, foo1] and the final bazMap = {10: baz2, 4: baz7, 3: baz5, 7: baz6}. Items foo1, baz1, foo2, baz3, and baz4 were all displaced (with foo1 added back at the last step)

Answer 1

I don't understand where the filtering comes from. If you're deleting the items in step 2 and 4, aren't they implicitly filtered?

If you're asking how to combine the two collections into a single list, that's pretty simple.

List<Item> items = new ArrayList<Item>(fooList.size() + bazMap.size());
items.addAll(fooList);
items.addAll(bazMap.values());

Maybe you can elaborate more on the "in the order they were added" part. The fooList could easily have that property, but the order of the bazMap is probably not going to have that property. And if you mean that foo is added, then baz, then foo, and you need the final resulting collection to be in that same order, that's more complicated still.

Answer 2

I don't understand either what exactly is being sought. If the problem is maintaining the insertion order of Foos and Bars, then you could store their index (i in your loop), and order them according to that, either by sorting a list or via a TreeMap or something. Another option would be using a LinkedHashMap (again using the index for key) that maintains insertion order.

Answer 3

Add the items to a separate master list of items and remove items from both the master list and the type specific data structures.

i.e.

for (int i = 0; i < SOME_LARGE_NUMBER; ++i)
{
    /* randomly do one of the following:
     * 1) put a new Foo somewhere in the fooList
     * 1a) put a new Foo at the end of masterList
     * 2) delete one or more members from the fooList
     * 2a) delete the same members from the masterList
     * 3) put a new Baz somewhere in the bazMap
     * 3a) put a new Baz at the end of masterList
     * 4) delete one or more members from the bazMap
     * 4a) delete the same members from masterList
     */
}