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 }