/[eiffelstudio]/trunk/eweasel/tests/incr071/arrayed_list.e
ViewVC logotype

Contents of /trunk/eweasel/tests/incr071/arrayed_list.e

Parent Directory Parent Directory | Revision Log Revision Log


Revision 65297 - (show annotations)
Thu Nov 30 20:22:33 2006 UTC (13 years ago) by manus
File size: 13046 byte(s)
Moved from trunk/Src/eweasel to trunk/eweasel so that a simple checkout of the source code is not penalized by the lenghty process of checking out all the tests of eweasel.
1 indexing
2
3 description:
4 "Lists implemented by resizable arrays"
5
6 status: "See notice at end of class"
7 names: sequence;
8 representation: array;
9 access: index, cursor, membership;
10 size: fixed;
11 contents: generic;
12 date: "$Date$"
13 revision: "$Revision$"
14
15 class ARRAYED_LIST [G] inherit
16
17 ARRAY [G]
18 rename
19 force as force_i_th,
20 item as array_item,
21 infix "@" as array_infix_at,
22 make as array_make,
23 put as put_i_th,
24 count as array_count,
25 index_set as array_index_set,
26 bag_put as put,
27 valid_index as array_valid_index
28 export
29 {NONE}
30 all
31 {ARRAYED_LIST}
32 array_make, subcopy
33 {ANY}
34 array_valid_index, capacity
35 undefine
36 linear_representation, prunable, put, is_equal,
37 prune, occurrences, extendible
38 redefine
39 extend, prune_all, full, wipe_out,
40 is_inserted, make_from_array, has
41 select
42 array_valid_index
43 end
44
45 DYNAMIC_LIST [G]
46 undefine
47 valid_index, put_i_th,
48 force, is_inserted, copy
49 redefine
50 first, last, swap, wipe_out, i_th, infix "@",
51 go_i_th, move, prunable, start, finish,
52 count, prune, remove,
53 put_left, merge_left,
54 merge_right, duplicate, prune_all, has, search,
55 append
56 select
57 count, index_set, i_th, infix "@"
58 end
59
60 create
61 make, make_filled, make_from_array
62
63 feature -- Initialization
64
65 make (n: INTEGER) is
66 -- Allocate list with `n' items.
67 -- (`n' may be zero for empty list.)
68 require
69 valid_number_of_items: n >= 0
70 do
71 index := 0
72 set_count (0)
73 array_make (1, n)
74 ensure
75 correct_position: before
76 is_empty: is_empty
77 end
78
79 make_filled (n: INTEGER) is
80 -- Allocate list with `n' items.
81 -- (`n' may be zero for empty list.)
82 -- This list will be full.
83 require
84 valid_number_of_items: n >= 0
85 do
86 index := 0
87 set_count (n)
88 array_make (1, n)
89 ensure
90 correct_position: before
91 filled: full
92 end
93
94 make_from_array (a: ARRAY [G]) is
95 -- Create list from array `a'.
96 do
97 Precursor (a)
98 lower := 1
99 set_count (a.count)
100 upper := count
101 index := 0
102 ensure then
103 correct_position: before
104 filled: count = a.count
105 end
106
107 feature -- Access
108
109 item: G is
110 -- Current item
111 require else
112 index_is_valid: valid_index (index)
113 do
114 Result := area.item (index - 1)
115 end
116
117 i_th, infix "@" (i: INTEGER): like item is
118 -- Item at `i'-th position
119 do
120 Result := area.item (i - 1)
121 end
122
123 first: like item is
124 -- Item at first position
125 do
126 Result := area.item (0)
127 end
128
129 last: like first is
130 -- Item at last position
131 do
132 Result := area.item (count - 1)
133 end
134
135 index: INTEGER
136 -- Index of `item', if valid.
137
138 cursor: CURSOR is
139 -- Current cursor position
140 do
141 create {ARRAYED_LIST_CURSOR} Result.make (index)
142 end
143
144 has (v: like item): BOOLEAN is
145 -- Does current include `v'?
146 -- (Reference or object equality,
147 -- based on `object_comparison'.)
148 local
149 l_area: like area
150 l_item: G
151 i, nb: INTEGER
152 do
153 l_area := area
154 nb := count - 1
155 if object_comparison and v /= Void then
156 from
157 until
158 i > nb or Result
159 loop
160 l_item := l_area.item (i)
161 Result := l_item /= Void and then v.is_equal (l_item)
162 i := i + 1
163 end
164 else
165 from
166 until
167 i > nb or Result
168 loop
169 Result := v = l_area.item (i)
170 i := i + 1
171 end
172 end
173 end
174
175 feature -- Measurement
176
177 count: INTEGER
178 -- Number of items.
179
180 feature -- Status report
181
182 prunable: BOOLEAN is
183 -- May items be removed? (Answer: yes.)
184 do
185 Result := True
186 end
187
188 full: BOOLEAN is
189 -- Is structure filled to capacity?
190 do
191 Result := (count = capacity)
192 end
193
194 valid_cursor (p: CURSOR): BOOLEAN is
195 -- Can the cursor be moved to position `p'?
196 local
197 al_c: ARRAYED_LIST_CURSOR
198 do
199 al_c ?= p
200 if al_c /= Void then
201 Result := valid_cursor_index (al_c.index)
202 end
203 end
204
205 valid_index (i: INTEGER): BOOLEAN is
206 -- Is `i' a valid index?
207 do
208 Result := (1 <= i) and (i <= count)
209 end
210
211 is_inserted (v: G): BOOLEAN is
212 -- Has `v' been inserted at the end by the most recent `put' or
213 -- `extend'?
214 do
215 check
216 put_constraint: (v /= last) implies not off
217 -- Because, if this routine has not been called by
218 -- `extend', it was called by `put' which replaces the
219 -- current item, which implies the cursor is not `off'.
220 end
221
222 Result := (v = last) or else (v = item)
223 end
224
225 feature -- Cursor movement
226
227 move (i: INTEGER) is
228 -- Move cursor `i' positions.
229 do
230 index := index + i
231 if (index > count + 1) then
232 index := count + 1
233 elseif (index < 0) then
234 index := 0
235 end
236 end
237
238 start is
239 -- Move cursor to first position if any.
240 do
241 index := 1
242 ensure then
243 after_when_empty: is_empty implies after
244 end
245
246 finish is
247 -- Move cursor to last position if any.
248 do
249 index := count
250 --| Temporary patch. Start moves the cursor
251 --| to the first element. If the list is empty
252 --| the cursor is before. The parents (CHAIN, LIST...)
253 --| and decendants (ARRAYED_TREE...) need to be revised.
254 ensure then
255 before_when_empty: is_empty implies before
256 end
257
258 forth is
259 -- Move cursor one position forward.
260 do
261 index := index + 1
262 end
263
264 back is
265 -- Move cursor one position backward.
266 do
267 index := index - 1
268 end
269
270 go_i_th (i: INTEGER) is
271 -- Move cursor to `i'-th position.
272 do
273 index := i
274 end
275
276 go_to (p: CURSOR) is
277 -- Move cursor to position `p'.
278 local
279 al_c: ARRAYED_LIST_CURSOR
280 do
281 al_c ?= p
282 check
283 al_c /= Void
284 end
285 index := al_c.index
286 end
287
288 search (v: like item) is
289 -- Move to first position (at or after current
290 -- position) where `item' and `v' are equal.
291 -- If structure does not include `v' ensure that
292 -- `exhausted' will be true.
293 -- (Reference or object equality,
294 -- based on `object_comparison'.)
295 local
296 l_area: like area
297 l_item: G
298 i, nb: INTEGER
299 l_found: BOOLEAN
300 do
301 l_area := area
302 nb := count - 1
303 -- If we are before we need to be sure
304 -- that i is positive.
305 i := (index - 1).max (0)
306 if object_comparison and v /= Void then
307 from
308 until
309 i > nb or l_found
310 loop
311 l_item := l_area.item (i)
312 l_found := l_item /= Void and then v.is_equal (l_item)
313 i := i + 1
314 end
315 else
316 from
317 until
318 i > nb or l_found
319 loop
320 l_found := v = l_area.item (i)
321 i := i + 1
322 end
323 end
324 -- Set position of `index' to `i', location of item when
325 -- found, otherwise to `i + 1' which corresponds to `after'.
326 if l_found then
327 index := i
328 else
329 index := i + 1
330 end
331 end
332
333 feature -- Element change
334
335 put_front (v: like item) is
336 -- Add `v' to the beginning.
337 -- Do not move cursor.
338 do
339 if is_empty then
340 extend (v)
341 else
342 insert (v, 1)
343 end
344 index := index + 1
345 end
346
347 force, extend (v: like item) is
348 -- Add `v' to end.
349 -- Do not move cursor.
350 do
351 set_count (count + 1)
352 force_i_th (v, count)
353 end
354
355 put_left (v: like item) is
356 -- Add `v' to the left of current position.
357 -- Do not move cursor.
358 do
359 if after or is_empty then
360 extend (v)
361 else
362 insert (v, index)
363 end
364 index := index + 1
365 end
366
367 put_right (v: like item) is
368 -- Add `v' to the right of current position.
369 -- Do not move cursor.
370 do
371 if index = count then
372 extend (v)
373 else
374 insert (v, index + 1)
375 end
376 end
377
378 replace (v: like first) is
379 -- Replace current item by `v'.
380 do
381 put_i_th (v, index)
382 end
383
384 merge_left (other: ARRAYED_LIST [G]) is
385 -- Merge `other' into current structure before cursor.
386 local
387 old_index: INTEGER
388 old_other_count: INTEGER
389 do
390 old_index := index
391 old_other_count := other.count
392 index := index - 1
393 merge_right (other)
394 index := old_index + old_other_count
395 end
396
397 merge_right (other: ARRAYED_LIST [G]) is
398 -- Merge `other' into current structure after cursor.
399 do
400 if not other.is_empty then
401 conservative_resize (1, count + other.count)
402 if index < count then
403 subcopy (Current, index + 1, count,
404 index + other.count + 1)
405 end
406 subcopy (other, 1, other.count, index + 1)
407 set_count (count + other.count)
408 other.wipe_out
409 end
410 end
411
412 append (s: SEQUENCE [G]) is
413 -- Append a copy of `s'.
414 local
415 al: ARRAYED_LIST [G]
416 c, new_count: INTEGER
417 do
418 al ?= s
419 if al /= Void then -- Optimization for arrayed lists
420 c := al.count
421 -- If `s' is empty nothing to be done.
422 if c > 0 then
423 new_count := count + c
424 conservative_resize (1, new_count)
425 subcopy (al, 1, c, count + 1)
426 set_count (new_count)
427 end
428 else
429 Precursor {DYNAMIC_LIST} (s)
430 end
431 end
432
433 feature -- Removal
434
435 prune (v: like item) is
436 -- Remove first occurrence of `v', if any,
437 -- after cursor position.
438 -- Move cursor to right neighbor.
439 -- (or `after' if no right neighbor or `v' does not occur)
440 do
441 if before then index := 1 end
442 if object_comparison then
443 if v /= Void then
444 from
445 until
446 after or else (item /= Void and then v.is_equal (item))
447 loop
448 forth
449 end
450 end
451 else
452 from
453 until
454 after or else item = v
455 loop
456 forth
457 end
458 end
459 if not after then remove end
460 end
461
462 remove is
463 -- Remove current item.
464 -- Move cursor to right neighbor
465 -- (or `after' if no right neighbor)
466 local
467 default_value: G
468 do
469 if index < count then
470 subcopy (Current, index + 1, count, index)
471 end
472 set_count (count - 1)
473 area.put (default_value, count)
474 ensure then
475 index: index = old index
476 end
477
478 prune_all (v: like item) is
479 -- Remove all occurrences of `v'.
480 -- (Reference or object equality,
481 -- based on `object_comparison'.)
482 local
483 i: INTEGER
484 offset: INTEGER
485 res: BOOLEAN
486 obj_cmp: BOOLEAN
487 default_val: like item
488 do
489 obj_cmp := object_comparison
490 from
491 i := 1
492 until
493 i > count
494 loop
495 if i <= count - offset then
496 if offset > 0 then
497 put_i_th (i_th (i + offset), i)
498 end
499 if obj_cmp then
500 res := equal (v, i_th (i))
501 else
502 res := (v = i_th (i))
503 end
504 if res then
505 offset := offset + 1
506 else
507 i := i + 1
508 end
509 else
510 put_i_th (default_val, i)
511 i := i + 1
512 end
513 end
514 set_count (count - offset)
515 index := count + 1
516 ensure then
517 is_after: after
518 end
519
520 remove_left is
521 -- Remove item to the left of cursor position.
522 -- Do not move cursor.
523 do
524 index := index - 1
525 remove
526 end
527
528 remove_right is
529 -- Remove item to the right of cursor position
530 -- Do not move cursor
531 do
532 index := index + 1
533 remove
534 index := index - 1
535 end
536
537 wipe_out is
538 -- Remove all items.
539 do
540 set_count (0)
541 index := 0
542 discard_items
543 end
544
545 feature -- Transformation
546
547 swap (i: INTEGER) is
548 -- Exchange item at `i'-th position with item
549 -- at cursor position.
550 local
551 old_item: like item
552 do
553 old_item := item
554 replace (area.item (i - 1))
555 area.put (old_item, i - 1)
556 end
557
558 feature -- Duplication
559
560 duplicate (n: INTEGER): like Current is
561 -- Copy of sub-list beginning at current position
562 -- and having min (`n', `count' - `index' + 1) items.
563 local
564 end_pos: INTEGER
565 do
566 if after then
567 create Result.make (0)
568 else
569 end_pos := count.min (index + n - 1)
570 create Result.make_filled (end_pos - index + 1)
571 Result.subcopy (Current, index, end_pos, 1)
572 end
573 end
574
575 feature {NONE} -- Inapplicable
576
577 new_chain: like Current is
578 -- Unused
579 do
580 end
581
582 feature {NONE} -- Implementation
583
584 insert (v: like item; pos: INTEGER) is
585 -- Add `v' at `pos', moving subsequent items
586 -- to the right.
587 require
588 index_small_enough: pos <= count
589 index_large_enough: pos >= 1
590 do
591 if count + 1 > capacity then
592 auto_resize (lower, count + 1)
593 end
594 set_count (count + 1)
595 subcopy (Current, pos , count - 1 , pos + 1)
596 enter (v, pos)
597 ensure
598 new_count: count = old count + 1
599 index_unchanged: index = old index
600 insertion_done: i_th (pos) = v
601 end
602
603 set_count (new_count: INTEGER) is
604 -- Set `count' to `new_count'
605 do
606 count := new_count
607 end
608
609 invariant
610
611 prunable: prunable
612 starts_from_one: lower = 1
613 empty_means_storage_empty: is_empty implies all_default
614
615 indexing
616
617 library: "[
618 EiffelBase: Library of reusable components for Eiffel.
619 ]"
620
621 status: "[
622 --| Copyright (c) 1993-2006 University of Southern California and contributors.
623 For ISE customers the original versions are an ISE product
624 covered by the ISE Eiffel license and support agreements.
625 ]"
626
627 license: "[
628 EiffelBase may now be used by anyone as FREE SOFTWARE to
629 develop any product, public-domain or commercial, without
630 payment to ISE, under the terms of the ISE Free Eiffel Library
631 License (IFELL) at http://eiffel.com/products/base/license.html.
632 ]"
633
634 source: "[
635 Interactive Software Engineering Inc.
636 ISE Building
637 360 Storke Road, Goleta, CA 93117 USA
638 Telephone 805-685-1006, Fax 805-685-6869
639 Electronic mail <info@eiffel.com>
640 Customer support http://support.eiffel.com
641 ]"
642
643 info: "[
644 For latest info see award-winning pages: http://eiffel.com
645 ]"
646
647 end -- class ARRAYED_LIST

Properties

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

  ViewVC Help
Powered by ViewVC 1.1.23