annatomic 0.4.0

use std::{
    cmp::Ordering,
    collections::{BTreeMap, HashSet},
};

use anyhow::Context as _;
use egui::{Button, KeyboardShortcut, TextBuffer, Ui};

use graphannis::{
    AnnotationGraph,
    graph::{AnnoKey, Annotation, NodeID},
    model::{
        AnnotationComponent,
        AnnotationComponentType::{self, PartOf},
    },
    update::UpdateEvent,
};
use graphannis_core::{
    annostorage::ValueSearch,
    graph::{ANNIS_NS, NODE_NAME_KEY, NODE_TYPE_KEY},
};
use serde::{Deserialize, Serialize};

use crate::app::util::token_helper::{TOKEN_KEY, TokenHelper};

use super::project::ChangeSet;

/// Common trait for actions that can be performed on a specifc editor.
///
/// Editor actions typically have a menu entry and can often be triggered by a shortcut.
/// They might create graph actions, but also just change the state of the editor to prepare another action.
pub(crate) trait EditorAction {
    type EditorImpl;

    fn label() -> &'static str;
    fn perform(editor: &mut Self::EditorImpl);
    fn enabled(editor: &Self::EditorImpl) -> bool;
    fn shortcut() -> Option<KeyboardShortcut> {
        None
    }

    fn create_menu_button(ui: &mut Ui, editor: &mut Self::EditorImpl) {
        let mut button = Button::new(Self::label());
        if let Some(shortcut) = Self::shortcut() {
            button = button.shortcut_text(ui.ctx().format_shortcut(&shortcut))
        }
        if ui.add_enabled(Self::enabled(editor), button).clicked() {
            Self::perform(editor);
        }
    }

    fn consume_and_perform_shortcut(ctx: &egui::Context, editor: &mut Self::EditorImpl) {
        if let Some(shortcut) = Self::shortcut()
            && Self::enabled(editor)
            && ctx.input_mut(|i| {
                i.consume_shortcut(&shortcut) && i.modifiers.matches_exact(shortcut.modifiers)
            })
        {
            Self::perform(editor);
        }
    }
}

#[derive(Clone, Debug, Deserialize, Serialize)]
#[non_exhaustive]
pub(crate) enum GraphAction {
    AddSubCorpus {
        parent_node: String,
    },
    DeleteCorpusNode {
        node_name: String,
    },
    AddInitialToken {
        parent_name: String,
    },
    AddBaseTokenBefore {
        reference_node: String,
        parent_name: String,
    },
    AddBaseTokenAfter {
        reference_node: String,
        parent_name: String,
    },
    ExpandNodeLeft {
        reference_node: String,
    },
    ExpandNodeRight {
        reference_node: String,
    },
    ShrinkNodeRight {
        reference_node: String,
    },
    ShrinkNodeLeft {
        reference_node: String,
    },
    AnnoValueChanged {
        node_name: String,
        anno: Annotation,
    },
    AnnoRemoved {
        node_name: String,
        anno_key: AnnoKey,
    },
    AddSpan {
        selected_token: HashSet<String>,
        parent_name: String,
        anno_key: AnnoKey,
    },
    AddSegmentationSpan {
        segmentation: String,
        selected_token: HashSet<String>,
        parent_name: String,
    },
    DeleteNodes {
        node_names: Vec<String>,
    },
}

