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

Properties

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

  ViewVC Help
Powered by ViewVC 1.1.23