chunk_column.bend

bendvy-ecs-core@0.1.0.3 · 247 lines · 73 definitions

1import Base
2import bendvy-ecs-core@0.1.0.3/lifecycle.bend as L
3import bendvy-ecs-core@0.1.0.3/change_tick.bend as Tick
4
5# Trusted storage. Public declarations confine these owners before gameplay runs.
6type Column<-S:Data,-C:Type> is Type:
7  Leaf{values:Array<Maybe<&1,C>>,stamps:Array<L.Stamp>}
8  Branch{half:U32,left:Column<S,C>,right:Column<S,C>}
9type SwapOutcome<-S:Data,-C:Type> is Type:
10  Accepted{column:Column<S,C>,previous:Maybe<&1,C>}
11  Rejected{column:Column<S,C>,incoming:Maybe<&1,C>}
12
13def absent_generic(-C:Type,depth:Nat) -> Array<Maybe<&1,C>>:
14  match depth:
15    case 0n:ALeaf{None{}}
16    case 1n++rest:ANode{absent_generic(C,rest),absent_generic(C,rest)}
17def empty_generic(-S:Data,-C:Type) -> Column<S,C>:
18  Leaf{absent_generic(C,3n),[L.Stamp{None{},None{}} : L.Stamp^3n]}
19def capacity_generic(-S:Data,-C:Type,column:Column<S,C>) -> Column<S,C> & U32:
20  match column:
21    case Leaf{values,stamps}:(Leaf{values,stamps},8)
22    case Branch{+half,left,right}:(Branch{half,left,right},U32.add(half,half))
23def vacant_generic(-S:Data,-C:Type,depth:Nat) -> Column<S,C>:
24  match depth:
25    case 0n:empty_generic(S,C)
26    case 1n++rest:
27      +half = U32.shln(8,rest)
28      Branch{half,vacant_generic(S,C,rest),vacant_generic(S,C,rest)}
29def grown_generic(-S:Data,-C:Type,fuel:Nat,column:Column<S,C>,+size:U32,+depth:Nat,+target:U32,enough:Bool) -> Column<S,C>:
30  match fuel enough:
31    case _ True{}:column
32    case 0n False{}:column
33    case 1n+rest False{}:grown_generic(S,C,rest,Branch{size,column,vacant_generic(S,C,depth)},U32.add(size,size),1n+depth,target,U32.is_le(target,U32.add(size,size)))
34def ensure_sized_generic(-S:Data,-C:Type,+target:U32,result:Column<S,C> & U32) -> Column<S,C>:
35  match result:
36    case (column,+size):grown_generic(S,C,14n,column,size,Nat.sub(U32.log2(size),3n),target,U32.is_le(target,size))
37def maximum_capacity() -> U32:131072
38def ensure_generic(-S:Data,-C:Type,column:Column<S,C>,target:U32) -> Column<S,C>:
39  ensure_sized_generic(S,C,U32.min(target,maximum_capacity()),capacity_generic(S,C,column))
40def absent(~C:Type,depth:Nat) -> Array<Maybe<&1,C>>:absent_generic(C,depth)
41def empty(~S:Data,~C:Type) -> Column<S,C>:empty_generic(S,C)
42def capacity(~S:Data,~C:Type,column:Column<S,C>) -> Column<S,C> & U32:capacity_generic(S,C,column)
43def vacant(~S:Data,~C:Type,depth:Nat) -> Column<S,C>:vacant_generic(S,C,depth)
44def grown(~S:Data,~C:Type,fuel:Nat,column:Column<S,C>,size:U32,depth:Nat,target:U32,enough:Bool) -> Column<S,C>:grown_generic(S,C,fuel,column,size,depth,target,enough)
45def ensure_sized(~S:Data,~C:Type,target:U32,result:Column<S,C> & U32) -> Column<S,C>:ensure_sized_generic(S,C,target,result)
46def ensure(~S:Data,~C:Type,column:Column<S,C>,target:U32) -> Column<S,C>:ensure_generic(S,C,column,target)
47
48# Actual presence only; None distinguishes unavailable/malformed leaf storage.
49# Bounds use actual array lengths before any affine cell is temporarily moved.
50def vacancy_restored(-S:Data,-C:Type,stamps:Array<L.Stamp>,index:U32,result:Array<Maybe<&1,C>> & Maybe<&1,C>) -> Column<S,C> & Maybe<&2,Bool>:
51  match result:
52    case (values,None{}):(Leaf{values,stamps},Some{True{}})
53    case (values,Some{owner}):(Leaf{Array.set(Maybe<&1,C>,values,index,Some{owner}),stamps},Some{False{}})
54def vacancy_bounded(-S:Data,-C:Type,values:Array<Maybe<&1,C>>,stamps:Array<L.Stamp>,+index:U32,valid:Bool) -> Column<S,C> & Maybe<&2,Bool>:
55  match valid:
56    case False{}:(Leaf{values,stamps},None{})
57    case True{}:vacancy_restored(S,C,stamps,index,Array.swap(Maybe<&1,C>,values,index,None{}))
58def vacancy_stamps(-S:Data,-C:Type,values:Array<Maybe<&1,C>>,valueSize:U32,+index:U32,result:Array<L.Stamp> & U32) -> Column<S,C> & Maybe<&2,Bool>:
59  match result:
60    case (stamps,stampSize):vacancy_bounded(S,C,values,stamps,index,Bool.and(U32.is_eq(valueSize,8),Bool.and(U32.is_eq(stampSize,8),U32.is_lt(index,8))))
61def vacancy_values(-S:Data,-C:Type,stamps:Array<L.Stamp>,index:U32,result:Array<Maybe<&1,C>> & U32) -> Column<S,C> & Maybe<&2,Bool>:
62  match result:
63    case (values,size):vacancy_stamps(S,C,values,size,index,Array.size(L.Stamp,stamps))
64def vacancy_join(-S:Data,-C:Type,half:U32,leftResult:Column<S,C> & Maybe<&2,Bool>,rightResult:Column<S,C> & Maybe<&2,Bool>) -> Column<S,C> & Maybe<&2,Bool>:
65  match leftResult rightResult:
66    case (left,Some{result}), (right,_):(Branch{half,left,right},Some{result})
67    case (left,None{}), (right,result):(Branch{half,left,right},result)
68def vacancy_selected(-S:Data,-C:Type,column:Column<S,C>,+index:U32,selected:Bool) -> Column<S,C> & Maybe<&2,Bool>:
69  match column selected:
70    case column False{}:(column,None{})
71    case Leaf{values,stamps} True{}:vacancy_values(S,C,stamps,index,Array.size(Maybe<&1,C>,values))
72    case Branch{+half,left,right} True{}:vacancy_join(S,C,half,vacancy_selected(S,C,left,index,U32.is_lt(index,half)),vacancy_selected(S,C,right,U32.sub(index,half),Bool.not(U32.is_lt(index,half))))
73def vacancy_generic(-S:Data,-C:Type,column:Column<S,C>,index:U32) -> Column<S,C> & Maybe<&2,Bool>:
74  vacancy_selected(S,C,column,index,True{})
75
76def present_generic(-C:Type,value:Maybe<&1,C>) -> Maybe<&1,C> & Bool:
77  match value:
78    case None{}: (None{},False{})
79    case Some{owner}: (Some{owner},True{})
80def present(~C:Type,value:Maybe<&1,C>) -> Maybe<&1,C> & Bool:
81  present_generic(C,value)
82
83def swap_finish_generic(-S:Data,-C:Type,values:Array<Maybe<&1,C>>,+index:U32,incoming:Bool,previous:Maybe<&1,C>,wasPresent:Bool,tick:Tick.Tick,result:Array<L.Stamp> & L.Stamp) -> SwapOutcome<S,C>:
84  match result:
85    case (stamps,stamp): Accepted{Leaf{values,Array.set(L.Stamp,stamps,index,L.after_write(incoming,wasPresent,stamp,tick))},previous}
86def swap_finish(~S:Data,~C:Type,values:Array<Maybe<&1,C>>,+index:U32,incoming:Bool,previous:Maybe<&1,C>,wasPresent:Bool,tick:Tick.Tick,result:Array<L.Stamp> & L.Stamp) -> SwapOutcome<S,C>:
87  swap_finish_generic(S,C,values,index,incoming,previous,wasPresent,tick,result)
88
89def swap_presence_generic(-S:Data,-C:Type,values:Array<Maybe<&1,C>>,stamps:Array<L.Stamp>,+index:U32,incoming:Bool,tick:Tick.Tick,result:Maybe<&1,C> & Bool) -> SwapOutcome<S,C>:
90  match result:
91    case (previous,wasPresent): swap_finish_generic(S,C,values,index,incoming,previous,wasPresent,tick,Array.get(L.Stamp,stamps,index))
92def swap_presence(~S:Data,~C:Type,values:Array<Maybe<&1,C>>,stamps:Array<L.Stamp>,+index:U32,incoming:Bool,tick:Tick.Tick,result:Maybe<&1,C> & Bool) -> SwapOutcome<S,C>:
93  swap_presence_generic(S,C,values,stamps,index,incoming,tick,result)
94
95def swap_previous_generic(-S:Data,-C:Type,stamps:Array<L.Stamp>,index:U32,incoming:Bool,tick:Tick.Tick,result:Array<Maybe<&1,C>> & Maybe<&1,C>) -> SwapOutcome<S,C>:
96  match result:
97    case (values,previous): swap_presence_generic(S,C,values,stamps,index,incoming,tick,present_generic(C,previous))
98def swap_previous(~S:Data,~C:Type,stamps:Array<L.Stamp>,index:U32,incoming:Bool,tick:Tick.Tick,result:Array<Maybe<&1,C>> & Maybe<&1,C>) -> SwapOutcome<S,C>:
99  swap_previous_generic(S,C,stamps,index,incoming,tick,result)
100
101def swap_incoming_generic(-S:Data,-C:Type,values:Array<Maybe<&1,C>>,stamps:Array<L.Stamp>,+index:U32,tick:Tick.Tick,result:Maybe<&1,C> & Bool) -> SwapOutcome<S,C>:
102  match result:
103    case (incoming,isPresent): swap_previous_generic(S,C,stamps,index,isPresent,tick,Array.swap(Maybe<&1,C>,values,index,incoming))
104def swap_incoming(~S:Data,~C:Type,values:Array<Maybe<&1,C>>,stamps:Array<L.Stamp>,+index:U32,tick:Tick.Tick,result:Maybe<&1,C> & Bool) -> SwapOutcome<S,C>:
105  swap_incoming_generic(S,C,values,stamps,index,tick,result)
106
107def swap_leaf_generic(-S:Data,-C:Type,values:Array<Maybe<&1,C>>,stamps:Array<L.Stamp>,+index:U32,incoming:Maybe<&1,C>,tick:Tick.Tick,valid:Bool) -> SwapOutcome<S,C>:
108  match valid:
109    case False{}: Rejected{Leaf{values,stamps},incoming}
110    case True{}: swap_incoming_generic(S,C,values,stamps,index,tick,present_generic(C,incoming))
111def swap_leaf(~S:Data,~C:Type,values:Array<Maybe<&1,C>>,stamps:Array<L.Stamp>,+index:U32,incoming:Maybe<&1,C>,tick:Tick.Tick,valid:Bool) -> SwapOutcome<S,C>:
112  swap_leaf_generic(S,C,values,stamps,index,incoming,tick,valid)
113
114def swap_left(~S:Data,~C:Type,half:U32,right:Column<S,C>,result:SwapOutcome<S,C>) -> SwapOutcome<S,C>:
115  match result:
116    case Accepted{left,previous}: Accepted{Branch{half,left,right},previous}
117    case Rejected{left,incoming}: Rejected{Branch{half,left,right},incoming}
118def swap_right(~S:Data,~C:Type,half:U32,left:Column<S,C>,result:SwapOutcome<S,C>) -> SwapOutcome<S,C>:
119  match result:
120    case Accepted{right,previous}: Accepted{Branch{half,left,right},previous}
121    case Rejected{right,incoming}: Rejected{Branch{half,left,right},incoming}
122type Path<-S:Data,-C:Type> is Type:
123  Root{}
124  FromLeft{half:U32,right:Column<S,C>,parent:Path<S,C>}
125  FromRight{half:U32,left:Column<S,C>,parent:Path<S,C>}
126def rebuild(~S:Data,~C:Type,path:Path<S,C>,column:Column<S,C>) -> Column<S,C>:
127  match path:
128    case Root{}: column
129    case FromLeft{half,right,parent}: rebuild(~S,~C,parent,Branch{half,column,right})
130    case FromRight{half,left,parent}: rebuild(~S,~C,parent,Branch{half,left,column})
131def returned(~S:Data,~C:Type,path:Path<S,C>,result:SwapOutcome<S,C>) -> SwapOutcome<S,C>:
132  match result:
133    case Accepted{column,previous}: Accepted{rebuild(~S,~C,path,column),previous}
134    case Rejected{column,incoming}: Rejected{rebuild(~S,~C,path,column),incoming}
135type Search<-S:Data,-C:Type> is Type:
136  Search{column:Column<S,C>,index:U32,incoming:Maybe<&1,C>,path:Path<S,C>}
137def route(~S:Data,~C:Type,left:Column<S,C>,right:Column<S,C>,+half:U32,+index:U32,incoming:Maybe<&1,C>,path:Path<S,C>,first:Bool) -> Search<S,C>:
138  match first:
139    case True{}: Search{left,index,incoming,FromLeft{half,right,path}}
140    case False{}: Search{right,U32.sub(index,half),incoming,FromRight{half,left,path}}
141def search(~S:Data,~C:Type,fuel:Nat,state:Search<S,C>,+tick:Tick.Tick) -> SwapOutcome<S,C>:
142  match fuel state:
143    case 0n Search{column,_,incoming,path}: Rejected{rebuild(~S,~C,path,column),incoming}
144    case 1n+_ Search{Leaf{values,stamps},+index,incoming,path}: returned(~S,~C,path,swap_leaf(~S,~C,values,stamps,index,incoming,tick,U32.is_lt(index,8)))
145    case 1n+rest Search{Branch{+half,left,right},+index,incoming,path}: search(~S,~C,rest,route(~S,~C,left,right,half,index,incoming,path,U32.is_lt(index,half)),tick)
146def swap_at(~S:Data,~C:Type,column:Column<S,C>,index:U32,incoming:Maybe<&1,C>,tick:Tick.Tick) -> SwapOutcome<S,C>:
147  search(~S,~C,15n,Search{column,index,incoming,Root{}},tick)
148def swap(~S:Data,~C:Type,column:Column<S,C>,index:U32,incoming:Maybe<&1,C>) -> SwapOutcome<S,C>:
149  swap_at(~S,~C,column,index,incoming,Tick.zero())
150
151def edit_mark(index:U32,tick:Tick.Tick,result:Array<L.Stamp> & L.Stamp) -> Array<L.Stamp>:
152  match result:
153    case (stamps,stamp): Array.set(L.Stamp,stamps,index,L.written(True{},stamp,tick))
154def edit_stamps(stamps:Array<L.Stamp>,+index:U32,tick:Tick.Tick,write:Bool) -> Array<L.Stamp>:
155  match write:
156    case False{}: stamps
157    case True{}: edit_mark(index,tick,Array.get(L.Stamp,stamps,index))
158def edit_projected(-S:Data,-C:Type,-V:Data,values:Array<Maybe<&1,C>>,stamps:Array<L.Stamp>,+index:U32,tick:Tick.Tick,write:Bool,result:C & V) -> Column<S,C> & Maybe<&2,V>:
159  match result:
160    case (owner,value): (Leaf{Array.set(Maybe<&1,C>,values,index,Some{owner}),edit_stamps(stamps,index,tick,write)},Some{value})
161def edit_taken(-S:Data,-C:Type,-V:Data,transform:C -> C & V,stamps:Array<L.Stamp>,index:U32,tick:Tick.Tick,write:Bool,result:Array<Maybe<&1,C>> & Maybe<&1,C>) -> Column<S,C> & Maybe<&2,V>:
162  match result:
163    case (values,None{}): (Leaf{values,stamps},None{})
164    case (values,Some{owner}): edit_projected(S,C,V,values,stamps,index,tick,write,transform(owner))
165def edit_leaf(-S:Data,-C:Type,-V:Data,transform:C -> C & V,values:Array<Maybe<&1,C>>,stamps:Array<L.Stamp>,+index:U32,tick:Tick.Tick,write:Bool,valid:Bool) -> Column<S,C> & Maybe<&2,V>:
166  match valid:
167    case False{}: (Leaf{values,stamps},None{})
168    case True{}: edit_taken(S,C,V,transform,stamps,index,tick,write,Array.swap(Maybe<&1,C>,values,index,None{}))
169def edit_return(~S:Data,~C:Type,~V:Data,path:Path<S,C>,result:Column<S,C> & Maybe<&2,V>) -> Column<S,C> & Maybe<&2,V>:
170  match result:
171    case (column,value): (rebuild(~S,~C,path,column),value)
172type Visit<-S:Data,-C:Type> is Type:
173  Visit{column:Column<S,C>,index:U32,path:Path<S,C>}
174def edit_route(~S:Data,~C:Type,left:Column<S,C>,right:Column<S,C>,+half:U32,+index:U32,path:Path<S,C>,first:Bool) -> Visit<S,C>:
175  match first:
176    case True{}: Visit{left,index,FromLeft{half,right,path}}
177    case False{}: Visit{right,U32.sub(index,half),FromRight{half,left,path}}
178def edit_search(~S:Data,~C:Type,~V:Data,transform:C -> C & V,fuel:Nat,state:Visit<S,C>,+tick:Tick.Tick,+write:Bool) -> Column<S,C> & Maybe<&2,V>:
179  match fuel state:
180    case 0n Visit{column,_,path}: (rebuild(~S,~C,path,column),None{})
181    case 1n+_ Visit{Leaf{values,stamps},+index,path}: edit_return(~S,~C,~V,path,edit_leaf(S,C,V,transform,values,stamps,index,tick,write,U32.is_lt(index,8)))
182    case 1n+rest Visit{Branch{+half,left,right},+index,path}: edit_search(~S,~C,~V,transform,rest,edit_route(~S,~C,left,right,half,index,path,U32.is_lt(index,half)),tick,write)
183def view(~S:Data,~C:Type,~V:Data,~project:C -> C & V,column:Column<S,C>,index:U32) -> Column<S,C> & Maybe<&2,V>:
184  edit_search(~S,~C,~V,project,15n,Visit{column,index,Root{}},Tick.zero(),False{})
185def modify_at(~S:Data,~C:Type,~V:Data,~transform:C -> C & V,column:Column<S,C>,index:U32,tick:Tick.Tick) -> Column<S,C> & Maybe<&2,V>:
186  edit_search(~S,~C,~V,transform,15n,Visit{column,index,Root{}},tick,True{})
187def modify(~S:Data,~C:Type,~V:Data,~transform:C -> C & V,column:Column<S,C>,index:U32) -> Column<S,C> & Maybe<&2,V>:
188  modify_at(~S,~C,~V,~transform,column,index,Tick.zero())
189def stamp_got(~S:Data,~C:Type,values:Array<Maybe<&1,C>>,result:Array<L.Stamp> & L.Stamp) -> Column<S,C> & Maybe<&2,L.Stamp>:
190  match result:
191    case (stamps,stamp): (Leaf{values,stamps},Some{stamp})
192def stamp_leaf(~S:Data,~C:Type,values:Array<Maybe<&1,C>>,stamps:Array<L.Stamp>,+index:U32,valid:Bool) -> Column<S,C> & Maybe<&2,L.Stamp>:
193  match valid:
194    case False{}: (Leaf{values,stamps},None{})
195    case True{}: stamp_got(~S,~C,values,Array.get(L.Stamp,stamps,index))
196def stamp_search(~S:Data,~C:Type,fuel:Nat,state:Visit<S,C>) -> Column<S,C> & Maybe<&2,L.Stamp>:
197  match fuel state:
198    case 0n Visit{column,_,path}: (rebuild(~S,~C,path,column),None{})
199    case 1n+_ Visit{Leaf{values,stamps},+index,path}: edit_return(~S,~C,~L.Stamp,path,stamp_leaf(~S,~C,values,stamps,index,U32.is_lt(index,8)))
200    case 1n+rest Visit{Branch{+half,left,right},+index,path}: stamp_search(~S,~C,rest,edit_route(~S,~C,left,right,half,index,path,U32.is_lt(index,half)))
201def lifecycle(~S:Data,~C:Type,column:Column<S,C>,index:U32) -> Column<S,C> & Maybe<&2,L.Stamp>:
202  stamp_search(~S,~C,15n,Visit{column,index,Root{} })
203
204# Trusted recovery restores the recorded stamp without changing payload owners.
205def restore_leaf(~S:Data,~C:Type,values:Array<Maybe<&1,C>>,stamps:Array<L.Stamp>,index:U32,stamp:L.Stamp,valid:Bool) -> Column<S,C>:
206  match valid:
207    case False{}:Leaf{values,stamps}
208    case True{}:Leaf{values,Array.set(L.Stamp,stamps,index,stamp)}
209def restore_search(~S:Data,~C:Type,fuel:Nat,state:Visit<S,C>,+stamp:L.Stamp) -> Column<S,C>:
210  match fuel state:
211    case 0n Visit{column,_,path}:rebuild(~S,~C,path,column)
212    case 1n+_ Visit{Leaf{values,stamps},+index,path}:rebuild(~S,~C,path,restore_leaf(~S,~C,values,stamps,index,stamp,U32.is_lt(index,8)))
213    case 1n+rest Visit{Branch{+half,left,right},+index,path}:restore_search(~S,~C,rest,edit_route(~S,~C,left,right,half,index,path,U32.is_lt(index,half)),stamp)
214def restore_stamp(~S:Data,~C:Type,column:Column<S,C>,index:U32,stamp:L.Stamp) -> Column<S,C>:
215  restore_search(~S,~C,15n,Visit{column,index,Root{}},stamp)
216
217def modify_runtime(~S:Data,~C:Type,~V:Data,transform:C -> C & V,column:Column<S,C>,index:U32,tick:Tick.Tick) -> Column<S,C> & Maybe<&2,V>:
218  edit_search(~S,~C,~V,transform,15n,Visit{column,index,Root{}},tick,True{})
219
220# Unlike the template-specialized write operations, this removal accepts an
221# ordinary irrelevant payload Type so a canonical heterogeneous schema fold can
222# return every actual owner. It never grows storage and clears the same stamps
223# as swap_at(..., None, ...), including an already absent in-range component.
224def take_leaf_done(-S:Data,-C:Type,stamps:Array<L.Stamp>,index:U32,result:Array<Maybe<&1,C>> & Maybe<&1,C>) -> Column<S,C> & Maybe<&1,C>:
225  match result:
226    case (values,previous):(Leaf{values,Array.set(L.Stamp,stamps,index,L.Stamp{None{},None{}})},previous)
227def take_leaf(-S:Data,-C:Type,values:Array<Maybe<&1,C>>,stamps:Array<L.Stamp>,+index:U32,allowed:Bool) -> Column<S,C> & Maybe<&1,C>:
228  match allowed:
229    case False{}:(Leaf{values,stamps},None{})
230    case True{}:take_leaf_done(S,C,stamps,index,Array.swap(Maybe<&1,C>,values,index,None{}))
231def take_left_done(-S:Data,-C:Type,half:U32,right:Column<S,C>,result:Column<S,C> & Maybe<&1,C>) -> Column<S,C> & Maybe<&1,C>:
232  match result:
233    case (left,previous):(Branch{half,left,right},previous)
234def take_right_done(-S:Data,-C:Type,half:U32,left:Column<S,C>,result:Column<S,C> & Maybe<&1,C>) -> Column<S,C> & Maybe<&1,C>:
235  match result:
236    case (right,previous):(Branch{half,left,right},previous)
237def take_branch(-S:Data,-C:Type,descend:Column<S,C> -> U32 -> Column<S,C> & Maybe<&1,C>,+half:U32,index:U32,left:Column<S,C>,right:Column<S,C>,first:Bool) -> Column<S,C> & Maybe<&1,C>:
238  match first:
239    case True{}:take_left_done(S,C,half,right,descend(left,index))
240    case False{}:take_right_done(S,C,half,left,descend(right,U32.sub(index,half)))
241def take_search(-S:Data,-C:Type,fuel:Nat,column:Column<S,C>,+index:U32) -> Column<S,C> & Maybe<&1,C>:
242  match fuel column:
243    case 0n column:(column,None{})
244    case 1n+_ Leaf{values,stamps}:take_leaf(S,C,values,stamps,index,U32.is_lt(index,8))
245    case 1n+rest Branch{+half,left,right}:take_branch(S,C,(column => index => take_search(S,C,rest,column,index)),half,index,left,right,U32.is_lt(index,half))
246def take(-S:Data,-C:Type,column:Column<S,C>,index:U32) -> Column<S,C> & Maybe<&1,C>:
247  take_search(S,C,15n,column,index)