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

Properties

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

  ViewVC Help
Powered by ViewVC 1.1.23