imnodes.cpp

// the structure of this file:
//
// [SECTION] internal data structures
// [SECTION] global struct
// [SECTION] editor context definition
// [SECTION] draw list helper
// [SECTION] ObjectPool implementation
// [SECTION] ui state logic
// [SECTION] render helpers
// [SECTION] API implementation

#include "imnodes.hpp"

#include <imgui.h>
#define IMGUI_DEFINE_MATH_OPERATORS
#include <imgui_internal.h>

// Check minimum ImGui version
#define MINIMUM_COMPATIBLE_IMGUI_VERSION 17400
#if IMGUI_VERSION_NUM < MINIMUM_COMPATIBLE_IMGUI_VERSION
#error                                                                         \
  "Minimum ImGui version requirement not met -- please use a newer version!"
#endif

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <new>
#include <stdint.h>
#include <stdio.h> // for fwrite, ssprintf, sscanf
#include <stdlib.h>
#include <string.h> // strlen, strncmp

namespace imnodes {
namespace {
enum ScopeFlags
{
    Scope_None = 1,
    Scope_Editor = 1 << 1,
    Scope_Node = 1 << 2,
    Scope_Attribute = 1 << 3
};

enum AttributeType
{
    AttributeType_None,
    AttributeType_Input,
    AttributeType_Output
};

enum ElementStateChange
{
    ElementStateChange_None = 0,
    ElementStateChange_LinkStarted = 1 << 0,
    ElementStateChange_LinkDropped = 1 << 1,
    ElementStateChange_LinkCreated = 1 << 2
};

// [SECTION] internal data structures

// The object T must have the following interface:
//
// struct T
// {
//     T();
//
//     int id;
// };
template<typename T>
struct ObjectPool
{
    ImVector<T> pool;
    ImVector<bool> in_use;
    ImVector<int> free_list;
    ImGuiStorage id_map;

    ObjectPool()
      : pool()
      , in_use()
      , free_list()
      , id_map()
    {}
};

// Emulates std::optional<int> using the sentinel value `invalid_index`.
struct OptionalIndex
{
    OptionalIndex()
      : m_index(invalid_index)
    {}
    OptionalIndex(const int value)
      : m_index(value)
    {}

    // Observers

    inline bool has_value() const
    {
        return m_index != invalid_index;
    }

    inline int value() const
    {
        assert(has_value());
        return m_index;
    }

    // Modifiers

    inline OptionalIndex& operator=(const int value)
    {
        m_index = value;
        return *this;
    }

    inline void reset()
    {
        m_index = invalid_index;
    }

    inline bool operator==(const OptionalIndex& rhs) const
    {
        return m_index == rhs.m_index;
    }

    inline bool operator==(const int rhs) const
    {
        return m_index == rhs;
    }

    inline bool operator!=(const OptionalIndex& rhs) const
    {
        return m_index != rhs.m_index;
    }

    inline bool operator!=(const int rhs) const
    {
        return m_index != rhs;
    }

    static const int invalid_index = -1;

private:
    int m_index;
};

struct NodeData
{
    int id;
    ImVec2 origin; // The node origin is in editor space
    ImRect title_bar_content_rect;
    ImRect rect;

    struct
    {
        ImU32 background, background_hovered, background_selected, outline,
          titlebar, titlebar_hovered, titlebar_selected;
    } color_style;

    struct
    {
        float corner_rounding;
        ImVec2 padding;
        float border_thickness;
    } layout_style;

    ImVector<int> pin_indices;
    bool draggable;

    NodeData(const int node_id)
      : id(node_id)
      , origin(100.0f, 100.0f)
      , title_bar_content_rect()
      , rect(ImVec2(0.0f, 0.0f), ImVec2(0.0f, 0.0f))
      , color_style()
      , layout_style()
      , pin_indices()
      , draggable(true)
    {}

    ~NodeData()
    {
        id = INT_MIN;
    }
};

struct PinData
{
    int id;
    int parent_node_idx;
    ImRect attribute_rect;
    AttributeType type;
    PinShape shape;
    ImVec2 pos; // screen-space coordinates
    int flags;

    struct
    {
        ImU32 background, hovered;
    } color_style;

    PinData(const int pin_id)
      : id(pin_id)
      , parent_node_idx()
      , attribute_rect()
      , type(AttributeType_None)
      , shape(PinShape_CircleFilled)
      , pos()
      , flags(AttributeFlags_None)
      , color_style()
    {}
};

struct LinkData
{
    int id;
    int start_pin_idx, end_pin_idx;

    struct
    {
        ImU32 base, hovered, selected;
    } color_style;

