1 //
2 // Copyright (c) 2010-2024 Antmicro
3 // Copyright (c) 2011-2015 Realtime Embedded
4 //
5 // This file is licensed under the MIT License.
6 // Full license text is available in 'licenses/MIT.txt'.
7 //
8 
9 using System.Collections.Generic;
10 using System.Linq;
11 using System;
12 
13 namespace Antmicro.Renode.Utilities.Collections
14 {
15     public class MultiTreeNode<TValue, TConnectionWay> : TreeBase<MultiTreeNode<TValue, TConnectionWay>, TValue>
16     {
MultiTreeNode(TValue value, MultiTree<TValue, TConnectionWay> root)17         internal MultiTreeNode(TValue value, MultiTree<TValue, TConnectionWay> root) : base(value)
18         {
19             if(root == null)
20             {
21                 root = (MultiTree<TValue, TConnectionWay>)this;
22             }
23             this.root = root;
24             ConnectionWays = new List<TConnectionWay>();
25         }
26 
AddChild(TValue value)27         public override MultiTreeNode<TValue, TConnectionWay> AddChild(TValue value)
28         {
29             return AddChild(value, default(TConnectionWay));
30         }
31 
AddChild(TValue value, TConnectionWay connectionWay)32         public MultiTreeNode<TValue, TConnectionWay> AddChild(TValue value, TConnectionWay connectionWay)
33         {
34             var node = root.FindOrCreateNode(value);
35             node.SetParent(this);
36             ChildrenList.Add(node);
37             ConnectionWays.Add(connectionWay);
38             return node;
39         }
40 
SetParent(MultiTreeNode<TValue, TConnectionWay> parentNode)41         public void SetParent(MultiTreeNode<TValue, TConnectionWay> parentNode)
42         {
43             ParentsList.Add(parentNode);
44         }
45 
GetConnectionWays(TValue value)46         public IEnumerable<TConnectionWay> GetConnectionWays(TValue value)
47         {
48             var childNode = root.GetNode(value);
49             var valueIndices = ChildrenList.IndicesOf(childNode);
50             foreach(var index in valueIndices)
51             {
52                 if(index == -1)
53                 {
54                     throw new KeyNotFoundException($"Could not find child with value '{value}'.");
55                 }
56                 yield return ConnectionWays[index];
57             }
58         }
59 
OnConnectionWays(Action<TValue, TConnectionWay> handler)60         public void OnConnectionWays(Action<TValue, TConnectionWay> handler)
61         {
62             for(var i = 0; i < ChildrenList.Count; i++)
63             {
64                 handler(ChildrenList[i].Value, ConnectionWays[i]);
65             }
66         }
67 
RemoveChild(TValue value)68         public override void RemoveChild(TValue value)
69         {
70             int index;
71             var nodeToRemove = root.GetNode(value);
72             var removed = false;
73             while((index = ChildrenList.IndexOf(nodeToRemove)) != -1)
74             {
75                 ChildrenList.RemoveAt(index);
76                 ConnectionWays.RemoveAt(index);
77                 removed = true;
78             }
79             if(!removed)
80             {
81                 throw new InvalidOperationException($"Node '{Value}' does not have child '{value}'.");
82             }
83             root.GarbageCollect();
84         }
85 
RemoveChild(TConnectionWay connectionWay, Func<TValue, bool> tester = null)86         public void RemoveChild(TConnectionWay connectionWay, Func<TValue, bool> tester = null)
87         {
88             var connectionWayIndices = ConnectionWays.IndicesOf(connectionWay);
89             var removed = false;
90             foreach(var index in connectionWayIndices.OrderByDescending(x => x))
91             {
92                 if(tester != null && !tester(ChildrenList[index].Value))
93                 {
94                     root.GarbageCollect();
95                     return;
96                 }
97 
98                 ChildrenList.RemoveAt(index);
99                 ConnectionWays.RemoveAt(index);
100                 removed = true;
101             }
102             if(!removed)
103             {
104                 throw new InvalidOperationException($"Node '{Value}' does not have child connected by '{connectionWay}'.");
105             }
106             root.GarbageCollect();
107         }
108 
ReplaceConnectionWay(TConnectionWay oldValue, TConnectionWay newValue)109         public void ReplaceConnectionWay(TConnectionWay oldValue, TConnectionWay newValue)
110         {
111             if(newValue.Equals(oldValue))
112             {
113                 return;
114             }
115 
116             int index;
117             var replaced = false;
118             while((index = ConnectionWays.IndexOf(oldValue)) != -1)
119             {
120                 ConnectionWays[index] = newValue;
121                 replaced = true;
122             }
123             if(!replaced)
124             {
125                 throw new InvalidOperationException($"Node '{Value}' does not have child with connection way '{oldValue}'.");
126             }
127         }
128 
TraverseWithConnectionWaysChildrenOnly(Action<MultiTreeNode<TValue, TConnectionWay>, TConnectionWay, TValue, int> nodeHandler, int initialLevel)129         protected void TraverseWithConnectionWaysChildrenOnly(Action<MultiTreeNode<TValue, TConnectionWay>, TConnectionWay, TValue, int> nodeHandler, int initialLevel)
130         {
131             for(var i = 0; i < ChildrenList.Count; i++)
132             {
133                 nodeHandler(ChildrenList[i], ConnectionWays[i], Value, initialLevel + 1);
134                 ChildrenList[i].TraverseWithConnectionWaysChildrenOnly(nodeHandler, initialLevel + 1);
135             }
136         }
137 
138         protected readonly List<TConnectionWay> ConnectionWays;
139         private readonly MultiTree<TValue, TConnectionWay> root;
140     }
141 
142     public static class ListExtensions
143     {
IndicesOf(this List<T> list, T value)144         public static IEnumerable<int> IndicesOf<T>(this List<T> list, T value)
145         {
146             var index = 0;
147             while((index = list.IndexOf(value, index)) != -1)
148             {
149                 yield return index++;
150             }
151         }
152     }
153 }
154