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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 91894 - (hide annotations)
Mon Jun 28 17:16:55 2010 UTC (9 years, 7 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 manus_eiffel 91676 note
2 manus_eiffel 91424 description: "Priority queues implemented as heaps"
3 ericb 91477 legal: "See notice at end of class."
4     status: "See notice at end of class."
5 manus_eiffel 91424 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 kwaxer 91870 full, prunable, prune, trim,
38 manus_eiffel 91424 put, extendible, wipe_out,
39     linear_representation,
40 manus_eiffel 91684 index_set, is_equal, extend
41 manus_eiffel 91424 end
42    
43     create
44     make
45    
46     feature -- Initialization
47    
48 manus_eiffel 91676 make (n: INTEGER)
49 manus_eiffel 91424 -- Allocate heap space.
50     do
51     array_make (1, n)
52     end
53    
54     feature -- Access
55    
56 manus_eiffel 91676 item: G
57 manus_eiffel 91424 -- 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 manus_eiffel 91676 index_set: INTEGER_INTERVAL
68 manus_eiffel 91424 -- 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 manus_eiffel 91676 extendible: BOOLEAN
78 manus_eiffel 91424 -- May items be added?
79     do
80     Result := not full
81     end
82    
83 manus_eiffel 91676 full: BOOLEAN
84 manus_eiffel 91424 -- Is structure filled to capacity?
85     do
86     Result := (count = capacity)
87     end
88    
89 manus_eiffel 91676 prunable: BOOLEAN = True
90 manus_eiffel 91424 -- May items be removed? (Answer: yes.)
91    
92     feature -- Comparison
93    
94 manus_eiffel 91676 is_equal (other: like Current): BOOLEAN
95 manus_eiffel 91424 -- 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 manus_eiffel 91671 Result := l_current.item ~ l_other.item
115 manus_eiffel 91424 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 manus_eiffel 91676 force (v: like item)
127 manus_eiffel 91424 -- 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 kwaxer 91644
135 manus_eiffel 91676 put (v: like item)
136 manus_eiffel 91424 -- 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 manus_eiffel 91684 extend (v: like item)
153     -- <Precursor>
154     do
155     put (v)
156     end
157    
158 manus_eiffel 91424 feature -- Removal
159    
160 manus_eiffel 91676 remove
161 manus_eiffel 91424 -- 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 kwaxer 91644 area.put_default (count)
188 manus_eiffel 91424 end
189    
190 manus_eiffel 91676 prune (v: G)
191 manus_eiffel 91424 -- 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 manus_eiffel 91671 if not l_done and l_item ~ v then
211 manus_eiffel 91424 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 kwaxer 91644
234 manus_eiffel 91424 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 manus_eiffel 91676 wipe_out
249 manus_eiffel 91424 -- Remove all items.
250     do
251     count := 0
252     discard_items
253     end
254    
255 kwaxer 91870 feature -- Resizing
256    
257     trim
258     -- <Precursor>
259     do
260     Precursor
261     upper := lower + count - 1
262     end
263    
264 manus_eiffel 91424 feature -- Conversion
265    
266 manus_eiffel 91676 linear_representation: ARRAYED_LIST [G]
267 manus_eiffel 91424 -- 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 manus_eiffel 91676 duplicate (n: INTEGER): like Current
286 manus_eiffel 91424 -- 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 manus_eiffel 91676 replace (v: like item)
323 manus_eiffel 91424 do
324     end
325    
326     feature {NONE} -- Comparison
327    
328 manus_eiffel 91676 safe_less_than (a, b: G): BOOLEAN
329 manus_eiffel 91424 -- 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 manus_eiffel 91894 asymmetric: Result implies not safe_less_than (b, a)
342 manus_eiffel 91424 end
343    
344     invariant
345    
346     empty_means_storage_empty: is_empty implies all_default
347    
348 manus_eiffel 91676 note
349 ericb 91477 library: "EiffelBase: Library of reusable components for Eiffel."
350 kwaxer 91870 copyright: "Copyright (c) 1984-2010, Eiffel Software and others"
351 ericb 91477 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 manus_eiffel 91424
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