/[eiffelstudio]/FreeELKS/tags/EiffelSoftware/Eiffel_66/library/structures/dispenser/heap_priority_queue.e
ViewVC logotype

Contents of /FreeELKS/tags/EiffelSoftware/Eiffel_66/library/structures/dispenser/heap_priority_queue.e

Parent Directory Parent Directory | Revision Log Revision Log


Revision 91894 - (show annotations)
Mon Jun 28 17:16:55 2010 UTC (9 years, 5 months ago) by manus_eiffel
File size: 6693 byte(s)
Simplified postcondition of `safe_less_than' to better reflect the contract of `<' as specified in COMPARABLE. It also let you redefine `safe_less_than' to mean something else than `<' in a descendant.

1 note
2 description: "Priority queues implemented as heaps"
3 legal: "See notice at end of class."
4 status: "See notice at end of class."
5 names: sorted_priority_queue, dispenser, heap;
6 representation: heap;
7 access: fixed, membership;
8 contents: generic;
9 date: "$Date$"
10 revision: "$Revision$"
11
12 class HEAP_PRIORITY_QUEUE [G -> COMPARABLE] inherit
13
14 PRIORITY_QUEUE [G]
15 undefine
16 is_equal, copy, is_empty
17 redefine
18 linear_representation
19 select
20 count
21 end
22
23 ARRAY [G]
24 rename
25 make as array_make,
26 item as i_th,
27 put as put_i_th,
28 bag_put as put,
29 force as array_force,
30 count as array_count
31 export
32 {NONE}
33 all
34 {HEAP_PRIORITY_QUEUE}
35 put_i_th, area, i_th, valid_index, upper, lower, subarray
36 redefine
37 full, prunable, prune, trim,
38 put, extendible, wipe_out,
39 linear_representation,
40 index_set, is_equal, extend
41 end
42
43 create
44 make
45
46 feature -- Initialization
47
48 make (n: INTEGER)
49 -- Allocate heap space.
50 do
51 array_make (1, n)
52 end
53
54 feature -- Access
55
56 item: G
57 -- Entry at top of heap.
58 do
59 Result := i_th (1)
60 end
61
62 feature -- Measurement
63
64 count: INTEGER
65 -- Number of items
66
67 index_set: INTEGER_INTERVAL
68 -- Range of acceptable indexes
69 do
70 create Result.make (1, count)
71 ensure then
72 count_definition: Result.count = count
73 end
74
75 feature -- Status report
76
77 extendible: BOOLEAN
78 -- May items be added?
79 do
80 Result := not full
81 end
82
83 full: BOOLEAN
84 -- Is structure filled to capacity?
85 do
86 Result := (count = capacity)
87 end
88
89 prunable: BOOLEAN = True
90 -- May items be removed? (Answer: yes.)
91
92 feature -- Comparison
93
94 is_equal (other: like Current): BOOLEAN
95 -- Is `other' attached to an object considered
96 -- equal to current object?
97 local
98 l_current, l_other: like Current
99 do
100 if other = Current then
101 Result := True
102 elseif
103 object_comparison = other.object_comparison and then
104 count = other.count
105 then
106 l_current := duplicate (count)
107 l_other := other.duplicate (count)
108 from
109 Result := True
110 until
111 not Result or l_current.is_empty
112 loop
113 if object_comparison then
114 Result := l_current.item ~ l_other.item
115 else
116 Result := l_current.item = l_other.item
117 end
118 l_current.remove
119 l_other.remove
120 end
121 end
122 end
123
124 feature -- Element change
125
126 force (v: like item)
127 -- Add item `v' at its proper position.
128 do
129 if full then
130 auto_resize (1, count + additional_space)
131 end
132 put (v)
133 end
134
135 put (v: like item)
136 -- Insert item `v' at its proper position.
137 local
138 i: INTEGER
139 do
140 count := count + 1
141 from
142 i := count
143 until
144 i <= 1 or else not safe_less_than (i_th (i // 2), v)
145 loop
146 put_i_th (i_th (i // 2), i)
147 i := i // 2
148 end
149 put_i_th (v, i)
150 end
151
152 extend (v: like item)
153 -- <Precursor>
154 do
155 put (v)
156 end
157
158 feature -- Removal
159
160 remove
161 -- Remove item of highest value.
162 local
163 i, j: INTEGER
164 up: like item
165 stop: BOOLEAN
166 do
167 count := count - 1
168 if count > 0 then
169 from
170 i := 1
171 up := i_th (count + 1)
172 until
173 stop or i > count // 2
174 loop
175 j := 2 * i
176 if (j < count) and safe_less_than (i_th (j), i_th (j + 1)) then
177 j := j + 1
178 end
179 stop := not safe_less_than (up, i_th (j))
180 if not stop then
181 put_i_th (i_th (j), i)
182 i := j
183 end
184 end
185 put_i_th (up, i)
186 end
187 area.put_default (count)
188 end
189
190 prune (v: G)
191 -- Remove first occurrence of `v' if any.
192 local
193 i, nb: INTEGER
194 l_tmp: ARRAYED_LIST [G]
195 l_item: G
196 l_done: BOOLEAN
197 do
198 --| Create an ARRAYED_LIST with all items of Current except first
199 --| occurrence of `v'. Then recreate current with items from ARRAYED_LIST
200 --| if `v' was found.
201 create l_tmp.make (count)
202 if object_comparison then
203 from
204 i := 1
205 nb := count
206 until
207 i > nb
208 loop
209 l_item := i_th (i)
210 if not l_done and l_item ~ v then
211 l_done := True
212 else
213 l_tmp.extend (l_item)
214 end
215 i := i + 1
216 end
217 else
218 from
219 i := 1
220 nb := count
221 until
222 i > nb
223 loop
224 l_item := i_th (i)
225 if not l_done and l_item = v then
226 l_done := True
227 else
228 l_tmp.extend (l_item)
229 end
230 i := i + 1
231 end
232 end
233
234 if l_tmp.count = count - 1 then
235 --| Item was found, we can update `Current'.
236 from
237 l_tmp.start
238 wipe_out
239 until
240 l_tmp.after
241 loop
242 put (l_tmp.item)
243 l_tmp.forth
244 end
245 end
246 end
247
248 wipe_out
249 -- Remove all items.
250 do
251 count := 0
252 discard_items
253 end
254
255 feature -- Resizing
256
257 trim
258 -- <Precursor>
259 do
260 Precursor
261 upper := lower + count - 1
262 end
263
264 feature -- Conversion
265
266 linear_representation: ARRAYED_LIST [G]
267 -- Representation as a linear structure
268 -- (Sorted according to decreasing priority)
269 local
270 l_current: like Current
271 do
272 from
273 l_current := twin
274 create Result.make (count)
275 until
276 l_current.is_empty
277 loop
278 Result.extend (l_current.item)
279 l_current.remove
280 end
281 end
282
283 feature -- Duplication
284
285 duplicate (n: INTEGER): like Current
286 -- New priority queue containing `n' greatest items of Current.
287 require
288 n_positive: n >= 0
289 n_in_bounds: n <= count
290 local
291 l_current: like Current
292 l_tmp: ARRAYED_LIST [G]
293 i: INTEGER
294 do
295 --| Extract `n' greatest items of Current.
296 from
297 l_current := twin
298 create l_tmp.make (n)
299 i := 1
300 until
301 i > n
302 loop
303 l_tmp.extend (l_current.item)
304 l_current.remove
305 i := i + 1
306 end
307
308 --| Insert `n' greatest items into new queue.
309 from
310 create Result.make (n)
311 l_tmp.start
312 until
313 l_tmp.after
314 loop
315 Result.put (l_tmp.item)
316 l_tmp.forth
317 end
318 end
319
320 feature {NONE} -- Inapplicable
321
322 replace (v: like item)
323 do
324 end
325
326 feature {NONE} -- Comparison
327
328 safe_less_than (a, b: G): BOOLEAN
329 -- Same as `a < b' when `a' and `b' are not Void.
330 -- If `a' is Void and `b' is not, then True
331 -- Otherwise False
332 do
333 if a /= Void and b /= Void then
334 Result := a < b
335 elseif a = Void and b /= Void then
336 Result := True
337 else
338 Result := False
339 end
340 ensure
341 asymmetric: Result implies not safe_less_than (b, a)
342 end
343
344 invariant
345
346 empty_means_storage_empty: is_empty implies all_default
347
348 note
349 library: "EiffelBase: Library of reusable components for Eiffel."
350 copyright: "Copyright (c) 1984-2010, Eiffel Software and others"
351 license: "Eiffel Forum License v2 (see http://www.eiffel.com/licensing/forum.txt)"
352 source: "[
353 Eiffel Software
354 356 Storke Road, Goleta, CA 93117 USA
355 Telephone 805-685-1006, Fax 805-685-6869
356 Website http://www.eiffel.com
357 Customer support http://support.eiffel.com
358 ]"
359
360 end -- class HEAP_PRIORITY_QUEUE

Properties

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

  ViewVC Help
Powered by ViewVC 1.1.23