/[eiffelstudio]/FreeELKS/trunk/library/structures/cursor_tree/cursor_tree.e
ViewVC logotype

Contents of /FreeELKS/trunk/library/structures/cursor_tree/cursor_tree.e

Parent Directory Parent Directory | Revision Log Revision Log


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

1 indexing
2
3 description:
4 "Trees as active structures that may be traversed using a cursor"
5
6 status: "See notice at end of class"
7 names: cursor_tree, tree;
8 access: cursor, membership;
9 contents: generic;
10 date: "$Date$"
11 revision: "$Revision$"
12
13 deferred class CURSOR_TREE [G] inherit
14
15 HIERARCHICAL [G]
16 rename
17 successor_count as arity
18 end
19
20 CURSOR_STRUCTURE [G]
21 rename
22 fill as container_fill
23 export
24 {NONE} prune_all
25 end
26
27 LINEAR [G]
28 rename
29 forth as preorder_forth,
30 finish as go_last_child,
31 occurrences as linear_occurrences,
32 has as linear_has,
33 off as linear_off,
34 do_all as linear_do_all,
35 do_if as linear_do_if,
36 there_exists as linear_there_exists,
37 for_all as linear_for_all
38 export
39 {ANY} all
40 {NONE} linear_occurrences, linear_has, linear_off
41 end
42
43 LINEAR [G]
44 rename
45 forth as preorder_forth,
46 finish as go_last_child,
47 do_all as linear_do_all,
48 do_if as linear_do_if,
49 there_exists as linear_there_exists,
50 for_all as linear_for_all
51 redefine
52 occurrences,
53 has,
54 off
55 select
56 occurrences,
57 has,
58 off,
59 linear_do_all, linear_do_if, linear_there_exists, linear_for_all
60 end
61
62 feature -- Access
63
64 parent_item: G is
65 -- Item in parent.
66 require
67 not_on_root: not is_root
68 local
69 pos: CURSOR
70 do
71 pos := cursor
72 up
73 Result := item
74 go_to (pos)
75 end
76
77 child_item (i: INTEGER): G is
78 -- Item in `i'-th child
79 require
80 argument_within_bounds: i >= 1 and then i <= arity
81 not_off: not off
82 local
83 pos: CURSOR
84 do
85 pos:= cursor
86 down (i)
87 Result := item
88 go_to (pos)
89 end
90
91 has (v: G): BOOLEAN is
92 -- Does structure include an occurrence of `v'?
93 -- (Reference or object equality,
94 -- based on `object_comparison'.)
95 local
96 pos: CURSOR
97 do
98 pos := cursor
99 Result := linear_has (v)
100 go_to (pos)
101 end
102
103 occurrences (v: G): INTEGER is
104 local
105 pos: CURSOR
106 do
107 pos := cursor
108 Result := linear_occurrences (v)
109 go_to (pos)
110 end
111
112 feature -- Measurement
113
114 depth: INTEGER is
115 -- Depth of the tree
116 local
117 pos: CURSOR
118 do
119 if not is_empty then
120 pos := cursor
121 go_above
122 Result := depth_from_active - 1
123 go_to (pos)
124 end
125 end
126
127 level: INTEGER is
128 -- Level of current node in tree
129 -- (Root is on level 1)
130 local
131 pos: CURSOR
132 do
133 from
134 pos := cursor
135 until
136 above
137 loop
138 Result := Result + 1
139 up
140 end
141 go_to (pos)
142 end
143
144 breadth: INTEGER is
145 -- Breadth of current level
146 local
147 l: INTEGER
148 pos: CURSOR
149 do
150 l := level
151 if l > 0 then
152 pos := cursor
153 go_above
154 Result := breadth_of_level_from_active (l + 1)
155 go_to (pos)
156 end
157 end
158
159 feature -- Status report
160
161 readable: BOOLEAN is
162 -- Is there a current item that may be read?
163 do
164 Result := not off
165 end
166
167 writable: BOOLEAN is
168 -- Is there a current item that may be modified?
169 do
170 Result := not off
171 end
172
173 extendible: BOOLEAN is
174 -- May new items be added?
175 do
176 Result := not above and then (level = 1) implies is_empty
177 end
178
179 is_leaf: BOOLEAN is
180 -- Is cursor on a leaf?
181 do
182 if not off then
183 Result := (arity = 0)
184 end
185 end
186
187 off: BOOLEAN is
188 -- Is there no current item?
189 -- (True if `is_empty')
190 do
191 Result := (after or before or below or above)
192 end
193
194 after: BOOLEAN is
195 -- Is there no valid cursor position to the right of cursor?
196 deferred
197 end
198
199 before: BOOLEAN is
200 -- Is there no valid cursor position to the left of cursor?
201 deferred
202 end
203
204 above: BOOLEAN is
205 -- Is there no valid cursor position above cursor?
206 deferred
207 end
208
209 below: BOOLEAN
210 -- Is there no valid cursor position below cursor?
211
212 isfirst: BOOLEAN is
213 -- Is cursor on first sibling?
214 deferred
215 end
216
217 islast: BOOLEAN is
218 -- Is cursor on last sibling?
219 deferred
220 end
221
222 is_root: BOOLEAN is
223 -- Is cursor on root?
224 deferred
225 end
226
227 valid_cursor_index (i: INTEGER): BOOLEAN is
228 -- Can cursor be moved to `i'-th child?
229 -- 0 is before and `arity' + 1 is after.
230 do
231 Result := i >= 0 and i <= (arity + 1)
232 end
233
234 feature -- Cursor movement
235
236 start is
237 -- Move cursor to root.
238 -- Leave cursor `off' if `is_empty'.
239 do
240 go_above
241 if not is_empty then
242 down (1)
243 end
244 ensure then
245 on_root_unless_empty: not is_empty implies is_root
246 end
247
248 go_last_child is
249 -- Go to the last child of current parent.
250 -- No effect if below
251 require else
252 not_above: not above
253 do
254 up
255 down (arity)
256 end
257
258 back is
259 -- Move cursor one position backward.
260 deferred
261 end
262
263 forth is
264 -- Move cursor one position forward.
265 deferred
266 end
267
268 up is
269 -- Move cursor one level upward to parent,
270 -- or `above' if `is_root' holds.
271 require else
272 not_above: not above
273 deferred
274 ensure then
275 not_before: not before
276 not_after: not after
277 not_below: not below
278 coherency: (not old off and above) = (old is_root)
279 end
280
281 down (i: INTEGER) is
282 -- Move cursor one level downward:
283 -- to `i'-th child if there is one,
284 -- or `after' if `i' = `arity' + 1,
285 -- or `before' if `i' = 0.
286 require else
287 not_before: not before
288 not_after: not after
289 not_below: not below
290 valid_cursor_index: (above and i = 0) or else valid_cursor_index (i)
291 deferred
292 ensure then
293 gone_before: (i = 0) implies before
294 --gone_after: (i = old arity + 1) implies after;
295 --gone_down: ((i > 0) and (i <= old arity)) implies not off;
296 --gone_below: ((old arity) = 0) implies below
297 end
298
299
300 preorder_forth is
301 -- Move cursor to next position in preorder.
302 -- If the active node is the last in
303 -- preorder, the cursor ends up `off'.
304 do
305 if is_leaf then
306 from
307 until
308 not islast
309 loop
310 up
311 end
312 if not above then forth end
313 else
314 down (1)
315 end
316 end
317
318 postorder_forth is
319 -- Move cursor to next position in postorder.
320 -- If the active node is the last in
321 -- postorder, the cursor ends up `off'.
322 require
323 not_off: not off
324 do
325 if islast then
326 up
327 else
328 forth
329 from
330 until
331 is_leaf
332 loop
333 down (1)
334 end
335 end
336 end
337
338 breadth_forth is
339 -- Move cursor to next position in breadth-first order.
340 -- If the active node is the last in
341 -- breadth-first order, the cursor ends up `off'.
342 require
343 not_off: not off
344 local
345 l: INTEGER
346 do
347 l := level
348 level_forth
349 if above and (l < depth) then
350 start_on_level (l + 1)
351 end
352 end
353
354 start_on_level (l: INTEGER) is
355 -- Move the cursor to the first position
356 -- of the `l'-th level counting from root.
357 require
358 argument_within_bounds: l >= 1 and then depth >= l
359 do
360 go_above
361 start_on_level_from_active (l + 1)
362 ensure
363 level_expected: level = l
364 is_first: isfirst
365 end
366
367 level_forth is
368 -- Move cursor to next position of current level.
369 do
370 if not above and then not islast then
371 forth
372 elseif not above then
373 from
374 up
375 level_forth
376 until
377 above or else not is_leaf
378 loop
379 level_forth
380 end
381 if not above then down (1) end
382 end
383 end
384
385 level_back is
386 -- Move cursor to previous position of current level.
387 do
388 if not isfirst then
389 back
390 elseif not above then
391 from
392 up
393 level_back
394 until
395 above or else not is_leaf
396 loop
397 level_back
398 end
399 if not above then down (arity) end
400 end
401 end
402
403 postorder_start is
404 -- Move cursor to first position in postorder.
405 -- Leave cursor off if tree is empty.
406 do
407 from
408 go_above
409 until
410 arity = 0
411 loop
412 down (1)
413 end
414 end
415
416 feature -- Element change
417
418 put (v: G) is
419 -- Put `v' at cursor position.
420 -- (Synonym for `replace')
421 do
422 replace (v)
423 end
424
425 extend (v: G) is
426 -- Add `v' after last child.
427 -- Make `v' the `first_child' if `below' and place
428 -- cursor `before'.
429 local
430 pos: CURSOR
431 do
432 pos := cursor
433 go_last_child
434 put_right (v)
435 go_to (pos)
436 if below then
437 below := False
438 down (0)
439 end
440 end
441
442 put_left (v: G) is
443 -- Add `v' to the left of cursor position.
444 require
445 not_before: not before
446 not_above: not above
447 only_one_root: (level = 1) implies is_empty
448 do
449 back
450 put_right (v)
451 forth
452 forth
453 end
454
455 put_right (v: G) is
456 -- Add `v' to the right of cursor position.
457 require
458 not_after: not after
459 not_above: not above
460 only_one_root: (level = 1) implies is_empty
461 deferred
462 end
463
464 fill (other: CURSOR_TREE [G]) is
465 -- Fill with as many items of `other'
466 -- as possible.
467 -- The representations of `other' and current structure
468 -- need not be the same.
469 require
470 is_empty: is_empty
471 do
472 go_above
473 if not other.is_empty then
474 other.start
475 down (0)
476 put_right (other.item)
477 forth
478 fill_from_active (other)
479 end
480 end
481
482 fill_from_active (other: CURSOR_TREE [G]) is
483 -- Copy subtree of `other''s active node
484 -- onto active node of current tree.
485 require
486 cursor_on_leaf: is_leaf
487 do
488 if not other.is_leaf then
489 from
490 other.down (1)
491 down (0)
492 until
493 other.after
494 loop
495 put_right (other.item)
496 forth
497 fill_from_active (other)
498 other.forth
499 end
500 other.up
501 up
502 end
503 end
504
505 merge_right (other: CURSOR_TREE [G]) is
506 -- Merge the items of `other' into current structure to
507 -- the right of cursor position.
508 require
509 other_exists: other /= Void
510 not_after: not after
511 not_above: not above
512 only_one_root: (level = 1) implies is_empty
513 local
514 pos: CURSOR
515 do
516 if not other.is_empty then
517 pos := other.cursor
518 other.start
519 put_right (other.item)
520 forth
521 if not other.is_leaf then
522 down (0)
523 other.down (0)
524 from
525 until
526 other.islast
527 loop
528 other.forth
529 merge_right (other.subtree)
530 end
531 up
532 end
533 other.go_to (pos)
534 end
535 end
536
537 merge_left (other: CURSOR_TREE [G]) is
538 -- Merge the items of `other' into current structure to
539 -- the left of cursor position.
540 require
541 other_exists: other /= Void
542 not_before: not before
543 not_above: not above
544 only_one_root: (level = 1) implies is_empty
545 do
546 back
547 merge_right (other)
548 end
549
550 feature -- Duplication
551
552 subtree: like Current is
553 -- Subtree rooted at current node
554 require
555 not_off: not off
556 do
557 Result := new_tree
558 Result.go_above
559 Result.down (0)
560 Result.put_right (item)
561 Result.forth
562 Result.fill_from_active (Current)
563 end
564
565 parent_tree: like Current is
566 -- Subtree rooted at parent
567 require
568 not_on_root: not is_root
569 not_off: not off
570 local
571 pos: CURSOR
572 do
573 pos := cursor
574 up
575 Result := subtree
576 go_to (pos)
577 end
578
579 child_tree (i: INTEGER): like Current is
580 -- Subtree rooted at `i'-th child
581 require
582 argument_within_bounds: i >= 1 and then i <= arity
583 not_off: not off
584 local
585 pos: CURSOR
586 do
587 pos := cursor
588 down (i)
589 Result := subtree
590 go_to (pos)
591 end
592
593 feature {NONE} -- Inapplicable
594
595 prune (v: G) is
596 -- Remove item `v'.
597 do
598 end
599
600 feature {CURSOR_TREE} -- Implementation
601
602 new_tree: like Current is
603 -- A newly created instance of the same type.
604 -- This feature may be redefined in descendants so as to
605 -- produce an adequately allocated and initialized object.
606 deferred
607 ensure
608 result_exists: Result /= Void
609 result_is_empty: Result.is_empty
610 end
611
612 go_above is
613 -- Move the cursor above the tree
614 do
615 from
616 until
617 above
618 loop
619 up
620 end
621 end
622
623 feature {NONE} -- Implementation
624
625 depth_from_active: INTEGER is
626 -- Depth of subtree starting at active
627 do
628 if not off and then arity = 0 then
629 Result := 1
630 else
631 from
632 down (1)
633 until
634 after
635 loop
636 Result := Result.max (depth_from_active + 1)
637 forth
638 end
639 up
640 end
641 end
642
643 breadth_of_level_from_active (a_level: INTEGER): INTEGER is
644 -- Breadth of level `level' of subtree starting at current node
645 do
646 if (a_level = 2) or else is_leaf then
647 Result := arity
648 else
649 from
650 down (1)
651 until
652 after
653 loop
654 Result := Result + breadth_of_level_from_active (a_level - 1)
655 forth
656 end
657 up
658 end
659 end
660
661 start_on_level_from_active (l: INTEGER) is
662 -- Move the cursor to the first position
663 -- of the `l'-th level counting from active.
664 require
665 deep_enough: depth_from_active >= l
666 do
667 from
668 down (1)
669 until
670 depth_from_active >= l - 1
671 loop
672 forth
673 end
674 if (l > 2) then
675 start_on_level_from_active (l - 1)
676 end
677 end
678
679 feature {NONE} -- Not applicable
680
681 index: INTEGER is
682 do
683 end
684
685 invariant
686
687 non_negative_depth: depth >= 0
688 non_negative_breadth: breadth >= 0
689 is_leaf_definition: not off implies is_leaf = (arity = 0)
690 above_property: above implies (arity <= 1)
691 on_tree: (isfirst or islast or is_leaf or is_root) implies not off
692
693 -- The following clauses express the constraints
694 -- on the different legal cursor positions.
695
696 off_definition: off = after or before or above or below
697 below_constraint: below implies ((after or before) and not above)
698 above_constraint: above implies not (before or after or below)
699 after_constraint: after implies not (before or above)
700 before_constaint: before implies not (after or above)
701 empty_below_constraint: (is_empty and (after or before)) implies below
702
703 indexing
704
705 library: "[
706 EiffelBase: Library of reusable components for Eiffel.
707 ]"
708
709 status: "[
710 Copyright 1986-2001 Interactive Software Engineering (ISE).
711 For ISE customers the original versions are an ISE product
712 covered by the ISE Eiffel license and support agreements.
713 ]"
714
715 license: "[
716 EiffelBase may now be used by anyone as FREE SOFTWARE to
717 develop any product, public-domain or commercial, without
718 payment to ISE, under the terms of the ISE Free Eiffel Library
719 License (IFELL) at http://eiffel.com/products/base/license.html.
720 ]"
721
722 source: "[
723 Interactive Software Engineering Inc.
724 ISE Building
725 360 Storke Road, Goleta, CA 93117 USA
726 Telephone 805-685-1006, Fax 805-685-6869
727 Electronic mail <info@eiffel.com>
728 Customer support http://support.eiffel.com
729 ]"
730
731 info: "[
732 For latest info see award-winning pages: http://eiffel.com
733 ]"
734
735 end -- class CURSOR_TREE
736
737
738

Properties

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

  ViewVC Help
Powered by ViewVC 1.1.23