/[eiffelstudio]/FreeELKS/trunk/library/kernel/array.e
ViewVC logotype

Contents of /FreeELKS/trunk/library/kernel/array.e

Parent Directory Parent Directory | Revision Log Revision Log


Revision 91424 - (show annotations)
Tue Oct 26 18:39:32 2004 UTC (15 years, 3 months ago) by manus_eiffel
File size: 15524 byte(s)
Initial revision

1 indexing
2
3 description: "[
4 Sequences of values, all of the same type or of a conforming one,
5 accessible through integer indices in a contiguous interval.
6 ]"
7
8 status: "See notice at end of class"
9 date: "$Date$"
10 revision: "$Revision$"
11
12 class ARRAY [G] inherit
13
14 RESIZABLE [G]
15 redefine
16 full, copy, is_equal
17 end
18
19 INDEXABLE [G, INTEGER]
20 redefine
21 copy, is_equal
22 end
23
24 TO_SPECIAL [G]
25 export
26 {ARRAY} set_area
27 redefine
28 copy, is_equal, item, put, infix "@", valid_index
29 end
30
31 create
32 make,
33 make_from_array
34
35 feature -- Initialization
36
37 make (min_index, max_index: INTEGER) is
38 -- Allocate array; set index interval to
39 -- `min_index' .. `max_index'; set all values to default.
40 -- (Make array empty if `min_index' = `max_index' + 1).
41 require
42 valid_bounds: min_index <= max_index + 1
43 do
44 lower := min_index
45 upper := max_index
46 if min_index <= max_index then
47 make_area (max_index - min_index + 1)
48 else
49 make_area (0)
50 end
51 ensure
52 lower_set: lower = min_index
53 upper_set: upper = max_index
54 items_set: all_default
55 end
56
57 make_from_array (a: ARRAY [G]) is
58 -- Initialize from the items of `a'.
59 -- (Useful in proper descendants of class `ARRAY',
60 -- to initialize an array-like object from a manifest array.)
61 require
62 array_exists: a /= Void
63 do
64 area := a.area
65 lower := a.lower
66 upper := a.upper
67 end
68
69 feature -- Access
70
71 item, infix "@" (i: INTEGER): G is
72 -- Entry at index `i', if in index interval
73 do
74 Result := area.item (i - lower)
75 end
76
77 entry (i: INTEGER): G is
78 -- Entry at index `i', if in index interval
79 require
80 valid_key: valid_index (i)
81 do
82 Result := item (i)
83 end
84
85 has (v: G): BOOLEAN is
86 -- Does `v' appear in array?
87 -- (Reference or object equality,
88 -- based on `object_comparison'.)
89 local
90 i, nb: INTEGER
91 l_area: like area
92 l_item: G
93 do
94 l_area := area
95 nb := upper - lower
96 if object_comparison and v /= Void then
97 from
98 until
99 i > nb or Result
100 loop
101 l_item := l_area.item (i)
102 Result := l_item /= Void and then l_item.is_equal (v)
103 i := i + 1
104 end
105 else
106 from
107 until
108 i > nb or Result
109 loop
110 Result := l_area.item (i) = v
111 i := i + 1
112 end
113 end
114 end
115
116 feature -- Measurement
117
118 lower: INTEGER
119 -- Minimum index
120
121 upper: INTEGER
122 -- Maximum index
123
124 count, capacity: INTEGER is
125 -- Number of available indices
126 do
127 Result := upper - lower + 1
128 ensure then
129 consistent_with_bounds: Result = upper - lower + 1
130 end
131
132 occurrences (v: G): INTEGER is
133 -- Number of times `v' appears in structure
134 local
135 i: INTEGER
136 do
137 if object_comparison then
138 if v /= Void then
139 from
140 i := lower
141 until
142 i > upper
143 loop
144 if item (i) /= Void and then v.is_equal (item (i)) then
145 Result := Result + 1
146 end
147 i := i + 1
148 end
149 end
150 else
151 from
152 i := lower
153 until
154 i > upper
155 loop
156 if item (i) = v then
157 Result := Result + 1
158 end
159 i := i + 1
160 end
161 end
162 end
163
164 index_set: INTEGER_INTERVAL is
165 -- Range of acceptable indexes
166 do
167 create Result.make (lower, upper)
168 ensure then
169 same_count: Result.count = count
170 same_bounds:
171 ((Result.lower = lower) and (Result.upper = upper))
172 end
173
174 feature -- Comparison
175
176 is_equal (other: like Current): BOOLEAN is
177 -- Is array made of the same items as `other'?
178 local
179 i: INTEGER
180 do
181 if lower = other.lower and then upper = other.upper and then
182 object_comparison = other.object_comparison then
183 if object_comparison then
184 from
185 Result := True
186 i := lower
187 until
188 not Result or i > upper
189 loop
190 Result := equal (item (i), other.item (i))
191 i := i + 1
192 end
193 else
194 Result := area.same_items (other.area, upper - lower)
195 end
196 end
197 end
198
199 feature -- Status report
200
201 all_default: BOOLEAN is
202 -- Are all items set to default values?
203 do
204 Result := area.all_default (upper - lower)
205 ensure
206 definition: Result = (count = 0 or else
207 ((item (upper) = Void or else
208 item (upper) = item (upper).default) and
209 subarray (lower, upper - 1).all_default))
210 end
211
212 full: BOOLEAN is
213 -- Is structure filled to capacity? (Answer: yes)
214 do
215 Result := True
216 end
217
218 same_items (other: like Current): BOOLEAN is
219 -- Do `other' and Current have same items?
220 require
221 other_not_void: other /= Void
222 do
223 if count = other.count then
224 Result := area.same_items (other.area, upper - lower)
225 end
226 ensure
227 definition: Result = ((count = other.count) and then
228 (count = 0 or else (item (upper) = other.item (other.upper)
229 and subarray (lower, upper - 1).same_items
230 (other.subarray (other.lower, other.upper - 1)))))
231 end
232
233 all_cleared: BOOLEAN is
234 -- Are all items set to default values?
235 obsolete
236 "Use `all_default' instead"
237 do
238 Result := all_default
239 end
240
241 valid_index (i: INTEGER): BOOLEAN is
242 -- Is `i' within the bounds of the array?
243 do
244 Result := (lower <= i) and then (i <= upper)
245 end
246
247 extendible: BOOLEAN is
248 -- May items be added?
249 -- (Answer: no, although array may be resized.)
250 do
251 Result := False
252 end
253
254 prunable: BOOLEAN is
255 -- May items be removed? (Answer: no.)
256 do
257 Result := False
258 end
259
260 valid_index_set: BOOLEAN is
261 do
262 Result := index_set.count = count
263 end
264
265 feature -- Element change
266
267 put (v: like item; i: INTEGER) is
268 -- Replace `i'-th entry, if in index interval, by `v'.
269 do
270 area.put (v, i - lower)
271 end
272
273 enter (v: like item; i: INTEGER) is
274 -- Replace `i'-th entry, if in index interval, by `v'.
275 require
276 valid_key: valid_index (i)
277 do
278 area.put (v, i - lower)
279 end
280
281 force (v: like item; i: INTEGER) is
282 -- Assign item `v' to `i'-th entry.
283 -- Always applicable: resize the array if `i' falls out of
284 -- currently defined bounds; preserve existing items.
285 do
286 if i < lower then
287 auto_resize (i, upper)
288 elseif i > upper then
289 auto_resize (lower, i)
290 end
291 put (v, i)
292 ensure
293 inserted: item (i) = v
294 higher_count: count >= old count
295 end
296
297 subcopy (other: ARRAY [G]; start_pos, end_pos, index_pos: INTEGER) is
298 -- Copy items of `other' within bounds `start_pos' and `end_pos'
299 -- to current array starting at index `index_pos'.
300 require
301 other_not_void: other /= Void
302 valid_start_pos: other.valid_index (start_pos)
303 valid_end_pos: other.valid_index (end_pos)
304 valid_bounds: (start_pos <= end_pos) or (start_pos = end_pos + 1)
305 valid_index_pos: valid_index (index_pos)
306 enough_space: (upper - index_pos) >= (end_pos - start_pos)
307 local
308 other_lower: INTEGER
309 do
310 other_lower := other.lower
311 area.subcopy (other.area, start_pos - other_lower, end_pos - other_lower, index_pos - lower)
312 ensure
313 -- copied: forall `i' in 0 .. (`end_pos'-`start_pos'),
314 -- item (index_pos + i) = other.item (start_pos + i)
315 end
316
317 feature -- Iteration
318
319 do_all (action: PROCEDURE [ANY, TUPLE [G]]) is
320 -- Apply `action' to every non-void item.
321 -- Semantics not guaranteed if `action' changes the structure;
322 -- in such a case, apply iterator to clone of structure instead.
323 require
324 action_not_void: action /= Void
325 local
326 t: TUPLE [G]
327 i, nb: INTEGER
328 l_area: like area
329 do
330 from
331 create t
332 i := 0
333 nb := capacity - 1
334 l_area := area
335 until
336 i > nb
337 loop
338 t.put (l_area.item (i), 1)
339 action.call (t)
340 i := i + 1
341 end
342 end
343
344 do_if (action: PROCEDURE [ANY, TUPLE [G]]; test: FUNCTION [ANY, TUPLE [G], BOOLEAN]) is
345 -- Apply `action' to every non-void item that satisfies `test'.
346 -- Semantics not guaranteed if `action' or `test' changes the structure;
347 -- in such a case, apply iterator to clone of structure instead.
348 require
349 action_not_void: action /= Void
350 test_not_void: test /= Void
351 local
352 t: TUPLE [G]
353 i, nb: INTEGER
354 l_area: like area
355 do
356 from
357 create t
358 i := 0
359 nb := capacity - 1
360 l_area := area
361 until
362 i > nb
363 loop
364 t.put (l_area.item (i), 1)
365 if test.item (t) then
366 action.call (t)
367 end
368 i := i + 1
369 end
370 end
371
372 there_exists (test: FUNCTION [ANY, TUPLE [G], BOOLEAN]): BOOLEAN is
373 -- Is `test' true for at least one item?
374 require
375 test_not_void: test /= Void
376 local
377 t: TUPLE [G]
378 i, nb: INTEGER
379 l_area: like area
380 do
381 from
382 create t
383 i := 0
384 nb := capacity - 1
385 l_area := area
386 until
387 i > nb or Result
388 loop
389 t.put (l_area.item (i), 1)
390 Result := test.item (t)
391 i := i + 1
392 end
393 end
394
395 for_all (test: FUNCTION [ANY, TUPLE [G], BOOLEAN]): BOOLEAN is
396 -- Is `test' true for all non-void items?
397 require
398 test_not_void: test /= Void
399 local
400 t: TUPLE [G]
401 i, nb: INTEGER
402 l_area: like area
403 do
404 from
405 create t
406 i := 0
407 nb := capacity - 1
408 l_area := area
409 Result := True
410 until
411 i > nb or not Result
412 loop
413 t.put (l_area.item (i), 1)
414 Result := test.item (t)
415 i := i + 1
416 end
417 end
418
419 feature -- Removal
420
421 wipe_out is
422 -- Make array empty.
423 obsolete
424 "Not applicable since not `prunable'. Use `discard_items' instead."
425 do
426 discard_items
427 end
428
429 discard_items is
430 -- Reset all items to default values with reallocation.
431 do
432 make_area (capacity)
433 ensure
434 default_items: all_default
435 end
436
437 clear_all is
438 -- Reset all items to default values.
439 do
440 area.clear_all
441 ensure
442 stable_lower: lower = old lower
443 stable_upper: upper = old upper
444 default_items: all_default
445 end
446
447 feature -- Resizing
448
449 grow (i: INTEGER) is
450 -- Change the capacity to at least `i'.
451 do
452 if i > capacity then
453 conservative_resize (lower, upper + i - capacity)
454 end
455 end
456
457 conservative_resize (min_index, max_index: INTEGER) is
458 -- Rearrange array so that it can accommodate
459 -- indices down to `min_index' and up to `max_index'.
460 -- Do not lose any previously entered item.
461 require
462 good_indices: min_index <= max_index
463 local
464 old_size, new_size, old_count: INTEGER
465 new_lower, new_upper: INTEGER
466 do
467 if empty_area then
468 new_lower := min_index
469 new_upper := max_index
470 else
471 new_lower := min_index.min (lower)
472 new_upper := max_index.max (upper)
473 end
474 new_size := new_upper - new_lower + 1
475 if not empty_area then
476 old_size := area.count
477 old_count := upper - lower + 1
478 end
479 if empty_area then
480 make_area (new_size)
481 elseif new_size > old_size or new_lower < lower then
482 area := arycpy ($area, new_size,
483 lower - new_lower, old_count)
484 end
485 lower := new_lower
486 upper := new_upper
487 ensure
488 no_low_lost: lower = min_index or else lower = old lower
489 no_high_lost: upper = max_index or else upper = old upper
490 end
491
492 resize (min_index, max_index: INTEGER) is
493 -- Rearrange array so that it can accommodate
494 -- indices down to `min_index' and up to `max_index'.
495 -- Do not lose any previously entered item.
496 obsolete
497 "Use `conservative_resize' instead as future versions will implement `resize' as specified in ELKS."
498 require
499 good_indices: min_index <= max_index
500 do
501 conservative_resize (min_index, max_index)
502 ensure
503 no_low_lost: lower = min_index or else lower = old lower
504 no_high_lost: upper = max_index or else upper = old upper
505 end
506
507 feature -- Conversion
508
509 to_c: ANY is
510 -- Address of actual sequence of values,
511 -- for passing to external (non-Eiffel) routines.
512 do
513 Result := area
514 end
515
516 linear_representation: LINEAR [G] is
517 -- Representation as a linear structure
518 local
519 temp: ARRAYED_LIST [G]
520 i: INTEGER
521 do
522 create temp.make (capacity)
523 from
524 i := lower
525 until
526 i > upper
527 loop
528 temp.extend (item (i))
529 i := i + 1
530 end
531 Result := temp
532 end
533
534 feature -- Duplication
535
536 copy (other: like Current) is
537 -- Reinitialize by copying all the items of `other'.
538 -- (This is also used by `clone'.)
539 do
540 if other /= Current then
541 standard_copy (other)
542 set_area (other.area.standard_twin)
543 end
544 ensure then
545 equal_areas: area.is_equal (other.area)
546 end
547
548 subarray (start_pos, end_pos: INTEGER): ARRAY [G] is
549 -- Array made of items of current array within
550 -- bounds `start_pos' and `end_pos'.
551 require
552 valid_start_pos: valid_index (start_pos)
553 valid_end_pos: valid_index (end_pos)
554 valid_bounds: (start_pos <= end_pos) or (start_pos = end_pos + 1)
555 do
556 create Result.make (start_pos, end_pos)
557 Result.subcopy (Current, start_pos, end_pos, start_pos)
558 ensure
559 lower: Result.lower = start_pos
560 upper: Result.upper = end_pos
561 -- copied: forall `i' in `start_pos' .. `end_pos',
562 -- Result.item (i) = item (i)
563 end
564
565 feature {NONE} -- Inapplicable
566
567 prune (v: G) is
568 -- Remove first occurrence of `v' if any.
569 -- (Precondition is False.)
570 do
571 end
572
573 extend (v: G) is
574 -- Add `v' to structure.
575 -- (Precondition is False.)
576 do
577 end
578
579 feature {ARRAY} -- Implementation
580
581 arycpy (old_area: POINTER; newsize, s, n: INTEGER): like area is
582 -- New area of size `newsize' containing `n' items
583 -- from `oldarea'.
584 -- Old items are at position `s' in new area.
585 external
586 "built_in"
587 end
588
589 feature {NONE} -- Implementation
590
591 auto_resize (min_index, max_index: INTEGER) is
592 -- Rearrange array so that it can accommodate
593 -- indices down to `min_index' and up to `max_index'.
594 -- Do not lose any previously entered item.
595 -- If area must be extended, ensure that space for at least
596 -- additional_space item is added.
597 require
598 valid_indices: min_index <= max_index
599 local
600 old_size, new_size: INTEGER
601 new_lower, new_upper: INTEGER
602 do
603 if empty_area then
604 new_lower := min_index
605 new_upper := max_index
606 else
607 new_lower := min_index.min (lower)
608 new_upper := max_index.max (upper)
609 end
610 new_size := new_upper - new_lower + 1
611 if not empty_area then
612 old_size := area.count
613 if new_size > old_size
614 and new_size - old_size < additional_space
615 then
616 new_size := old_size + additional_space
617 end
618 end
619 if empty_area then
620 make_area (new_size)
621 elseif new_size > old_size or new_lower < lower then
622 area := arycpy ($area, new_size,
623 lower - new_lower, capacity)
624 end
625 lower := new_lower
626 upper := new_upper
627 end
628
629 empty_area: BOOLEAN is
630 -- Is `area' empty?
631 do
632 Result := area = Void or else area.count = 0
633 end
634
635 invariant
636
637 area_exists: area /= Void
638 consistent_size: capacity = upper - lower + 1
639 non_negative_count: count >= 0
640 index_set_has_same_count: valid_index_set
641 -- Internal discussion haven't reached an agreement on this invariant
642 -- index_set_has_same_bounds: ((index_set.lower = lower) and
643 -- (index_set.upper = lower + count - 1))
644
645 indexing
646
647 library: "[
648 EiffelBase: Library of reusable components for Eiffel.
649 ]"
650
651 status: "[
652 Copyright 1986-2001 Interactive Software Engineering (ISE).
653 For ISE customers the original versions are an ISE product
654 covered by the ISE Eiffel license and support agreements.
655 ]"
656
657 license: "[
658 EiffelBase may now be used by anyone as FREE SOFTWARE to
659 develop any product, public-domain or commercial, without
660 payment to ISE, under the terms of the ISE Free Eiffel Library
661 License (IFELL) at http://eiffel.com/products/base/license.html.
662 ]"
663
664 source: "[
665 Interactive Software Engineering Inc.
666 ISE Building
667 360 Storke Road, Goleta, CA 93117 USA
668 Telephone 805-685-1006, Fax 805-685-6869
669 Electronic mail <info@eiffel.com>
670 Customer support http://support.eiffel.com
671 ]"
672
673 info: "[
674 For latest info see award-winning pages: http://eiffel.com
675 ]"
676
677 end -- class ARRAY

Properties

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

  ViewVC Help
Powered by ViewVC 1.1.23