基于前缀树的红点系统

前缀树

前缀树本质上是一种多叉树，树节点存储了字符，具有相同前缀的字符串将具有相同的父节点。
通过红点抽象为路径，只需要稍加修改，让节点中存储对应的路径字符串和节点值，便可以实现红点系统。
1.png
处理痛点：

  • 1.在处理路径时直接使用split方法进行字符串暴力切割，导致额外的内存分配
  • 2.在子节点状态改变后需要也改变父节点状态时不进行限制，多个子节点同时改变将导致额外的无用刷新。

TreeNode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
/// <summary>
/// 树节点
/// </summary>
public class TreeNode
{
    /// <summary>
    /// 子节点
    /// </summary>
    private Dictionary<RangeString, TreeNode> m_Children;

	/// <summary>
    /// 节点值改变回调
    /// </summary>
    private Action<int> m_ChangeCallback;

	/// <summary>
    /// 完整路径
    /// </summary>
    private string m_FullPath;

	/// <summary>
    /// 节点名
    /// </summary>
    public string Name
    {
        get;
        private set;
    }

	/// <summary>
    /// 完整路径
    /// </summary>
    public string FullPath
    {
        get
        {
            if (string.IsNullOrEmpty(m_FullPath))
            {
                if (Parent == null || Parent == ReddotMananger.Instance.Root)
                {
                    m_FullPath = Name;
                }
                else
                {
                    m_FullPath = Parent.FullPath + ReddotMananger.Instance.SplitChar + Name;
                }
            }

            return m_FullPath;
        }
    }


    /// <summary>
    /// 节点值
    /// </summary>
    public int Value
    {
        get;
        private set;
    }

	/// <summary>
    /// 父节点
    /// </summary>
    public TreeNode Parent
    {
        get;
        private set;
    }

	/// <summary>
    /// 子节点
    /// </summary>
    public Dictionary<RangeString, TreeNode>.ValueCollection Children
    {
        get
        {
            return m_Children?.Values;
        }
    }

    /// <summary>
    /// 子节点数量
    /// </summary>
    public int ChildrenCount
    {
        get
        {
            if (m_Children == null)
            {
                return 0;
            }

            int sum = m_Children.Count;
            foreach (TreeNode node in m_Children.Values)
            {
                sum += node.ChildrenCount;
            }
            return sum;
        }
    }

    public TreeNode(string name)
    {
        Name = name;
        Value = 0;
        m_ChangeCallback = null;
    }

    public TreeNode(string name, TreeNode parent) : this(name)
    {
        Parent = parent;
    }

	/// <summary>
    /// 添加节点值监听
    /// </summary>
    public void AddListener(Action<int> callback)
    {
        m_ChangeCallback += callback;
    }

    /// <summary>
    /// 移除节点值监听
    /// </summary>
    public void RemoveListener(Action<int> callback)
    {
        m_ChangeCallback -= callback;
    }

    /// <summary>
    /// 移除所有节点值监听
    /// </summary>
    public void RemoveAllListener()
    {
        m_ChangeCallback = null;
    }

	/// <summary>
    /// 改变节点值（使用传入的新值，只能在叶子节点上调用）
    /// </summary>
    public void ChangeValue(int newValue)
    {
        if (m_Children != null && m_Children.Count != 0)
        {
            throw new Exception("不允许直接改变非叶子节点的值：" + FullPath);
        }

        InternalChangeValue(newValue);
    }

    /// <summary>
    /// 改变节点值（根据子节点值计算新值，只对非叶子节点有效）
    /// </summary>
    public void ChangeValue()
    {
        int sum = 0;

        if (m_Children != null && m_Children.Count != 0)
        {
            foreach (KeyValuePair<RangeString, TreeNode> child in m_Children)
            {
                sum += child.Value.Value;
            }
        }

        InternalChangeValue(sum);
    }

	/// <summary>
    /// 获取子节点，如果不存在则添加
    /// </summary>
    public TreeNode GetOrAddChild(RangeString key)
    {
        TreeNode child = GetChild(key);
        if (child == null)
        {
            child = AddChild(key);
        }
        return child;
    }

    /// <summary>
    /// 获取子节点
    /// </summary>
    public TreeNode GetChild(RangeString key)
    {
        TreeNode child = null;

        if (m_Children == null)
        {
            return null;
        }

        m_Children.TryGetValue(key, out child);
        return child;
    }

    /// <summary>
    /// 添加子节点
    /// </summary>
    public TreeNode AddChild(RangeString key)
    {
        if (m_Children == null)
        {
            m_Children = new Dictionary<RangeString, TreeNode>();
        }
        else if (m_Children.ContainsKey(key))
        {
            throw new Exception("子节点添加失败，不允许重复添加：" + FullPath);
        }

        TreeNode child = new TreeNode(key.ToString(), this);
        m_Children.Add(key, child);
        ReddotMananger.Instance.NodeNumChangeCallback?.Invoke();
        return child;
    }

