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

Contents of /FreeELKS/trunk/library/structures/cursor_tree/compact_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, 3 months ago) by manus_eiffel
File size: 15802 byte(s)
Initial revision

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

Properties

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

  ViewVC Help
Powered by ViewVC 1.1.23