import { UnitConverter } from "@devexpress/utils/lib/class/unit-converter";
import { Point } from "@devexpress/utils/lib/geometry/point";
import { Size } from "@devexpress/utils/lib/geometry/size";

import { AddConnectionHistoryItem } from "../History/Common/AddConnectionHistoryItem";
import { AddConnectorHistoryItem } from "../History/Common/AddConnectorHistoryItem";
import { AddShapeHistoryItem } from "../History/Common/AddShapeHistoryItem";
import { DeleteConnectionHistoryItem } from "../History/Common/DeleteConnectionHistoryItem";
import { ResizeShapeHistoryItem } from "../History/Common/ResizeShapeHistoryItem";
import { History } from "../History/History";
import {
    ChangeConnectorPropertyHistoryItem
} from "../History/Properties/ChangeConnectorPropertyHistoryItem";
import {
    ChangeConnectorTextHistoryItem
} from "../History/Properties/ChangeConnectorTextHistoryItem";
import { ChangeCustomDataHistoryItem } from "../History/Properties/ChangeCustomDataHistoryItem";
import { ChangeLockedHistoryItem } from "../History/Properties/ChangeLockedHistoryItem";
import { ChangeShapeImageHistoryItem } from "../History/Properties/ChangeShapeImageHistoryItem";
import { ChangeShapeTextHistoryItem } from "../History/Properties/ChangeShapeTextHistoryItem";
import { ChangeZindexHistoryItem } from "../History/Properties/ChangeZindexHistoryItem";
import { ChangeStyleHistoryItem } from "../History/StyleProperties/ChangeStyleHistoryItem";
import { ChangeStyleTextHistoryItem } from "../History/StyleProperties/ChangeStyleTextHistoryItem";
import { KeySet } from "../ListUtils";
import {
    Connector, CONNECTOR_DEFAULT_TEXT_POSITION, ConnectorPosition
} from "../Model/Connectors/Connector";
import { DiagramItem, ItemDataKey, ItemKey } from "../Model/DiagramItem";
import { DiagramModel } from "../Model/Model";
import { ModelUtils } from "../Model/ModelUtils";
import { IShapeDescriptionManager } from "../Model/Shapes/Descriptions/ShapeDescriptionManager";
import { Shape } from "../Model/Shapes/Shape";
import { ShapeTypes } from "../Model/Shapes/ShapeTypes";
import { ITextMeasurer, TextOwner } from "../Render/Measurer/ITextMeasurer";
import { Selection } from "../Selection/Selection";
import { IShapeSizeSettings } from "../Settings";
import { ObjectUtils } from "../Utils";
import { ColorUtils } from "@devexpress/utils/lib/utils/color";
import { Data } from "../Utils/Data";
import { isColorProperty } from "../Utils/Svg";
import { getOptimalTextRectangle } from "../Utils/TextUtils";
import {
    DataSourceEdgeDataImporter, DataSourceItemDataImporter, DataSourceNodeDataImporter
} from "./DataImporter";
import { DataLayoutParameters } from "./DataLayoutParameters";
import { DataSourceEdgeItem, DataSourceItem, DataSourceNodeItem } from "./DataSourceItems";
import {
    IDataImportParameters, IEdgeDataImporter, IItemDataImporter, INodeDataImporter
} from "./Interfaces";
import { ReplaceConnectorPointsHistoryItem } from "../History/Common/ChangeConnectorPointsHistoryItem";
import { DiagramUnit } from "../Enums";

interface IDataSourceItemsChanges {
    remained: ItemDataKey[];
    remainedNewKeys: ItemDataKey[];
    removed: ItemDataKey[];
    added: ItemDataKey[];
}

interface IDataSourceChanges {
    nodes: IDataSourceItemsChanges;
    edges: IDataSourceItemsChanges;
}

export abstract class DataSource {
    nodes: DataSourceNodeItem[] = [];
    edges: DataSourceEdgeItem[] = [];
    protected autoGeneratedDataKeys: KeySet = {};
    protected addInternalKeyOnInsert: boolean = false;

    protected useNodeParentId = false;
    protected useNodeContainerId = false;
    protected useNodeChildren = false;
    protected useNodeItems = false;
    protected canUseAutoSize = false;
    protected canUpdateEdgeDataSource = false;

    nodeDataImporter: INodeDataImporter;
    edgeDataImporter: IEdgeDataImporter;
    protected nodeDataSource: any[];
    protected edgeDataSource: any[];

    constructor(public key: string,
        nodeDataSource: any[], edgeDataSource: any[],
        parameters?: IDataImportParameters,
        nodeDataImporter?: INodeDataImporter,
        edgeDataImporter?: IEdgeDataImporter) {
        if(key === undefined || key === null)
            throw new Error("DataSource key must be specified");
        this.key = key.toString();
        this.loadParameters(parameters || {});
        this.nodeDataImporter = this.createNodeDataImporter(nodeDataImporter);
        this.edgeDataImporter = this.createEdgeDataImporter(edgeDataImporter);
        this.nodeDataSource = nodeDataSource || [];
        this.edgeDataSource = edgeDataSource || [];
        this.canUpdateEdgeDataSource = !!edgeDataSource;
        this.fetchData();
    }

    protected loadParameters(parameters: IDataImportParameters): void {
        this.addInternalKeyOnInsert = !!parameters.addInternalKeyOnInsert;
    }

    isAutoGeneratedKey(dataKey: any): boolean {
        return dataKey && !!this.autoGeneratedDataKeys[dataKey];
    }

