partition
0.1.1
|
A partition is a high performance container that organizes a sequential set of integer IDs into an arbitrary number of non-overlapping groups. Each integer can be associated with a user defined member of type M, and each group can be associated with a user defined value of type V. Together these associations enable mappings from objects of type M (with known IDs) to objects of type V, and conversely from objects of type V (with known groups) to a list of objects of type M.
A partition has not one, but two fundamental classes: Domain<M,V> and Group<M,V>. An instance of Domain maintains a resizable array of Entry objects, each Entry having a sequentially numbered ID paired with a user-provided member object of type M. The Entry objects of a Domain may be partitioned among instances of the companion class Group<M,V> where each Group maintains Entry objects from a single Domain as a doubly linked list, and also has an association with a user-provided value object of type V. Each Entry may exist in at most one Group and so a Domain along with its associated Groups form a partition (in the mathematical sense) of the Entry objects from a Domain.
The functionality of a partition includes these constant time operations which together distinguish it from other common containers:
Normally, the range of IDs defined for a Domain is known to the application. Accordingly, passing an out-of-range ID to most methods is treated as an error. For example, the following will (perhaps surprisingly) produce an exception:
Domain<int, std::string> d; d.addEntry(1, "one"); d.addEntry(2, "two"); Group<int, std::string> g(d); g.addBack(2); Group<int, std::string>::Iterator i = g.find(3); // Raises exception because 3 is not in Domain
The only methods that don't follow this rule are those that dynamically resize the Domain to accomodate the given id; for example: Domain::addEntry(int id, const M& member);