using System;
using System.Collections.Generic;

namespace Development {

    public class HierarchyGraphLayeredApproach<TKey, TValue> {

        #region Properties
        public Dictionary<TKey, GraphNode<TKey, TValue>> UpperNodes { get; }
        public Dictionary<TKey, GraphNode<TKey, TValue>> LowerNodes { get; }
        public GraphNodeLayer<TKey, TValue> UppermostLayer { get; private set; }
        public GraphNodeLayer<TKey, TValue> LowermostLayer { get; private set; }
        public IEnumerable<GraphNode<TKey, TValue>> AllNodes => allNodes;
        #endregion

        #region Instance Fields
        private Dictionary<TKey, int> slotStackCount;
        private HashSet<GraphNode<TKey, TValue>> allNodes;
        private HashSet<TKey> allSlots;

        public HierarchyGraphLayeredApproach() {

            UpperNodes = new Dictionary<TKey, GraphNode<TKey, TValue>>();
            LowerNodes = new Dictionary<TKey, GraphNode<TKey, TValue>>();

            var baseLayer = new GraphNodeLayer<TKey, TValue>();
            UppermostLayer = baseLayer;
            LowermostLayer = baseLayer;

            slotStackCount = new Dictionary<TKey, int>();
            allNodes = new HashSet<GraphNode<TKey, TValue>>();
            allSlots = new HashSet<TKey>();
        }
        #endregion

        #region Instance Methods
        public int StackCountAt(TKey location) {
            slotStackCount.TryGetValue(location, out int count);
            return count;
        }

        public void AttachUpper(GraphNode<TKey, TValue> node) {

            if (allNodes.Add(node) == false)
                throw new Exception("Node already attached!");

            // Survey for the uppermost layer which is 1 layer below the lowermost layer that can recieve this node
            GraphNodeLayer<TKey, TValue> layer = LowermostLayer;
            foreach (var location in node.Coverage)
                if (UpperNodes.TryGetValue(location, out var other) && other.Layer.LayerCountAbove < layer.LayerCountAbove)
                    layer = other.Layer;

            // Continue and try to insert the node
            while (layer != null && layer.Insert(node) == false)
                layer = layer.LayerAbove;

            // Apparently the node must go on a new layer
            if (layer == null) {
                layer = new GraphNodeLayer<TKey, TValue>();
                layer.LayerBelow = UppermostLayer;
                UppermostLayer.LayerAbove = layer;
                UppermostLayer = layer;
                layer.Insert(node);
            }

            // Include and return
            node.Layer = layer;
            Include(node);
        }
        public void AttachLower(GraphNode<TKey, TValue> node) {

            if (allNodes.Add(node) == false)
                throw new Exception("Node already attached!");

            // Survey for the lowermost layer which is 1 layer above the uppermost layer that can recieve this node
            GraphNodeLayer<TKey, TValue> layer = UppermostLayer;
            foreach (var location in node.Coverage)
                if (LowerNodes.TryGetValue(location, out var other) && other.Layer.LayerCountBelow < layer.LayerCountBelow)
                    layer = other.Layer;

            // Continue and try to insert the node
            while (layer != null && layer.Insert(node) == false)
                layer = layer.LayerBelow;

            // Apparently the node must go on a new layer
            if (layer == null) {
                layer = new GraphNodeLayer<TKey, TValue>();
                layer.LayerAbove = LowermostLayer;
                LowermostLayer.LayerBelow = layer;
                LowermostLayer = layer;
                layer.Insert(node);
            }

            // Include and return
            node.Layer = layer;
            Include(node);
        }

        public void Detach(GraphNode<TKey, TValue> node) {

            if (allNodes.Remove(node)) {

                #region Update coverage
                foreach (var location in node.Coverage) {

                    bool hasNodeAbove = node.UpperConnections.TryGetValue(location, out var nodeAbove);
                    bool hasNodeBelow = node.LowerConnections.TryGetValue(location, out var nodeBelow);

                    // Update lower connections / coverage, remove upper connection
                    if (hasNodeAbove) {
                        if (hasNodeBelow) {
                            nodeAbove.LowerConnections[location] = nodeBelow;
                        } else {
                            nodeAbove.LowerConnections.Remove(location);
                            LowerNodes[location] = nodeAbove;
                        }
                        node.UpperConnections.Remove(location);
                    }

                    // Update upper connections / coverage, remove lower connection
                    if (hasNodeBelow) {
                        if (hasNodeAbove) {
                            nodeBelow.UpperConnections[location] = nodeAbove;
                        } else {
                            nodeBelow.UpperConnections.Remove(location);
                            UpperNodes[location] = nodeBelow;
                        }
                        node.LowerConnections.Remove(location);
                    }

                    // This slot was only occupied by this node
                    if (!hasNodeAbove && !hasNodeBelow) {
                        UpperNodes.Remove(location);
                        LowerNodes.Remove(location);
                        allSlots.Remove(location);
                    }

                    --slotStackCount[location];
                }
                #endregion

                #region Update layers
                var layer = node.Layer;
                if (layer.Remove(node) == false)
                    throw new Exception();

                // Node's layer is empty
                if (layer.NodeCount == 0) {

                    int upperHeight = layer.LayerCountAbove;
                    int lowerHeight = layer.LayerCountBelow;
                    bool hasLayerAbove = upperHeight > 0;
                    bool hasLayerBelow = lowerHeight > 0;

                    // Node's layer was "sandwiched"
                    if (hasLayerAbove && hasLayerBelow) {
                        layer.LayerAbove.LayerBelow = layer.LayerBelow;
                        layer.LayerBelow.LayerAbove = layer.LayerAbove;
                        return;
                    }

                    // TotalLayerCount - 1 == 1 (Above or Below?)
                    if (upperHeight + lowerHeight == 1) {

                        if (hasLayerAbove) {
                            UppermostLayer = layer.LayerAbove;
                            LowermostLayer = layer.LayerAbove;
                            return;
                        }

                        if (hasLayerBelow) {
                            UppermostLayer = layer.LayerBelow;
                            LowermostLayer = layer.LayerBelow;
                            return;
                        }

                        throw new Exception(); // Some weird continuity error

                    } else {

                        // Node's layer was the lowermost layer
                        if (layer == LowermostLayer && hasLayerAbove)
                            LowermostLayer = layer.LayerAbove;
                        // Node's layer was the uppermost layer
                        if (layer == UppermostLayer && hasLayerBelow)
                            UppermostLayer = layer.LayerBelow;
                    }
                }
                #endregion
            }
        }