    private createNodeDataImporter(source: INodeDataImporter): INodeDataImporter {
        const result = new DataSourceNodeDataImporter();
        if(source)
            this.assignNodeDataImporterProperties(source, result);
        return result;
    }
    private createEdgeDataImporter(source: IEdgeDataImporter): IEdgeDataImporter {
        const result = new DataSourceEdgeDataImporter();
        if(source)
            this.assignEdgeDataImporterProperties(source, result);
        return result;
    }
    private assignItemDataImporterProperties(source: IItemDataImporter, importer: DataSourceItemDataImporter) {
        if(source.getKey)
            importer.getKey = source.getKey;
        if(source.setKey)
            importer.setKey = source.setKey;

        if(source.getCustomData)
            importer.getCustomData = source.getCustomData;
        if(source.setCustomData)
            importer.setCustomData = source.setCustomData;

        if(source.getLocked)
            importer.getLocked = source.getLocked;
        if(source.setLocked)
            importer.setLocked = source.setLocked;

        if(source.getStyle)
            importer.getStyle = source.getStyle;
        if(source.setStyle)
            importer.setStyle = source.setStyle;
        if(source.getStyleText)
            importer.getStyleText = source.getStyleText;
        if(source.setStyleText)
            importer.setStyleText = source.setStyleText;
        if(source.getZIndex)
            importer.getZIndex = source.getZIndex;
        if(source.setZIndex)
            importer.setZIndex = source.setZIndex;
    }
    private assignNodeDataImporterProperties(source: INodeDataImporter, importer: DataSourceNodeDataImporter) {
        this.assignItemDataImporterProperties(source, importer);

        if(source.getType)
            importer.getType = source.getType;
        if(source.setType)
            importer.setType = source.setType;

        if(source.getImage)
            importer.getImage = source.getImage;
        if(source.setImage)
            importer.setImage = source.setImage;
        if(source.getText)
            importer.getText = source.getText;
        if(source.setText)
            importer.setText = source.setText;

        if(source.getLeft)
            importer.getLeft = source.getLeft;
        if(source.setLeft)
            importer.setLeft = source.setLeft;
        if(source.getTop)
            importer.getTop = source.getTop;
        if(source.setTop)
            importer.setTop = source.setTop;
        if(source.getWidth)
            importer.getWidth = source.getWidth;
        if(source.setWidth)
            importer.setWidth = source.setWidth;
        if(source.getHeight)
            importer.getHeight = source.getHeight;
        if(source.setHeight)
            importer.setHeight = source.setHeight;

        if(source.getChildren)
            importer.getChildren = source.getChildren;
        if(source.setChildren)
            importer.setChildren = source.setChildren;

        if(source.getParentKey)
            importer.getParentKey = source.getParentKey;
        if(source.setParentKey)
            importer.setParentKey = source.setParentKey;
        if(source.getItems)
            importer.getItems = source.getItems;
        if(source.setItems)
            importer.setItems = source.setItems;
        if(source.getContainerKey)
            importer.getContainerKey = source.getContainerKey;
        if(source.setContainerKey)
            importer.setContainerKey = source.setContainerKey;
    }
    private assignEdgeDataImporterProperties(source: IEdgeDataImporter, importer: DataSourceEdgeDataImporter) {
        this.assignItemDataImporterProperties(source, importer);

        if(source.getFrom)
            importer.getFrom = source.getFrom;
        if(source.setFrom)
            importer.setFrom = source.setFrom;
        if(source.getFromPointIndex)
            importer.getFromPointIndex = source.getFromPointIndex;
        if(source.setFromPointIndex)
            importer.setFromPointIndex = source.setFromPointIndex;
        if(source.getTo)
            importer.getTo = source.getTo;
        if(source.setTo)
            importer.setTo = source.setTo;
        if(source.getToPointIndex)
            importer.getToPointIndex = source.getToPointIndex;
        if(source.setToPointIndex)
            importer.setToPointIndex = source.setToPointIndex;

        if(source.getPoints)
            importer.getPoints = source.getPoints;
        if(source.setPoints)
            importer.setPoints = source.setPoints;

        if(source.getText)
            importer.getText = source.getText;
        if(source.setText)
            importer.setText = source.setText;

        if(source.getLineOption)
            importer.getLineOption = source.getLineOption;
        if(source.setLineOption)
            importer.setLineOption = source.setLineOption;
        if(source.getStartLineEnding)
            importer.getStartLineEnding = source.getStartLineEnding;
        if(source.setStartLineEnding)
            importer.setStartLineEnding = source.setStartLineEnding;
        if(source.getEndLineEnding)
            importer.getEndLineEnding = source.getEndLineEnding;
        if(source.setEndLineEnding)
            importer.setEndLineEnding = source.setEndLineEnding;
    }