impl GraphAction {
    /// Returns the graph updates necessary to apply and undo the changes, but
    /// does not create an editor state update.
    pub(crate) fn create_changeset(&self, graph: &AnnotationGraph) -> anyhow::Result<ChangeSet> {
        let mut updates = Vec::new();
        let mut reverse_updates = Vec::new();

        match self {
            GraphAction::AddSubCorpus { parent_node } => {
                let new_node_name = format!("{parent_node}/new");

                updates.push(UpdateEvent::AddNode {
                    node_name: new_node_name.clone(),
                    node_type: "corpus".to_string(),
                });

                updates.push(UpdateEvent::AddEdge {
                    source_node: new_node_name.clone(),
                    target_node: parent_node.clone(),
                    layer: ANNIS_NS.to_string(),
                    component_type: PartOf.to_string(),
                    component_name: "".to_string(),
                });

                reverse_updates.push(UpdateEvent::DeleteNode {
                    node_name: new_node_name,
                });
            }
            GraphAction::DeleteCorpusNode { node_name } => {
                let node_id = graph
                    .get_node_annos()
                    .get_node_id_from_name(node_name)?
                    .context("Missing node ID")?;

                updates.push(UpdateEvent::DeleteNode {
                    node_name: node_name.clone(),
                });

                reverse_updates.extend(update_events_to_restore_deleted_node(graph, node_name)?);

                // Find all nodes that are part of this subcorpus/document and delete them, too.
                for c in graph.get_all_components(Some(PartOf), None) {
                    if let Some(gs) = graph.get_graphstorage_as_ref(&c) {
                        for other in
                            gs.find_connected_inverse(node_id, 1, std::ops::Bound::Unbounded)
                        {
                            let other = other?;
                            let other_name = graph
                                .get_node_annos()
                                .get_value_for_item(&other, &NODE_NAME_KEY)?
                                .context("Missing node name")?;
                            updates.push(UpdateEvent::DeleteNode {
                                node_name: other_name.to_string(),
                            });
                            reverse_updates
                                .extend(update_events_to_restore_deleted_node(graph, &other_name)?);
                        }
                    }
                }
            }
            GraphAction::AddInitialToken { parent_name } => {
                let name_prefix = if let Some((prefix, _suffix)) = parent_name.split_once("#") {
                    prefix
                } else {
                    parent_name
                };
                let new_node_name = format!("{name_prefix}#tok{}", 1);
                updates.push(UpdateEvent::AddNode {
                    node_name: new_node_name.clone(),
                    node_type: "node".into(),
                });
                updates.push(UpdateEvent::AddNodeLabel {
                    node_name: new_node_name.clone(),
                    anno_ns: ANNIS_NS.to_string(),
                    anno_name: "tok".to_string(),
                    anno_value: egui_phosphor::regular::BIRD.to_string(),
                });
                updates.push(UpdateEvent::AddEdge {
                    source_node: new_node_name.clone(),
                    target_node: parent_name.to_string(),
                    layer: ANNIS_NS.to_string(),
                    component_type: PartOf.to_string(),
                    component_name: "".to_string(),
                });
                reverse_updates.push(UpdateEvent::DeleteNode {
                    node_name: new_node_name.clone(),
                });
            }
            GraphAction::AddBaseTokenBefore {
                reference_node,
                parent_name,
            } => {
                apply_add_base_token(
                    graph,
                    reference_node,
                    parent_name,
                    true,
                    &mut updates,
                    &mut reverse_updates,
                )?;
            }
            GraphAction::AddBaseTokenAfter {
                reference_node,
                parent_name,
            } => {
                apply_add_base_token(
                    graph,
                    reference_node,
                    parent_name,
                    false,
                    &mut updates,
                    &mut reverse_updates,
                )?;
            }
            GraphAction::AnnoValueChanged { node_name, anno } => {
                updates.push(UpdateEvent::DeleteNodeLabel {
                    node_name: node_name.to_string(),
                    anno_ns: anno.key.ns.clone(),
                    anno_name: anno.key.name.clone(),
                });
                updates.push(UpdateEvent::AddNodeLabel {
                    node_name: node_name.to_string(),
                    anno_ns: anno.key.ns.clone(),
                    anno_name: anno.key.name.clone(),
                    anno_value: anno.val.to_string(),
                });

                reverse_updates.push(UpdateEvent::DeleteNodeLabel {
                    node_name: node_name.to_string(),
                    anno_ns: anno.key.ns.to_string(),
                    anno_name: anno.key.name.to_string(),
                });
                let old_value = graph
                    .get_node_annos()
                    .get_value_for_item(&get_referenced_node_id(graph, node_name)?, &anno.key)?;

                if let Some(old_value) = old_value {
                    // Add the old annotation value back
                    reverse_updates.push(UpdateEvent::AddNodeLabel {
                        node_name: node_name.to_string(),
                        anno_ns: anno.key.ns.to_string(),
                        anno_name: anno.key.name.to_string(),
                        anno_value: old_value.to_string(),
                    });
                }
            }
            GraphAction::ExpandNodeLeft { reference_node } => {
                let reference_node_id = graph
                    .get_node_annos()
                    .get_node_id_from_name(reference_node)?
                    .context("Missing node ID")?;
                let tok_helper = TokenHelper::new(graph)?;
                if let Some(token_before_id) =
                    tok_helper.get_token_before(reference_node_id, None)?
                {
                    let token_before = graph
                        .get_node_annos()
                        .get_value_for_item(&token_before_id, &NODE_NAME_KEY)?
                        .context("Missing node name")?;
                    for cov_component in
                        graph.get_all_components(Some(AnnotationComponentType::Coverage), None)
                    {
                        let cov_gs = graph
                            .get_graphstorage(&cov_component)
                            .context("Missing coverage component")?;
                        if cov_gs.has_outgoing_edges(reference_node_id)? {
                            updates.push(UpdateEvent::AddEdge {
                                source_node: reference_node.to_string(),
                                target_node: token_before.to_string(),
                                layer: cov_component.layer.to_string(),
                                component_type: cov_component.get_type().to_string(),
                                component_name: cov_component.name.to_string(),
                            });
                            reverse_updates.push(UpdateEvent::DeleteEdge {
                                source_node: reference_node.to_string(),
                                target_node: token_before.to_string(),
                                layer: cov_component.layer.to_string(),
                                component_type: cov_component.get_type().to_string(),
                                component_name: cov_component.name.to_string(),
                            });
                        }
                    }
                }
            }
            GraphAction::ExpandNodeRight { reference_node } => {
                let reference_node_id = graph
                    .get_node_annos()
                    .get_node_id_from_name(reference_node)?
                    .context("Missing node ID")?;
                let tok_helper = TokenHelper::new(graph)?;
                if let Some(token_after_id) = tok_helper.get_token_after(reference_node_id, None)? {
                    let token_before = graph
                        .get_node_annos()
                        .get_value_for_item(&token_after_id, &NODE_NAME_KEY)?
                        .context("Missing node name")?;
                    for cov_component in
                        graph.get_all_components(Some(AnnotationComponentType::Coverage), None)
                    {
                        let cov_gs = graph
                            .get_graphstorage(&cov_component)
                            .context("Missing coverage component")?;
                        if cov_gs.has_outgoing_edges(reference_node_id)? {
                            updates.push(UpdateEvent::AddEdge {
                                source_node: reference_node.to_string(),
                                target_node: token_before.to_string(),
                                layer: cov_component.layer.to_string(),
                                component_type: cov_component.get_type().to_string(),
                                component_name: cov_component.name.to_string(),
                            });
                            reverse_updates.push(UpdateEvent::DeleteEdge {
                                source_node: reference_node.to_string(),
                                target_node: token_before.to_string(),
                                layer: cov_component.layer.to_string(),
                                component_type: cov_component.get_type().to_string(),
                                component_name: cov_component.name.to_string(),
                            });
                        }
                    }
                }
            }
            GraphAction::ShrinkNodeLeft { reference_node } => {
                let reference_node_id = graph
                    .get_node_annos()
                    .get_node_id_from_name(reference_node)?
                    .context("Missing node ID")?;
                let tok_helper = TokenHelper::new(graph)?;
                let sorted_covered = tok_helper.covered_token(reference_node_id)?;
                if let Some(first_covered_token_id) = sorted_covered.first() {
                    let first_covered_token = graph
                        .get_node_annos()
                        .get_value_for_item(first_covered_token_id, &NODE_NAME_KEY)?
                        .context("Missing node name")?;
                    for cov_component in
                        graph.get_all_components(Some(AnnotationComponentType::Coverage), None)
                    {
                        let cov_gs = graph
                            .get_graphstorage(&cov_component)
                            .context("Missing coverage component")?;
                        if cov_gs.has_outgoing_edges(reference_node_id)? {
                            updates.push(UpdateEvent::DeleteEdge {
                                source_node: reference_node.to_string(),
                                target_node: first_covered_token.to_string(),
                                layer: cov_component.layer.to_string(),
                                component_type: cov_component.get_type().to_string(),
                                component_name: cov_component.name.to_string(),
                            });
                            reverse_updates.push(UpdateEvent::AddEdge {
                                source_node: reference_node.to_string(),
                                target_node: first_covered_token.to_string(),
                                layer: cov_component.layer.to_string(),
                                component_type: cov_component.get_type().to_string(),
                                component_name: cov_component.name.to_string(),
                            });
                        }
                    }
                }
            }
            GraphAction::ShrinkNodeRight { reference_node } => {
                let reference_node_id = graph
                    .get_node_annos()
                    .get_node_id_from_name(reference_node)?
                    .context("Missing node ID")?;
                let tok_helper = TokenHelper::new(graph)?;
                let sorted_covered = tok_helper.covered_token(reference_node_id)?;
                if let Some(last_covered_token_id) = sorted_covered.last() {
                    let last_covered_token = graph
                        .get_node_annos()
                        .get_value_for_item(last_covered_token_id, &NODE_NAME_KEY)?
                        .context("Missing node name")?;
                    for cov_component in
                        graph.get_all_components(Some(AnnotationComponentType::Coverage), None)
                    {
                        let cov_gs = graph
                            .get_graphstorage(&cov_component)
                            .context("Missing coverage component")?;
                        if cov_gs.has_outgoing_edges(reference_node_id)? {
                            updates.push(UpdateEvent::DeleteEdge {
                                source_node: reference_node.to_string(),
                                target_node: last_covered_token.to_string(),
                                layer: cov_component.layer.to_string(),
                                component_type: cov_component.get_type().to_string(),
                                component_name: cov_component.name.to_string(),
                            });
                            reverse_updates.push(UpdateEvent::AddEdge {
                                source_node: reference_node.to_string(),
                                target_node: last_covered_token.to_string(),
                                layer: cov_component.layer.to_string(),
                                component_type: cov_component.get_type().to_string(),
                                component_name: cov_component.name.to_string(),
                            });
                        }
                    }
                }
            }
            GraphAction::AnnoRemoved {
                node_name,
                anno_key,
            } => {
                updates.push(UpdateEvent::DeleteNodeLabel {
                    node_name: node_name.to_string(),
                    anno_ns: anno_key.ns.clone(),
                    anno_name: anno_key.name.clone(),
                });
                // Remember the removed annotation value
                if let Some(old_value) = graph
                    .get_node_annos()
                    .get_value_for_item(&get_referenced_node_id(graph, node_name)?, anno_key)?
                {
                    reverse_updates.push(UpdateEvent::AddNodeLabel {
                        node_name: node_name.to_string(),
                        anno_ns: anno_key.ns.to_string(),
                        anno_name: anno_key.name.to_string(),
                        anno_value: old_value.to_string(),
                    });
                }
            }
            GraphAction::AddSpan {
                selected_token,
                parent_name,
                anno_key,
            } => apply_add_span(
                graph,
                parent_name,
                anno_key,
                selected_token,
                &mut updates,
                &mut reverse_updates,
            )?,
            GraphAction::AddSegmentationSpan {
                segmentation,
                selected_token,
                parent_name,
            } => apply_add_segmentation(
                graph,
                parent_name,
                segmentation,
                selected_token,
                &mut updates,
                &mut reverse_updates,
            )?,
            GraphAction::DeleteNodes { node_names } => {
                let mut deleted_nodes_by_ordering: BTreeMap<_, Vec<NodeID>> = BTreeMap::new();
                let tok_helper = TokenHelper::new(graph)?;

                for node_name in node_names {
                    let node_id = graph
                        .get_node_annos()
                        .get_node_id_from_name(node_name)?
                        .context(
                            "Can't delete \"{node_name\" because its internal ID is missing",
                        )?;

                    updates.push(UpdateEvent::DeleteNode {
                        node_name: node_name.to_string(),
                    });
                    reverse_updates
                        .extend(update_events_to_restore_deleted_node(graph, node_name)?);

                    for c in graph.get_all_components(Some(AnnotationComponentType::Ordering), None)
                    {
                        if let Some(gs) = graph.get_graphstorage(&c)
                            && (gs.has_ingoing_edges(node_id)? || gs.has_outgoing_edges(node_id)?)
                        {
                            deleted_nodes_by_ordering
                                .entry(c.clone())
                                .or_default()
                                .push(node_id);
                        }
                    }
                }

                // Find all the tokens and segmention nodes that have been
                // deleted, and add edges where gaps have been created.
                for (ordering_component, deleted_nodes) in deleted_nodes_by_ordering {
                    let ordering_gs =
                        graph
                            .get_graphstorage(&ordering_component)
                            .with_context(|| {
                                format!("Missing ordering component {ordering_component}")
                            })?;
                    let segmentation = if ordering_component.name.is_empty() {
                        None
                    } else {
                        Some(ordering_component.name.as_str())
                    };
                    let deleted_spans =
                        tok_helper.continuous_segmentation_spans(&deleted_nodes, segmentation)?;

                    for span in deleted_spans {
                        if let Some(ingoing) = ordering_gs.get_ingoing_edges(span.0).next()
                            && let Some(outgoing) = ordering_gs.get_outgoing_edges(span.1).next()
                        {
                            let ingoing = graph
                                .get_node_annos()
                                .get_value_for_item(&ingoing?, &NODE_NAME_KEY)?
                                .context("Missing node name")?;
                            let outgoing = graph
                                .get_node_annos()
                                .get_value_for_item(&outgoing?, &NODE_NAME_KEY)?
                                .context("Missing node name")?;
                            updates.push(UpdateEvent::AddEdge {
                                source_node: ingoing.to_string(),
                                target_node: outgoing.to_string(),
                                layer: ordering_component.layer.to_string(),
                                component_type: ordering_component.get_type().to_string(),
                                component_name: ordering_component.name.to_string(),
                            });
                            reverse_updates.push(UpdateEvent::DeleteEdge {
                                source_node: ingoing.to_string(),
                                target_node: outgoing.to_string(),
                                layer: ordering_component.layer.to_string(),
                                component_type: ordering_component.get_type().to_string(),
                                component_name: ordering_component.name.to_string(),
                            });
                        }
                    }
                }
            }
        }

        let result = ChangeSet::from((updates, reverse_updates));
        Ok(result)
    }
}

