-
Notifications
You must be signed in to change notification settings - Fork 0
/
Queue.cs
97 lines (83 loc) · 2.73 KB
/
Queue.cs
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
namespace DataStructures.Queue
{
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using EnsureThat;
using MoreLinq;
public class Queue<T> : IDynamicSet<T>
where T : IComparable<T>
{
private QueueNode<T>[] nodes = new QueueNode<T>[1];
private int head = 0;
private int tail = 0;
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
public IEnumerator<IDynamicSetNode<T>> GetEnumerator()
{
for (int i = this.head; i < this.tail; i++)
{
yield return this.nodes[i];
}
}
public int Count()
{
return this.tail >= this.head ?
this.tail - this.head :
this.nodes.Length - (this.head - this.tail);
}
public IDynamicSetNode<T> Insert(T value)
{
int nextTail = (this.tail + 1) % this.nodes.Length;
if (nextTail == this.head)
{
this.ExpandCapacity();
}
QueueNode<T> node = new QueueNode<T>(value, this);
this.nodes[this.tail] = node;
this.tail = (this.tail + 1) % this.nodes.Length;
return node;
}
public void Delete(IDynamicSetNode<T> node)
{
this.ValidateNodeBelongsToThisSet(node);
QueueNode<T> sNode = node as QueueNode<T>;
if (sNode == this.nodes[this.head])
{
sNode.RemoveFromList();
this.head = (this.head + 1) % this.nodes.Length;
}
else
{
throw new InvalidOperationException("can only delete first node in the queue");
}
}
public IDynamicSetNode<T> Search(T value)
{
return this.FirstOrDefault(nodes => nodes.Value.Equals(value));
}
public IDynamicSetNode<T> Minimum()
{
return this.MinBy(i => i.Value).FirstOrDefault();
}
public IDynamicSetNode<T> Maximum()
{
return this.MaxBy(i => i.Value).FirstOrDefault();
}
private void ValidateNodeBelongsToThisSet(IDynamicSetNode<T> node)
{
QueueNode<T> sNode = node as QueueNode<T>;
EnsureArg.IsNotNull(sNode, nameof(node));
EnsureArg.IsTrue(sNode.Set == this, nameof(node), opts => opts.WithMessage("node does not belong to this queue"));
}
private void ExpandCapacity()
{
QueueNode<T>[] newArray = new QueueNode<T>[this.nodes.Length * 2];
this.nodes.CopyTo(newArray, 0);
this.nodes = newArray;
}
}
}