    protected fetchData() {
        this.nodes = [];
        this.edges = [];
        this.autoGeneratedDataKeys = {};

        this.useNodeParentId = this.nodeDataImporter.getParentKey !== undefined;
        this.useNodeContainerId = this.nodeDataImporter.getContainerKey !== undefined;
        this.useNodeItems = this.nodeDataImporter.getItems !== undefined;
        this.useNodeChildren = this.nodeDataImporter.getChildren !== undefined;
        this.canUseAutoSize = this.nodeDataImporter.getWidth === undefined && this.nodeDataImporter.getText !== undefined;

        if(this.useEdgesArray() && this.useNodeParentId)
            throw new Error("You cannot use edges array and parentKey simultaneously.");
        if(this.useEdgesArray() && this.useNodeItems)
            throw new Error("You cannot use edges array and items array simultaneously.");
        if(this.useNodeParentId && this.useNodeItems)
            throw new Error("You cannot use parentKey and items array simultaneously.");
        if(this.useNodeContainerId && this.useNodeChildren)
            throw new Error("You cannot use containerKey and children array simultaneously.");

        this.nodeDataSource.forEach(nodeDataObj => {
            this.addNode(nodeDataObj);
        });
        if(this.useEdgesArray())
            this.edgeDataSource.forEach(edgeDataObj => {
                this.addEdge(edgeDataObj);
            });

        else
            this.nodes.forEach(node => {
                this.addNodeEdgesByParentId(node);
            });

    }
    private containers: KeySet = null;
    protected isContainer(itemKey: ItemDataKey): boolean {
        if(!this.containers && this.useNodeContainerId)
            this.containers = this.nodeDataSource
                .map(i => this.nodeDataImporter.getContainerKey(i))
                .filter(i => i !== undefined && i !== null)
                .reduce((map, i) => {
                    map[i] = true;
                    return map;
                }, {});

        return this.containers && this.containers[itemKey];
    }
    refetchData(nodeDataSource?: any[], edgeDataSource?: any[]): IDataSourceChanges {
        this.nodeDataSource = nodeDataSource || this.nodeDataSource;
        this.edgeDataSource = edgeDataSource || this.edgeDataSource;

        const oldNodes = this.nodes.slice();
        const oldEdges = this.edges.slice();
        this.fetchData();
        const changedNodes =
            this.getItemChanges(oldNodes, this.nodes, (item1: DataSourceNodeItem, item2: DataSourceNodeItem) => {
                return (item1.key === item2.key) || (item1.dataObj === item2.dataObj);
            });
        const changedEdges =
            this.getItemChanges(oldEdges, this.edges, (item1: DataSourceEdgeItem, item2: DataSourceEdgeItem) => {
                if(this.useNodeParentId || this.useNodeItems)
                    return (item1.key === item2.key) || (item1.from === item2.from && item1.to === item2.to);
                return (item1.key === item2.key) || (item1.dataObj === item2.dataObj);
            });
        return { nodes: changedNodes, edges: changedEdges };
    }
    protected getItemChanges(oldItems: DataSourceItem[], newItems: DataSourceItem[], areEqual: (item1: DataSourceItem, item2: DataSourceItem) => boolean): IDataSourceItemsChanges {
        const remainedItems = oldItems.filter(item => this.containsItem(newItems, item, areEqual));
        const removedItems = oldItems.filter(item => !this.containsItem(newItems, item, areEqual));
        const addedItems = newItems.filter(item => !this.containsItem(oldItems, item, areEqual));
        return {
            remained: remainedItems.map(item => item.key),
            remainedNewKeys: remainedItems.map(item => newItems.find(i => areEqual(item, i))?.key),
            removed: removedItems.map(item => item.key),
            added: addedItems.map(item => item.key)
        };
    }
    protected containsItem(items: DataSourceItem[], item: DataSourceItem, areEqual: (item1: DataSourceItem, item2: DataSourceItem) => boolean): boolean {
        let result = false;
        items.forEach(i => {
            if(!result && areEqual(i, item))
                result = true;
        });
        return result;
    }
    protected useEdgesArray() {
        return Array.isArray(this.edgeDataSource) && (this.edgeDataSource.length || !(this.useNodeParentId || this.useNodeItems));
    }
    protected addNode(nodeDataObj: any, parentNodeDataObj?: any, containerKey?: ItemDataKey, containerNodeDataObj?: any) {
        const childNodeDataObjs = this.nodeDataImporter.getChildren && this.nodeDataImporter.getChildren(nodeDataObj);
        const hasChildren = childNodeDataObjs && Array.isArray(childNodeDataObjs) && childNodeDataObjs.length;
        const isContainer = hasChildren || this.isContainer(this.nodeDataImporter.getKey(nodeDataObj));
        const type = this.nodeDataImporter.getType && this.nodeDataImporter.getType(nodeDataObj) || (isContainer && ShapeTypes.VerticalContainer) || ShapeTypes.Rectangle;
        const text = this.nodeDataImporter.getText && (this.nodeDataImporter.getText(nodeDataObj) || "");
        const node = this.addNodeInternal(nodeDataObj, type, text, parentNodeDataObj, containerKey, containerNodeDataObj);
        this.assignNodeProperties(node, nodeDataObj);
        if(hasChildren)
            childNodeDataObjs.forEach(childNodeDataObj => {
                this.addNode(childNodeDataObj, undefined, node.key, nodeDataObj);
            });

        if(this.useNodeItems) {
            const itemDataObjs = this.nodeDataImporter.getItems(nodeDataObj);
            if(Array.isArray(itemDataObjs) && itemDataObjs.length)
                itemDataObjs.forEach(itemDataObj => {
                    const itemNode = this.addNode(itemDataObj, nodeDataObj, containerKey, containerNodeDataObj);
                    this.addEdgeInternal(undefined, node.key, itemNode.key);
                });

        }
        return node;
    }
    protected addNodeEdgesByParentId(node: DataSourceNodeItem) {
        if(this.useNodeParentId) {
            const parentKey = this.nodeDataImporter.getParentKey(node.dataObj);
            if(parentKey !== undefined && parentKey !== null) {
                const parentNode = this.findNode(parentKey);
                if(parentNode)
                    this.addEdgeInternal(undefined,
                        this.getNodeKey(node.dataObj, this.nodeDataImporter.getParentKey),
                        this.getNodeKey(node.dataObj, this.nodeDataImporter.getKey));

            }
        }
    }
    protected addNodeInternal(nodeDataObj: any, type: string, text: string, parentNodeDataObj?: any,
        containerKey?: ItemDataKey, containerNodeDataObj?: any) {
        let externalKey = this.nodeDataImporter.getKey(nodeDataObj);
        const key = (externalKey !== undefined && externalKey !== null) ? externalKey : ModelUtils.getGuidItemKey();
        const node = new DataSourceNodeItem(this.key, key, nodeDataObj, type, text, parentNodeDataObj,
            containerKey, containerNodeDataObj);
        this.nodes.push(node);
        if(externalKey === undefined || externalKey === null) {
            externalKey = key;
            this.autoGeneratedDataKeys[key] = true;
        }
        return node;
    }
    protected addEdge(edgeDataObj: any) {
        const edge = this.addEdgeInternal(edgeDataObj, this.getNodeKey(edgeDataObj, this.edgeDataImporter.getFrom),
            this.getNodeKey(edgeDataObj, this.edgeDataImporter.getTo));
        this.assignEdgeProperties(edge, edgeDataObj);
        return edge;
    }
    protected addEdgeInternal(edgeDataObj: any, from: ItemDataKey, to: ItemDataKey): DataSourceEdgeItem {
        let externalKey = edgeDataObj && this.edgeDataImporter.getKey(edgeDataObj);
        const key = (externalKey !== undefined && externalKey !== null) ? externalKey : ModelUtils.getGuidItemKey();
        const edge = new DataSourceEdgeItem(this.key, key, edgeDataObj, from, to);
        this.edges.push(edge);
        if(externalKey === undefined || externalKey === null) {
            externalKey = key;
            this.autoGeneratedDataKeys[key] = true;
        }
        return edge;
    }
    protected assignItemProperties(item: DataSourceItem, dataObj: any, importer: IItemDataImporter) {
        if(importer.getCustomData)
            item.customData = ObjectUtils.cloneObject(importer.getCustomData(dataObj));

        if(importer.getLocked)
            item.locked = importer.getLocked(dataObj);

        if(importer.getStyle) {
            const style = importer.getStyle(dataObj);
            item.style = typeof style === "string" ? Data.cssTextToObject(style) : style;
        }
        if(importer.getStyleText) {
            const style = importer.getStyleText(dataObj);
            item.styleText = typeof style === "string" ? Data.cssTextToObject(style) : style;
        }
        if(importer.getZIndex)
            item.zIndex = importer.getZIndex(dataObj);
    }
    protected assignNodeProperties(item: DataSourceNodeItem, dataObj: any) {
        this.assignItemProperties(item, dataObj, this.nodeDataImporter);

        if(this.nodeDataImporter.getImage)
            item.image = this.nodeDataImporter.getImage(dataObj);

        if(this.nodeDataImporter.getLeft)
            item.left = this.nodeDataImporter.getLeft(dataObj);
        if(this.nodeDataImporter.getTop)
            item.top = this.nodeDataImporter.getTop(dataObj);
        if(this.nodeDataImporter.getWidth)
            item.width = this.nodeDataImporter.getWidth(dataObj);
        if(this.nodeDataImporter.getHeight)
            item.height = this.nodeDataImporter.getHeight(dataObj);
        if(this.nodeDataImporter.getContainerKey)
            item.containerKey = this.nodeDataImporter.getContainerKey(dataObj);
    }
    protected assignEdgeProperties(item: DataSourceEdgeItem, dataObj: any) {
        this.assignItemProperties(item, dataObj, this.edgeDataImporter);

        if(this.edgeDataImporter.getFromPointIndex)
            item.fromPointIndex = this.edgeDataImporter.getFromPointIndex(dataObj);
        if(this.edgeDataImporter.getToPointIndex)
            item.toPointIndex = this.edgeDataImporter.getToPointIndex(dataObj);
        if(this.edgeDataImporter.getPoints)
            item.points = this.edgeDataImporter.getPoints(dataObj);

        if(this.edgeDataImporter.getText) {
            const texts = this.edgeDataImporter.getText(dataObj);
            item.texts = {};
            if(typeof texts === "object")
                for(const key in texts) {
                    if(!Object.prototype.hasOwnProperty.call(texts, key)) continue;

                    let position = parseFloat(key);
                    const text = texts[key];
                    if(!isNaN(position) && typeof text === "string" && text !== "") {
                        position = Math.min(1, Math.max(0, position));
                        item.texts[position] = text;
                    }
                }


            else if(typeof texts === "string" && texts !== "")
                item.texts[CONNECTOR_DEFAULT_TEXT_POSITION] = texts;
        }

        if(this.edgeDataImporter.getLineOption)
            item.lineOption = this.edgeDataImporter.getLineOption(dataObj);
        if(this.edgeDataImporter.getStartLineEnding)
            item.startLineEnding = this.edgeDataImporter.getStartLineEnding(dataObj);
        if(this.edgeDataImporter.getEndLineEnding)
            item.endLineEnding = this.edgeDataImporter.getEndLineEnding(dataObj);
    }
    findNode(key: ItemDataKey): DataSourceNodeItem {
        return this.nodes.filter(i => key !== undefined && i.key === key)[0];
    }
    findEdge(key: ItemDataKey): DataSourceEdgeItem {
        return this.edges.filter(i => key !== undefined && i.key === key)[0];
    }
    protected getNodeKey(nodeDataObj: any, getKey: (obj: any) => ItemDataKey) {
        return getKey(nodeDataObj);
    }

