Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.ExtLibs/HeuristicLab.AvalonEdit/5.0.1/AvalonEdit-5.0.1/Utils/Deque.cs @ 17021

Last change on this file since 17021 was 11700, checked in by jkarder, 10 years ago

#2077: created branch and added first version

File size: 4.8 KB
Line 
1// Copyright (c) 2014 AlphaSierraPapa for the SharpDevelop Team
2//
3// Permission is hereby granted, free of charge, to any person obtaining a copy of this
4// software and associated documentation files (the "Software"), to deal in the Software
5// without restriction, including without limitation the rights to use, copy, modify, merge,
6// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons
7// to whom the Software is furnished to do so, subject to the following conditions:
8//
9// The above copyright notice and this permission notice shall be included in all copies or
10// substantial portions of the Software.
11//
12// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
13// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
14// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
15// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
16// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
17// DEALINGS IN THE SOFTWARE.
18
19using System;
20using System.Collections.Generic;
21using System.Diagnostics;
22
23namespace ICSharpCode.AvalonEdit.Utils
24{
25  /// <summary>
26  /// Double-ended queue.
27  /// </summary>
28  [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix")]
29  [Serializable]
30  public sealed class Deque<T> : ICollection<T>
31  {
32    T[] arr = Empty<T>.Array;
33    int size, head, tail;
34   
35    /// <inheritdoc/>
36    public int Count {
37      get { return size; }
38    }
39   
40    /// <inheritdoc/>
41    public void Clear()
42    {
43      arr = Empty<T>.Array;
44      size = 0;
45      head = 0;
46      tail = 0;
47    }
48   
49    /// <summary>
50    /// Gets/Sets an element inside the deque.
51    /// </summary>
52    public T this[int index] {
53      get {
54        ThrowUtil.CheckInRangeInclusive(index, "index", 0, size - 1);
55        return arr[(head + index) % arr.Length];
56      }
57      set {
58        ThrowUtil.CheckInRangeInclusive(index, "index", 0, size - 1);
59        arr[(head + index) % arr.Length] = value;
60      }
61    }
62   
63    /// <summary>
64    /// Adds an element to the end of the deque.
65    /// </summary>
66    [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1702:CompoundWordsShouldBeCasedCorrectly", MessageId = "PushBack")]
67    public void PushBack(T item)
68    {
69      if (size == arr.Length)
70        SetCapacity(Math.Max(4, arr.Length * 2));
71      arr[tail++] = item;
72      if (tail == arr.Length) tail = 0;
73      size++;
74    }
75   
76    /// <summary>
77    /// Pops an element from the end of the deque.
78    /// </summary>
79    public T PopBack()
80    {
81      if (size == 0)
82        throw new InvalidOperationException();
83      if (tail == 0)
84        tail = arr.Length - 1;
85      else
86        tail--;
87      T val = arr[tail];
88      arr[tail] = default(T); // allow GC to collect the element
89      size--;
90      return val;
91    }
92   
93    /// <summary>
94    /// Adds an element to the front of the deque.
95    /// </summary>
96    public void PushFront(T item)
97    {
98      if (size == arr.Length)
99        SetCapacity(Math.Max(4, arr.Length * 2));
100      if (head == 0)
101        head = arr.Length - 1;
102      else
103        head--;
104      arr[head] = item;
105      size++;
106    }
107   
108    /// <summary>
109    /// Pops an element from the end of the deque.
110    /// </summary>
111    public T PopFront()
112    {
113      if (size == 0)
114        throw new InvalidOperationException();
115      T val = arr[head];
116      arr[head] = default(T); // allow GC to collect the element
117      head++;
118      if (head == arr.Length) head = 0;
119      size--;
120      return val;
121    }
122   
123    void SetCapacity(int capacity)
124    {
125      T[] newArr = new T[capacity];
126      CopyTo(newArr, 0);
127      head = 0;
128      tail = (size == capacity) ? 0 : size;
129      arr = newArr;
130    }
131   
132    /// <inheritdoc/>
133    public IEnumerator<T> GetEnumerator()
134    {
135      if (head < tail) {
136        for (int i = head; i < tail; i++)
137          yield return arr[i];
138      } else {
139        for (int i = head; i < arr.Length; i++)
140          yield return arr[i];
141        for (int i = 0; i < tail; i++)
142          yield return arr[i];
143      }
144    }
145   
146    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
147    {
148      return this.GetEnumerator();
149    }
150   
151    bool ICollection<T>.IsReadOnly {
152      get { return false; }
153    }
154   
155    void ICollection<T>.Add(T item)
156    {
157      PushBack(item);
158    }
159   
160    /// <inheritdoc/>
161    public bool Contains(T item)
162    {
163      EqualityComparer<T> comparer = EqualityComparer<T>.Default;
164      foreach (T element in this)
165        if (comparer.Equals(item, element))
166          return true;
167      return false;
168    }
169   
170    /// <inheritdoc/>
171    public void CopyTo(T[] array, int arrayIndex)
172    {
173      if (array == null)
174        throw new ArgumentNullException("array");
175      if (head < tail) {
176        Array.Copy(arr, head, array, arrayIndex, tail - head);
177      } else {
178        int num1 = arr.Length - head;
179        Array.Copy(arr, head, array, arrayIndex, num1);
180        Array.Copy(arr, 0, array, arrayIndex + num1, tail);
181      }
182    }
183   
184    bool ICollection<T>.Remove(T item)
185    {
186      throw new NotSupportedException();
187    }
188  }
189}
Note: See TracBrowser for help on using the repository browser.