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

Properties

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

  ViewVC Help
Powered by ViewVC 1.1.23