1 | ///
|
---|
2 | /// This file is part of ILNumerics Community Edition.
|
---|
3 | ///
|
---|
4 | /// ILNumerics Community Edition - high performance computing for applications.
|
---|
5 | /// Copyright (C) 2006 - 2012 Haymo Kutschbach, http://ilnumerics.net
|
---|
6 | ///
|
---|
7 | /// ILNumerics Community Edition is free software: you can redistribute it and/or modify
|
---|
8 | /// it under the terms of the GNU General Public License version 3 as published by
|
---|
9 | /// the Free Software Foundation.
|
---|
10 | ///
|
---|
11 | /// ILNumerics Community Edition is distributed in the hope that it will be useful,
|
---|
12 | /// but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
13 | /// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
14 | /// GNU General Public License for more details.
|
---|
15 | ///
|
---|
16 | /// You should have received a copy of the GNU General Public License
|
---|
17 | /// along with ILNumerics Community Edition. See the file License.txt in the root
|
---|
18 | /// of your distribution package. If not, see <http://www.gnu.org/licenses/>.
|
---|
19 | ///
|
---|
20 | /// In addition this software uses the following components and/or licenses:
|
---|
21 | ///
|
---|
22 | /// =================================================================================
|
---|
23 | /// The Open Toolkit Library License
|
---|
24 | ///
|
---|
25 | /// Copyright (c) 2006 - 2009 the Open Toolkit library.
|
---|
26 | ///
|
---|
27 | /// Permission is hereby granted, free of charge, to any person obtaining a copy
|
---|
28 | /// of this software and associated documentation files (the "Software"), to deal
|
---|
29 | /// in the Software without restriction, including without limitation the rights to
|
---|
30 | /// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
|
---|
31 | /// the Software, and to permit persons to whom the Software is furnished to do
|
---|
32 | /// so, subject to the following conditions:
|
---|
33 | ///
|
---|
34 | /// The above copyright notice and this permission notice shall be included in all
|
---|
35 | /// copies or substantial portions of the Software.
|
---|
36 | ///
|
---|
37 | /// =================================================================================
|
---|
38 | ///
|
---|
39 |
|
---|
40 | using System;
|
---|
41 | using System.Collections.Generic;
|
---|
42 | using System.Text;
|
---|
43 | using ILNumerics.Algorithms;
|
---|
44 | using System.Collections;
|
---|
45 |
|
---|
46 | namespace ILNumerics.Misc {
|
---|
47 | /// <summary>
|
---|
48 | /// List items to be used in ILQueueList
|
---|
49 | /// </summary>
|
---|
50 | /// <typeparam name="T1">Data type</typeparam>
|
---|
51 | /// <typeparam name="T2">Index type</typeparam>
|
---|
52 | /// <remarks>This class is not intended to be used directly. Internally it serves as a helper class for sorting.</remarks>
|
---|
53 | internal class ILListItem<T1,T2> {
|
---|
54 | internal T1 Data;
|
---|
55 | internal T2 m_index;
|
---|
56 | internal ILListItem<T1,T2> Next;
|
---|
57 | /// <summary>
|
---|
58 | /// construct list item by data
|
---|
59 | /// </summary>
|
---|
60 | /// <param name="item">item data</param>
|
---|
61 | /// <remarks>the indet will be set to its default value</remarks>
|
---|
62 | public ILListItem(T1 item) {
|
---|
63 | Data = item;
|
---|
64 | m_index = default(T2);
|
---|
65 | }
|
---|
66 | /// <summary>
|
---|
67 | /// construct list item, takes item data and index
|
---|
68 | /// </summary>
|
---|
69 | /// <param name="item">item data</param>
|
---|
70 | /// <param name="index">index</param>
|
---|
71 | public ILListItem(T1 item, T2 index) {
|
---|
72 | Data = item;
|
---|
73 | m_index = index;
|
---|
74 | }
|
---|
75 | /// <summary>
|
---|
76 | /// index stored with this item
|
---|
77 | /// </summary>
|
---|
78 | public T2 Index {
|
---|
79 | get {
|
---|
80 | return m_index;
|
---|
81 | }
|
---|
82 | set {
|
---|
83 | m_index = value;
|
---|
84 | }
|
---|
85 | }
|
---|
86 | }
|
---|
87 | /// <summary>
|
---|
88 | /// Queuelist - a queue with partial list properties
|
---|
89 | /// </summary>
|
---|
90 | /// <typeparam name="T1">data type</typeparam>
|
---|
91 | /// <typeparam name="T2">index type</typeparam>
|
---|
92 | /// <remarks>This class is not intended to be used directly. Internally it serves as a helper class for sorting.</remarks>
|
---|
93 | internal class ILQueueList<T1,T2> : IEnumerable<T1> {
|
---|
94 | internal ILListItem<T1,T2> Head;
|
---|
95 | internal ILListItem<T1,T2> Tail;
|
---|
96 | internal int m_count = 0;
|
---|
97 | /// <summary>
|
---|
98 | /// number of items currentliy in the queue (readonly)
|
---|
99 | /// </summary>
|
---|
100 | public int Count {
|
---|
101 | get {
|
---|
102 | return m_count;
|
---|
103 | }
|
---|
104 | }
|
---|
105 |
|
---|
106 | /// <summary>
|
---|
107 | /// add indexed item at end of queue
|
---|
108 | /// </summary>
|
---|
109 | public void Enqueue(T1 item, T2 index) {
|
---|
110 | if (Head == null) {
|
---|
111 | Head = new ILListItem<T1,T2>(item, index);
|
---|
112 | Tail = Head;
|
---|
113 | } else {
|
---|
114 | ILListItem<T1,T2> newItem = new ILListItem<T1,T2>(item,index);
|
---|
115 | Tail.Next = newItem;
|
---|
116 | Tail = newItem;
|
---|
117 | }
|
---|
118 | m_count++;
|
---|
119 | }
|
---|
120 |
|
---|
121 | /// <summary>
|
---|
122 | /// add item at end of queue
|
---|
123 | /// </summary>
|
---|
124 | public void Enqueue(T1 item) {
|
---|
125 | if (Head == null) {
|
---|
126 | Head = new ILListItem<T1,T2>(item);
|
---|
127 | Tail = Head;
|
---|
128 | } else {
|
---|
129 | ILListItem<T1,T2> newItem = new ILListItem<T1,T2>(item);
|
---|
130 | Tail.Next = newItem;
|
---|
131 | Tail = newItem;
|
---|
132 | }
|
---|
133 | m_count++;
|
---|
134 | }
|
---|
135 | /// <summary>
|
---|
136 | /// add item at end of queue
|
---|
137 | /// </summary>
|
---|
138 | public void Enqueue(ILListItem<T1,T2> item) {
|
---|
139 | System.Diagnostics.Debug.Assert(item.Next == null);
|
---|
140 | if (Head == null) {
|
---|
141 | Head = item;
|
---|
142 | Tail = item;
|
---|
143 | } else {
|
---|
144 | Tail.Next = item;
|
---|
145 | Tail = item;
|
---|
146 | }
|
---|
147 | m_count++;
|
---|
148 | }
|
---|
149 | /// <summary>
|
---|
150 | /// add queue list to end of this queue list
|
---|
151 | /// </summary>
|
---|
152 | /// <param name="list">queue list to be added</param>
|
---|
153 | public void Enqueue(ILQueueList<T1,T2> list) {
|
---|
154 | if (list == null || list.Count == 0) return;
|
---|
155 | if (Tail != null) {
|
---|
156 | Tail.Next = list.Head;
|
---|
157 | Tail = list.Tail;
|
---|
158 | } else {
|
---|
159 | Head = list.Head;
|
---|
160 | Tail = list.Tail;
|
---|
161 | }
|
---|
162 | m_count += list.m_count;
|
---|
163 | }
|
---|
164 |
|
---|
165 | /// <summary>
|
---|
166 | /// Remove from start of queue
|
---|
167 | /// </summary>
|
---|
168 | /// <returns>item from start of queue</returns>
|
---|
169 | public ILListItem<T1,T2> Dequeue() {
|
---|
170 | switch (m_count) {
|
---|
171 | case 0:
|
---|
172 | return null;
|
---|
173 | case 1:
|
---|
174 | ILListItem<T1,T2> retIt = Head;
|
---|
175 | Head = null;
|
---|
176 | Tail = null;
|
---|
177 | m_count--;
|
---|
178 | System.Diagnostics.Debug.Assert(retIt.Next == null);
|
---|
179 | return retIt;
|
---|
180 | default:
|
---|
181 | retIt = Head;
|
---|
182 | Head = Head.Next;
|
---|
183 | m_count--;
|
---|
184 | retIt.Next = null;
|
---|
185 | return retIt;
|
---|
186 | }
|
---|
187 | }
|
---|
188 |
|
---|
189 | /// <summary>
|
---|
190 | /// Add to start of queue
|
---|
191 | /// </summary>
|
---|
192 | /// <param name="item">item data to add to start of queue</param>
|
---|
193 | public void AddToStart(T1 item) {
|
---|
194 | ILListItem<T1,T2> newLItem = new ILListItem<T1,T2>(item);
|
---|
195 | newLItem.Next = Head;
|
---|
196 | Head = newLItem;
|
---|
197 | m_count++;
|
---|
198 | }
|
---|
199 | /// <summary>
|
---|
200 | /// concatenate 2 queuelists
|
---|
201 | /// </summary>
|
---|
202 | /// <param name="qlist">queue list to be added at start of this queuelist</param>
|
---|
203 | public void AddToStart(ILQueueList<T1,T2> qlist) {
|
---|
204 | m_count += qlist.m_count;
|
---|
205 | qlist.Tail.Next = Head;
|
---|
206 | Head = qlist.Head;
|
---|
207 | }
|
---|
208 | /// <summary>
|
---|
209 | /// sort utilizing bucket sort
|
---|
210 | /// </summary>
|
---|
211 | /// <typeparam name="SubelementType">subelement type</typeparam>
|
---|
212 | /// <param name="mapper">keymapper mapping subelement items to buckets</param>
|
---|
213 | public void Sort<SubelementType>(ILKeyMapper<T1,SubelementType> mapper) {
|
---|
214 | ILQueueList<T1,T2> ret = ILBucketSort.BucketSort<T1,SubelementType,T2>(this,null,mapper,ILBucketSort.SortMethod.ConstantLength);
|
---|
215 | this.Head = ret.Head;
|
---|
216 | this.Tail = ret.Tail;
|
---|
217 | }
|
---|
218 | /// <summary>
|
---|
219 | /// convert (copy) items to system array
|
---|
220 | /// </summary>
|
---|
221 | /// <returns>system array with items</returns>
|
---|
222 | public T1[] ToArray() {
|
---|
223 | T1[] ret = new T1[m_count];
|
---|
224 | ILListItem<T1,T2> curr = Head;
|
---|
225 | for (int i = 0; curr != null; i++) {
|
---|
226 | ret[i] = curr.Data;
|
---|
227 | curr = curr.Next;
|
---|
228 | }
|
---|
229 | return ret;
|
---|
230 | }
|
---|
231 | /// <summary>
|
---|
232 | /// Clear this queue list from all elements
|
---|
233 | /// </summary>
|
---|
234 | public void Clear() {
|
---|
235 | Head = null;
|
---|
236 | Tail = null;
|
---|
237 | m_count = 0;
|
---|
238 | }
|
---|
239 |
|
---|
240 | #region IEnumerable<T> Member
|
---|
241 | /// <summary>
|
---|
242 | /// Create enumerator utilizing 'foreach'
|
---|
243 | /// </summary>
|
---|
244 | /// <returns>enumerator for contained elements</returns>
|
---|
245 | public IEnumerator<T1> GetEnumerator() {
|
---|
246 | ILListItem<T1,T2> curr = Head;
|
---|
247 | while (curr != null) {
|
---|
248 | yield return curr.Data;
|
---|
249 | curr = curr.Next;
|
---|
250 | }
|
---|
251 | }
|
---|
252 | /// <summary>
|
---|
253 | /// Gives enumerator for contained items (ILListItem)
|
---|
254 | /// </summary>
|
---|
255 | public IEnumerable<ILListItem<T1,T2>> ListItems {
|
---|
256 | get {
|
---|
257 | ILListItem<T1,T2> curr = Head;
|
---|
258 | while (curr != null) {
|
---|
259 | yield return curr;
|
---|
260 | curr = curr.Next;
|
---|
261 | }
|
---|
262 | }
|
---|
263 | }
|
---|
264 | #endregion
|
---|
265 |
|
---|
266 | #region IEnumerable Member
|
---|
267 | /// <summary>
|
---|
268 | /// gives enumerator for internal list items (ILListItem)
|
---|
269 | /// </summary>
|
---|
270 | /// <returns>ILListItem's</returns>
|
---|
271 | IEnumerator IEnumerable.GetEnumerator() {
|
---|
272 | ILListItem<T1,T2> curr = Head;
|
---|
273 | while (curr != null) {
|
---|
274 | yield return curr;
|
---|
275 | curr = curr.Next;
|
---|
276 | }
|
---|
277 | }
|
---|
278 |
|
---|
279 | #endregion
|
---|
280 | }
|
---|
281 | }
|
---|