    LinkData(const int link_id)
      : id(link_id)
      , start_pin_idx()
      , end_pin_idx()
      , color_style()
    {}
};

struct LinkPredicate
{
    bool operator()(const LinkData& lhs, const LinkData& rhs) const
    {
        // Do a unique compare by sorting the pins' addresses.
        // This catches duplicate links, whether they are in the
        // same direction or not.
        // Sorting by pin index should have the uniqueness guarantees as sorting
        // by id -- each unique id will get one slot in the link pool array.

        int lhs_start = lhs.start_pin_idx;
        int lhs_end = lhs.end_pin_idx;
        int rhs_start = rhs.start_pin_idx;
        int rhs_end = rhs.end_pin_idx;

        if (lhs_start > lhs_end) {
            ImSwap(lhs_start, lhs_end);
        }

        if (rhs_start > rhs_end) {
            ImSwap(rhs_start, rhs_end);
        }

        return lhs_start == rhs_start && lhs_end == rhs_end;
    }
};

struct BezierCurve
{
    // the curve control points
    ImVec2 p0, p1, p2, p3;
};

struct LinkBezierData
{
    BezierCurve bezier;
    int num_segments;
};

enum ClickInteractionType
{
    ClickInteractionType_Node,
    ClickInteractionType_Link,
    ClickInteractionType_LinkCreation,
    ClickInteractionType_Panning,
    ClickInteractionType_BoxSelection,
    ClickInteractionType_None
};

enum LinkCreationType
{
    LinkCreationType_Standard,
    LinkCreationType_FromDetach
};

struct ClickInteractionState
{
    struct
    {
        int start_pin_idx;
        OptionalIndex end_pin_idx;
        LinkCreationType link_creation_type;
    } link_creation;

    struct
    {
        ImRect rect;
    } box_selector;
};

struct ColorStyleElement
{
    ImU32 color;
    ColorStyle item;

    ColorStyleElement(const ImU32 c, const ColorStyle s)
      : color(c)
      , item(s)
    {}
};

struct StyleElement
{
    StyleVar item;
    float value;

    StyleElement(const float value, const StyleVar variable)
      : item(variable)
      , value(value)
    {}
};
} // namespace
// [SECTION] global struct
// this stores data which only lives for one frame
struct Context
{
    EditorContext* default_editor_ctx;
    EditorContext* editor_ctx;

    // Canvas draw list and helper state
    ImDrawList* canvas_draw_list;
    ImGuiStorage node_idx_to_submission_idx;
    ImVector<int> node_idx_submission_order;
    ImVector<int> node_indices_overlapping_with_mouse;
    ImVector<int> occluded_pin_indices;

    // Canvas extents
    ImVec2 canvas_origin_screen_space;
    ImRect canvas_rect_screen_space;

    // Debug helpers
    ScopeFlags current_scope;

    // Configuration state
    IO io;
    Style style;
    ImVector<ColorStyleElement> color_modifier_stack;
    ImVector<StyleElement> style_modifier_stack;
    ImGuiTextBuffer text_buffer;

    int current_attribute_flags;
    ImVector<int> attribute_flag_stack;

    // UI element state
    int current_node_idx;
    int current_pin_idx;
    int current_attribute_id;

    OptionalIndex hovered_node_idx;
    OptionalIndex interactive_node_idx;
    OptionalIndex hovered_link_idx;
    OptionalIndex hovered_pin_idx;
    int hovered_pin_flags;

    OptionalIndex deleted_link_idx;
    OptionalIndex snap_link_idx;

    // Event helper state
    int element_state_change;

    int active_attribute_id;
    bool active_attribute;

    // ImGui::IO cache

    ImVec2 mouse_pos;

