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

Contents of /FreeELKS/trunk/library/structures/dispenser/heap_priority_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: 6762 byte(s)
Synchronized with ISE 6.0.65740
1 indexing
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,
38 put, extendible, wipe_out,
39 linear_representation,
40 index_set, is_equal
41 end
42
43 create
44 make
45
46 feature -- Initialization
47
48 make (n: INTEGER) is
49 -- Allocate heap space.
50 do
51 array_make (1, n)
52 end
53
54 feature -- Access
55
56 item: G is
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 is
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 is
78 -- May items be added?
79 do
80 Result := not full
81 end
82
83 full: BOOLEAN is
84 -- Is structure filled to capacity?
85 do
86 Result := (count = capacity)
87 end
88
89 prunable: BOOLEAN is True
90 -- May items be removed? (Answer: yes.)
91
92 feature -- Comparison
93
94 is_equal (other: like Current): BOOLEAN is
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 := equal (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) is
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) is
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 feature -- Removal
153
154 remove is
155 -- Remove item of highest value.
156 local
157 l_default: G
158 i, j: INTEGER
159 up: like item
160 stop: BOOLEAN
161 do
162 count := count - 1
163 if count > 0 then
164 from
165 i := 1
166 up := i_th (count + 1)
167 until
168 stop or i > count // 2
169 loop
170 j := 2 * i
171 if (j < count) and safe_less_than (i_th (j), i_th (j + 1)) then
172 j := j + 1
173 end
174 stop := not safe_less_than (up, i_th (j))
175 if not stop then
176 put_i_th (i_th (j), i)
177 i := j
178 end
179 end
180 put_i_th (up, i)
181 end
182 put_i_th (l_default, count + 1)
183 end
184
185 prune (v: G) is
186 -- Remove first occurrence of `v' if any.
187 local
188 i, nb: INTEGER
189 l_tmp: ARRAYED_LIST [G]
190 l_item: G
191 l_done: BOOLEAN
192 do
193 --| Create an ARRAYED_LIST with all items of Current except first
194 --| occurrence of `v'. Then recreate current with items from ARRAYED_LIST
195 --| if `v' was found.
196 create l_tmp.make (count)
197 if object_comparison then
198 from
199 i := 1
200 nb := count
201 until
202 i > nb
203 loop
204 l_item := i_th (i)
205 if not l_done and equal (l_item, v) then
206 l_done := True
207 else
208 l_tmp.extend (l_item)
209 end
210 i := i + 1
211 end
212 else
213 from
214 i := 1
215 nb := count
216 until
217 i > nb
218 loop
219 l_item := i_th (i)
220 if not l_done and l_item = v then
221 l_done := True
222 else
223 l_tmp.extend (l_item)
224 end
225 i := i + 1
226 end
227 end
228
229 if l_tmp.count = count - 1 then
230 --| Item was found, we can update `Current'.
231 from
232 l_tmp.start
233 wipe_out
234 until
235 l_tmp.after
236 loop
237 put (l_tmp.item)
238 l_tmp.forth
239 end
240 end
241 end
242
243 wipe_out is
244 -- Remove all items.
245 do
246 count := 0
247 discard_items
248 end
249
250 feature -- Conversion
251
252 linear_representation: ARRAYED_LIST [G] is
253 -- Representation as a linear structure
254 -- (Sorted according to decreasing priority)
255 local
256 l_current: like Current
257 do
258 from
259 l_current := twin
260 create Result.make (count)
261 until
262 l_current.is_empty
263 loop
264 Result.extend (l_current.item)
265 l_current.remove
266 end
267 end
268
269 feature -- Duplication
270
271 duplicate (n: INTEGER): like Current is
272 -- New priority queue containing `n' greatest items of Current.
273 require
274 n_positive: n >= 0
275 n_in_bounds: n <= count
276 local
277 l_current: like Current
278 l_tmp: ARRAYED_LIST [G]
279 i: INTEGER
280 do
281 --| Extract `n' greatest items of Current.
282 from
283 l_current := twin
284 create l_tmp.make (n)
285 i := 1
286 until
287 i > n
288 loop
289 l_tmp.extend (l_current.item)
290 l_current.remove
291 i := i + 1
292 end
293
294 --| Insert `n' greatest items into new queue.
295 from
296 create Result.make (n)
297 l_tmp.start
298 until
299 l_tmp.after
300 loop
301 Result.put (l_tmp.item)
302 l_tmp.forth
303 end
304 end
305
306 feature {NONE} -- Inapplicable
307
308 replace (v: like item) is
309 do
310 end
311
312 feature {NONE} -- Comparison
313
314 safe_less_than (a, b: G): BOOLEAN is
315 -- Same as `a < b' when `a' and `b' are not Void.
316 -- If `a' is Void and `b' is not, then True
317 -- Otherwise False
318 do
319 if a /= Void and b /= Void then
320 Result := a < b
321 elseif a = Void and b /= Void then
322 Result := True
323 else
324 Result := False
325 end
326 ensure
327 definition: (a /= Void and b /= Void) implies Result = (a < b)
328 left_void_definition: (a = Void and b /= Void) implies Result
329 right_void_definition: (a /= Void and b = Void) implies not Result
330 end
331
332 invariant
333
334 empty_means_storage_empty: is_empty implies all_default
335
336 indexing
337 library: "EiffelBase: Library of reusable components for Eiffel."
338 copyright: "Copyright (c) 1984-2006, Eiffel Software and others"
339 license: "Eiffel Forum License v2 (see http://www.eiffel.com/licensing/forum.txt)"
340 source: "[
341 Eiffel Software
342 356 Storke Road, Goleta, CA 93117 USA
343 Telephone 805-685-1006, Fax 805-685-6869
344 Website http://www.eiffel.com
345 Customer support http://support.eiffel.com
346 ]"
347
348
349
350
351
352
353
354 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