    createModelItems(history: History, model: DiagramModel, shapeDescriptionManager: IShapeDescriptionManager, selection: Selection,
        layoutParameters: DataLayoutParameters, snapToGrid: boolean, gridSize: number, measurer?: ITextMeasurer) {
        this.beginChangesNotification();
        history.clear();
        history.beginTransaction();

        ModelUtils.deleteAllItems(history, model, selection);

        model.initializeKeyCounter();

        const DEFAULT_STEP = snapToGrid ? Math.max(1, Math.floor(2000 / gridSize)) * gridSize : 2000;
        let rowIndex = 0;
        let colIndex = 0;
        const externalToInnerMap: {[externalID: number]: ItemKey} = {};
        const shapes: Shape[] = [];
        const connectors: Connector[] = [];

        this.nodes.forEach(node => {
            const point = new Point(colIndex++ * DEFAULT_STEP, rowIndex * DEFAULT_STEP);
            const shape = this.createShapeByNode(history, model, selection, shapeDescriptionManager, node, point, layoutParameters, snapToGrid, gridSize, measurer);
            if(node.key !== undefined)
                externalToInnerMap[node.key] = shape.key;
            if(colIndex > 4) {
                colIndex = 0;
                rowIndex++;
            }
            shapes.push(shape);
        });
        this.nodes.forEach(node => {
            if(node.containerKey !== undefined && node.containerKey !== null) {
                const shapeKey = externalToInnerMap[node.key];
                const shape = model.findShape(shapeKey);
                const containerShapeKey = externalToInnerMap[node.containerKey];
                const containerShape = model.findShape(containerShapeKey);
                if(containerShape)
                    ModelUtils.insertToContainer(history, model, shape, containerShape);
            }
        });
        this.edges.forEach(edge => {
            const toShape = model.findShape(externalToInnerMap[edge.to]);
            const fromShape = model.findShape(externalToInnerMap[edge.from]);

            const connector = this.createConnectorByEdge(history, model, selection, edge, fromShape, toShape);
            if(connector) {
                connectors.push(connector);
                ModelUtils.updateConnectorContainer(history, model, connector);
            }
        });

        if(layoutParameters.needAutoLayout)
            this.applyLayout(history, model, shapes, connectors, layoutParameters, snapToGrid, gridSize);

        ModelUtils.tryUpdateModelRectangle(history);
        history.endTransaction(true);
        this.endChangesNotification(true);
    }