    bool left_mouse_clicked;
    bool left_mouse_released;
    bool alt_mouse_clicked;
    bool left_mouse_dragging;
    bool alt_mouse_dragging;
};

Context* g = NULL;

namespace {

EditorContext&
editor_context_get()
{
    // No editor context was set! Did you forget to call imnodes::Initialize?
    assert(g->editor_ctx != NULL);
    return *g->editor_ctx;
}

inline ImVec2
eval_bezier(float t, const BezierCurve& bezier)
{
    // B(t) = (1-t)**3 p0 + 3(1 - t)**2 t P1 + 3(1-t)t**2 P2 + t**3 P3
    return ImVec2((1 - t) * (1 - t) * (1 - t) * bezier.p0.x +
                    3 * (1 - t) * (1 - t) * t * bezier.p1.x +
                    3 * (1 - t) * t * t * bezier.p2.x + t * t * t * bezier.p3.x,
                  (1 - t) * (1 - t) * (1 - t) * bezier.p0.y +
                    3 * (1 - t) * (1 - t) * t * bezier.p1.y +
                    3 * (1 - t) * t * t * bezier.p2.y +
                    t * t * t * bezier.p3.y);
}

// Calculates the closest point along each bezier curve segment.
ImVec2
get_closest_point_on_cubic_bezier(const int num_segments,
                                  const ImVec2& p,
                                  const BezierCurve& bezier)
{
    IM_ASSERT(num_segments > 0);
    ImVec2 p_last = bezier.p0;
    ImVec2 p_closest;
    float p_closest_dist = FLT_MAX;
    float t_step = 1.0f / (float)num_segments;
    for (int i = 1; i <= num_segments; ++i) {
        ImVec2 p_current = eval_bezier(t_step * i, bezier);
        ImVec2 p_line = ImLineClosestPoint(p_last, p_current, p);
        float dist = ImLengthSqr(p - p_line);
        if (dist < p_closest_dist) {
            p_closest = p_line;
            p_closest_dist = dist;
        }
        p_last = p_current;
    }
    return p_closest;
}

inline float
get_distance_to_cubic_bezier(const ImVec2& pos,
                             const BezierCurve& bezier,
                             const int num_segments)
{
    const ImVec2 point_on_curve =
      get_closest_point_on_cubic_bezier(num_segments, pos, bezier);

    const ImVec2 to_curve = point_on_curve - pos;
    return ImSqrt(ImLengthSqr(to_curve));
}

inline ImRect
get_containing_rect_for_bezier_curve(const BezierCurve& bezier)
{
    const ImVec2 min =
      ImVec2(ImMin(bezier.p0.x, bezier.p3.x), ImMin(bezier.p0.y, bezier.p3.y));
    const ImVec2 max =
      ImVec2(ImMax(bezier.p0.x, bezier.p3.x), ImMax(bezier.p0.y, bezier.p3.y));

    const float hover_distance = g->style.link_hover_distance;

    ImRect rect(min, max);
    rect.Add(bezier.p1);
    rect.Add(bezier.p2);
    rect.Expand(ImVec2(hover_distance, hover_distance));

    return rect;
}

inline LinkBezierData
get_link_renderable(ImVec2 start,
                    ImVec2 end,
                    const AttributeType start_type,
                    const float line_segments_per_length)
{
    assert((start_type == AttributeType_Input) ||
           (start_type == AttributeType_Output));
    if (start_type == AttributeType_Input) {
        ImSwap(start, end);
    }

    const float link_length = ImSqrt(ImLengthSqr(end - start));
    const ImVec2 offset = ImVec2(0.25f * link_length, 0.f);
    LinkBezierData link_data;
    link_data.bezier.p0 = start;
    link_data.bezier.p1 = start + offset;
    link_data.bezier.p2 = end - offset;
    link_data.bezier.p3 = end;
    link_data.num_segments =
      ImMax(static_cast<int>(link_length * line_segments_per_length), 1);
    return link_data;
}

inline float
eval_implicit_line_eq(const ImVec2& p1, const ImVec2& p2, const ImVec2& p)
{
    return (p2.y - p1.y) * p.x + (p1.x - p2.x) * p.y +
           (p2.x * p1.y - p1.x * p2.y);
}

inline int
sign(float val)
{
    return int(val > 0.0f) - int(val < 0.0f);
}

inline bool
rectangle_overlaps_line_segment(const ImRect& rect,
                                const ImVec2& p1,
                                const ImVec2& p2)
{
    // Trivial case: rectangle contains an endpoint
    if (rect.Contains(p1) || rect.Contains(p2)) {
        return true;
    }

    // Flip rectangle if necessary
    ImRect flip_rect = rect;

    if (flip_rect.Min.x > flip_rect.Max.x) {
        ImSwap(flip_rect.Min.x, flip_rect.Max.x);
    }

    if (flip_rect.Min.y > flip_rect.Max.y) {
        ImSwap(flip_rect.Min.y, flip_rect.Max.y);
    }

    // Trivial case: line segment lies to one particular side of rectangle
    if ((p1.x < flip_rect.Min.x && p2.x < flip_rect.Min.x) ||
        (p1.x > flip_rect.Max.x && p2.x > flip_rect.Max.x) ||
        (p1.y < flip_rect.Min.y && p2.y < flip_rect.Min.y) ||
        (p1.y > flip_rect.Max.y && p2.y > flip_rect.Max.y)) {
        return false;
    }

    const int corner_signs[4] = {
        sign(eval_implicit_line_eq(p1, p2, flip_rect.Min)),
        sign(eval_implicit_line_eq(
          p1, p2, ImVec2(flip_rect.Max.x, flip_rect.Min.y))),
        sign(eval_implicit_line_eq(
          p1, p2, ImVec2(flip_rect.Min.x, flip_rect.Max.y))),
        sign(eval_implicit_line_eq(p1, p2, flip_rect.Max))
    };

    int sum = 0;
    int sum_abs = 0;

    for (int i = 0; i < 4; ++i) {
        sum += corner_signs[i];
        sum_abs += abs(corner_signs[i]);
    }

    // At least one corner of rectangle lies on a different side of line segment
    return abs(sum) != sum_abs;
}

inline bool
rectangle_overlaps_bezier(const ImRect& rectangle,
                          const LinkBezierData& link_data)
{
    ImVec2 current = eval_bezier(0.f, link_data.bezier);
    const float dt = 1.0f / link_data.num_segments;
    for (int s = 0; s < link_data.num_segments; ++s) {
        ImVec2 next =
          eval_bezier(static_cast<float>((s + 1) * dt), link_data.bezier);
        if (rectangle_overlaps_line_segment(rectangle, current, next)) {
            return true;
        }
        current = next;
    }
    return false;
}

inline bool
rectangle_overlaps_link(const ImRect& rectangle,
                        const ImVec2& start,
                        const ImVec2& end,
                        const AttributeType start_type)
{
    // First level: simple rejection test via rectangle overlap:

    ImRect lrect = ImRect(start, end);
    if (lrect.Min.x > lrect.Max.x) {
        ImSwap(lrect.Min.x, lrect.Max.x);
    }

    if (lrect.Min.y > lrect.Max.y) {
        ImSwap(lrect.Min.y, lrect.Max.y);
    }

    if (rectangle.Overlaps(lrect)) {
        // First, check if either one or both endpoinds are trivially contained
        // in the rectangle

        if (rectangle.Contains(start) || rectangle.Contains(end)) {
            return true;
        }

        // Second level of refinement: do a more expensive test against the
        // link

        const LinkBezierData link_data = get_link_renderable(
          start, end, start_type, g->style.link_line_segments_per_length);
        return rectangle_overlaps_bezier(rectangle, link_data);
    }

    return false;
}
} // namespace

// [SECTION] editor context definition

struct EditorContext
{
    ObjectPool<NodeData> nodes;
    ObjectPool<PinData> pins;
    ObjectPool<LinkData> links;

