{"id":29,"date":"2013-03-27T17:58:54","date_gmt":"2013-03-27T17:58:54","guid":{"rendered":"https:\/\/www.mattbusche.org\/blog\/?p=29"},"modified":"2014-05-04T21:46:18","modified_gmt":"2014-05-04T21:46:18","slug":"partition-intro","status":"publish","type":"post","link":"https:\/\/www.mattbusche.org\/blog\/article\/partition-intro\/","title":{"rendered":"Tracking the States of a Set of Objects by PartitionAn Introduction to the Partition Container<\/span>"},"content":{"rendered":"

<\/p>\n

In this post I share a useful programming technique I first saw used
\ntwenty-some years ago while reading through some C code. The technique
\ncombined aspects of an array and a linked-list into a single data construct.
\nI’ve here abstracted the technique into a reusable container I call a
\npartition. (If someone knows of some library in some language that offers a
\nsimilar container I’d appreciate a reference.)<\/p>\n

A partition is a high performance container that organizes
\na set of N sequential integer IDs (which together are called the domain) into
\nan arbitrary number of non-overlapping groups. (I.e., each ID of the
\ndomain can be in at most one group.) The functionality of a partition
\nincludes these constant time operations:<\/p>\n

    \n
  1. \n Given an ID, determine the group to which the ID belongs (if any).\n<\/li>\n
  2. \n Given a group, find an ID in that group (if any).\n<\/li>\n
  3. \n Given an ID, move that ID to a particular group (simultaneously removing
    \n it from the group with which it was previously a member if any).\n<\/li>\n<\/ol>\n

    None of the above operations use the heap and are each considerably faster
    \nthan even a single push to standard implementations of a doubly linked list.<\/p>\n

    A partition has not one, but two fundamental classes: Domain and Group.
    \nThe set of sequential IDs in a partition are defined by a Domain
    \nobject; and a Group is a list of IDs from a Domain. Domain and Group each
    \nhave two templatization parameters M and V. IDs can be bound to a
    \nuser-defined member<\/i> object of type M and Groups can be bound to a user
    \ndefined value<\/i> object of type V. Together these associations enable
    \nmappings from objects of type M (with known IDs) to objects of type V, and
    \nconversely from objects of type V (with known Groups) to a list of objects
    \nof type M.<\/p>\n

    The partition is potentially useful any time objects need to be
    \norganized into groups; and that happens all the time! In this post, I show
    \nhow you can use a partition to track the states of a set of like objects.
    \nThis is just one possible usage of a partition and is intended only as a
    \ntutorial example of how you can use this versatile storage class.<\/p>\n

    <\/p>\n

    Contents<\/h2>\n
    \n
    Motivation<\/a><\/div>\n
    An Example<\/a><\/div>\n
    The Problem<\/a><\/div>\n
    A Solution<\/a><\/div>\n
    Conclusions<\/a><\/div>\n
    Software Downloads and Documentation<\/a><\/div>\n<\/div>\n
    \n<\/a><\/p>\n

    Motivation<\/h2>\n

    Suppose you have a set of N objects of some common type each having an
    \nindependent state variable. Perhaps you have hardware monitoring the
    \nbit-error-rates on N communications ports and it is your job to categorize
    \nthem into signal quality states of CLEAR, DEGRADED or FAILED. Or perhaps
    \nyou are tracking the BUSY-IDLE states of N processors in a massively
    \nparallel computer processing environment. Or you might be tracking
    \nthe activity of N threads in a thread pool. Obviously, such problems abound.<\/p>\n

    A common use-case for such systems is to find one or more objects in a
    \nparticular state. For example, you may need to find one port in the
    \nCLEAR state for allocation to some new network communications service; or
    \nyou may want to find and list all processors in the BUSY state to
    \nperform an audit. If the number of objects is small, you could simply
    \niterate over them all until you find the objects with the desired
    \nstate; but if you have many objects, this approach can be highly inefficient.
    \nTo solve such problems for large sets, you will naturally use containers to
    \nhold objects that share a common state; but what type of container should
    \nyou use?<\/p>\n

    For C++ you might group your objects into standard STL maps.
    \nSimilarly, for Java you could use HashMaps from the java.util package.
    \nThese classes provide convenient solutions, but such heavy-weight
    \ncontainers may be prohibitively slow for some applications.<\/p>\n

    A lighter-weight alternative is to use linked-lists, but then a state
    \nchange of, for example, a circuit from CLEAR to DEGRADED now requires you
    \nfirst find the circuit in the CLEAR list so that it can be removed from that
    \nlist before adding it to the DEGRADED list; this search can again be slow for
    \nlarge sets. In the C++ domain you can remedy this by giving each circuit
    \nobject an iterator that tracks its own location in the linked-list of which it
    \nis currently a member. This is actually an effective (if slightly cumbersome)
    \nsolution. In the Java domain, such an approach is not possible if you restrict
    \nyourself to standard library containers which suffer from the limitation that
    \niterators point between two members and are in any case necessarily invalidated
    \nwhenever the container they reference is updated. (Oh, the horror! I need a
    \nProzac!)<\/p>\n

    The partition container is specialized to handle exactly this type of problem
    \nand is both easier to use and faster than any of the above alternatives.<\/p>\n

    <\/a><\/p>\n

    An Example<\/h2>\n

    <\/a><\/p>\n

    The problem<\/h3>\n

    A partition is often useful for solving resource management problems. For our working example, we’ll track the state of a box of eight crayons being shared by my two girls Becky and Cate to draw pictures. (This is not the most compelling resource management problem, but it is at least easy to understand and certainly doesn’t look like any proprietary software I’ve ever written.) I want to show how you might model a resource that has multiple states, so we’ll give each crayon both a User<\/code> state (which can be one of BECKY<\/code>, CATE<\/code>, or BOX<\/code>), and a Quality<\/code> state (which can be one of SHARP<\/code> or DULL<\/code>). The programming problem is merely to efficiently keep track of this state information for all eight crayons and support a variety of use cases, like “find a sharp crayon in the box”, “get the state of the red crayon”, or “return all of Cate’s crayons to the box”.<\/p>\n

    <\/a><\/p>\n

    A solution<\/h3>\n