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

Properties

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

  ViewVC Help
Powered by ViewVC 1.1.23