JBCACHE-166 - TreeSet/Map, LinkedHashMap

[genman]

What would be ideal for implementing ordered values for POJOs would be to able to create a org.jboss.Cache.Node with an ordered implementation for the children nodes.

In particular, it might be nice to add this method to Node:

interface Node {
 // ...
 void setChildrenOrdering(Comparator c);
}

By default, no ordering (ConcurrentReaderHashMap) would be fine. I'm not sure the alternative in the sorted case, however. It obviously wouldn't be as efficient. The edu.oswego "SyncSortedSet" might be okay, although iteration over children could then result in ConcurrentModificationExceptions.

This would be very useful for creating a POJO LinkedList as well.

This might be useful outside of POJO land as well, especially for users who want an ordered tree.

Without this, I don't see how you could create an optimal POJO SortedSet.

[genman]

Just as a note, there is this:

http://doc.java.sun.com/DocWeb/api/java.util.concurrent.ConcurrentSkipListSet

which would be a good replacement for ConcurrentReaderHashMap for sorted nodes. I'm guessing the source is public domain like the backport was.

[genman]

A couple more thoughts.

Maybe create: setNodeOrdering and getNodeOrdering, as well as make the ordering of nodes be automatically inherited.

This might be better expressed as regions, but there may be thousands of regions for handling POJOs.

And as for replication or cache storage, I'm not clear on how this might be handled.

Perhaps this is just a hack?

[manik]

From another thread that I started by mistake.

This is referring to:

https://jira.jboss.org/jira/browse/JBCACHE-841

And rather than exposing the backing Map impl to users, I'd prefer to just provide a few settings on a node such that:

Node.isDataOrdered(); // tests if the data map is ordered
Node.isChildrenOrdered(); // tests if the child map is ordered
Node.setDataOrdered(boolean b); // locks the map, and then copies out the existing data map into a new ordered map structure
Node.setChildrenOrdered(boolean b); // similar to above

Is there anything else we'd need? Using iterators on the sets and maps returned when accessing data/data-keys/children/children-names will be ordered if the node is set to be ordered. I guess perhaps providing comparators if the data has no natural ordering would be useful? This comparator would have to be serializable though if it is to be replicated/persisted.

Node.setDataComparator(Comparator<K> c);

I'm guessing we'd need a SortedMap similar to FastCopyHashMap that is optimised for copying/cloning?

Finally, these settings would have to be replicated/persisted. I'm guessing there should be no special options on cache loaders, but when the data is loaded into the node it would be ordered by the map implementation.

Also, I see this as a per-node option. Any thoughts on whether this would be useful as a cache-wide cfg option? There may be cases where a thread is reading a node in a tx, and another thread sets it's sorted flag to true. I'm guessing flag changes like these are considered a write operation since the map implementation changes and a copy of contents will take place. Or - to make life easier - do we want this to be cache-wide so that all nodes are either sorted or not, and there is no issue with changing them?

[jason.greene]

For now I think it makes sense as just a per node option.

Another API possibility would be something like

enum Sorting {CHILDREN, DATA, BOTH}
cache.createSortedNode(Fqn fqn, Sorting sorting);
cache.createSortedNode(Fqn fqn, Sorting sorting, Comparator<?> nodeComp, Comparator<?> dataComp);

Then you don't have to worry about the sorting switching back and forth on you, as it would be fixed.

[jason.greene]

Also, to emulate TreeMap I would need some methods, that are probably best on other interfaces

interface SortedData {
 getSortedMap();
}

interface SortedChildren {
 subChildMap(Object from, Object to);
 tailChildMap(Object from);
}

[manik]

The problem with a createSortedNode() method on cache is the implicit creation of nodes. So what happens if you do:

cache.createSortedNode(/a/b/c, mySorting);

where /a exists and is sorted, but /b does not? Does /b get created as a sorted or unsorted node?

I guess as long as any assumptions are clearly documented, then we can use that as the only mechanism to create a sorted node. Beyond that, we could use Node.isSorted() and Node.getSortedData(), Node.getSortedChildren() as you suggested, throwing exceptions if Node.isSorted() == false.