fn get_referenced_node_id(graph: &AnnotationGraph, node_name: &str) -> anyhow::Result<NodeID> {
    graph
        .get_node_annos()
        .get_node_id_from_name(node_name)?
        .with_context(|| format!("Missing node with name {node_name}"))
}

/// Create update events that restore all labels and edges of a deleted node
fn update_events_to_restore_deleted_node(
    graph: &AnnotationGraph,
    node_name: &str,
) -> anyhow::Result<Vec<UpdateEvent>> {
    let mut result = Vec::new();

    let node_id = get_referenced_node_id(graph, node_name)?;

    let node_type = graph
        .get_node_annos()
        .get_value_for_item(&node_id, &NODE_TYPE_KEY)?
        .context("Missing node type")?;
    result.push(UpdateEvent::AddNode {
        node_name: node_name.to_string(),
        node_type: node_type.to_string(),
    });

    for label in graph.get_node_annos().get_annotations_for_item(&node_id)? {
        if &label.key != NODE_TYPE_KEY.as_ref() {
            result.push(UpdateEvent::AddNodeLabel {
                node_name: node_name.to_string(),
                anno_ns: label.key.ns.to_string(),
                anno_name: label.key.name.to_string(),
                anno_value: label.val.to_string(),
            });
        }
    }

    for component in graph.get_all_components(None, None) {
        if let Some(gs) = graph.get_graphstorage_as_ref(&component) {
            // All outgoing edges and their labels
            for target_id in gs.get_outgoing_edges(node_id) {
                let target_id = target_id?;
                let target_node = graph
                    .get_node_annos()
                    .get_value_for_item(&target_id, &NODE_NAME_KEY)?
                    .context("Missing node name")?;
                // Since we don't know if the node is already added or comes later, add an "AddNode" update for the target node.
                result.push(UpdateEvent::AddNode {
                    node_name: target_node.to_string(),
                    node_type: "node".to_string(),
                });
                // Add the edge and edge annos
                result.push(UpdateEvent::AddEdge {
                    source_node: node_name.to_string(),
                    target_node: target_node.to_string(),
                    layer: component.layer.to_string(),
                    component_type: component.get_type().to_string(),
                    component_name: component.name.to_string(),
                });
                for edge_anno in gs
                    .get_anno_storage()
                    .get_annotations_for_item(&(node_id, target_id).into())?
                {
                    result.push(UpdateEvent::AddEdgeLabel {
                        source_node: node_name.to_string(),
                        target_node: target_node.to_string(),
                        layer: component.layer.to_string(),
                        component_type: component.get_type().to_string(),
                        component_name: component.name.to_string(),
                        anno_ns: edge_anno.key.ns.to_string(),
                        anno_name: edge_anno.key.name.to_string(),
                        anno_value: edge_anno.val.to_string(),
                    });
                }
            }
            // All incoming edges and their labels
            for source_id in gs.get_ingoing_edges(node_id) {
                let source_id = source_id?;
                let source_node = graph
                    .get_node_annos()
                    .get_value_for_item(&source_id, &NODE_NAME_KEY)?
                    .context("Missing node name")?;
                // Since we don't know if the node is already added or comes later, add an "AddNode" update for the target node.
                result.push(UpdateEvent::AddNode {
                    node_name: source_node.to_string(),
                    node_type: "node".to_string(),
                });

                // Add the edge and edge annos
                result.push(UpdateEvent::AddEdge {
                    source_node: source_node.to_string(),
                    target_node: node_name.to_string(),
                    layer: component.layer.to_string(),
                    component_type: component.get_type().to_string(),
                    component_name: component.name.to_string(),
                });
                for edge_anno in gs
                    .get_anno_storage()
                    .get_annotations_for_item(&(source_id, node_id).into())?
                {
                    result.push(UpdateEvent::AddEdgeLabel {
                        source_node: source_node.to_string(),
                        target_node: node_name.to_string(),
                        layer: component.layer.to_string(),
                        component_type: component.get_type().to_string(),
                        component_name: component.name.to_string(),
                        anno_ns: edge_anno.key.ns.to_string(),
                        anno_name: edge_anno.key.name.to_string(),
                        anno_value: edge_anno.val.to_string(),
                    });
                }
            }
        }
    }

    Ok(result)
}

