SHARE
TWEET

Untitled

a guest Nov 9th, 2019 94 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. namespace Development {
  5.  
  6.     public class HierarchyGraphLayeredApproach<TKey, TValue> {
  7.  
  8.         #region Properties
  9.         public Dictionary<TKey, GraphNode<TKey, TValue>> UpperNodes { get; }
  10.         public Dictionary<TKey, GraphNode<TKey, TValue>> LowerNodes { get; }
  11.         public GraphNodeLayer<TKey, TValue> UppermostLayer { get; private set; }
  12.         public GraphNodeLayer<TKey, TValue> LowermostLayer { get; private set; }
  13.         public IEnumerable<GraphNode<TKey, TValue>> AllNodes => allNodes;
  14.         #endregion
  15.  
  16.         #region Instance Fields
  17.         private Dictionary<TKey, int> slotStackCount;
  18.         private HashSet<GraphNode<TKey, TValue>> allNodes;
  19.         private HashSet<TKey> allSlots;
  20.  
  21.         public HierarchyGraphLayeredApproach() {
  22.  
  23.             UpperNodes = new Dictionary<TKey, GraphNode<TKey, TValue>>();
  24.             LowerNodes = new Dictionary<TKey, GraphNode<TKey, TValue>>();
  25.  
  26.             var baseLayer = new GraphNodeLayer<TKey, TValue>();
  27.             UppermostLayer = baseLayer;
  28.             LowermostLayer = baseLayer;
  29.  
  30.             slotStackCount = new Dictionary<TKey, int>();
  31.             allNodes = new HashSet<GraphNode<TKey, TValue>>();
  32.             allSlots = new HashSet<TKey>();
  33.         }
  34.         #endregion
  35.  
  36.         #region Instance Methods
  37.         public int StackCountAt(TKey location) {
  38.             slotStackCount.TryGetValue(location, out int count);
  39.             return count;
  40.         }
  41.  
  42.         public void AttachUpper(GraphNode<TKey, TValue> node) {
  43.  
  44.             if (allNodes.Add(node) == false)
  45.                 throw new Exception("Node already attached!");
  46.  
  47.             // Survey for the uppermost layer which is 1 layer below the lowermost layer that can recieve this node
  48.             GraphNodeLayer<TKey, TValue> layer = LowermostLayer;
  49.             foreach (var location in node.Coverage)
  50.                 if (UpperNodes.TryGetValue(location, out var other) && other.Layer.LayerCountAbove < layer.LayerCountAbove)
  51.                     layer = other.Layer;
  52.  
  53.             // Continue and try to insert the node
  54.             while (layer != null && layer.Insert(node) == false)
  55.                 layer = layer.LayerAbove;
  56.  
  57.             // Apparently the node must go on a new layer
  58.             if (layer == null) {
  59.                 layer = new GraphNodeLayer<TKey, TValue>();
  60.                 layer.LayerBelow = UppermostLayer;
  61.                 UppermostLayer.LayerAbove = layer;
  62.                 UppermostLayer = layer;
  63.                 layer.Insert(node);
  64.             }
  65.  
  66.             // Include and return
  67.             node.Layer = layer;
  68.             Include(node);
  69.         }
  70.         public void AttachLower(GraphNode<TKey, TValue> node) {
  71.  
  72.             if (allNodes.Add(node) == false)
  73.                 throw new Exception("Node already attached!");
  74.  
  75.             // Survey for the lowermost layer which is 1 layer above the uppermost layer that can recieve this node
  76.             GraphNodeLayer<TKey, TValue> layer = UppermostLayer;
  77.             foreach (var location in node.Coverage)
  78.                 if (LowerNodes.TryGetValue(location, out var other) && other.Layer.LayerCountBelow < layer.LayerCountBelow)
  79.                     layer = other.Layer;
  80.  
  81.             // Continue and try to insert the node
  82.             while (layer != null && layer.Insert(node) == false)
  83.                 layer = layer.LayerBelow;
  84.  
  85.             // Apparently the node must go on a new layer
  86.             if (layer == null) {
  87.                 layer = new GraphNodeLayer<TKey, TValue>();
  88.                 layer.LayerAbove = LowermostLayer;
  89.                 LowermostLayer.LayerBelow = layer;
  90.                 LowermostLayer = layer;
  91.                 layer.Insert(node);
  92.             }
  93.  
  94.             // Include and return
  95.             node.Layer = layer;
  96.             Include(node);
  97.         }
  98.  
  99.         public void Detach(GraphNode<TKey, TValue> node) {
  100.  
  101.             if (allNodes.Remove(node)) {
  102.  
  103.                 #region Update coverage
  104.                 foreach (var location in node.Coverage) {
  105.  
  106.                     bool hasNodeAbove = node.UpperConnections.TryGetValue(location, out var nodeAbove);
  107.                     bool hasNodeBelow = node.LowerConnections.TryGetValue(location, out var nodeBelow);
  108.  
  109.                     // Update lower connections / coverage, remove upper connection
  110.                     if (hasNodeAbove) {
  111.                         if (hasNodeBelow) {
  112.                             nodeAbove.LowerConnections[location] = nodeBelow;
  113.                         } else {
  114.                             nodeAbove.LowerConnections.Remove(location);
  115.                             LowerNodes[location] = nodeAbove;
  116.                         }
  117.                         node.UpperConnections.Remove(location);
  118.                     }
  119.  
  120.                     // Update upper connections / coverage, remove lower connection
  121.                     if (hasNodeBelow) {
  122.                         if (hasNodeAbove) {
  123.                             nodeBelow.UpperConnections[location] = nodeAbove;
  124.                         } else {
  125.                             nodeBelow.UpperConnections.Remove(location);
  126.                             UpperNodes[location] = nodeBelow;
  127.                         }
  128.                         node.LowerConnections.Remove(location);
  129.                     }
  130.  
  131.                     // This slot was only occupied by this node
  132.                     if (!hasNodeAbove && !hasNodeBelow) {
  133.                         UpperNodes.Remove(location);
  134.                         LowerNodes.Remove(location);
  135.                         allSlots.Remove(location);
  136.                     }
  137.  
  138.                     --slotStackCount[location];
  139.                 }
  140.                 #endregion
  141.  
  142.                 #region Update layers
  143.                 var layer = node.Layer;
  144.                 if (layer.Remove(node) == false)
  145.                     throw new Exception();
  146.  
  147.                 // Node's layer is empty
  148.                 if (layer.NodeCount == 0) {
  149.  
  150.                     int upperHeight = layer.LayerCountAbove;
  151.                     int lowerHeight = layer.LayerCountBelow;
  152.                     bool hasLayerAbove = upperHeight > 0;
  153.                     bool hasLayerBelow = lowerHeight > 0;
  154.  
  155.                     // Node's layer was "sandwiched"
  156.                     if (hasLayerAbove && hasLayerBelow) {
  157.                         layer.LayerAbove.LayerBelow = layer.LayerBelow;
  158.                         layer.LayerBelow.LayerAbove = layer.LayerAbove;
  159.                         return;
  160.                     }
  161.  
  162.                     // TotalLayerCount - 1 == 1 (Above or Below?)
  163.                     if (upperHeight + lowerHeight == 1) {
  164.  
  165.                         if (hasLayerAbove) {
  166.                             UppermostLayer = layer.LayerAbove;
  167.                             LowermostLayer = layer.LayerAbove;
  168.                             return;
  169.                         }
  170.  
  171.                         if (hasLayerBelow) {
  172.                             UppermostLayer = layer.LayerBelow;
  173.                             LowermostLayer = layer.LayerBelow;
  174.                             return;
  175.                         }
  176.  
  177.                         throw new Exception(); // Some weird continuity error
  178.  
  179.                     } else {
  180.  
  181.                         // Node's layer was the lowermost layer
  182.                         if (layer == LowermostLayer && hasLayerAbove)
  183.                             LowermostLayer = layer.LayerAbove;
  184.                         // Node's layer was the uppermost layer
  185.                         if (layer == UppermostLayer && hasLayerBelow)
  186.                             UppermostLayer = layer.LayerBelow;
  187.                     }
  188.                 }
  189.                 #endregion
  190.             }
  191.         }
  192.  
  193.         private void Include(GraphNode<TKey, TValue> node) {
  194.  
  195.             foreach (var location in node.Coverage)
  196.  
  197.                 if (allSlots.Add(location)) {
  198.  
  199.                     slotStackCount[location] = 1;
  200.                     UpperNodes[location] = node;
  201.                     LowerNodes[location] = node;
  202.  
  203.                 } else {
  204.  
  205.                     slotStackCount[location]++;
  206.  
  207.                     var layerAbove = node.Layer.LayerAbove;
  208.                     while (layerAbove != null) {
  209.                         if (layerAbove.TryGetNode(location, out var nodeAbove)) {
  210.                             nodeAbove.LowerConnections[location] = node;
  211.                             node.UpperConnections[location] = nodeAbove;
  212.                             break;
  213.                         } else layerAbove = layerAbove.LayerAbove;
  214.                     }
  215.  
  216.                     var layerBelow = node.Layer.LayerBelow;
  217.                     while (layerBelow != null) {
  218.                         if (layerBelow.TryGetNode(location, out var nodeBelow)) {
  219.                             nodeBelow.UpperConnections[location] = node;
  220.                             node.LowerConnections[location] = nodeBelow;
  221.                             break;
  222.                         } else layerBelow = layerBelow.LayerBelow;
  223.                     }
  224.  
  225.                     if (layerAbove == null)
  226.                         UpperNodes[location] = node;
  227.                     if (layerBelow == null)
  228.                         LowerNodes[location] = node;
  229.                 }
  230.         }
  231.         #endregion
  232.     }
  233.  
  234.     public class GraphNode<TKey, TValue> {
  235.  
  236.         #region Properties
  237.         public TValue Value { get; set; }
  238.         public GraphNodeLayer<TKey, TValue> Layer { get; set; }
  239.         public Dictionary<TKey, GraphNode<TKey, TValue>> UpperConnections { get; }
  240.         public Dictionary<TKey, GraphNode<TKey, TValue>> LowerConnections { get; }
  241.         public bool IsExposedAbove => UpperConnections.Count == 0;
  242.         public bool IsExposedBelow => LowerConnections.Count == 0;
  243.         public IEnumerable<TKey> Coverage => keyset;
  244.         #endregion
  245.  
  246.         #region Instance Fields
  247.         private HashSet<TKey> keyset;
  248.         #endregion
  249.  
  250.         #region Constructors
  251.         public GraphNode(TKey[] coverage) {
  252.             Value = default;
  253.             UpperConnections = new Dictionary<TKey, GraphNode<TKey, TValue>>();
  254.             LowerConnections = new Dictionary<TKey, GraphNode<TKey, TValue>>();
  255.             keyset = new HashSet<TKey>(coverage);
  256.         }
  257.         #endregion
  258.  
  259.         #region Instance Methods
  260.         public bool Overlaps(TKey location) => keyset.Contains(location);
  261.         #endregion
  262.     }
  263.  
  264.     public class GraphNodeLayer<TKey, TValue> {
  265.  
  266.         #region Properties
  267.         public int NodeCount => allNodes.Count;
  268.         public int LayerCountAbove {
  269.             get {
  270.                 int count = 0;
  271.                 var layer = LayerAbove;
  272.                 while (layer != null) {
  273.                     layer = layer.LayerAbove;
  274.                     count++;
  275.                 }
  276.                 return count;
  277.             }
  278.         }
  279.         public int LayerCountBelow {
  280.             get {
  281.                 int count = 0;
  282.                 var layer = LayerBelow;
  283.                 while (layer != null) {
  284.                     layer = layer.LayerBelow;
  285.                     count++;
  286.                 }
  287.                 return count;
  288.             }
  289.         }
  290.         public GraphNodeLayer<TKey, TValue> LayerAbove { get; set; }
  291.         public GraphNodeLayer<TKey, TValue> LayerBelow { get; set; }
  292.         public IEnumerable<GraphNode<TKey, TValue>> AllNodes => allNodes;
  293.         #endregion
  294.  
  295.         #region Instance Fields
  296.         private Dictionary<TKey, GraphNode<TKey, TValue>> nodeMap;
  297.         private HashSet<GraphNode<TKey, TValue>> allNodes;
  298.         #endregion
  299.  
  300.         #region Constructors
  301.         public GraphNodeLayer() {
  302.             nodeMap = new Dictionary<TKey, GraphNode<TKey, TValue>>();
  303.             allNodes = new HashSet<GraphNode<TKey, TValue>>();
  304.         }
  305.         #endregion
  306.  
  307.         #region Instance Fields
  308.         public bool Insert(GraphNode<TKey, TValue> node) {
  309.             if (allNodes.Contains(node))
  310.                 return false;
  311.             foreach (var location in node.Coverage)
  312.                 if (nodeMap.ContainsKey(location))
  313.                     return false;
  314.             foreach (var location in node.Coverage)
  315.                 nodeMap[location] = node;
  316.             allNodes.Add(node);
  317.             return true;
  318.         }
  319.         public bool Remove(GraphNode<TKey, TValue> node) {
  320.             if (allNodes.Contains(node) == false)
  321.                 return false;
  322.             foreach (var location in node.Coverage)
  323.                 nodeMap.Remove(location);
  324.             allNodes.Remove(node);
  325.             return true;
  326.         }
  327.  
  328.         public bool TryGetNode(TKey location, out GraphNode<TKey, TValue> node) => nodeMap.TryGetValue(location, out node);
  329.  
  330.         public HashSet<GraphNode<TKey, TValue>> Query(params TKey[] coverage) {
  331.             HashSet<GraphNode<TKey, TValue>> nodeSet = new HashSet<GraphNode<TKey, TValue>>();
  332.             foreach (var location in coverage)
  333.                 if (nodeMap.TryGetValue(location, out var node))
  334.                     nodeSet.Add(node);
  335.             return nodeSet;
  336.         }
  337.         #endregion
  338.     }
  339. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top