    updateModelItems(history: History, model: DiagramModel, shapeDescriptionManager: IShapeDescriptionManager, selection: Selection, layoutParameters: DataLayoutParameters,
        addNewHistoryItem: boolean, updateDataKeys: ItemDataKey[], updateTemplateItem: (item: DiagramItem) => void,
        changes: IDataSourceChanges, snapToGrid: boolean, gridSize: number, measurer?: ITextMeasurer): void {
        this.beginChangesNotification();
        history.beginTransaction();

        const itemsToUpdate = [];
        let layoutShapes = [];
        const layoutConnectors = [];

        const shapesToRemove = changes.nodes.removed.map(key => model.findShapeByDataKey(key)).filter(item => item);
        shapesToRemove.forEach(shape => {
            shape.attachedConnectors.forEach(connector => {
                if(connector.beginItem && connector.beginItem !== shape)
                    layoutShapes.push(connector.beginItem);
                if(connector.endItem && connector.endItem !== shape)
                    layoutShapes.push(connector.endItem);
            });
        });
        ModelUtils.deleteItems(history, model, selection, shapesToRemove, true);

        const connectorsToRemove = changes.edges.removed.map(key => model.findConnectorByDataKey(key)).filter(item => item);
        connectorsToRemove.forEach(connector => {
            if(connector.beginItem)
                layoutShapes.push(connector.beginItem);
            if(connector.endItem)
                layoutShapes.push(connector.endItem);
        });
        ModelUtils.deleteItems(history, model, selection, connectorsToRemove, true);

        layoutShapes = this.purgeLayoutShapes(layoutShapes, shapesToRemove); 

        const nodeKeysToUpdate = updateDataKeys || [];
        nodeKeysToUpdate.forEach(dataKey => {
            if(changes.nodes.remained.indexOf(dataKey) === -1) return;

            const node = this.findNode(dataKey);
            if(node) {
                let shape = model.findShapeByDataKey(dataKey);
                if(shape) {
                    const position = shape.position.clone();
                    this.changeShapeByDataItem(history, model, shape, node, position);
                    this.changeItemByDataItem(history, shape, node);
                }
                else
                    shape = this.createShapeByNode(history, model, selection, shapeDescriptionManager, node, new Point(0, 0), layoutParameters, snapToGrid, gridSize, measurer);

                this.updateShapeContainer(history, model, shape, node);
                layoutShapes.push(shape);
                itemsToUpdate.push(shape);
            }
        });
        changes.nodes.remained.forEach((dataKey, index) => {
            const shape = model.findShapeByDataKey(dataKey);
            if(shape) shape.dataKey = changes.nodes.remainedNewKeys[index];
        });

        changes.nodes.added.forEach(dataKey => {
            const node = this.findNode(dataKey);
            const shape = this.createShapeByNode(history, model, selection, shapeDescriptionManager, node, new Point(0, 0), layoutParameters, snapToGrid, gridSize, measurer);
            this.updateShapeContainer(history, model, shape, node);
            layoutShapes.push(shape);
        });
        changes.edges.added.forEach(dataKey => {
            const edge = this.findEdge(dataKey);
            const fromShape = model.findShapeByDataKey(edge.from);
            const toShape = model.findShapeByDataKey(edge.to);
            const connector = this.createConnectorByEdge(history, model, selection,
                edge, fromShape, toShape);
            if(connector) {
                ModelUtils.updateConnectorContainer(history, model, connector);
                layoutConnectors.push(connector);
            }
        });

        const edgeKeysToUpdate = updateDataKeys || [];
        changes.edges.remained.forEach(dataKey => { 
            const edge = this.findEdge(dataKey);
            if(edge && ((changes.nodes.added.indexOf(edge.from) !== -1) || (changes.nodes.added.indexOf(edge.to) !== -1)))
                edgeKeysToUpdate.push(dataKey);
        });
        edgeKeysToUpdate.forEach(dataKey => {
            if(changes.edges.remained.indexOf(dataKey) === -1) return;

            const edge = this.findEdge(dataKey);
            if(edge) {
                const fromShape = model.findShapeByDataKey(edge.from);
                const toShape = model.findShapeByDataKey(edge.to);
                let connector = model.findConnectorByDataKey(dataKey);
                if(connector) {
                    this.changeConnectorPointsByDataItem(history, connector, this.getConnectorPointsByEdge(model, edge, fromShape, toShape, false));
                    this.changeConnectorByDataItem(history, model, connector, fromShape, toShape, edge);
                    this.changeItemByDataItem(history, connector, edge);
                }
                else
                    connector = this.createConnectorByEdge(history, model, selection, edge, fromShape, toShape);

                if(connector) {
                    ModelUtils.updateConnectorContainer(history, model, connector);
                    layoutConnectors.push(connector);
                    itemsToUpdate.push(connector);
                }
            }
        });
        changes.edges.remained.forEach((dataKey, index) => {
            const connector = model.findConnectorByDataKey(dataKey);
            if(connector) connector.dataKey = changes.edges.remainedNewKeys[index];
        });
        if(itemsToUpdate.length && updateTemplateItem)
            itemsToUpdate.forEach(item => { item.hasTemplate && updateTemplateItem(item); });

        if(layoutParameters.needAutoLayout && (layoutShapes.length || layoutConnectors.length))
            this.applyLayout(history, model, layoutShapes, layoutConnectors, layoutParameters, snapToGrid, gridSize);

        ModelUtils.tryUpdateModelRectangle(history);
        history.endTransaction(!addNewHistoryItem);
        this.endChangesNotification(false);
    }

