← Back to branch summary

~halega/+junk/sharpdevelop

« back to all changes in this revision

Viewing changes to src/Libraries/AvalonEdit/ICSharpCode.AvalonEdit/Utils/Deque.cs

  • Committer: sk
  • Date: 2011-09-10 05:17:57 UTC
  • Revision ID: halega@halega.com-20110910051757-qfouz1llya9m6boy
4.1.0.7915 Release Candidate 1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/Libraries/AvalonEdit/ICSharpCode.AvalonEdit/Utils/Deque.cs
 
1
// Copyright (c) AlphaSierraPapa for the SharpDevelop Team (for details please see \doc\copyright.txt)
 
2
// This code is distributed under the GNU LGPL (for details please see \doc\license.txt)
 
3
 
 
4
using System;
 
5
using System.Collections.Generic;
 
6
using System.Diagnostics;
 
7
 
 
8
namespace ICSharpCode.AvalonEdit.Utils
 
9
{
 
10
        /// <summary>
 
11
        /// Double-ended queue.
 
12
        /// </summary>
 
13
        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix")]
 
14
        [Serializable]
 
15
        public sealed class Deque<T> : ICollection<T>
 
16
        {
 
17
                T[] arr = Empty<T>.Array;
 
18
                int size, head, tail;
 
19
                
 
20
                /// <inheritdoc/>
 
21
                public int Count {
 
22
                        get { return size; }
 
23
                }
 
24
                
 
25
                /// <inheritdoc/>
 
26
                public void Clear()
 
27
                {
 
28
                        arr = Empty<T>.Array;
 
29
                        size = 0;
 
30
                        head = 0;
 
31
                        tail = 0;
 
32
                }
 
33
                
 
34
                /// <summary>
 
35
                /// Gets/Sets an element inside the deque.
 
36
                /// </summary>
 
37
                public T this[int index] {
 
38
                        get {
 
39
                                ThrowUtil.CheckInRangeInclusive(index, "index", 0, size - 1);
 
40
                                return arr[(head + index) % arr.Length];
 
41
                        }
 
42
                        set {
 
43
                                ThrowUtil.CheckInRangeInclusive(index, "index", 0, size - 1);
 
44
                                arr[(head + index) % arr.Length] = value;
 
45
                        }
 
46
                }
 
47
                
 
48
                /// <summary>
 
49
                /// Adds an element to the end of the deque.
 
50
                /// </summary>
 
51
                [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1702:CompoundWordsShouldBeCasedCorrectly", MessageId = "PushBack")]
 
52
                public void PushBack(T item)
 
53
                {
 
54
                        if (size == arr.Length)
 
55
                                SetCapacity(Math.Max(4, arr.Length * 2));
 
56
                        arr[tail++] = item;
 
57
                        if (tail == arr.Length) tail = 0;
 
58
                        size++;
 
59
                }
 
60
                
 
61
                /// <summary>
 
62
                /// Pops an element from the end of the deque.
 
63
                /// </summary>
 
64
                public T PopBack()
 
65
                {
 
66
                        if (size == 0)
 
67
                                throw new InvalidOperationException();
 
68
                        if (tail == 0)
 
69
                                tail = arr.Length - 1;
 
70
                        else
 
71
                                tail--;
 
72
                        T val = arr[tail];
 
73
                        arr[tail] = default(T); // allow GC to collect the element
 
74
                        size--;
 
75
                        return val;
 
76
                }
 
77
                
 
78
                /// <summary>
 
79
                /// Adds an element to the front of the deque.
 
80
                /// </summary>
 
81
                public void PushFront(T item)
 
82
                {
 
83
                        if (size == arr.Length)
 
84
                                SetCapacity(Math.Max(4, arr.Length * 2));
 
85
                        if (head == 0)
 
86
                                head = arr.Length - 1;
 
87
                        else
 
88
                                head--;
 
89
                        arr[head] = item;
 
90
                        size++;
 
91
                }
 
92
                
 
93
                /// <summary>
 
94
                /// Pops an element from the end of the deque.
 
95
                /// </summary>
 
96
                public T PopFront()
 
97
                {
 
98
                        if (size == 0)
 
99
                                throw new InvalidOperationException();
 
100
                        T val = arr[head];
 
101
                        arr[head] = default(T); // allow GC to collect the element
 
102
                        head++;
 
103
                        if (head == arr.Length) head = 0;
 
104
                        size--;
 
105
                        return val;
 
106
                }
 
107
                
 
108
                void SetCapacity(int capacity)
 
109
                {
 
110
                        T[] newArr = new T[capacity];
 
111
                        CopyTo(newArr, 0);
 
112
                        head = 0;
 
113
                        tail = (size == capacity) ? 0 : size;
 
114
                        arr = newArr;
 
115
                }
 
116
                
 
117
                /// <inheritdoc/>
 
118
                public IEnumerator<T> GetEnumerator()
 
119
                {
 
120
                        if (head < tail) {
 
121
                                for (int i = head; i < tail; i++)
 
122
                                        yield return arr[i];
 
123
                        } else {
 
124
                                for (int i = head; i < arr.Length; i++)
 
125
                                        yield return arr[i];
 
126
                                for (int i = 0; i < tail; i++)
 
127
                                        yield return arr[i];
 
128
                        }
 
129
                }
 
130
                
 
131
                System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
 
132
                {
 
133
                        return this.GetEnumerator();
 
134
                }
 
135
                
 
136
                bool ICollection<T>.IsReadOnly {
 
137
                        get { return false; }
 
138
                }
 
139
                
 
140
                void ICollection<T>.Add(T item)
 
141
                {
 
142
                        PushBack(item);
 
143
                }
 
144
                
 
145
                /// <inheritdoc/>
 
146
                public bool Contains(T item)
 
147
                {
 
148
                        EqualityComparer<T> comparer = EqualityComparer<T>.Default;
 
149
                        foreach (T element in this)
 
150
                                if (comparer.Equals(item, element))
 
151
                                        return true;
 
152
                        return false;
 
153
                }
 
154
                
 
155
                /// <inheritdoc/>
 
156
                public void CopyTo(T[] array, int arrayIndex)
 
157
                {
 
158
                        if (array == null)
 
159
                                throw new ArgumentNullException("array");
 
160
                        if (head < tail) {
 
161
                                Array.Copy(arr, head, array, arrayIndex, tail - head);
 
162
                        } else {
 
163
                                int num1 = arr.Length - head;
 
164
                                Array.Copy(arr, head, array, arrayIndex, num1);
 
165
                                Array.Copy(arr, 0, array, arrayIndex + num1, tail);
 
166
                        }
 
167
                }
 
168
                
 
169
                bool ICollection<T>.Remove(T item)
 
170
                {
 
171
                        throw new NotSupportedException();
 
172
                }
 
173
        }
 
174
}