Customization of data structures

Back to Programming techniques

A data structure is customizable, if

A customization is a single-parameter class template, parametrized by the settings-type of the data-structure that is to be customized. The data-structure is passed the customization from whose settings-instance it publicly derives from. The customization makes its constructors and its assignment operator available only to the data-structure, to avoid the possibility of slicing.

Abstract example

template <
    typename Settings,
    template <typename> class Customization>
class DataStructure
    : public Customization<Settings>
{
public:
    void insert(int someParameter)
    {
        // A customization point.
        this->onInsert(someParameter);
    }
};

template <typename Settings>
class Demo_Customization
{
public:
    // Since the data structure inherits from its customization,
    // you can extend the public interface of the data structure 
    // by specifying public functions here.
    void newMemberFunction()
    {
    }

protected:
    // The customization functions should be protected
    // so that they can only be called by the data structure.

    Demo_Customization() {}

    // The code for the customization points.
    void onInsert(int someParameter) {}

private:
    // These functions will not be used, and so should
    // be deleted to avoid accidental splicing.
    Demo_Customization(const Demo_Customization& that) = delete;
    Demo_Customization(Demo_Customization&& that) = delete;
    Demo_Customization& operator=(Demo_Customization) = delete;

    // Since the data structure is derived from the
    // customization, a reference to the data structure
    // can be obtained by casting.
    DataStructure<Settings, ::Demo_Customization>& self()
    {
        return (DataStructure<Settings, ::Demo_Customization>&)*this;
    }

    const DataStructure<Settings, ::Demo_Customization>& self() const
    {
        return (const DataStructure<Settings, ::Demo_Customization>&)*this;
    }

    // Customization state can be introduced here.
    int state_;
};

// This is how the data structure appears in code.
template <typename Settings, template <typename> class Customization>
void f(const DataStructure<Settings, Customization>& dataStructure)
{
}

int main()
{
    class Settings {};
    DataStructure<Settings, Demo_Customization> a;
    f(a);
    return 0;
}

Concrete examples

The red-black tree is a self-balancing binary search tree. In Pastel, this data structure is customizable. This allows, among other things, to define a propagation function which is used to propagate information from a children node to a parent node. This allows to solve many algorithmic problems, such as the maximum clique problem for aligned boxes, and to implement new data structures, such as the interval tree.

Learn more