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

Properties

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

  ViewVC Help
Powered by ViewVC 1.1.23