    purgeLayoutShapes(layoutShapes: Shape[], shapesToRemove: DiagramItem[]): Shape[] {
        const shapesToRemoveKeySet = shapesToRemove.reduce((acc, shape) => (acc[shape.key] = true) && acc, {});

        return layoutShapes.reduce((acc, shape) => {
            if(acc.keySet[shape.key] === undefined && shapesToRemoveKeySet[shape.key] === undefined) {
                acc.uniqueShapes.push(shape);
                acc.keySet[shape.key] = true;
            }
            return acc;
        }, { uniqueShapes: [], keySet: {} }).uniqueShapes;
    }

    protected applyShapeAutoSize(history: History, measurer: ITextMeasurer, shapeSizeSettings: IShapeSizeSettings, shape: Shape, snapToGrid: boolean, gridSize: number): void {
        if(!shape.description.enableText) return;
        const shapeTextSize = shape.textRectangle.createSize();
        const shapeSize = shape.size;
        const textHorOffset = shapeTextSize.width - shapeSize.width;
        const textVerOffset = shapeTextSize.height - shapeSize.height;
        const maxWidth = shape.getMaxWidth(shapeSizeSettings.shapeMaxWidth);
        const maxHeight = shape.getMaxHeight(shapeSizeSettings.shapeMaxHeight);
        const sizeToPx = (size: number | undefined, isHorizontal: boolean) => typeof (size) === "number" ? UnitConverter.twipsToPixelsF(size + (isHorizontal ? textHorOffset : textVerOffset)) : undefined;
        const newShapeTextSize = getOptimalTextRectangle(shape.text, shape.styleText, TextOwner.Shape, measurer,
            shapeTextSize.clone().applyConverter(UnitConverter.twipsToPixelsF), shape.description.keepRatioOnAutoSize,
            sizeToPx(shape.getMinWidth(shapeSizeSettings.shapeMinWidth), true),
            sizeToPx(maxWidth, true),
            sizeToPx(shape.getMinHeight(shapeSizeSettings.shapeMinHeight), false),
            sizeToPx(maxHeight, false))
            .clone().applyConverter(UnitConverter.pixelsToTwips);
        if(!newShapeTextSize.equals(shapeTextSize)) {
            let shapeNewSize = shape.description.getSizeByText(newShapeTextSize, shape);
            if(snapToGrid && gridSize)
                shapeNewSize = new Size(
                    Math.min(gridSize * Math.ceil(shapeNewSize.width / gridSize), maxWidth || Number.MAX_VALUE),
                    Math.min(gridSize * Math.ceil(shapeNewSize.height / gridSize), maxHeight || Number.MAX_VALUE));
            history.addAndRedo(new ResizeShapeHistoryItem(shape.key, shape.position, shapeNewSize));
        }
    }