    ImVector<int> node_depth_order;

    // ui related fields
    ImVec2 panning;

    ImVector<int> selected_node_indices;
    ImVector<int> selected_link_indices;

    ClickInteractionType click_interaction_type;
    ClickInteractionState click_interaction_state;

    EditorContext()
      : nodes()
      , pins()
      , links()
      , panning(0.f, 0.f)
      , selected_node_indices()
      , selected_link_indices()
      , click_interaction_type(ClickInteractionType_None)
      , click_interaction_state()
    {}
};

namespace {
// [SECTION] draw list helper

void
ImDrawList_grow_channels(ImDrawList* draw_list, const int num_channels)
{
    ImDrawListSplitter& splitter = draw_list->_Splitter;

    if (splitter._Count == 1) {
        splitter.Split(draw_list, num_channels + 1);
        return;
    }

    // NOTE: this logic has been lifted from ImDrawListSplitter::Split with
    // slight modifications to allow nested splits. The main modification is
    // that we only create new ImDrawChannel instances after splitter._Count,
    // instead of over the whole splitter._Channels array like the regular
    // ImDrawListSplitter::Split method does.

    const int old_channel_capacity = splitter._Channels.Size;
    // NOTE: _Channels is not resized down, and therefore _Count <=
    // _Channels.size()!
    const int old_channel_count = splitter._Count;
    const int requested_channel_count = old_channel_count + num_channels;
    if (old_channel_capacity < old_channel_count + num_channels) {
        splitter._Channels.resize(requested_channel_count);
    }

    splitter._Count = requested_channel_count;

    for (int i = old_channel_count; i < requested_channel_count; ++i) {
        ImDrawChannel& channel = splitter._Channels[i];

        // If we're inside the old capacity region of the array, we need to
        // reuse the existing memory of the command and index buffers.
        if (i < old_channel_capacity) {
            channel._CmdBuffer.resize(0);
            channel._IdxBuffer.resize(0);
        }
        // Else, we need to construct new draw channels.
        else {
            IM_PLACEMENT_NEW(&channel) ImDrawChannel();
        }

        {
            ImDrawCmd draw_cmd;
            draw_cmd.ClipRect = draw_list->_ClipRectStack.back();
            draw_cmd.TextureId = draw_list->_TextureIdStack.back();
            channel._CmdBuffer.push_back(draw_cmd);
        }
    }
}

void
ImDrawListSplitter_swap_channels(ImDrawListSplitter& splitter,
                                 const int lhs_idx,
                                 const int rhs_idx)
{
    if (lhs_idx == rhs_idx) {
        return;
    }

    assert(lhs_idx >= 0 && lhs_idx < splitter._Count);
    assert(rhs_idx >= 0 && rhs_idx < splitter._Count);

    ImDrawChannel& lhs_channel = splitter._Channels[lhs_idx];
    ImDrawChannel& rhs_channel = splitter._Channels[rhs_idx];
    lhs_channel._CmdBuffer.swap(rhs_channel._CmdBuffer);
    lhs_channel._IdxBuffer.swap(rhs_channel._IdxBuffer);

    const int current_channel = splitter._Current;

    if (current_channel == lhs_idx) {
        splitter._Current = rhs_idx;
    } else if (current_channel == rhs_idx) {
        splitter._Current = lhs_idx;
    }
}

void
draw_list_set(ImDrawList* window_draw_list)
{
    g->canvas_draw_list = window_draw_list;
    g->node_idx_to_submission_idx.Clear();
    g->node_idx_submission_order.clear();
}

// The draw list channels are structured as follows. First we have our base
// channel, the canvas grid on which we render the grid lines in
// BeginNodeEditor(). The base channel is the reason
// draw_list_submission_idx_to_background_channel_idx offsets the index by one.
// Each BeginNode() call appends two new draw channels, for the node background
// and foreground. The node foreground is the channel into which the node's
// ImGui content is rendered. Finally, in EndNodeEditor() we append one last
// draw channel for rendering the selection box and the incomplete link on top
// of everything else.
//
// +----------+----------+----------+----------+----------+----------+
// |          |          |          |          |          |          |
// |canvas    |node      |node      |...       |...       |click     |
// |grid      |background|foreground|          |          |interaction
// |          |          |          |          |          |          |
// +----------+----------+----------+----------+----------+----------+
//            |                     |
//            |   submission idx    |
//            |                     |
//            -----------------------

void
draw_list_add_node(const int node_idx)
{
    g->node_idx_to_submission_idx.SetInt(static_cast<ImGuiID>(node_idx),
                                         g->node_idx_submission_order.Size);
    g->node_idx_submission_order.push_back(node_idx);
    ImDrawList_grow_channels(g->canvas_draw_list, 2);
}

void
draw_list_append_click_interaction_channel()
{
    // NOTE: don't use this function outside of EndNodeEditor. Using this before
    // all nodes have been added will screw up the node draw order.
    ImDrawList_grow_channels(g->canvas_draw_list, 1);
}

int
draw_list_submission_idx_to_background_channel_idx(const int submission_idx)
{
    // NOTE: the first channel is the canvas background, i.e. the grid
    return 1 + 2 * submission_idx;
}

int
draw_list_submission_idx_to_foreground_channel_idx(const int submission_idx)
{
    return draw_list_submission_idx_to_background_channel_idx(submission_idx) +
           1;
}

void
draw_list_activate_click_interaction_channel()
{
    g->canvas_draw_list->_Splitter.SetCurrentChannel(
      g->canvas_draw_list, g->canvas_draw_list->_Splitter._Count - 1);
}

void
draw_list_activate_current_node_foreground()
{
    const int foreground_channel_idx =
      draw_list_submission_idx_to_foreground_channel_idx(
        g->node_idx_submission_order.Size - 1);
    g->canvas_draw_list->_Splitter.SetCurrentChannel(g->canvas_draw_list,
                                                     foreground_channel_idx);
}

void
draw_list_activate_node_background(const int node_idx)
{
    const int submission_idx =
      g->node_idx_to_submission_idx.GetInt(static_cast<ImGuiID>(node_idx), -1);
    // There is a discrepancy in the submitted node count and the rendered node
    // count! Did you call one of the following functions
    // * EditorContextMoveToNode
    // * SetNodeScreenSpacePos
    // * SetNodeGridSpacePos
    // * SetNodeDraggable
    // after the BeginNode/EndNode function calls?
    assert(submission_idx != -1);
    const int background_channel_idx =
      draw_list_submission_idx_to_background_channel_idx(submission_idx);
    g->canvas_draw_list->_Splitter.SetCurrentChannel(g->canvas_draw_list,
                                                     background_channel_idx);
}

void
draw_list_swap_submission_indices(const int lhs_idx, const int rhs_idx)
{
    assert(lhs_idx != rhs_idx);

    const int lhs_foreground_channel_idx =
      draw_list_submission_idx_to_foreground_channel_idx(lhs_idx);
    const int lhs_background_channel_idx =
      draw_list_submission_idx_to_background_channel_idx(lhs_idx);
    const int rhs_foreground_channel_idx =
      draw_list_submission_idx_to_foreground_channel_idx(rhs_idx);
    const int rhs_background_channel_idx =
      draw_list_submission_idx_to_background_channel_idx(rhs_idx);

    ImDrawListSplitter_swap_channels(g->canvas_draw_list->_Splitter,
                                     lhs_background_channel_idx,
                                     rhs_background_channel_idx);
    ImDrawListSplitter_swap_channels(g->canvas_draw_list->_Splitter,
                                     lhs_foreground_channel_idx,
                                     rhs_foreground_channel_idx);
}

void
draw_list_sort_channels_by_depth(const ImVector<int>& node_idx_depth_order)
{
    if (g->node_idx_to_submission_idx.Data.Size < 2) {
        return;
    }

    assert(node_idx_depth_order.Size == g->node_idx_submission_order.Size);

    int start_idx = node_idx_depth_order.Size - 1;

    while (node_idx_depth_order[start_idx] ==
           g->node_idx_submission_order[start_idx]) {
        if (--start_idx == 0) {
            // early out if submission order and depth order are the same
            return;
        }
    }

    // TODO: this is an O(N^2) algorithm. It might be worthwhile revisiting this
    // to see if the time complexity can be reduced.

    for (int depth_idx = start_idx; depth_idx > 0; --depth_idx) {
        const int node_idx = node_idx_depth_order[depth_idx];

        // Find the current index of the node_idx in the submission order array
        int submission_idx = -1;
        for (int i = 0; i < g->node_idx_submission_order.Size; ++i) {
            if (g->node_idx_submission_order[i] == node_idx) {
                submission_idx = i;
                break;
            }
        }
        assert(submission_idx >= 0);

        if (submission_idx == depth_idx) {
            continue;
        }

        for (int j = submission_idx; j < depth_idx; ++j) {
            draw_list_swap_submission_indices(j, j + 1);
            ImSwap(g->node_idx_submission_order[j],
                   g->node_idx_submission_order[j + 1]);
        }
    }
}

// [SECTION] ObjectPool implementation

template<typename T>
int
object_pool_find(ObjectPool<T>& objects, const int id)
{
    const int index = objects.id_map.GetInt(static_cast<ImGuiID>(id), -1);
    return index;
}

template<typename T>
void
object_pool_update(ObjectPool<T>& objects)
{
    objects.free_list.clear();
    for (int i = 0; i < objects.in_use.size(); ++i) {
        if (!objects.in_use[i]) {
            objects.id_map.SetInt(objects.pool[i].id, -1);
            objects.free_list.push_back(i);
            (objects.pool.Data + i)->~T();
        }
    }
}

template<>
void
object_pool_update(ObjectPool<NodeData>& nodes)
{
    nodes.free_list.clear();
    for (int i = 0; i < nodes.in_use.size(); ++i) {
        if (nodes.in_use[i]) {
            nodes.pool[i].pin_indices.clear();
        } else {
            const int previous_id = nodes.pool[i].id;
            const int previous_idx = nodes.id_map.GetInt(previous_id, -1);

            if (previous_idx != -1) {
                assert(previous_idx == i);
                // Remove node idx form depth stack the first time we detect
                // that this idx slot is unused
                ImVector<int>& depth_stack =
                  editor_context_get().node_depth_order;
                const int* const elem = depth_stack.find(i);
                assert(elem != depth_stack.end());
                depth_stack.erase(elem);
            }

            nodes.id_map.SetInt(previous_id, -1);
            nodes.free_list.push_back(i);
            (nodes.pool.Data + i)->~NodeData();
        }
    }
}

template<typename T>
void
object_pool_reset(ObjectPool<T>& objects)
{
    if (!objects.in_use.empty()) {
        memset(objects.in_use.Data, 0, objects.in_use.size_in_bytes());
    }
}

template<typename T>
int
object_pool_find_or_create_index(ObjectPool<T>& objects, const int id)
{
    int index = objects.id_map.GetInt(static_cast<ImGuiID>(id), -1);

    // Construct new object
    if (index == -1) {
        if (objects.free_list.empty()) {
            index = objects.pool.size();
            IM_ASSERT(objects.pool.size() == objects.in_use.size());
            const int new_size = objects.pool.size() + 1;
            objects.pool.resize(new_size);
            objects.in_use.resize(new_size);
        } else {
            index = objects.free_list.back();
            objects.free_list.pop_back();
        }
        IM_PLACEMENT_NEW(objects.pool.Data + index) T(id);
        objects.id_map.SetInt(static_cast<ImGuiID>(id), index);
    }

    // Flag it as used
    objects.in_use[index] = true;

    return index;
}

template<>
int
object_pool_find_or_create_index(ObjectPool<NodeData>& nodes, const int node_id)
{
    int node_idx = nodes.id_map.GetInt(static_cast<ImGuiID>(node_id), -1);

    // Construct new node
    if (node_idx == -1) {
        if (nodes.free_list.empty()) {
            node_idx = nodes.pool.size();
            IM_ASSERT(nodes.pool.size() == nodes.in_use.size());
            const int new_size = nodes.pool.size() + 1;
            nodes.pool.resize(new_size);
            nodes.in_use.resize(new_size);
        } else {
            node_idx = nodes.free_list.back();
            nodes.free_list.pop_back();
        }
        IM_PLACEMENT_NEW(nodes.pool.Data + node_idx) NodeData(node_id);
        nodes.id_map.SetInt(static_cast<ImGuiID>(node_id), node_idx);

        EditorContext& editor = editor_context_get();
        editor.node_depth_order.push_back(node_idx);
    }

    // Flag node as used
    nodes.in_use[node_idx] = true;

    return node_idx;
}

template<typename T>
T&
object_pool_find_or_create_object(ObjectPool<T>& objects, const int id)
{
    const int index = object_pool_find_or_create_index(objects, id);
    return objects.pool[index];
}

// [SECTION] ui state logic

ImVec2
get_screen_space_pin_coordinates(const ImRect& node_rect,
                                 const ImRect& attribute_rect,
                                 const AttributeType type)
{
    assert(type == AttributeType_Input || type == AttributeType_Output);
    const float x = type == AttributeType_Input
                      ? (node_rect.Min.x - g->style.pin_offset)
                      : (node_rect.Max.x + g->style.pin_offset);
    return ImVec2(x, 0.5f * (attribute_rect.Min.y + attribute_rect.Max.y));
}

ImVec2
get_screen_space_pin_coordinates(const EditorContext& editor,
                                 const PinData& pin)
{
    const ImRect& parent_node_rect =
      editor.nodes.pool[pin.parent_node_idx].rect;
    return get_screen_space_pin_coordinates(
      parent_node_rect, pin.attribute_rect, pin.type);
}

bool
mouse_in_canvas()
{
    // This flag should be true either when hovering or clicking something in
    // the canvas.
    const bool is_window_hovered_or_focused =
      ImGui::IsWindowHovered() || ImGui::IsWindowFocused();

    return is_window_hovered_or_focused &&
           g->canvas_rect_screen_space.Contains(ImGui::GetMousePos());
}

void
begin_node_selection(EditorContext& editor, const int node_idx)
{
    // Don't start selecting a node if we are e.g. already creating and dragging
    // a new link! New link creation can happen when the mouse is clicked over
    // a node, but within the hover radius of a pin.
    if (editor.click_interaction_type != ClickInteractionType_None) {
        return;
    }

    editor.click_interaction_type = ClickInteractionType_Node;
    // If the node is not already contained in the selection, then we want only
    // the interaction node to be selected, effective immediately.
    //
    // Otherwise, we want to allow for the possibility of multiple nodes to be
    // moved at once.
    if (!editor.selected_node_indices.contains(node_idx)) {
        editor.selected_node_indices.clear();
        editor.selected_link_indices.clear();
        editor.selected_node_indices.push_back(node_idx);

        // Ensure that individually selected nodes get rendered on top
        ImVector<int>& depth_stack = editor.node_depth_order;
        const int* const elem = depth_stack.find(node_idx);
        assert(elem != depth_stack.end());
        depth_stack.erase(elem);
        depth_stack.push_back(node_idx);
    }
}

void
begin_link_selection(EditorContext& editor, const int link_idx)
{
    editor.click_interaction_type = ClickInteractionType_Link;
    // When a link is selected, clear all other selections, and insert the link
    // as the sole selection.
    editor.selected_node_indices.clear();
    editor.selected_link_indices.clear();
    editor.selected_link_indices.push_back(link_idx);
}

void
begin_link_detach(EditorContext& editor,
                  const int link_idx,
                  const int detach_pin_idx)
{
    const LinkData& link = editor.links.pool[link_idx];
    ClickInteractionState& state = editor.click_interaction_state;
    state.link_creation.end_pin_idx.reset();
    state.link_creation.start_pin_idx = detach_pin_idx == link.start_pin_idx
                                          ? link.end_pin_idx
                                          : link.start_pin_idx;
    g->deleted_link_idx = link_idx;
}

void
begin_link_interaction(EditorContext& editor, const int link_idx)
{
    // First check if we are clicking a link in the vicinity of a pin.
    // This may result in a link detach via click and drag.
    if (editor.click_interaction_type == ClickInteractionType_LinkCreation) {
        if ((g->hovered_pin_flags &
             AttributeFlags_EnableLinkDetachWithDragClick) != 0) {
            begin_link_detach(editor, link_idx, g->hovered_pin_idx.value());
            editor.click_interaction_state.link_creation.link_creation_type =
              LinkCreationType_FromDetach;
        }
    }
    // If we aren't near a pin, check if we are clicking the link with the
    // modifier pressed. This may also result in a link detach via clicking.
    else {
        const bool modifier_pressed =
          g->io.link_detach_with_modifier_click.modifier == NULL
            ? false
            : *g->io.link_detach_with_modifier_click.modifier;

        if (modifier_pressed) {
            const LinkData& link = editor.links.pool[link_idx];
            const PinData& start_pin = editor.pins.pool[link.start_pin_idx];
            const PinData& end_pin = editor.pins.pool[link.end_pin_idx];
            const ImVec2& mouse_pos = g->mouse_pos;
            const float dist_to_start = ImLengthSqr(start_pin.pos - mouse_pos);
            const float dist_to_end = ImLengthSqr(end_pin.pos - mouse_pos);
            const int closest_pin_idx = dist_to_start < dist_to_end
                                          ? link.start_pin_idx
                                          : link.end_pin_idx;

            editor.click_interaction_type = ClickInteractionType_LinkCreation;
            begin_link_detach(editor, link_idx, closest_pin_idx);
            editor.click_interaction_state.link_creation.link_creation_type =
              LinkCreationType_FromDetach;
        } else {
            begin_link_selection(editor, link_idx);
        }
    }
}

void
begin_link_creation(EditorContext& editor, const int hovered_pin_idx)
{
    editor.click_interaction_type = ClickInteractionType_LinkCreation;
    editor.click_interaction_state.link_creation.start_pin_idx =
      hovered_pin_idx;
    editor.click_interaction_state.link_creation.end_pin_idx.reset();
    editor.click_interaction_state.link_creation.link_creation_type =
      LinkCreationType_Standard;
    g->element_state_change |= ElementStateChange_LinkStarted;
}

void
begin_canvas_interaction(EditorContext& editor)
{
    const bool any_ui_element_hovered =
      g->hovered_node_idx.has_value() || g->hovered_link_idx.has_value() ||
      g->hovered_pin_idx.has_value() || ImGui::IsAnyItemHovered();

    const bool mouse_not_in_canvas = !mouse_in_canvas();

    if (editor.click_interaction_type != ClickInteractionType_None ||
        any_ui_element_hovered || mouse_not_in_canvas) {
        return;
    }

    const bool started_panning = g->alt_mouse_clicked;

    if (started_panning) {
        editor.click_interaction_type = ClickInteractionType_Panning;
    } else if (g->left_mouse_clicked) {
        editor.click_interaction_type = ClickInteractionType_BoxSelection;
        editor.click_interaction_state.box_selector.rect.Min = g->mouse_pos;
    }
}

void
box_selector_update_selection(EditorContext& editor, ImRect box_rect)
{
    // Invert box selector coordinates as needed

    if (box_rect.Min.x > box_rect.Max.x) {
        ImSwap(box_rect.Min.x, box_rect.Max.x);
    }

    if (box_rect.Min.y > box_rect.Max.y) {
        ImSwap(box_rect.Min.y, box_rect.Max.y);
    }

    // Update node selection

    editor.selected_node_indices.clear();

    // Test for overlap against node rectangles

    for (int node_idx = 0; node_idx < editor.nodes.pool.size(); ++node_idx) {
        if (editor.nodes.in_use[node_idx]) {
            NodeData& node = editor.nodes.pool[node_idx];
            if (box_rect.Overlaps(node.rect)) {
                editor.selected_node_indices.push_back(node_idx);
            }
        }
    }

    // Update link selection

    editor.selected_link_indices.clear();

    // Test for overlap against links

    for (int link_idx = 0; link_idx < editor.links.pool.size(); ++link_idx) {
        if (editor.links.in_use[link_idx]) {
            const LinkData& link = editor.links.pool[link_idx];

            const PinData& pin_start = editor.pins.pool[link.start_pin_idx];
            const PinData& pin_end = editor.pins.pool[link.end_pin_idx];
            const ImRect& node_start_rect =
              editor.nodes.pool[pin_start.parent_node_idx].rect;
            const ImRect& node_end_rect =
              editor.nodes.pool[pin_end.parent_node_idx].rect;

            const ImVec2 start = get_screen_space_pin_coordinates(
              node_start_rect, pin_start.attribute_rect, pin_start.type);
            const ImVec2 end = get_screen_space_pin_coordinates(
              node_end_rect, pin_end.attribute_rect, pin_end.type);

            // Test
            if (rectangle_overlaps_link(box_rect, start, end, pin_start.type)) {
                editor.selected_link_indices.push_back(link_idx);
            }
        }
    }
}

void
translate_selected_nodes(EditorContext& editor)
{
    if (g->left_mouse_dragging) {
        const ImGuiIO& io = ImGui::GetIO();
        for (int i = 0; i < editor.selected_node_indices.size(); ++i) {
            const int node_idx = editor.selected_node_indices[i];
            NodeData& node = editor.nodes.pool[node_idx];
            if (node.draggable) {
                node.origin += io.MouseDelta;
            }
        }
    }
}

OptionalIndex
find_duplicate_link(const EditorContext& editor,
                    const int start_pin_idx,
                    const int end_pin_idx)
{
    LinkData test_link(0);
    test_link.start_pin_idx = start_pin_idx;
    test_link.end_pin_idx = end_pin_idx;
    for (int link_idx = 0; link_idx < editor.links.pool.size(); ++link_idx) {
        const LinkData& link = editor.links.pool[link_idx];
        if (LinkPredicate()(test_link, link) && editor.links.in_use[link_idx]) {
            return OptionalIndex(link_idx);
        }
    }

    return OptionalIndex();
}

bool
should_link_snap_to_pin(const EditorContext& editor,
                        const PinData& start_pin,
                        const int hovered_pin_idx,
                        const OptionalIndex duplicate_link)
{
    const PinData& end_pin = editor.pins.pool[hovered_pin_idx];

    // The end pin must be in a different node
    if (start_pin.parent_node_idx == end_pin.parent_node_idx) {
        return false;
    }

    // The end pin must be of a different type
    if (start_pin.type == end_pin.type) {
        return false;
    }

    // The link to be created must not be a duplicate, unless it is the link
    // which was created on snap. In that case we want to snap, since we want it
    // to appear visually as if the created link remains snapped to the pin.
    if (duplicate_link.has_value() && !(duplicate_link == g->snap_link_idx)) {
        return false;
    }

    return true;
}

void
click_interaction_update(EditorContext& editor)
{
    switch (editor.click_interaction_type) {
    case ClickInteractionType_BoxSelection: {
        ImRect& box_rect = editor.click_interaction_state.box_selector.rect;
        box_rect.Max = g->mouse_pos;

        box_selector_update_selection(editor, box_rect);

        const ImU32 box_selector_color =
          g->style.colors[ColorStyle_BoxSelector];
        const ImU32 box_selector_outline =
          g->style.colors[ColorStyle_BoxSelectorOutline];
        g->canvas_draw_list->AddRectFilled(
          box_rect.Min, box_rect.Max, box_selector_color);
        g->canvas_draw_list->AddRect(
          box_rect.Min, box_rect.Max, box_selector_outline);

        if (g->left_mouse_released) {
            ImVector<int>& depth_stack = editor.node_depth_order;
            const ImVector<int>& selected_idxs = editor.selected_node_indices;

            // Bump the selected node indices, in order, to the top of the depth
            // stack. NOTE: this algorithm has worst case time complexity of
            // O(N^2), if the node selection is ~ N (due to
            // selected_idxs.contains()).

            if ((selected_idxs.Size > 0) &&
                (selected_idxs.Size < depth_stack.Size)) {
                int num_moved = 0; // The number of indices moved. Stop after
                                   // selected_idxs.Size
                for (int i = 0; i < depth_stack.Size - selected_idxs.Size;
                     ++i) {
                    for (int node_idx = depth_stack[i];
                         selected_idxs.contains(node_idx);
                         node_idx = depth_stack[i]) {
                        depth_stack.erase(depth_stack.begin() +
                                          static_cast<size_t>(i));
                        depth_stack.push_back(node_idx);
                        ++num_moved;
                    }

                    if (num_moved == selected_idxs.Size) {
                        break;
                    }
                }
            }

            editor.click_interaction_type = ClickInteractionType_None;
        }
    } break;
    case ClickInteractionType_Node: {
        translate_selected_nodes(editor);

        if (g->left_mouse_released) {
            editor.click_interaction_type = ClickInteractionType_None;
        }
    } break;
    case ClickInteractionType_Link: {
        if (g->left_mouse_released) {
            editor.click_interaction_type = ClickInteractionType_None;
        }
    } break;
    case ClickInteractionType_LinkCreation: {
        const PinData& start_pin =
          editor.pins
            .pool[editor.click_interaction_state.link_creation.start_pin_idx];

        const OptionalIndex maybe_duplicate_link_idx =
          g->hovered_pin_idx.has_value<