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

Properties

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

  ViewVC Help
Powered by ViewVC 1.1.23