    applyLayout(history: History, model: DiagramModel, shapes: Shape[], connectors: Connector[],
        layoutParameters: DataLayoutParameters, snapToGrid: boolean, gridSize: number): void {
        const graphInfo = ModelUtils.getGraphInfoByItems(model, shapes, connectors);
        graphInfo.forEach(info => {
            const layout = layoutParameters.getLayoutBuilder(info.graph).build();
            const nonGraphItems = ModelUtils.getNonGraphItems(model, info.container, layout.nodeToLayout, shapes, connectors);
            ModelUtils.applyLayout(history, model, info.container, info.graph, layout, nonGraphItems,
                layoutParameters.layoutSettings, snapToGrid, gridSize, layoutParameters.skipPointIndices);
        });
    }
    private changeItemByDataItem(history: History, item: DiagramItem, dataItem: DataSourceItem) {
        if(dataItem.customData !== undefined && !ObjectUtils.compareObjects(dataItem.customData, item.customData))
            history.addAndRedo(new ChangeCustomDataHistoryItem(item.key, dataItem.customData));

        if(dataItem.zIndex !== undefined && dataItem.zIndex !== item.zIndex)
            history.addAndRedo(new ChangeZindexHistoryItem(item, dataItem.zIndex));

        if(dataItem.style !== undefined)
            for(const key in dataItem.style) {
                if(!Object.prototype.hasOwnProperty.call(dataItem.style, key)) continue;
                const value = this.getPreparedStyleValue(dataItem.style[key], isColorProperty(key));
                if(value !== item.style[key])
                    history.addAndRedo(new ChangeStyleHistoryItem(item.key, key, value));
            }
        const defaultStyle = item.style.getDefaultInstance();
        item.style.forEach(key => {
            if((dataItem.style && dataItem.style[key] === undefined) && item.style[key] !== defaultStyle[key])
                history.addAndRedo(new ChangeStyleHistoryItem(item.key, key, defaultStyle[key]));
        });

        if(dataItem.styleText !== undefined)
            for(const key in dataItem.styleText) {
                if(!Object.prototype.hasOwnProperty.call(dataItem.styleText, key)) continue;
                const value = this.getPreparedStyleValue(dataItem.styleText[key], isColorProperty(key));
                if(value !== item.styleText[key])
                    history.addAndRedo(new ChangeStyleTextHistoryItem(item.key, key, value));
            }
        const defaultTextStyle = item.styleText.getDefaultInstance();
        item.styleText.forEach(key => {
            if((dataItem.styleText && dataItem.styleText[key] === undefined) && item.styleText[key] !== defaultTextStyle[key])
                history.addAndRedo(new ChangeStyleTextHistoryItem(item.key, key, defaultTextStyle[key]));
        });

        if(dataItem.locked !== undefined && dataItem.locked !== item.locked)
            history.addAndRedo(new ChangeLockedHistoryItem(item, dataItem.locked));

    }
    getPreparedStyleValue(value: any, isColorProperty: boolean): any {
        if(isColorProperty) {
            const colorValue = ColorUtils.stringToHash(value);
            if(colorValue !== null)
                value = colorValue;
        }
        return value;
    }
    private createShapeByNode(history: History, model: DiagramModel, selection: Selection, shapeDescriptionManager: IShapeDescriptionManager,
        node: DataSourceNodeItem, point: Point, layoutParameters: DataLayoutParameters, snapToGrid: boolean, gridSize: number, measurer?: ITextMeasurer): Shape {
        const insert = new AddShapeHistoryItem(shapeDescriptionManager.get(node.type), point, "", node.key);
        history.addAndRedo(insert);

        const shape = model.findShape(insert.shapeKey);
        ModelUtils.updateNewShapeProperties(history, selection, insert.shapeKey);
        this.changeShapeByDataItem(history, model, shape, node, point);
        this.changeItemByDataItem(history, shape, node);
        if(measurer && this.canUseAutoSize && layoutParameters.autoSizeEnabled)
            this.applyShapeAutoSize(history, measurer, layoutParameters.sizeSettings, shape, snapToGrid, gridSize);
        return shape;
    }
    private changeShapeByDataItem(history: History, model: DiagramModel, shape: Shape,
        node: DataSourceNodeItem, point: Point) {
        let updated = false;
        if(node.left !== undefined)
            point.x = ModelUtils.getTwipsValue(model.units, node.left);
        if(node.top !== undefined)
            point.y = ModelUtils.getTwipsValue(model.units, node.top);
        updated = ModelUtils.setShapePosition(history, model, shape, point, false) || updated;
        if(node.type !== undefined)
            updated = ModelUtils.changeShapeType(history, model, shape, node.type) || updated;

        const size = shape.size.clone();
        if(node.width !== undefined)
            size.width = ModelUtils.getTwipsValue(model.units, node.width);
        if(node.height !== undefined)
            size.height = ModelUtils.getTwipsValue(model.units, node.height);
        updated = ModelUtils.setShapeSize(history, model, shape, point, size) || updated;

        if(updated)
            ModelUtils.updateShapeAttachedConnectors(history, model, shape);

        if(node.text !== undefined && node.text !== shape.text)
            history.addAndRedo(new ChangeShapeTextHistoryItem(shape, node.text));

        if(node.image !== undefined && node.image !== shape.image.actualUrl)
            history.addAndRedo(new ChangeShapeImageHistoryItem(shape, node.image));
    }
    private updateShapeContainer(history: History, model: DiagramModel, shape: Shape, node: DataSourceNodeItem) {
        const containerShape = (node.containerKey !== undefined) ? model.findShapeByDataKey(node.containerKey) : undefined;
        if(containerShape !== shape.container)
            if(containerShape)
                ModelUtils.insertToContainer(history, model, shape, containerShape);
            else
                ModelUtils.removeFromContainer(history, model, shape);

    }
    private getConnectorPointsByEdge(model: DiagramModel, edge: DataSourceEdgeItem, fromShape: Shape, toShape: Shape, forceCreate: boolean): Point[] {
        const result: Point[] = [];
        const modelPoints = this.createModelPointFromDataSourceEdgeItemPoints(model.units, edge);
        if(modelPoints && modelPoints.length > 1) {
            const lastIndex = modelPoints.length - 1;
            for(let i = 0; i <= lastIndex; i++) {
                const modelPoint = modelPoints[i];
                if(modelPoint !== null)
                    result.push(modelPoint);
                else if(!fromShape && !toShape)
                    return undefined;
                else if(i === 0 && fromShape)
                    result.push(fromShape.position.clone());
                else if(i === lastIndex && toShape)
                    result.push(toShape.position.clone());
            }
        }
        else if(forceCreate) {
            if(fromShape)
                result.push(fromShape.position.clone());
            if(toShape)
                result.push(toShape.position.clone());
        }
        return result;
    }

