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

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

Parent Directory Parent Directory | Revision Log Revision Log


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

1 indexing
2
3 description:
4 "Queues with a bounded physical size, implemented by 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 BOUNDED_QUEUE [G] inherit
16
17 QUEUE [G]
18 redefine
19 linear_representation, has
20 end
21
22 BOUNDED [G]
23 undefine
24 copy, is_equal
25 end
26
27 create
28
29 make
30
31 feature -- Initialization
32
33 make (n: INTEGER) is
34 -- Create queue for at most `n' items.
35 require
36 non_negative_argument: n >= 0
37 do
38 create fl.make (0, n)
39 -- One entry is kept free (the last one in the list)
40 ensure
41 capacity_expected: capacity = n
42 end
43
44 feature -- Access
45
46 item: G is
47 -- Oldest item.
48 do
49 Result := fl.item (out_index)
50 end
51
52 item_for_iteration: G is
53 -- Element at current iteration position
54 require
55 not_off: not off
56 do
57 Result := fl.item (index)
58 end
59
60 has (v: like item): BOOLEAN is
61 -- Does queue include `v'?
62 -- (Reference or object equality,
63 -- based on `object_comparison'.)
64 local
65 i: INTEGER
66 do
67 if object_comparison then
68 if v /= Void then
69 if out_index > in_index then
70 from
71 i := out_index
72 until
73 Result or i >= fl.count
74 loop
75 Result := fl.item (i) /= Void and then v.is_equal (fl.item (i))
76 i := i + 1
77 end
78 from
79 i := 0
80 until
81 Result or i >= in_index
82 loop
83 Result := fl.item (i) /= Void and then v.is_equal (fl.item (i))
84 i := i + 1
85 end
86 else
87 from
88 i := out_index
89 until
90 Result or i >= in_index
91 loop
92 Result := fl.item (i) /= Void and then v.is_equal (fl.item (i))
93 i := i + 1
94 end
95 end
96 end
97 else
98 if out_index > in_index then
99 from
100 i := out_index
101 until
102 Result or i >= fl.count
103 loop
104 Result := v = fl.item (i)
105 i := i + 1
106 end
107 from
108 i := 0
109 until
110 Result or i >= in_index
111 loop
112 Result := v = fl.item (i)
113 i := i + 1
114 end
115 else
116 from
117 i := out_index
118 until
119 Result or i >= in_index
120 loop
121 Result := v = fl.item (i)
122 i := i + 1
123 end
124 end
125 end
126 end
127
128
129 feature -- Measurement
130
131 capacity: INTEGER is
132 -- Number of items that may be kept.
133 do
134 Result := fl.capacity - 1
135 end
136
137 count: INTEGER is
138 -- Number of items.
139 local
140 size: INTEGER
141 do
142 size := fl.capacity
143 Result := (in_index - out_index + size)\\ size
144 end
145
146 feature -- Status report
147
148 off: BOOLEAN is
149 -- Is there no current item?
150 local
151 size: INTEGER
152 do
153 if index = in_index then
154 Result := True
155 else
156 size := fl.capacity
157 Result := count <= ((index - out_index + size) \\ size)
158 end
159 end
160
161 prunable: BOOLEAN is True
162
163 resizable: BOOLEAN is True
164
165 extendible: BOOLEAN is
166 do
167 Result := not full
168 end
169
170 feature -- Cursor movement
171
172 start is
173 -- Move cursor to first position.
174 do
175 index := out_index
176 end
177
178 finish is
179 -- Move cursor to last position.
180 local
181 size: INTEGER
182 do
183 if is_empty then
184 index := 0
185 else
186 size := fl.capacity
187 index := (in_index - 1 + size) \\ size
188 end
189 end
190
191 forth is
192 -- Move cursor to next position.
193 do
194 index := (index + 1) \\ fl.capacity
195 end
196
197 feature -- Element change
198
199 extend, force, put (v: G) is
200 -- Add `v' as newest element.
201 do
202 fl.put (v, in_index)
203 in_index := (in_index + 1) \\ fl.capacity
204 end
205
206 replace (v: like item) is
207 -- Replace oldest item by `v'.
208 do
209 fl.put (v, out_index)
210 end
211
212 feature -- Removal
213
214 remove is
215 -- Remove oldest item.
216 do
217 out_index := (out_index + 1) \\ fl.capacity
218 end
219
220 prune (v: like item) is
221 do
222 end
223
224 wipe_out is
225 -- Remove all items.
226 do
227 out_index := 0
228 in_index := 0
229 end
230
231 feature -- Conversion
232
233 linear_representation: ARRAYED_LIST [G] is
234 -- Representation as a linear structure
235 -- (in the original insertion order)
236 local
237 i: INTEGER
238 do
239 create Result.make (count)
240 if out_index > in_index then
241 from
242 i := out_index
243 until
244 i >= fl.count
245 loop
246 Result.extend (fl.item (i))
247 i := i + 1
248 end
249 from
250 i := 1
251 until
252 i >= in_index
253 loop
254 Result.extend (fl.item (i))
255 i := i + 1
256 end
257 else
258 from
259 i := out_index
260 until
261 i >= in_index
262 loop
263 Result.extend (fl.item (i))
264 i := i + 1
265 end
266 end
267 end
268
269
270 feature {BOUNDED_QUEUE} -- Implementation
271
272 out_index: INTEGER
273 -- Position of oldest item
274
275 in_index: INTEGER
276 -- Position for next insertion
277
278 index: INTEGER
279 -- Current position
280
281 fl: ARRAY [G]
282 -- Storage
283
284 feature -- Measurement
285
286 occurrences (v: G): INTEGER is
287 do
288 if object_comparison then
289 fl.compare_objects
290 else
291 fl.compare_references
292 end
293 Result := fl.occurrences (v)
294 end
295
296 invariant
297
298 extendible_definition: extendible = not full
299
300 indexing
301
302 library: "[
303 EiffelBase: Library of reusable components for Eiffel.
304 ]"
305
306 status: "[
307 Copyright 1986-2001 Interactive Software Engineering (ISE).
308 For ISE customers the original versions are an ISE product
309 covered by the ISE Eiffel license and support agreements.
310 ]"
311
312 license: "[
313 EiffelBase may now be used by anyone as FREE SOFTWARE to
314 develop any product, public-domain or commercial, without
315 payment to ISE, under the terms of the ISE Free Eiffel Library
316 License (IFELL) at http://eiffel.com/products/base/license.html.
317 ]"
318
319 source: "[
320 Interactive Software Engineering Inc.
321 ISE Building
322 360 Storke Road, Goleta, CA 93117 USA
323 Telephone 805-685-1006, Fax 805-685-6869
324 Electronic mail <info@eiffel.com>
325 Customer support http://support.eiffel.com
326 ]"
327
328 info: "[
329 For latest info see award-winning pages: http://eiffel.com
330 ]"
331
332 end -- class BOUNDED_QUEUE
333
334
335

Properties

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

  ViewVC Help
Powered by ViewVC 1.1.23