fn apply_add_base_token(
    graph: &AnnotationGraph,
    reference_node: &str,
    parent_name: &str,
    before: bool,
    updates: &mut Vec<UpdateEvent>,
    reverse_updates: &mut Vec<UpdateEvent>,
) -> anyhow::Result<()> {
    let reference_node_id = graph
        .get_node_annos()
        .get_node_id_from_name(reference_node)?
        .context("Missing node ID")?;
    let name_prefix = if let Some((prefix, _suffix)) = parent_name.split_once("#") {
        prefix
    } else {
        parent_name
    };
    let number_of_token = graph
        .get_node_annos()
        .exact_anno_search(Some(ANNIS_NS), "tok", ValueSearch::Any)
        .count();
    let new_node_name = format!("{name_prefix}#tok{}", number_of_token + 1);

    add_basic_token_updates(&new_node_name, parent_name, updates, reverse_updates);

    let ordering_component = AnnotationComponent::new(
        AnnotationComponentType::Ordering,
        ANNIS_NS.into(),
        "".into(),
    );

    if let Some(ordering_gs) = graph.get_graphstorage_as_ref(&ordering_component) {
        // Find nodes that cover both the token before/ after the insertion and
        // let the cover the new token as well
        let next_token = if before {
            ordering_gs.get_ingoing_edges(reference_node_id).next()
        } else {
            ordering_gs.get_outgoing_edges(reference_node_id).next()
        };
        if let Some(next_token) = next_token {
            let next_token = next_token?;
            for (cov_component, cov_gs) in graph
                .get_all_components(Some(AnnotationComponentType::Coverage), None)
                .iter()
                .filter_map(|c| graph.get_graphstorage(c).map(|gs| (c.clone(), gs)))
            {
                for covering_node_id in cov_gs.get_ingoing_edges(reference_node_id) {
                    let covering_node_id = covering_node_id?;
                    let covering_node = graph
                        .get_node_annos()
                        .get_value_for_item(&covering_node_id, &NODE_NAME_KEY)?
                        .context("Missing node name")?;
                    if cov_gs.is_connected(
                        covering_node_id,
                        next_token,
                        1,
                        std::ops::Bound::Included(1),
                    )? {
                        updates.push(UpdateEvent::AddEdge {
                            source_node: covering_node.as_str().into(),
                            target_node: new_node_name.as_str().into(),
                            layer: cov_component.layer.to_string(),
                            component_type: cov_component.get_type().to_string(),
                            component_name: cov_component.name.to_string(),
                        });
                        reverse_updates.push(UpdateEvent::DeleteEdge {
                            source_node: covering_node.as_str().into(),
                            target_node: new_node_name.as_str().into(),
                            layer: cov_component.layer.to_string(),
                            component_type: cov_component.get_type().to_string(),
                            component_name: cov_component.name.to_string(),
                        });
                    }
                }
            }
        }

        // Insert ordering edges to from and to the new token
        if before {
            if let Some(previous_token_id) = ordering_gs.get_ingoing_edges(reference_node_id).next()
            {
                let previous_token_id = previous_token_id?;
                let previous_token_name = graph
                    .get_node_annos()
                    .get_value_for_item(&previous_token_id, &NODE_NAME_KEY)?
                    .context("Missing node name for token")?;
                updates.push(UpdateEvent::DeleteEdge {
                    source_node: previous_token_name.to_string(),
                    target_node: reference_node.to_string(),
                    layer: ordering_component.layer.to_string(),
                    component_type: ordering_component.get_type().to_string(),
                    component_name: ordering_component.name.to_string(),
                });
                reverse_updates.push(UpdateEvent::AddEdge {
                    source_node: previous_token_name.to_string(),
                    target_node: reference_node.to_string(),
                    layer: ordering_component.layer.to_string(),
                    component_type: ordering_component.get_type().to_string(),
                    component_name: ordering_component.name.to_string(),
                });
                updates.push(UpdateEvent::AddEdge {
                    source_node: previous_token_name.to_string(),
                    target_node: new_node_name.clone(),
                    layer: ordering_component.layer.to_string(),
                    component_type: ordering_component.get_type().to_string(),
                    component_name: ordering_component.name.to_string(),
                });
                reverse_updates.push(UpdateEvent::DeleteEdge {
                    source_node: previous_token_name.to_string(),
                    target_node: new_node_name.clone(),
                    layer: ordering_component.layer.to_string(),
                    component_type: ordering_component.get_type().to_string(),
                    component_name: ordering_component.name.to_string(),
                });
            }
            updates.push(UpdateEvent::AddEdge {
                source_node: new_node_name.clone(),
                target_node: reference_node.to_string(),
                layer: ordering_component.layer.to_string(),
                component_type: ordering_component.get_type().to_string(),
                component_name: ordering_component.name.to_string(),
            });
            reverse_updates.push(UpdateEvent::DeleteEdge {
                source_node: new_node_name.clone(),
                target_node: reference_node.to_string(),
                layer: ordering_component.layer.to_string(),
                component_type: ordering_component.get_type().to_string(),
                component_name: ordering_component.name.to_string(),
            });
        } else {
            if let Some(next_token_id) = ordering_gs.get_outgoing_edges(reference_node_id).next() {
                let next_token_id = next_token_id?;
                let next_token_name = graph
                    .get_node_annos()
                    .get_value_for_item(&next_token_id, &NODE_NAME_KEY)?
                    .context("Missing node name for token")?;
                updates.push(UpdateEvent::DeleteEdge {
                    source_node: reference_node.to_string(),
                    target_node: next_token_name.to_string(),
                    layer: ordering_component.layer.to_string(),
                    component_type: ordering_component.get_type().to_string(),
                    component_name: ordering_component.name.to_string(),
                });
                reverse_updates.push(UpdateEvent::AddEdge {
                    source_node: reference_node.to_string(),
                    target_node: next_token_name.to_string(),
                    layer: ordering_component.layer.to_string(),
                    component_type: ordering_component.get_type().to_string(),
                    component_name: ordering_component.name.to_string(),
                });
                updates.push(UpdateEvent::AddEdge {
                    source_node: new_node_name.to_string(),
                    target_node: next_token_name.to_string(),
                    layer: ordering_component.layer.to_string(),
                    component_type: ordering_component.get_type().to_string(),
                    component_name: ordering_component.name.to_string(),
                });
                reverse_updates.push(UpdateEvent::DeleteEdge {
                    source_node: new_node_name.to_string(),
                    target_node: next_token_name.to_string(),
                    layer: ordering_component.layer.to_string(),
                    component_type: ordering_component.get_type().to_string(),
                    component_name: ordering_component.name.to_string(),
                });
            }
            updates.push(UpdateEvent::AddEdge {
                source_node: reference_node.to_string(),
                target_node: new_node_name.to_string(),
                layer: ordering_component.layer.to_string(),
                component_type: ordering_component.get_type().to_string(),
                component_name: ordering_component.name.to_string(),
            });
            reverse_updates.push(UpdateEvent::DeleteEdge {
                source_node: reference_node.to_string(),
                target_node: new_node_name.to_string(),
                layer: ordering_component.layer.to_string(),
                component_type: ordering_component.get_type().to_string(),
                component_name: ordering_component.name.to_string(),
            });
        }
    }

    Ok(())
}

