Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GaussianProcessTuning/ILNumerics.2.14.4735.573/Algorithms/Sorting/ILQueue.cs @ 10442

Last change on this file since 10442 was 9102, checked in by gkronber, 12 years ago

#1967: ILNumerics source for experimentation

File size: 10.1 KB
Line 
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
40using System;
41using System.Collections.Generic;
42using System.Text;
43using ILNumerics.Algorithms;
44using System.Collections;
45
46namespace 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}
Note: See TracBrowser for help on using the repository browser.