    /// <summary>
    /// 移除子节点
    /// </summary>
    public bool RemoveChild(RangeString key)
    {
        if (m_Children == null || m_Children.Count == 0)
        {
            return false;
        }

        TreeNode child = GetChild(key);

        if (child != null)
        {
            //子节点被删除 需要进行一次父节点刷新
            ReddotMananger.Instance.MarkDirtyNode(this);

            m_Children.Remove(key);

            ReddotMananger.Instance.NodeNumChangeCallback?.Invoke();

            return true;
        }

        return false;
    }

    /// <summary>
    /// 移除所有子节点
    /// </summary>
    public void RemoveAllChild()
    {
        if (m_Children == null || m_Children.Count == 0)
        {
            return;
        }

        m_Children.Clear();
        ReddotMananger.Instance.MarkDirtyNode(this);
        ReddotMananger.Instance.NodeNumChangeCallback?.Invoke();
    }

    public override string ToString()
    {
        return FullPath;
    }

    /// <summary>
    /// 改变节点值
    /// </summary>
    private void InternalChangeValue(int newValue)
    {
        if (Value == newValue)
        {
            return;
        }

        Value = newValue;
        m_ChangeCallback?.Invoke(newValue);
        ReddotMananger.Instance.NodeValueChangeCallback?.Invoke(this, Value);

        //标记父节点为脏节点
        ReddotMananger.Instance.MarkDirtyNode(Parent);
    }
}

TreeNode类很简单，使用string和TreeNode为键值的字典维护所有子节点，并持有一个Action作为子节点值改变的回调提供给上层逻辑监听，需要注意的是改变子节点值的两种重载分别适用于叶子节点与非叶子节点，只有叶子节点的值能被直接修改，非叶子节点的值需要通过计算子节点的值得到。

ReddotManager

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
/// <summary>
/// 红点管理器
/// </summary>
public class ReddotMananger
{
    private static ReddotMananger m_Instance;

    public static ReddotMananger Instance
    {
        get
        {
            if (m_Instance == null)
            {
                m_Instance = new ReddotMananger();
            }
            return m_Instance;
        }
    }

	/// <summary>
    /// 所有节点集合
    /// </summary>
    private Dictionary<string, TreeNode> m_AllNodes;

    /// <summary>
    /// 脏节点集合
    /// </summary>
    private HashSet<TreeNode> m_DirtyNodes;

	/// <summary>
    /// 临时脏节点集合
    /// </summary>
    private List<TreeNode> m_TempDirtyNodes;

	/// <summary>
    /// 节点数量改变回调
    /// </summary>
    public Action NodeNumChangeCallback;

	/// <summary>
    /// 节点值改变回调
    /// </summary>
    public Action<TreeNode,int> NodeValueChangeCallback;

	/// <summary>
    /// 路径分隔字符
    /// </summary>
    public char SplitChar
    {
        get;
        private set;
    }

    /// <summary>
    /// 缓存的StringBuild
    /// </summary>
    public StringBuilder CachedSb
    {
        get;
        private set;
    }

	/// <summary>
    /// 红点树根节点
    /// </summary>
    public TreeNode Root
    {
        get;
        private set;
    }

    public ReddotMananger()
    {
        SplitChar = '/';
        m_AllNodes = new Dictionary<string, TreeNode>();
        Root = new TreeNode("Root");
        m_DirtyNodes = new HashSet<TreeNode>();
        m_TempDirtyNodes = new List<TreeNode>();
        CachedSb = new StringBuilder();
    }

	/// <summary>
    /// 添加节点值监听
    /// </summary>
    public TreeNode AddListener(string path,Action<int> callback)
    {
        if (callback == null)
        {
            return null;
        }

        TreeNode node = GetTreeNode(path);
        node.AddListener(callback);

        return node;
    }

    /// <summary>
    /// 移除节点值监听
    /// </summary>
    public void RemoveListener(string path,Action<int> callback)
    {
        if (callback == null)
        {
            return;
        }

        TreeNode node = GetTreeNode(path);
        node.RemoveListener(callback);
    }

    /// <summary>
    /// 移除所有节点值监听
    /// </summary>
    public void RemoveAllListener(string path)
    {
        TreeNode node = GetTreeNode(path);
        node.RemoveAllListener();
    }

    /// <summary>
    /// 改变节点值
    /// </summary>
    public void ChangeValue(string path,int newValue)
    {
        TreeNode node = GetTreeNode(path);
        node.ChangeValue(newValue);
    }

	/// <summary>
    /// 获取节点值
    /// </summary>
    public int GetValue(string path)
    {
        TreeNode node = GetTreeNode(path);
        if (node == null)
        {
            return 0;
        }

        return node.Value;
    }