fn apply_add_segmentation(
    graph: &AnnotationGraph,
    parent_name: &str,
    segmentation: &str,
    selected_token: &HashSet<String>,
    updates: &mut Vec<UpdateEvent>,
    reverse_updates: &mut Vec<UpdateEvent>,
) -> anyhow::Result<()> {
    let new_node_name = format!(
        "{}#{}",
        &parent_name,
        graph
            .get_node_annos()
            .get_largest_item()?
            .map(|id| id + 1)
            .unwrap_or_default()
    );
    let tok_helper = TokenHelper::new(graph)?;
    let mut sorted_covered_token = Vec::new();
    for node_name in selected_token {
        if let Some(n) = graph.get_node_annos().get_node_id_from_name(node_name)? {
            sorted_covered_token.push((n, node_name.to_string()));
        }
    }
    if let Some(gs) = tok_helper.get_ordering_gs(None) {
        sorted_covered_token.sort_by(|a, b| {
            if a == b {
                Ordering::Equal
            } else if let Ok(connected) = gs.is_connected(a.0, b.0, 1, std::ops::Bound::Unbounded) {
                if connected {
                    Ordering::Less
                } else {
                    Ordering::Greater
                }
            } else {
                Ordering::Less
            }
        });
    }

    updates.push(UpdateEvent::AddNode {
        node_name: new_node_name.clone(),
        node_type: "node".to_string(),
    });
    updates.push(UpdateEvent::AddEdge {
        source_node: new_node_name.clone(),
        target_node: parent_name.to_string(),
        layer: ANNIS_NS.to_string(),
        component_type: AnnotationComponentType::PartOf.to_string(),
        component_name: "".to_string(),
    });
    updates.push(UpdateEvent::AddNodeLabel {
        node_name: new_node_name.clone(),
        anno_ns: TOKEN_KEY.ns.to_string(),
        anno_name: TOKEN_KEY.name.to_string(),
        anno_value: String::default(),
    });
    updates.push(UpdateEvent::AddNodeLabel {
        node_name: new_node_name.clone(),
        anno_ns: ANNIS_NS.to_string(),
        anno_name: segmentation.to_string(),
        anno_value: String::default(),
    });

    for target_node in &sorted_covered_token {
        updates.push(UpdateEvent::AddEdge {
            source_node: new_node_name.clone(),
            target_node: target_node.1.to_string(),
            layer: "".to_string(),
            component_type: AnnotationComponentType::Coverage.to_string(),
            component_name: "".to_string(),
        });
    }

    let first_covered = sorted_covered_token.first().cloned();
    let last_covered = sorted_covered_token.last().cloned();

    // Find the segmentations node before and after the selection to add the Ordering edges
    let matching_ordering_components =
        graph.get_all_components(Some(AnnotationComponentType::Ordering), Some(segmentation));
    if let Some(ordering_component) = matching_ordering_components.first() {
        if let Some(first_covered) = &first_covered
            && let Some(token_before) =
                tok_helper.get_token_before(first_covered.0, Some(segmentation))?
        {
            let token_before = graph
                .get_node_annos()
                .get_value_for_item(&token_before, &NODE_NAME_KEY)?
                .context("Missing node name")?;

            updates.push(UpdateEvent::AddEdge {
                source_node: token_before.to_string(),
                target_node: new_node_name.clone(),
                layer: ordering_component.layer.to_string(),
                component_type: ordering_component.get_type().to_string(),
                component_name: ordering_component.name.to_string(),
            });
        }
        if let Some(last_covered) = &last_covered
            && let Some(token_after) =
                tok_helper.get_token_after(last_covered.0, Some(segmentation))?
        {
            let token_after = graph
                .get_node_annos()
                .get_value_for_item(&token_after, &NODE_NAME_KEY)?
                .context("Missing node name")?;

            updates.push(UpdateEvent::AddEdge {
                source_node: new_node_name.clone(),
                target_node: token_after.to_string(),
                layer: ordering_component.layer.to_string(),
                component_type: ordering_component.get_type().to_string(),
                component_name: ordering_component.name.to_string(),
            });
        }
    }
    reverse_updates.push(UpdateEvent::DeleteNode {
        node_name: new_node_name.clone(),
    });

    Ok(())
}

