1 module auxil.sizeindex;
2 
3 import std.range : isRandomAccessRange;
4 
5 struct SizeWindow
6 {
7 	/// lower boundary of the requested window in size units
8 	double start;
9 	/// length of the requested window in size units
10 	double length;
11 }
12 
13 struct IndexWindow
14 {
15 	/// lower boundary of the result window in index units
16 	size_t start;
17 	/// length of the result window in index units
18 	size_t length;
19 	/// lower boundary of the result window in size units
20 	double current;
21 }
22 
23 /// Given a range of items having size convert given indices to the 
24 /// cumulative size of all elements from the first one to elements with
25 /// given indices
26 ///
27 /// data given range those elements have some size
28 /// spacing is additional size for spacing between range elements
29 /// start index is the index of the first range element whose size we want to get
30 /// last index is the index of the last given range element whose size we want to get
31 /// start, finish are sizes of first and last elements
32 SizeWindow indexToSize(R)(R data, auto ref const(IndexWindow) iw)
33 	if (isRandomAccessRange!R)
34 {
35 	// current summary size
36 	double curr = 0;
37 	// the index of the current range element
38 	size_t idx;
39 	size_t last_index = iw.start + iw.length;
40 	// initial values of resulting sizes
41 	double start_size = 0;
42 
43 	// find for the summary size of the first given range element
44 	foreach(ref const e; data)
45 	{
46 		if (idx >= iw.start)
47 		{
48 			start_size = curr;
49 			idx++;
50 			curr += e;
51 			break;
52 		}
53 		idx++;
54 		curr += e;
55 	}
56 
57 	// start index is beyond range
58 	// set result size equal to total summary size
59 	if (iw.start >= data.length)
60 	{
61 		return SizeWindow(curr, 0);
62 	}
63 
64 	double last_size = 0;
65 	// find the size of the last element
66 	const low_boundary = idx;
67 	foreach(ref const e; data[low_boundary..$])
68 	{
69 		if (idx >= last_index)
70 		{
71 			last_size = curr;
72 			break;
73 		}
74 		idx++;
75 		curr += e;
76 	}
77 
78 	// if only the last index is beyond the given range
79 	// then only the weight of the last element is equal
80 	// to summary weight
81 	if (last_index >= data.length)
82 		last_size = curr;
83 
84 	return SizeWindow(start_size, last_size - start_size);
85 }
86 
87 /// Given range of elements having size convert `data` convert window in size units `sw`
88 /// to the result window in index units using current window in index units `iw`
89 ///
90 /// data the range of elements having size
91 /// sw the requested window in size units
92 /// iw the current window in index units
93 ///
94 /// returns the result window in index units
95 auto sizeToIndex(R)(R data, auto ref const(SizeWindow) sw, auto ref const(IndexWindow) iw)
96 	if (isRandomAccessRange!R)
97 {
98 	IndexWindow index;
99 	index.start = iw.start;
100 
101 	size_t idx = iw.start;
102 	double current_size = iw.current;
103 
104 	assert(sw.length >= 0);
105 
106 	// current weight is greater than start weight so
107 	// iterate over the range backward
108 	if (current_size > sw.start)
109 	{
110 		assert(0 <= idx && idx < data.length);
111 		for(; idx > 0; idx--)
112 		{
113 			// check if the current element has size lesser than
114 			// start size but the next element has size greater than
115 			// start size
116 			if (current_size - data[idx-1] <= sw.start &&
117 				current_size > sw.start)
118 			{
119 				index.start = idx-1;
120 				current_size -= data[idx-1];
121 				break;
122 			}
123 			else
124 			{
125 				current_size -= data[idx-1];
126 			}
127 		}
128 	}
129 	else
130 	{
131 		// current weight is equal to or lesser than start weight so
132 		// iterate over the range forward
133 		idx = index.start;
134 		for(; idx < data.length; idx++)
135 		{
136 			// check if the current element has cumulative size lesser than
137 			// start weight and the next element has cumulative size larger
138 			// than start weight
139 			if (current_size <= sw.start && current_size + data[idx] > sw.start)
140 			{
141 				index.start = idx;
142 				break;
143 			}
144 			else
145 			{
146 				current_size += data[idx];
147 			}
148 		}
149 		assert(idx <= data.length);
150 		assert(
151 			(current_size <= sw.start && idx == data.length) ||
152 			(current_size <= sw.start && (current_size + data[idx]) > sw.start) || 
153 			(idx == data.length /*&& e0 == E*/)
154 		);
155 	}
156 
157 	// if current index is out of give range
158 	// set start index equal to the last element
159 	// and length equals to zero, current size is equal
160 	// to total size of the range
161 	if (idx == data.length)
162 	{
163 		// start (and finish too) is beyond the last index
164 
165 		index.start = data.length;
166 		index.length = 0;
167 		index.current = current_size;
168 		return index;
169 	}
170 
171 	// we have found the first element and its
172 	// position both in size and index units 
173 	index.current = current_size;
174 
175 	// looking for the last element
176 
177 	// go to next element
178 	current_size += data[idx];
179 	idx++;
180 
181 	// find index of the element which cumulative size
182 	// equals to or larger than high boundary in size units
183 	for(; idx < data.length; idx++)
184 	{
185 		if (current_size >= sw.start + sw.length)
186 		{
187 			break;
188 		}
189 		else
190 			current_size += data[idx];
191 	}
192 
193 	index.length = idx - index.start;
194 	return index;
195 }
196 
197 private
198 {
199 	struct Record
200 	{
201 		ubyte[]     data;
202 		SizeWindow  size_window;
203 		IndexWindow input_idx, index_window;
204 	}
205 
206 	enum ubyte[] data = [30, 40, 50, 20];
207 
208 	import std.algorithm : sum;
209 	const double total_size = sum(data); // total size of all elements
210 
211 	auto sizeToIndexData = [
212 		//                     start size                      start index                    start index
213 		//                        ||        length             || length                       ||           length
214 		//                        \/           ||              || || current size              ||           || current size
215 		// window length is zero               \/              \/ \/ \/                        \/           \/           \/
216 		Record(data, SizeWindow(   0,           0), IndexWindow(0, 0, 0), IndexWindow(          0,           1,          0)),
217 		// window length equals to first element size minus one
218 		Record(data, SizeWindow(   0, data[0] - 1), IndexWindow(0, 0, 0), IndexWindow(          0,           1,          0)),
219 		// window length equals to first element size
220 		Record(data, SizeWindow(   0,     data[0]), IndexWindow(0, 0, 0), IndexWindow(          0,           1,          0)),
221 		// window length is larger than first element size
222 		// (but less than size of two first elements)
223 		Record(data, SizeWindow(   0, data[0] + 1), IndexWindow(0, 0, 0), IndexWindow(          0,           2,          0)),
224 		// window length is larger than total size of the range
225 		Record(data, SizeWindow(   0,        1e18), IndexWindow(0, 0, 0), IndexWindow(          0, data.length,          0)),
226 		// new size is larger than total size of the range
227 		Record(data, SizeWindow(1e18,          10), IndexWindow(0, 0, 0), IndexWindow(data.length,           0, total_size)),
228 		// new size is larger than total size of the range
229 		Record(data, SizeWindow(1e18,        1e18), IndexWindow(0, 0, 0), IndexWindow(data.length,           0, total_size)),
230 
231 		// Record(data, SizeWindow(   0,     data[2]), IndexWindow(2, 0,  70), IndexWindow(          2,           1,          0)),
232 		// Record(data, SizeWindow(   0,     data[2]), IndexWindow(3, 0, 120), IndexWindow(          2,           1,          0)),
233 	];
234 
235 	auto indexToSizeData = [
236 		//                     start size                      start index                    start index
237 		//                        ||        length             || length                       ||           length
238 		//                        \/           ||              || || current size              ||           || current size
239 		// window length is zero               \/              \/ \/ \/                        \/           \/           \/
240 		Record(data, SizeWindow(   0,     data[0]), IndexWindow(0, 0, 0), IndexWindow(          0,           1,          0)),
241 		Record(data, SizeWindow(   0,  total_size), IndexWindow(0, 0, 0), IndexWindow(          0, data.length,          0)),
242 		Record(data, SizeWindow(  70,     data[2]), IndexWindow(0, 0, 0), IndexWindow(          2,           1,          0)),
243 		Record(data, SizeWindow(total_size,     0), IndexWindow(0, 0, 0), IndexWindow(data.length,          10,          0)),
244 	];
245 }
246 
247 version(unittest)
248 {
249 	@(0, 1, 2, 3, 4, 5, 6)
250 	void testSizeToIndex(int id)
251 	{
252 		import unit_threaded;
253 
254 		with(sizeToIndexData[id])
255 		{
256 			auto index = sizeToIndex(data, size_window, input_idx);
257 
258 			index.start  .should.be == index_window.start;
259 			index.length .should.be == index_window.length;
260 			index.current.should.be  ~ index_window.current;
261 		}
262 	}
263 
264 	@(0, 1, 2, 3)
265 	void testIndexToSize(int id)
266 	{
267 		import unit_threaded;
268 
269 		with(indexToSizeData[id])
270 		{
271 			auto size = indexToSize(data, index_window);
272 
273 			size.start  .should.be == size_window.start;
274 			size.length .should.be == size_window.length;
275 		}
276 	}
277 }