	/// <summary>
    /// 获取节点
    /// </summary>
    public TreeNode GetTreeNode(string path)
    {
        if (string.IsNullOrEmpty(path))
        {
            throw new Exception("路径不合法，不能为空");
        }

        TreeNode node = null;

        if (m_AllNodes.TryGetValue(path,out node))
        {
            return node;
        }

        TreeNode cur = Root;
        int length = path.Length;

        int startIndex = 0;

        for (int i = 0; i < length; i++)
        {
            if (path[i] == SplitChar)
            {
                if (i == length - 1)
                {
                    throw new Exception("路径不合法，不能以路径分隔符结尾：" + path);
                }

                int endIndex = i - 1;
                if (endIndex < startIndex)
                {
                    throw new Exception("路径不合法，不能存在连续的路径分隔符或以路径分隔符开头：" + path);
                }

                TreeNode child = cur.GetOrAddChild(new RangeString(path,startIndex,endIndex));

                //更新startIndex
                startIndex = i + 1;

                cur = child;
            }
        }

        //最后一个节点 直接用length - 1作为endIndex
        TreeNode target = cur.GetOrAddChild(new RangeString(path, startIndex, length - 1));

        m_AllNodes.Add(path, target);

        return target;
    }

    /// <summary>
    /// 移除节点
    /// </summary>
    public bool RemoveTreeNode(string path)
    {
        if (!m_AllNodes.ContainsKey(path))
        {
            return false;
        }

        TreeNode node = GetTreeNode(path);
        m_AllNodes.Remove(path);
        return node.Parent.RemoveChild(new RangeString(node.Name, 0, node.Name.Length - 1));
    }

    /// <summary>
    /// 移除所有节点
    /// </summary>
    public void RemoveAllTreeNode()
    {
        Root.RemoveAllChild();
        m_AllNodes.Clear();
    }

    /// <summary>
    /// 管理器轮询
    /// </summary>
    public void Update()
    {
        if (m_DirtyNodes.Count == 0)
        {
            return;
        }

        m_TempDirtyNodes.Clear();
        foreach (TreeNode node in m_DirtyNodes)
        {
            m_TempDirtyNodes.Add(node);
        }
        m_DirtyNodes.Clear();

        //处理所有脏节点
        for (int i = 0; i < m_TempDirtyNodes.Count; i++)
        {
            m_TempDirtyNodes[i].ChangeValue();
        }
    }

    /// <summary>
    /// 标记脏节点
    /// </summary>
    public void MarkDirtyNode(TreeNode node)
    {
        if (node == null || node.Name == Root.Name)
        {
            return;
        }

        m_DirtyNodes.Add(node);
    }
}

RangeString

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
/// <summary>
/// 范围字符串
/// 表示在Source字符串中，从StartIndex到EndIndex范围的字符构成的字符串
/// </summary>
public struct RangeString : IEquatable<RangeString>
{
    /// <summary>
    /// 源字符串
    /// </summary>
    private string m_Source;
	
	/// <summary>
    /// 开始索引
    /// </summary>
    private int m_StartIndex;

	/// <summary>
    /// 结束范围
    /// </summary>
    private int m_EndIndex;

	/// <summary>
    /// 长度
    /// </summary>
    private int m_Length;

    /// <summary>
    /// 源字符串是否为Null或Empty
    /// </summary>
    private bool m_IsSourceNullOrEmpty;

    /// <summary>
    /// 哈希码
    /// </summary>
    private int m_HashCode;

    public RangeString(string source, int startIndex, int endIndex)
    {
        m_Source = source;
        m_StartIndex = startIndex;
        m_EndIndex = endIndex;
        m_Length = endIndex - startIndex + 1;
        m_IsSourceNullOrEmpty = string.IsNullOrEmpty(source);
        m_HashCode = 0;
    }

    public bool Equals(RangeString other)
    {

        bool isOtherNullOrEmpty = string.IsNullOrEmpty(other.m_Source);

        if (m_IsSourceNullOrEmpty && isOtherNullOrEmpty)
        {
            return true;
        }

        if (m_IsSourceNullOrEmpty || isOtherNullOrEmpty)
        {
            return false;
        }

        if (m_Length != other.m_Length)
        {
            return false;
        }

        for (int i = m_StartIndex, j = other.m_StartIndex; i <= m_EndIndex; i++, j++)
        {
            if (m_Source[i] != other.m_Source[j])
            {
                return false;
            }
        }

        return true;
    }

    public override int GetHashCode()
    {
        if (m_HashCode == 0 && !m_IsSourceNullOrEmpty)
        {
            for (int i = m_StartIndex; i <= m_EndIndex; i++)
            {
                m_HashCode = 31 * m_HashCode + m_Source[i];
            }
        }

        return m_HashCode;
    }

    public override string ToString()
    {
        ReddotMananger.Instance.CachedSb.Clear();
        for (int i = m_StartIndex; i <= m_EndIndex; i++)
        {
            ReddotMananger.Instance.CachedSb.Append(m_Source[i]);
        }
        string str = ReddotMananger.Instance.CachedSb.ToString();

        return str;
    }
}