        private void Include(GraphNode<TKey, TValue> node) {

            foreach (var location in node.Coverage)

                if (allSlots.Add(location)) {

                    slotStackCount[location] = 1;
                    UpperNodes[location] = node;
                    LowerNodes[location] = node;

                } else {

                    slotStackCount[location]++;

                    var layerAbove = node.Layer.LayerAbove;
                    while (layerAbove != null) {
                        if (layerAbove.TryGetNode(location, out var nodeAbove)) {
                            nodeAbove.LowerConnections[location] = node;
                            node.UpperConnections[location] = nodeAbove;
                            break;
                        } else layerAbove = layerAbove.LayerAbove;
                    }

                    var layerBelow = node.Layer.LayerBelow;
                    while (layerBelow != null) {
                        if (layerBelow.TryGetNode(location, out var nodeBelow)) {
                            nodeBelow.UpperConnections[location] = node;
                            node.LowerConnections[location] = nodeBelow;
                            break;
                        } else layerBelow = layerBelow.LayerBelow;
                    }

                    if (layerAbove == null)
                        UpperNodes[location] = node;
                    if (layerBelow == null)
                        LowerNodes[location] = node;
                }
        }
        #endregion
    }

    public class GraphNode<TKey, TValue> {

        #region Properties
        public TValue Value { get; set; }
        public GraphNodeLayer<TKey, TValue> Layer { get; set; }
        public Dictionary<TKey, GraphNode<TKey, TValue>> UpperConnections { get; }
        public Dictionary<TKey, GraphNode<TKey, TValue>> LowerConnections { get; }
        public bool IsExposedAbove => UpperConnections.Count == 0;
        public bool IsExposedBelow => LowerConnections.Count == 0;
        public IEnumerable<TKey> Coverage => keyset;
        #endregion

        #region Instance Fields
        private HashSet<TKey> keyset;
        #endregion

        #region Constructors
        public GraphNode(TKey[] coverage) {
            Value = default;
            UpperConnections = new Dictionary<TKey, GraphNode<TKey, TValue>>();
            LowerConnections = new Dictionary<TKey, GraphNode<TKey, TValue>>();
            keyset = new HashSet<TKey>(coverage);
        }
        #endregion

        #region Instance Methods
        public bool Overlaps(TKey location) => keyset.Contains(location);
        #endregion
    }

    public class GraphNodeLayer<TKey, TValue> {

        #region Properties
        public int NodeCount => allNodes.Count;
        public int LayerCountAbove {
            get {
                int count = 0;
                var layer = LayerAbove;
                while (layer != null) {
                    layer = layer.LayerAbove;
                    count++;
                }
                return count;
            }
        }
        public int LayerCountBelow {
            get {
                int count = 0;
                var layer = LayerBelow;
                while (layer != null) {
                    layer = layer.LayerBelow;
                    count++;
                }
                return count;
            }
        }
        public GraphNodeLayer<TKey, TValue> LayerAbove { get; set; }
        public GraphNodeLayer<TKey, TValue> LayerBelow { get; set; }
        public IEnumerable<GraphNode<TKey, TValue>> AllNodes => allNodes;
        #endregion

        #region Instance Fields
        private Dictionary<TKey, GraphNode<TKey, TValue>> nodeMap;
        private HashSet<GraphNode<TKey, TValue>> allNodes;
        #endregion

        #region Constructors
        public GraphNodeLayer() {
            nodeMap = new Dictionary<TKey, GraphNode<TKey, TValue>>();
            allNodes = new HashSet<GraphNode<TKey, TValue>>();
        }
        #endregion

        #region Instance Fields
        public bool Insert(GraphNode<TKey, TValue> node) {
            if (allNodes.Contains(node))
                return false;
            foreach (var location in node.Coverage)
                if (nodeMap.ContainsKey(location))
                    return false;
            foreach (var location in node.Coverage)
                nodeMap[location] = node;
            allNodes.Add(node);
            return true;
        }
        public bool Remove(GraphNode<TKey, TValue> node) {
            if (allNodes.Contains(node) == false)
                return false;
            foreach (var location in node.Coverage)
                nodeMap.Remove(location);
            allNodes.Remove(node);
            return true;
        }

        public bool TryGetNode(TKey location, out GraphNode<TKey, TValue> node) => nodeMap.TryGetValue(location, out node);

        public HashSet<GraphNode<TKey, TValue>> Query(params TKey[] coverage) {
            HashSet<GraphNode<TKey, TValue>> nodeSet = new HashSet<GraphNode<TKey, TValue>>();
            foreach (var location in coverage)
                if (nodeMap.TryGetValue(location, out var node))
                    nodeSet.Add(node);
            return nodeSet;
        }
        #endregion
    }
}