PDG_WorkItemSort.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * COMMENTS:
 */

#ifndef __PDG_WORKITEM_SORT_H__
#define __PDG_WORKITEM_SORT_H__

#include "PDG_API.h"

#include "PDG_AttributeEvaluator.h"
#include "PDG_Node.h"
#include "PDG_SortOptions.h"
#include "PDG_WorkItemTypes.h"

class PDG_WorkItem;

/**
 * Utility functors for sorting work items. All functors can be used for both
 * ascending or descending order, as determined by the "reverse" parameter
 * passed during construction. They default to ascending order for compatibility
 * with the standard C++ std::sort/less-than comparator.
 *
 * It is also possible to statically create a reversed comparator using the
 * reverse template argument. This is useful when defining datastructures that
 * need to use one of the comparators as a template argument for ordering, e.g.
 * a Priority Queue.
 */
class PDG_API PDG_WorkItemSort
{
private:
    /// Shared implementation for ordering work items by their presence or
    /// absents from a required dependency map
    static bool prioritize(
                    const PDG_WorkItemIDBoolMap* priority_items,
                    const PDG_WorkItem* lhs,
                    const PDG_WorkItem* rhs,
                    bool reverse,
                    bool& result);

    /// Base class for comparators
    template <typename T, bool Reverse, typename... Args>
    class Comparator : public T
    {
    public:
        Comparator() : T(), myReverse(Reverse), myPriorityItems(nullptr) {}
        Comparator(bool reverse, Args... args)
            : T(std::forward<Args>(args)...)
            , myPriorityItems(nullptr)
            , myReverse(reverse)
        {
        }
        Comparator(bool reverse,
                   const PDG_WorkItemIDBoolMap* priority_items,
                   Args... args)
            : T(std::forward<Args>(args)...)
            , myPriorityItems(priority_items)
            , myReverse(reverse)
        {
        }

        inline bool operator()(const PDG_WorkItem* lhs,
                               const PDG_WorkItem* rhs) const
        {
            if (lhs == rhs)
                return false;
            if (!lhs)
                return myReverse;
            if (!rhs)
                return !myReverse;

            bool result = false;
            if (prioritize(lhs, rhs, result))
                return result;

            return T::compare(*lhs, *rhs) ^ myReverse;
        }

        inline bool operator()(const PDG_WorkItem& lhs,
                               const PDG_WorkItem& rhs) const
        {
            if (&lhs == &rhs)
                return false;

            bool result = false;
            if (prioritize(&lhs, &rhs, result))
                return result;

            return T::compare(lhs, rhs) ^ myReverse;
        }

        inline bool prioritize(const PDG_WorkItem* lhs,
                               const PDG_WorkItem* rhs,
                               bool& result) const
        {
            return PDG_WorkItemSort::prioritize(
                myPriorityItems, lhs, rhs, myReverse, result);
        }

    private:
        const PDG_WorkItemIDBoolMap*        myPriorityItems;
        bool                                myReverse;
    };

    class PriorityComparator
    {
    public:
        bool compare(const PDG_WorkItem& lhs, const PDG_WorkItem& rhs) const;
    };

    class IndexComparator
    {
    public:
        IndexComparator(const PDG_NodeArray* input_list=nullptr)
            : myInputs(input_list) {}
        bool compare(const PDG_WorkItem& lhs, const PDG_WorkItem& rhs) const;
    private:
        const PDG_NodeArray* myInputs;
    };

    class InputComparator
    {
    public:
        InputComparator(const PDG_NodeArray* input_list=nullptr)
            : myInputs(input_list) {}
        bool compare(const PDG_WorkItem& lhs, const PDG_WorkItem& rhs) const;

    private:
        const PDG_NodeArray* myInputs;
    };

    class AttributeComparator
    { 
    public:
        AttributeComparator(const PDG_AttributeEvaluator* evaluator)
            : myEvaluator(evaluator) {}
        bool compare(const PDG_WorkItem& lhs, const PDG_WorkItem& rhs) const;

    private:
        const PDG_AttributeEvaluator* myEvaluator;
    };
    
    class FrameComparator
    {
    public:
        FrameComparator(const PDG_NodeArray* input_list=nullptr)
            : myInputs(input_list) {}
        bool compare(const PDG_WorkItem& lhs, const PDG_WorkItem& rhs) const;

    private:
        const PDG_NodeArray* myInputs;
    };

public:
    /// Functor that compares two work item references or pointers by priority
    template<bool Reverse=false>
    using Priority = Comparator<PriorityComparator, Reverse>;

    /// Functor for comparing work items for sorting by index
    template<bool Reverse=false>
    using Index = Comparator<IndexComparator, Reverse>;

    /// Functor for comparing work items for sorting by index and node.
    template<bool Reverse=false>
    using IndexInput =
        Comparator<IndexComparator, Reverse, const PDG_NodeArray*>;

    /// Functor for comparing work items for sorting by input number. Fallback
    /// to index when the input is the same.
    template<bool Reverse=false>
    using Input =
        Comparator<InputComparator, Reverse, const PDG_NodeArray*>;

    /// Compares work items using an attribute
    template<bool Reverse=false>
    using Attribute =
        Comparator<AttributeComparator, Reverse, const PDG_AttributeEvaluator*>;

    /// Compars work items using their frame value
    template<bool Reverse=false>
    using Frame = Comparator<FrameComparator, Reverse, const PDG_NodeArray*>;

public:

    /// Sorts the work items based on index, in ascending order.
    template <typename Array>
    static void             sortItems(Array& work_items)
    {
        PDG_SortOptions default_options;
        sortItems(work_items, default_options, nullptr, nullptr);
    }

    /// Sorts the work items based on the sort preferences of the specified
    /// node
    template <typename Array>
    static void             sortItems(
                                Array& work_items,
                                const PDG_Node* target_node,
                                const PDG_WorkItemIDBoolMap* required_items)
    {
        if (!target_node)
            return;

        PDG_NodeArray inputs;
        target_node->connectedNodes(inputs, PDG_PortType::eInput);

        sortItems(
            work_items, target_node->sortOptions(), required_items, &inputs);
    }

    /// Sorts the work items based on a sort options struct
    template <typename Array>
    static void             sortItems(
                                Array& work_items,
                                const PDG_SortOptions& sort_options,
                                const PDG_WorkItemIDBoolMap* required_items,
                                const PDG_NodeArray* inputs)
    {
        bool reverse = sort_options.myDirection;
        PDG_WorkItemSortOrder sort_order = sort_options.myOrder;
        const PDG_WorkItemIDBoolMap* priority_items = 
            sort_options.myRequired ? required_items : nullptr;

        if (sort_order == PDG_WorkItemSortOrder::eSortIndex)
        {
            if (inputs)
                work_items.sort(IndexInput<>(reverse, priority_items, inputs));
            else
                work_items.sort(Index<>(reverse, priority_items));
        }
        else if (sort_order == PDG_WorkItemSortOrder::eSortInputOrder)
        {
            if (inputs)
                work_items.sort(Input<>(reverse, priority_items, inputs));
            else
                work_items.sort(Index<>(reverse, priority_items));
        }
        else if (sort_order == PDG_WorkItemSortOrder::eSortAttribute)
        {
            PDG_AttributeEvaluator evaluator(sort_options.myAttribute);
            work_items.sort(Attribute<>(reverse, priority_items, &evaluator));
        }
        else if (sort_order == PDG_WorkItemSortOrder::eSortFrame)
        {
            work_items.sort(Frame<>(reverse, priority_items, inputs));
        }
    }
};

#endif /* __PDG_WORKITEM_SORT_H__ */