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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 91477 - (hide annotations)
Sun Jan 14 09:47:13 2007 UTC (13 years, 1 month ago) by ericb
File size: 15649 byte(s)
Synchronized with ISE 6.0.65740
1 manus_eiffel 91424 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 manus_eiffel 91434 library: "Free implementation of ELKS library"
9 ericb 91450 copyright: "Copyright (c) 1986-2005, Eiffel Software and others"
10 manus_eiffel 91434 license: "Eiffel Forum License v2 (see forum.txt)"
11 manus_eiffel 91424 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 ericb 91450 rename
23     item as item alias "[]"
24 manus_eiffel 91424 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 ericb 91450 make_from_array,
38     make_from_cil
39 manus_eiffel 91424
40 ericb 91450 convert
41     to_cil: {NATIVE_ARRAY [G]},
42 ericb 91475 to_special: {SPECIAL [G]},
43 ericb 91450 make_from_cil ({NATIVE_ARRAY [G]})
44    
45 manus_eiffel 91424 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 ericb 91477 make_from_cil (na: NATIVE_ARRAY [like item]) is
80 ericb 91450 -- 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 manus_eiffel 91424 feature -- Access
91    
92 ericb 91450 item alias "[]", infix "@" (i: INTEGER): G assign put is
93 manus_eiffel 91424 -- 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 ericb 91450 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 manus_eiffel 91424 end
167 ericb 91450 i := i + 1
168 manus_eiffel 91424 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 ericb 91450 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 manus_eiffel 91424 if object_comparison then
206 ericb 91450 from
207 manus_eiffel 91424 Result := True
208     i := lower
209 ericb 91450 until
210 ericb 91475 not Result or i > upper
211 manus_eiffel 91424 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 ericb 91475 definition: Result = (count = 0 or else
229     ((item (upper) = Void or else
230     item (upper) = item (upper).default) and
231 manus_eiffel 91424 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 ericb 91475 and subarray (lower, upper - 1).same_items
252 manus_eiffel 91424 (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 ericb 91477 subcopy (other: ARRAY [like item]; start_pos, end_pos, index_pos: INTEGER) is
320 manus_eiffel 91424 -- 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 ericb 91450 area.copy_data (other.area, start_pos - other.lower, index_pos - lower, end_pos - start_pos + 1)
331 manus_eiffel 91424 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 ericb 91477 -- Apply `action' to every item.
340 manus_eiffel 91424 -- Semantics not guaranteed if `action' changes the structure;
341 ericb 91475 -- in such a case, apply iterator to clone of structure instead.
342 manus_eiffel 91424 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 ericb 91477 -- Apply `action' to every item that satisfies `test'.
365 manus_eiffel 91424 -- Semantics not guaranteed if `action' or `test' changes the structure;
366 ericb 91475 -- in such a case, apply iterator to clone of structure instead.
367 manus_eiffel 91424 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 ericb 91477 -- Is `test' true for all items?
416 manus_eiffel 91424 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 ericb 91450 offset: INTEGER
486     v: G
487 manus_eiffel 91424 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 ericb 91450 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 manus_eiffel 91424 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 ericb 91450 require
540     not_is_dotnet: not {PLATFORM}.is_dotnet
541 manus_eiffel 91424 do
542     Result := area
543     end
544 ericb 91475
545 ericb 91450 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 manus_eiffel 91424
556 ericb 91475 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 manus_eiffel 91424 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 ericb 91450 set_area (other.area.twin)
591 manus_eiffel 91424 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 ericb 91477 valid_end_pos: end_pos <= upper
602 manus_eiffel 91424 valid_bounds: (start_pos <= end_pos) or (start_pos = end_pos + 1)
603     do
604     create Result.make (start_pos, end_pos)
605 ericb 91477 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 manus_eiffel 91424 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 ericb 91450 offset: INTEGER
644     v: G
645 manus_eiffel 91424 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 ericb 91450 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 manus_eiffel 91424 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 ericb 91475 -- index_set_has_same_bounds: ((index_set.lower = lower) and
692 manus_eiffel 91424 -- (index_set.upper = lower + count - 1))
693    
694 manus_eiffel 91438 end

Properties

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

  ViewVC Help
Powered by ViewVC 1.1.23