/[eiffelstudio]/FreeELKS/trunk/library/structures/dispenser/arrayed_queue.e
ViewVC logotype

Contents of /FreeELKS/trunk/library/structures/dispenser/arrayed_queue.e

Parent Directory Parent Directory | Revision Log Revision Log


Revision 91424 - (show annotations)
Tue Oct 26 18:39:32 2004 UTC (15 years, 2 months ago) by manus_eiffel
File size: 5534 byte(s)
Initial revision

1 indexing
2
3 description:
4 "Unbounded queues, implemented by resizable arrays"
5
6 status: "See notice at end of class"
7 names: dispenser, array;
8 representation: array;
9 access: fixed, fifo, membership;
10 size: fixed;
11 contents: generic;
12 date: "$Date$"
13 revision: "$Revision$"
14
15 class ARRAYED_QUEUE [G] inherit
16
17 QUEUE [G]
18 undefine
19 copy, is_equal, prune_all
20 redefine
21 linear_representation, has, is_empty
22 select
23 count, is_empty, put
24 end
25
26 ARRAY [G]
27 rename
28 count as array_count,
29 force as force_i_th,
30 item as i_th,
31 make as array_make,
32 put as put_i_th,
33 grow as array_grow,
34 is_empty as array_empty
35 export
36 {ANY} valid_index
37 {ARRAYED_QUEUE} lower, upper, i_th, area, subarray
38 {NONE} all
39 redefine
40 wipe_out, extend, prunable,
41 linear_representation,
42 has, full, extendible,
43 valid_index_set,
44 index_set
45 end
46
47 create
48
49 make
50
51 feature -- Initialization
52
53 make (n: INTEGER) is
54 -- Create queue for at most `n' items.
55 require
56 non_negative_argument: n >= 0
57 do
58 array_make (1, n)
59 in_index := 1
60 out_index := 1
61 -- One entry is kept free
62 ensure
63 capacity_expected: capacity = n
64 end
65
66 feature -- Access
67
68 item: G is
69 -- Oldest item.
70 do
71 Result := i_th (out_index)
72 end
73
74 has (v: like item): BOOLEAN is
75 -- Does queue include `v'?
76 -- (Reference or object equality,
77 -- based on `object_comparison'.)
78 local
79 i: INTEGER
80 do
81 if object_comparison then
82 if v /= Void then
83 from
84 i := out_index
85 until
86 i = in_index or (i_th (i) /= Void and then v.is_equal (i_th (i)))
87 loop
88 i := i + 1
89 if i > capacity then
90 i := 1
91 end
92 end
93 end
94 else
95 from
96 i := out_index
97 until
98 i = in_index or v = i_th (i)
99 loop
100 i := i + 1
101 if i > capacity then
102 i := 1
103 end
104 end
105 end
106 Result := (i /= in_index)
107 end
108
109 feature -- Measurement
110
111 count: INTEGER is
112 -- Number of items.
113 do
114 if capacity > 0 then
115 Result := (in_index - out_index + capacity) \\ capacity
116 end
117 end
118
119 index_set: INTEGER_INTERVAL is
120 -- Range of acceptable indexes
121 do
122 create Result.make (1, count)
123 ensure then
124 count_definition: Result.count = count
125 end
126
127 feature -- Status report
128
129 is_empty, off: BOOLEAN is
130 -- Is the structure empty?
131 do
132 Result := (in_index = out_index)
133 end
134
135 full: BOOLEAN is
136 -- Is structure filled to capacity?
137 -- (Answer: no.)
138 do
139 Result := False
140 end
141
142 extendible: BOOLEAN is
143 -- May items be added? (Answer: yes.)
144 do
145 Result := True
146 end
147
148 prunable: BOOLEAN is
149 -- May items be removed? (Answer: yes.)
150 do
151 Result := True
152 end
153
154 feature -- Element change
155
156 extend, put, force (v: G) is
157 -- Add `v' as newest item.
158 do
159 if count + 1 >= array_count then grow end
160 put_i_th (v, in_index)
161 in_index := (in_index + 1) \\ capacity
162 if in_index = 0 then in_index := capacity end
163 end
164
165 replace (v: like item) is
166 -- Replace oldest item by `v'.
167 do
168 put_i_th (v, out_index)
169 end
170
171 feature -- Removal
172
173 remove is
174 -- Remove oldest item.
175 local
176 default_value: G
177 do
178 put_i_th (default_value, out_index)
179 out_index := (out_index + 1) \\ capacity
180 if out_index = 0 then out_index := capacity end
181 end
182
183 wipe_out is
184 -- Remove all items.
185 do
186 clear_all
187 out_index := 1
188 in_index := 1
189 end
190
191 feature -- Conversion
192
193 linear_representation: ARRAYED_LIST [G] is
194 -- Representation as a linear structure
195 -- (in the original insertion order)
196 local
197 i: INTEGER
198 do
199 create Result.make (count)
200 from
201 i := out_index
202 until
203 i = in_index
204 loop
205 Result.extend (i_th (i))
206 i := i + 1
207 if i > capacity then i := 1 end
208 end
209 i := 1
210 end
211
212 feature {NONE} -- Inapplicable
213
214 start is
215 -- Move cursor to first position.
216 do
217 end
218
219 finish is
220 -- Move cursor to last position.
221 do
222 end
223
224 forth is
225 -- Move cursor to next position.
226 do
227 end
228
229 valid_index_set: BOOLEAN is
230 do
231 Result := True
232 end
233
234 feature {ARRAYED_QUEUE} -- Implementation
235
236 out_index: INTEGER
237 -- Position of oldest item
238
239 in_index: INTEGER
240 -- Position for next insertion
241
242 grow is
243 local
244 i, j: INTEGER
245 default_value: G
246 do
247 i := array_count
248 conservative_resize (1, capacity + additional_space)
249 if out_index > 1 then
250 from
251 j := capacity
252 until
253 i < out_index
254 loop
255 put_i_th (i_th (i), j)
256 put_i_th (default_value, i)
257 i := i - 1
258 j := j - 1
259 end
260 out_index := j + 1
261 end
262 end
263
264 invariant
265
266 not_full: not full
267 extendible: extendible
268 prunable: prunable
269 empty_means_storage_empty: is_empty implies all_default
270
271
272 indexing
273
274 library: "[
275 EiffelBase: Library of reusable components for Eiffel.
276 ]"
277
278 status: "[
279 Copyright 1986-2001 Interactive Software Engineering (ISE).
280 For ISE customers the original versions are an ISE product
281 covered by the ISE Eiffel license and support agreements.
282 ]"
283
284 license: "[
285 EiffelBase may now be used by anyone as FREE SOFTWARE to
286 develop any product, public-domain or commercial, without
287 payment to ISE, under the terms of the ISE Free Eiffel Library
288 License (IFELL) at http://eiffel.com/products/base/license.html.
289 ]"
290
291 source: "[
292 Interactive Software Engineering Inc.
293 ISE Building
294 360 Storke Road, Goleta, CA 93117 USA
295 Telephone 805-685-1006, Fax 805-685-6869
296 Electronic mail <info@eiffel.com>
297 Customer support http://support.eiffel.com
298 ]"
299
300 info: "[
301 For latest info see award-winning pages: http://eiffel.com
302 ]"
303
304 end -- class ARRAYED_QUEUE
305
306
307

Properties

Name Value
svn:eol-style native
svn:keywords Author Date Id Revision

  ViewVC Help
Powered by ViewVC 1.1.23