• R/O
  • SSH
  • HTTPS

tenarai: 提交


Commit MetaInfo

修訂16 (tree)
時間2007-07-08 13:59:29
作者junkikuchi

Log Message

added tree support to db staffs.

Change Summary

差異

--- trunk/test/test_db_tree.rb (nonexistent)
+++ trunk/test/test_db_tree.rb (revision 16)
@@ -0,0 +1,258 @@
1+#
2+# Copyright (C) 2007 Jun Kikuchi <kikuchi@bonnou.com>
3+#
4+
5+require 'test/unit'
6+require 'tenarai/db/table'
7+require 'tenarai/db/tree'
8+
9+class DBRowTreeTest < Test::Unit::TestCase
10+ class Tree < Tenarai::DB::Row::Tree
11+ column Tenarai::DB::String.new('name', :default => 'DEFAULT')
12+ end
13+
14+ class ArrayTree < Tenarai::DB::Row::ArrayTree
15+ column Tenarai::DB::String.new('name', :default => 'DEFAULT')
16+ end
17+
18+ def setup
19+ @config = YAML.load_file(File.dirname(__FILE__) + '/db.yaml')
20+ end
21+
22+ def test_mysql_tree
23+ Tenarai::DB.new(@config[:mysql]) do |db|
24+ begin
25+ t = Tenarai::DB::Table.new(db, Tree, 'test_table_tree')
26+ r = Tenarai::DB::Relation.new(db, t, 'parent', t, 'nodes')
27+
28+ t.create
29+ r.create
30+
31+ tr = Tree.new(t)
32+ tr.name = 'root'
33+
34+ t1 = Tree.new(t)
35+ t1.name = 't1'
36+
37+ t2 = Tree.new(t)
38+ t2.name = 't2'
39+
40+ t3 = Tree.new(t)
41+ t3.name = 't2'
42+
43+ t11 = Tree.new(t)
44+ t11.name = 't11'
45+
46+ tr.nodes << t1
47+ tr.nodes << t2
48+ tr.nodes << t3
49+
50+ t1.nodes << t11
51+
52+ tr.save
53+ t1.save
54+ t2.save
55+ t3.save
56+ t11.save
57+
58+ assert_equal([tr], tr.path)
59+ assert_equal([tr, t1], t1.path)
60+ assert_equal([tr, t1, t11], t11.path)
61+ assert_equal([tr, t2], t2.path)
62+ assert_equal([tr, t3], t3.path)
63+
64+ assert_nil(tr.parent)
65+ assert_equal(tr, t1.parent)
66+ assert_equal(tr, t2.parent)
67+ assert_equal(tr, t3.parent)
68+ assert_equal(t1, t11.parent)
69+
70+ assert_equal(tr, t1.root)
71+ assert_equal(tr, t2.root)
72+ assert_equal(tr, t3.root)
73+ assert_equal(tr, t11.root)
74+
75+ assert(tr.path.include?(tr))
76+ assert(t1.path.include?(tr))
77+ assert(t1.path.include?(t1))
78+ assert(t11.path.include?(tr))
79+ assert(t11.path.include?(t1))
80+ assert(t11.path.include?(t11))
81+ assert(t2.path.include?(tr))
82+ assert(t2.path.include?(t2))
83+
84+ tmp = tr.nodes.map
85+ assert(tmp.include?(t1))
86+ assert(tmp.include?(t2))
87+ assert(tmp.include?(t3))
88+
89+ tmp = t1.nodes.map
90+ assert(tmp.include?(t11))
91+
92+ assert_equal([], t2.nodes.map)
93+
94+ tr.delete
95+ assert_nil(t1.parent)
96+ assert_nil(t2.parent)
97+ assert_nil(t3.parent)
98+ assert_equal(t1, t11.parent)
99+ ensure
100+ r.drop
101+ t.drop
102+ end
103+ end
104+ end
105+
106+ def test_mysql_array_tree
107+ Tenarai::DB.new(@config[:mysql]) do |db|
108+ begin
109+ #db.echo = true
110+
111+ t = Tenarai::DB::Table.new(db, ArrayTree, 'test_table_tree')
112+ r = Tenarai::DB::Relation.new(db, t, 'parent', t, 'nodes')
113+
114+ t.create
115+ r.create
116+
117+ tr = ArrayTree.new(t)
118+ tr.name = 'root'
119+
120+ t1 = ArrayTree.new(t)
121+ t1.name = 't1'
122+
123+ t2 = ArrayTree.new(t)
124+ t2.name = 't2'
125+
126+ t3 = ArrayTree.new(t)
127+ t3.name = 't3'
128+
129+ t11 = ArrayTree.new(t)
130+ t11.name = 't11'
131+
132+ t1.nodes << t11
133+ assert_equal(1, t1.min)
134+ assert_equal(2, t11.min)
135+ assert_equal(3, t11.max)
136+ assert_equal(4, t1.max)
137+ assert_equal(t1, t1.root)
138+ assert_equal(t1, t11.root)
139+ assert_equal([t1], t1.path)
140+ assert_equal([t1, t11], t11.path)
141+
142+ tr.nodes << t1
143+ assert_equal(1, tr.min)
144+ assert_equal(2, t1.min)
145+ assert_equal(3, t11.min)
146+ assert_equal(4, t11.max)
147+ assert_equal(5, t1.max)
148+ assert_equal(6, tr.max)
149+ assert_equal(tr, tr.root)
150+ assert_equal(tr, t1.root)
151+ assert_equal(tr, t11.root)
152+ assert_equal([tr], tr.path)
153+ assert_equal([tr, t1], t1.path)
154+ assert_equal([tr, t1, t11], t11.path)
155+
156+ tr.nodes << t2
157+ tr.nodes << t3
158+ assert_equal(1, tr.min)
159+ assert_equal(2, t1.min)
160+ assert_equal(3, t11.min)
161+ assert_equal(4, t11.max)
162+ assert_equal(5, t1.max)
163+ assert_equal(6, t2.min)
164+ assert_equal(7, t2.max)
165+ assert_equal(8, t3.min)
166+ assert_equal(9, t3.max)
167+ assert_equal(10, tr.max)
168+ assert_equal(tr, tr.root)
169+ assert_equal(tr, t1.root)
170+ assert_equal(tr, t11.root)
171+ assert_equal(tr, t2.root)
172+ assert_equal(tr, t3.root)
173+ assert_equal([tr], tr.path)
174+ assert_equal([tr, t1], t1.path)
175+ assert_equal([tr, t1, t11], t11.path)
176+ assert_equal([tr, t2], t2.path)
177+ assert_equal([tr, t3], t3.path)
178+
179+ tr.nodes.insert(t1.min, t3)
180+ assert_equal(1, tr.min)
181+ assert_equal(2, t3.min)
182+ assert_equal(3, t3.max)
183+ assert_equal(4, t1.min)
184+ assert_equal(5, t11.min)
185+ assert_equal(6, t11.max)
186+ assert_equal(7, t1.max)
187+ assert_equal(8, t2.min)
188+ assert_equal(9, t2.max)
189+ assert_equal(10, tr.max)
190+ assert_equal(tr, tr.root)
191+ assert_equal(tr, t1.root)
192+ assert_equal(tr, t11.root)
193+ assert_equal(tr, t2.root)
194+ assert_equal(tr, t3.root)
195+ assert_equal([tr], tr.path)
196+ assert_equal([tr, t1], t1.path)
197+ assert_equal([tr, t1, t11], t11.path)
198+ assert_equal([tr, t2], t2.path)
199+ assert_equal([tr, t3], t3.path)
200+
201+ tr.nodes << t3
202+ assert_equal(1, tr.min)
203+ assert_equal(2, t1.min)
204+ assert_equal(3, t11.min)
205+ assert_equal(4, t11.max)
206+ assert_equal(5, t1.max)
207+ assert_equal(6, t2.min)
208+ assert_equal(7, t2.max)
209+ assert_equal(8, t3.min)
210+ assert_equal(9, t3.max)
211+ assert_equal(10, tr.max)
212+ assert_equal(tr, tr.root)
213+ assert_equal(tr, t1.root)
214+ assert_equal(tr, t11.root)
215+ assert_equal(tr, t2.root)
216+ assert_equal(tr, t3.root)
217+ assert_equal([tr], tr.path)
218+ assert_equal([tr, t1], t1.path)
219+ assert_equal([tr, t1, t11], t11.path)
220+ assert_equal([tr, t2], t2.path)
221+ assert_equal([tr, t3], t3.path)
222+
223+ t2.delete
224+ assert_equal(1, tr.min)
225+ assert_equal(2, t1.min)
226+ assert_equal(3, t11.min)
227+ assert_equal(4, t11.max)
228+ assert_equal(5, t1.max)
229+ assert_equal(6, t3.min)
230+ assert_equal(7, t3.max)
231+ assert_equal(8, tr.max)
232+ assert_equal(tr, tr.root)
233+ assert_equal(tr, t1.root)
234+ assert_equal(tr, t11.root)
235+ assert_equal(tr, t3.root)
236+ assert_equal([tr], tr.path)
237+ assert_equal([tr, t1], t1.path)
238+ assert_equal([tr, t1, t11], t11.path)
239+ assert_equal([tr, t3], t3.path)
240+
241+ t1.delete
242+ assert_equal(1, tr.min)
243+ assert_equal(2, t3.min)
244+ assert_equal(3, t3.max)
245+ assert_equal(4, tr.max)
246+ assert_equal(tr, tr.root)
247+ assert_equal(tr, t3.root)
248+ assert_equal([tr], tr.path)
249+ assert_equal([tr, t3], t3.path)
250+
251+ #db.query('select id, parent, min, max, name from %s order by id' % 'test_table_tree') do |row| p row end
252+ ensure
253+ r.drop
254+ t.drop
255+ end
256+ end
257+ end
258+end
--- trunk/lib/tenarai/db/tree.rb (nonexistent)
+++ trunk/lib/tenarai/db/tree.rb (revision 16)
@@ -0,0 +1,155 @@
1+#
2+# Copyright (C) 2007 Jun Kikuchi <kikuchi@bonnou.com>
3+#
4+
5+require 'tenarai/db/table'
6+
7+module Tenarai
8+ class DB
9+ class Row
10+ class Tree < Row
11+ column Reference.new('parent')
12+ column Reference.new('nodes', :multiple => true)
13+
14+ def root
15+ path.shift
16+ end
17+
18+ def path
19+ parent.nil? ? [self] : parent.path << self
20+ end
21+ end
22+
23+ class ArrayTree < Row
24+ class Multiple < Tenarai::DB::Reference::Multiple
25+ def _insert(nth, node)
26+ size = (node.max - node.min) + 1
27+ diff = nth - (node.min + size)
28+
29+ ArrayTree.open_loop(@link.src_table, size, nth)
30+ if 0 < diff
31+ ArrayTree.open_loop(
32+ @link.src_table, diff + size, node.min, node.max
33+ )
34+ else
35+ ArrayTree.close_loop(
36+ @link.src_table, diff.abs, node.min + size, node.max + size
37+ )
38+ end
39+ ArrayTree.close_loop(@link.src_table, size, node.min + size)
40+
41+ @link.src_table.reload
42+ @link.link(@row, node)
43+ node.save
44+
45+ node
46+ end
47+
48+ def <<(node)
49+ @row.save
50+ node.save
51+ _insert(@row.max, node)
52+ end
53+
54+ def insert(nth, node)
55+ @row.save
56+ node.save
57+ _insert(nth, node)
58+ end
59+ end
60+
61+ SQLA = "UPDATE %s SET %s = %s %s ? WHERE ? <= %s ORDER BY %s %s"
62+ SQLB =<<-END
63+ UPDATE %s SET %s = %s %s ? WHERE ? <= %s AND %s <= ? ORDER BY %s %s
64+ END
65+ SQL_MAX = "SELECT MAX(%s) AS m FROM %s"
66+ SQL_DELETE = "DELETE FROM %s WHERE ? <= %s AND %s <= ? ORDER BY %s DESC"
67+
68+ class << self
69+ def inc(table, col, size, first, last=nil)
70+ unless last
71+ table.db.execute(
72+ SQLA % [table.name, col, col, '+', col, col, "DESC"],
73+ size, first
74+ )
75+ else
76+ table.db.execute(
77+ SQLB % [table.name, col, col, '+', col, col, col, "DESC"],
78+ size, first, last
79+ )
80+ end
81+ end
82+
83+ def dec(table, col, size, first, last=nil)
84+ unless last
85+ table.db.execute(
86+ SQLA % [table.name, col, col, '-', col, col, "ASC"],
87+ size, first
88+ )
89+ else
90+ table.db.execute(
91+ SQLB % [table.name, col, col, '-', col, col, col, "ASC"],
92+ size, first, last
93+ )
94+ end
95+ end
96+
97+ def open_loop(table, size, first, last=nil)
98+ inc(table, 'min', size, first, last)
99+ inc(table, 'max', size, first, last)
100+ end
101+
102+ def close_loop(table, size, first, last=nil)
103+ dec(table, 'min', size, first, last)
104+ dec(table, 'max', size, first, last)
105+ end
106+
107+ def fetch_max(table)
108+ table.db.query(SQL_MAX % ['max', table.name]) do |row|
109+ return row['m'] || 0
110+ end
111+ end
112+
113+ def delete(table, min, max)
114+ table.db.execute(
115+ SQL_DELETE % [table.name, 'min', 'max', 'min'], min, max
116+ )
117+ end
118+ end
119+
120+ column Reference.new('parent')
121+ column Reference.new('nodes', :multiple => true, :class => Multiple)
122+ column Integer.new('min', :unsigned => true)
123+ column Integer.new('max', :unsigned => true)
124+ index Index.new('min_max_idx', :cols => ['min', 'max'])
125+
126+ def save
127+ if min.nil? || max.nil?
128+ @row['min'] = self.class.fetch_max(@table) + 1
129+ @row['max'] = @row['min'] + 1
130+ end
131+ super
132+ end
133+
134+ def root
135+ path.shift
136+ end
137+
138+ def path
139+ parent.nil? ? [self] : parent.path << self
140+ end
141+
142+ def include?(node)
143+ (min <= node.min.to_i) && (node.min.to_i <= max)
144+ end
145+
146+ def delete
147+ self.class.delete(@table, min, max)
148+ self.class.close_loop(@table, (max - min + 1), min)
149+ super
150+ @table.reload
151+ end
152+ end
153+ end
154+ end
155+end
Show on old repository browser