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

Contents of /FreeELKS/trunk/library/structures/cursor_tree/recursive_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: 7125 byte(s)
Initial revision

1 indexing
2
3 description:
4 "Cursor trees with a recursive structure"
5
6 status: "See notice at end of class"
7 names: recursive_cursor_tree, cursor_tree, tree;
8 access: cursor, membership;
9 representation: recursive;
10 contents: generic;
11 date: "$Date$"
12 revision: "$Revision$"
13
14 deferred class RECURSIVE_CURSOR_TREE [G] inherit
15
16 CURSOR_TREE [G]
17 redefine
18 is_empty, extendible, extend
19 end
20
21 feature -- Access
22
23 item: G is
24 -- Item at cursor position
25 do
26 Result := active.item
27 end
28
29 cursor: RECURSIVE_TREE_CURSOR [G] is
30 -- Current cursor position
31 do
32 create Result.make (active, active_parent, after, before, below)
33 end
34
35 feature -- Measurement
36
37 arity: INTEGER is
38 -- Number of children of active node.
39 -- If cursor is `above', 0 if tree is empty, 1 otherwise.
40 require else
41 valid_cursor: not off or else above
42 do
43 Result := active.arity
44 end
45
46 count: INTEGER is
47 -- Number of items in the tree
48 local
49 pos: like cursor
50 do
51 pos ?= cursor
52 from
53 start
54 until
55 off
56 loop
57 Result := Result + 1
58 preorder_forth
59 end
60 go_to (pos)
61 corresponding_child
62 end
63
64 feature -- Status report
65
66 after: BOOLEAN
67 -- Is there no valid cursor position to the right of cursor?
68
69 before: BOOLEAN
70 -- Is there no valid cursor position to the left of cursor?
71
72 above: BOOLEAN is
73 -- Is there no valid cursor position above cursor?
74 do
75 if not below then
76 Result := (active_parent = Void)
77 end
78 end
79
80 is_empty: BOOLEAN is
81 -- Is the tree empty?
82 do
83 Result := (above_node.arity = 0)
84 end
85
86 extendible: BOOLEAN is
87 -- May new items be added on current level?
88 do
89 Result := (not above) and (not is_root)
90 end
91
92 isfirst: BOOLEAN is
93 -- Is cursor on first sibling?
94 do
95 if not off then
96 Result := active_parent.child_isfirst
97 end
98 end
99
100 islast: BOOLEAN is
101 -- Is cursor on last sibling?
102 do
103 if not off then
104 Result := active_parent.child_islast
105 end
106 end
107
108 is_root: BOOLEAN is
109 -- Is cursor on tree root?
110 do
111 if not off then
112 Result := (active_parent = above_node)
113 end
114 end
115
116 valid_cursor (p: CURSOR): BOOLEAN is
117 -- Can the cursor be moved to position `p'?
118 local
119 pos, temp: like cursor
120 do
121 temp ?= p
122 if temp /= Void then
123 if temp.active = above_node or temp.before or
124 temp.after or temp.below
125 then
126 Result := True
127 else
128 pos := cursor
129 from
130 start
131 until
132 active = temp.active or else off
133 loop
134 preorder_forth
135 end
136 Result := not off
137 go_to (pos)
138 end
139 end
140 end
141
142 feature -- Cursor movement
143
144 back is
145 -- Move cursor one position backward.
146 do
147 if below then
148 after := False
149 before := True
150 elseif after then
151 after := False
152 elseif isfirst then
153 before := True
154 else
155 active_parent.child_back
156 active := active_parent.child
157 end
158 end
159
160 forth is
161 -- Move cursor one position forward.
162 do
163 if below then
164 before := False
165 after := True
166 elseif before then
167 before := False
168 elseif islast then
169 after := True
170 else
171 active_parent.child_forth
172 active := active_parent.child
173 end
174 end
175
176 up is
177 -- Move cursor one level upward to parent,
178 -- or `above' if `is_root' holds.
179 do
180 if below then
181 below := False
182 else
183 active := active_parent
184 if active /= Void then
185 active_parent := active.parent
186 end
187 corresponding_child
188 end
189 after := False
190 before := False
191 end
192
193 down (i: INTEGER) is
194 -- Move cursor one level downward:
195 -- to `i'-th child if there is one,
196 -- or `after' if `i' = `arity' + 1,
197 -- or `before' if `i' = 0.
198 do
199 if i = 0 then
200 if arity = 0 then
201 below := True
202 else
203 active_parent := active
204 active.child_go_i_th (1)
205 active := active.child
206 end
207 before := True
208 elseif above or else i <= arity then
209 active_parent := active
210 active.child_go_i_th (i)
211 active := active.child
212 else
213 if arity = 0 then
214 below := True
215 else
216 active_parent := active
217 active.child_go_i_th (arity)
218 active := active.child
219 end
220 after := True
221 end
222 end
223
224 go_to (p: CURSOR) is
225 -- Move cursor to position `p'.
226 local
227 temp: like cursor
228 do
229 temp ?= p
230 check
231 temp /= Void
232 end
233 unchecked_go (temp)
234 end
235
236 feature -- Insert element
237
238 extend (v: G) is
239 -- Add `v' after last child.
240 -- Make `v' the `first_child' if `below' and place
241 -- cursor `before'.
242 local
243 pos: CURSOR
244 do
245 pos := cursor
246 go_last_child
247 put_right (v)
248 go_to (pos)
249 if below then
250 below := False
251 before := False
252 after := False
253 down (0)
254 end
255 end
256
257 feature -- Element change
258
259 replace (v: G) is
260 -- Replace current item by `v'.
261 do
262 active.replace (v)
263 end
264
265 feature -- Removal
266
267 remove is
268 -- Remove node at cursor position
269 -- (and consequently the corresponding
270 -- subtree). Cursor moved up one level.
271 do
272 corresponding_child
273 active := active_parent
274 active_parent := active.parent
275 active.remove_child
276 active.child_back
277 ensure then
278 not_off_unless_empty: is_empty or else not off
279 end
280
281 wipe_out is
282 -- Remove all items.
283 do
284 if not is_empty then
285 above_node.child_start
286 above_node.remove_child
287 end
288 active := above_node
289 active_parent := Void
290 after := False
291 before := False
292 below := False
293 ensure then
294 cursor_above: above
295 end
296
297 feature {NONE} -- Implementation
298
299 active: DYNAMIC_TREE [G]
300 -- Current node
301
302 active_parent: like active
303 -- Parent of current node
304
305 above_node: like active
306 -- Node above root; physical root of tree
307
308 corresponding_child is
309 -- Make `active' the current child of `active_parent'.
310 require
311 active_exists: active /= Void
312 do
313 if active_parent /= Void then
314 active_parent.set_child (active)
315 end
316 end
317
318 unchecked_go (p: like cursor) is
319 -- Make an attempt to move cursor
320 -- to position `p', without checking
321 -- whether `p' is a valid cursor position
322 -- or not.
323 do
324 active_parent := p.active_parent
325 active := p.active
326 corresponding_child
327 after := p.after
328 before := p.before
329 below := p.below
330 end
331
332 invariant
333 coherency: not above implies active_parent.child = active
334
335 indexing
336
337 library: "[
338 EiffelBase: Library of reusable components for Eiffel.
339 ]"
340
341 status: "[
342 Copyright 1986-2001 Interactive Software Engineering (ISE).
343 For ISE customers the original versions are an ISE product
344 covered by the ISE Eiffel license and support agreements.
345 ]"
346
347 license: "[
348 EiffelBase may now be used by anyone as FREE SOFTWARE to
349 develop any product, public-domain or commercial, without
350 payment to ISE, under the terms of the ISE Free Eiffel Library
351 License (IFELL) at http://eiffel.com/products/base/license.html.
352 ]"
353
354 source: "[
355 Interactive Software Engineering Inc.
356 ISE Building
357 360 Storke Road, Goleta, CA 93117 USA
358 Telephone 805-685-1006, Fax 805-685-6869
359 Electronic mail <info@eiffel.com>
360 Customer support http://support.eiffel.com
361 ]"
362
363 info: "[
364 For latest info see award-winning pages: http://eiffel.com
365 ]"
366
367 end -- class RECURSIVE_CURSOR_TREE
368
369
370

Properties

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

  ViewVC Help
Powered by ViewVC 1.1.23