    private createModelPointFromDataSourceEdgeItemPoints(units: DiagramUnit, edge : DataSourceEdgeItem) : Point[] {
        const result: Point[] = [];
        if(!Array.isArray(edge.points))
            return undefined;
        edge.points.forEach(dep => result.push(this.isValidDataSourceEdgeItemPoint(dep) ? this.createModelPoint(units, dep) : null));
        return result;
    }
    private createModelPoint(units: DiagramUnit, point: any) : Point {
        return new Point(
            ModelUtils.getTwipsValue(units, point.x),
            ModelUtils.getTwipsValue(units, point.y)
        );
    }
    private isValidDataSourceEdgeItemPoint(point: any) : boolean {
        return point !== undefined && point !== null &&
            point.x !== undefined && point.y !== undefined &&
            point.x !== null && point.y !== null;
    }
    private createConnectorByEdge(history: History, model: DiagramModel, selection: Selection,
        edge: DataSourceEdgeItem, fromShape: Shape, toShape: Shape): Connector {
        let connector: Connector;
        const dataKey = edge.key;
        const points = this.getConnectorPointsByEdge(model, edge, fromShape, toShape, true);

        if(points && points.length > 1) {
            const insert = new AddConnectorHistoryItem(points, dataKey);
            history.addAndRedo(insert);

            connector = model.findConnector(insert.connectorKey);
            ModelUtils.updateNewConnectorProperties(history, selection, insert.connectorKey);
            this.changeConnectorByDataItem(history, model, connector, fromShape, toShape, edge);
            this.changeItemByDataItem(history, connector, edge);
        }
        return connector;
    }
    private changeConnectorByDataItem(history: History, model: DiagramModel, connector: Connector,
        fromShape: Shape, toShape: Shape, edge: DataSourceEdgeItem) {
        const fromPointIndex = edge.fromPointIndex !== undefined ? edge.fromPointIndex : connector.beginConnectionPointIndex;
        if(connector.beginItem !== fromShape || connector.beginConnectionPointIndex !== fromPointIndex) {
            if(connector.beginItem)
                history.addAndRedo(new DeleteConnectionHistoryItem(connector, ConnectorPosition.Begin));
            if(fromShape)
                history.addAndRedo(new AddConnectionHistoryItem(connector, fromShape, fromPointIndex, ConnectorPosition.Begin));
        }
        const toPointIndex = edge.toPointIndex !== undefined ? edge.toPointIndex : connector.endConnectionPointIndex;
        if(connector.endItem !== toShape || connector.endConnectionPointIndex !== toPointIndex) {
            if(connector.endItem)
                history.addAndRedo(new DeleteConnectionHistoryItem(connector, ConnectorPosition.End));
            if(toShape)
                history.addAndRedo(new AddConnectionHistoryItem(connector, toShape, toPointIndex, ConnectorPosition.End));
        }
        ModelUtils.updateConnectorAttachedPoints(history, model, connector);

        if(edge.texts !== undefined && !this.compareTexts(edge, connector)) {
            connector.texts.forEach(text => {
                history.addAndRedo(new ChangeConnectorTextHistoryItem(connector, text.position, undefined));

            });
            for(const key in edge.texts) {
                if(!Object.prototype.hasOwnProperty.call(edge.texts, key)) continue;

                const position = parseFloat(key);
                history.addAndRedo(new ChangeConnectorTextHistoryItem(connector, position, edge.texts[key]));
            }
        }

        if(edge.lineOption !== undefined && edge.lineOption !== connector.properties.lineOption)
            history.addAndRedo(new ChangeConnectorPropertyHistoryItem(connector.key, "lineOption", edge.lineOption));
        if(edge.startLineEnding !== undefined && edge.startLineEnding !== connector.properties.startLineEnding)
            history.addAndRedo(new ChangeConnectorPropertyHistoryItem(connector.key, "startLineEnding", edge.startLineEnding));
        if(edge.endLineEnding !== undefined && edge.endLineEnding !== connector.properties.endLineEnding)
            history.addAndRedo(new ChangeConnectorPropertyHistoryItem(connector.key, "endLineEnding", edge.endLineEnding));
    }
    private changeConnectorPointsByDataItem(history: History, connector: Connector, newPoints: Point[]) {
        if(newPoints && newPoints.length > 1 && newPoints.join(",") !== connector.points.join(","))
            history.addAndRedo(new ReplaceConnectorPointsHistoryItem(connector.key, newPoints));
    }

    protected compareTexts(edgeObj: DataSourceEdgeItem, connector: Connector): boolean {
        const texts = edgeObj.texts || {};
        let result = Object.keys(texts).length === connector.getTextCount();
        if(result)
            for(const key in texts) {
                if(!Object.prototype.hasOwnProperty.call(texts, key)) continue;

                const position = parseFloat(key);
                if(!this.compareStrings(connector.getText(position), texts[key]))
                    result = false;

            }

        return result;
    }
    protected compareStrings(str1: string, str2: string): boolean {
        if(typeof str1 === "string" && typeof str2 === "string")
            return str1 === str2;
        return this.isEmptyString(str1) && this.isEmptyString(str2);
    }
    protected isEmptyString(str: string): boolean {
        return str === "" || str === null || str === undefined;
    }

    protected abstract beginChangesNotification(): void;
    protected abstract endChangesNotification(preventReloadContent : boolean) : void;
}