fn apply_add_span(
    graph: &AnnotationGraph,
    parent_name: &str,
    anno_key: &AnnoKey,
    selected_token: &HashSet<String>,
    updates: &mut Vec<UpdateEvent>,
    reverse_updates: &mut Vec<UpdateEvent>,
) -> anyhow::Result<()> {
    let new_node_name = format!(
        "{}#n{}",
        &parent_name,
        graph
            .get_node_annos()
            .get_largest_item()?
            .map(|id| id + 1)
            .unwrap_or_default()
    );

    updates.push(UpdateEvent::AddNode {
        node_name: new_node_name.clone(),
        node_type: "node".to_string(),
    });
    updates.push(UpdateEvent::AddEdge {
        source_node: new_node_name.clone(),
        target_node: parent_name.to_string(),
        layer: ANNIS_NS.to_string(),
        component_type: AnnotationComponentType::PartOf.to_string(),
        component_name: "".to_string(),
    });
    updates.push(UpdateEvent::AddNodeLabel {
        node_name: new_node_name.clone(),
        anno_ns: anno_key.ns.to_string(),
        anno_name: anno_key.name.to_string(),
        anno_value: "".to_string(),
    });

    for target_node in selected_token {
        updates.push(UpdateEvent::AddEdge {
            source_node: new_node_name.clone(),
            target_node: target_node.to_string(),
            layer: "".to_string(),
            component_type: AnnotationComponentType::Coverage.to_string(),
            component_name: "".to_string(),
        });
    }

    reverse_updates.push(UpdateEvent::DeleteNode {
        node_name: new_node_name.clone(),
    });

    Ok(())
}

fn add_basic_token_updates(
    new_node_name: &str,
    parent_name: &str,
    updates: &mut Vec<UpdateEvent>,
    reverse_updates: &mut Vec<UpdateEvent>,
) {
    // Add the basic node annotation
    updates.push(UpdateEvent::AddNode {
        node_name: new_node_name.to_string(),
        node_type: "node".to_string(),
    });
    updates.push(UpdateEvent::AddNodeLabel {
        node_name: new_node_name.to_string(),
        anno_ns: ANNIS_NS.to_string(),
        anno_name: "tok".to_string(),
        anno_value: String::new(),
    });
    updates.push(UpdateEvent::AddEdge {
        source_node: new_node_name.to_string(),
        target_node: parent_name.to_string(),
        layer: ANNIS_NS.to_string(),
        component_type: AnnotationComponentType::PartOf.to_string(),
        component_name: "".to_string(),
    });

    reverse_updates.push(UpdateEvent::DeleteNode {
        node_name: new_node_name.to_string(),
    });
}