| 286 | | |
| 287 | | |
| | 286 | === 5. Boost.Flyweight: multi-key flyweights === |
| | 287 | |
| | 288 | Potential mentors: Joaquín M López Muñoz, Vicente J. Botet Escriba |
| | 289 | |
| | 290 | ==== Background ==== |
| | 291 | |
| | 292 | [http://www.boost.org/libs/flyweight/doc/index.html Boost.Flyweight] allows for memory-efficient handling of large quantities of immutable objects when many of them have equivalent states, i.e. when their representation can be reduced to a smaller number of surrogate instances. These common representatives are stored and looked up in so-called ''[http://www.boost.org/libs/flyweight/doc/reference/factories.html#factory factories]''. As it happens, flyweight factories are one-keyed, i.e. they can only be looked up by values of one type (either that of the elements stored themselves, in the default case, or a user-specified type for ''[http://www.boost.org/libs/flyweight/doc/tutorial/key_value.html key-value flyweights]''). Sometimes the need arises of specifying more than one key type by which the same underyling objects can be accessed, naturally leading to an extended concept of ''multi-key factories'', which as of today are not part of Boost.Flyweight. More context is given in a recent [http://thread.gmane.org/gmane.comp.lib.boost.devel/265379 thread] on the Boost mailing list. |
| | 293 | |
| | 294 | ==== Project: multi-key flyweights ==== |
| | 295 | |
| | 296 | Let `Key1`, ... , `KeyN` be types with some notion of identity ~ under which they are isomorphic, i.e. there are mappings `fij(Keyi)->Keyj` that preserve intra-type identity, and let be `Value` be some other, different type (the flyweight type). A multi-key flyweight on (`Key1`, ... , `KeyN`, `Value`) is a type `M` that behaves as a key-value flyweight for each (`Keyi`, `Value`) with the additional property that |
| | 297 | |
| | 298 | `ki` ~ `kj` <=> `M(ki)==M(kj)` for each 1 <= `i`, `j` <= `N`, `ki` of type `Keyi`, `ki` of type `Keyj`, |
| | 299 | |
| | 300 | that is, equivalent keys (even if of different types) refer to the same object, and conversely. The goal of the project is to extend Boost.Flyweight to support this multi-key flyweights. Some of the items to be completed will be: |
| | 301 | |
| | 302 | * Define the concepts required for multi-key factories and their specifiers, in a manner consistent and interoperable with the existing concepts for [http://www.boost.org/libs/flyweight/doc/reference/holders.html#holder holders], [http://www.boost.org/libs/flyweight/doc/reference/locking.html#locking locking policies] and [http://www.boost.org/libs/flyweight/doc/reference/tracking.html#tracking tracking policies]. As a kind of sanity check, the concept of multi-key factory when the number of keys is 1 should coincide with the already existing concept of factory. |
| | 303 | * Write at least one implementation of a multi-key factory (and associated specifier) to be provided off-the-shelf by Boost.Flyweight. This is very likely to be based on [http://www.boost.org/libs/multi_index/doc/index.html Boost.MultiIndex]. This component has to be flexible enough to support different lookup strategies, including at least hash-based and less-based. |
| | 304 | * Define and implement a `multikey_flyweight` class template that uses and weaves together multi-key factories, holders, locking and tracking. Make this class template taggable in the same way as `boost::flyweight`. |
| | 305 | * ''' Extra:''' allow for tagged key types that extend the applicability of the library to the case where some `Keyi` is the same type as some other `Keyj`. |
| | 306 | * ''' Extra:''' implement a lazy version of a multi-key factory, i.e. one in which keys of type `Keyi` are not created unless explicitly used. Laziness is expected to impose some space penalty on the associated data structure, this has to be understood and documented. (In fact, Boost.!MultiIndex is probably not up to this task.) |
| | 307 | * Provide full docs (tutorial and reference), examples and full test coverage to be merged with existing Boost.Flyweight material. |
| | 308 | |
| | 309 | ==== Potential project extension funded by Boost ==== |
| | 310 | |
| | 311 | The student is asked to work in this project as long as required to submit an industry-grade piece of work to the consideration of the Boost community, which should not but might extend beyond GSoC timelines. No additional funding from Boost is available. |
| | 312 | |
| | 313 | ==== Skills and competency test ==== |
| | 314 | |
| | 315 | The student will need |
| | 316 | |
| | 317 | * A mathematically-inclined mind to correctly capture and define the (non-trivial) concepts involved. |
| | 318 | * Good command of C++11. Code should ideally be C++03-compatible, with C++11 extra features (such as move semantics) leveraged where available. |
| | 319 | * Fluency with template metaprogramming in general and [http://www.boost.org/libs/mpl/doc/index.html Boost.MPL] in particular. The metaprogramming and generic programming involved is quite hard: please take a look at Boost.Flyweight source code to get an idea of the level of complexity this calls for. |
| | 320 | * Good command of the English language for documentation purposes. |
| | 321 | |
| | 322 | No specific competency test is proposed, but candidate students are required to show some previous work where all or most of these skills are exhibited. |
