ikod.containers.unrolledlist source code

1 module ikod.containers.unrolledlist;
2 
3 private import core.memory;
4 private import core.bitop;
5 private import core.exception;
6 
7 private import std.experimental.allocator;
8 private import std.experimental.allocator.mallocator : Mallocator;
9 private import std.experimental.allocator.gc_allocator;
10 private import std.experimental.logger;
11 private import std.format;
12 private import std.algorithm;
13 private import std.typecons;
14 private import std.compiler;
15 
16 private import automem.unique;
17 
18 private import ikod.containers.internal;
19 
20 ///
21 struct UnrolledList(T, Allocator = Mallocator, bool GCRangesAllowed = true)
22 {
23     invariant(_nodes_counter>=0 && _count>=0);
24 private:
25     alias allocator = Allocator.instance;
26     alias StoredT = StoredType!T;
27     enum  ItemsPerNode = 32; // can be variable maybe
28     enum  MaxRanges = 16;
29     enum  NewItemPosition = ItemsPerNode/2;
30     //
31     int                      _count;
32     int                      _nodes_counter;
33     Node*                    _first_node, _last_node;
34     short                    _constRanges_counter;
35     short                    _mutRanges_counter;
36     Impl!"mut"*[MaxRanges]   _mutRanges;
37     Impl!"const"*[MaxRanges] _constRanges;
38 
39     struct Node
40     {
41 
42         static assert(ItemsPerNode <= 32);
43 
44         uint                    _count;
45         uint                    _bitmap;
46         Node*                   _next_node;
47 
48         StoredT[ItemsPerNode]   _items;
49         Node*                   _prev_node;
50 
51         bool empty() @safe @nogc nothrow
52         {
53             return _bitmap == 0;
54         }
55         bool full() pure @safe @nogc nothrow
56         {
57             return _count == ItemsPerNode;
58         }
59         int count_free_high_bits()
60         in(_count>=0 && _count <= ItemsPerNode)
61         {
62             if ( _count == ItemsPerNode || test_bit(ItemsPerNode-1) )
63             {
64                 return 0;
65             }
66             if ( _count == 0 )
67             {
68                 return ItemsPerNode;
69             }
70             return(bsf(bitswap(_bitmap)));
71         }
72         int count_free_low_bits()
73         in(_count>=0 && _count <= ItemsPerNode)
74         {
75             if ( _count == ItemsPerNode || test_bit(0) )
76             {
77                 return 0;
78             }
79             if ( _count == 0 )
80             {
81                 return ItemsPerNode;
82             }
83             return(bsf(_bitmap));
84         }
85 
86         pragma(inline, true):
87         void mark_bit(size_t n) pure @safe @nogc
88         {
89             debug assert(n < ItemsPerNode, format("%s must be less than %d", n, ItemsPerNode));
90             _bitmap |= 1 << n;
91         }
92 
93         pragma(inline, true):
94         void clear_bit(size_t n) pure @safe @nogc nothrow
95         {
96             if ( n >= ItemsPerNode )
97             {
98                 debug throw new Exception("X");
99             }
100             assert(n < ItemsPerNode);
101             _bitmap &= uint.max ^ (1 << n);
102         }
103         pragma(inline, true):
104         int _hi_mask(int pos)
105         {
106             return _bitmap >> pos;
107         }
108         pragma(inline, true):
109         int _lo_mask(int pos)
110         {
111             return bitswap((((1<<pos) - 1) & _bitmap) << (int.sizeof*8-pos));
112         }
113         pragma(inline, true):
114         bool test_bit(size_t n) pure @safe @nogc nothrow
115         in(n<ItemsPerNode)
116         {
117             return cast(bool)(_bitmap & (1 << n));
118         }
119 
120         int translate_pos(int n) pure @safe @nogc nothrow
121         in( n < ItemsPerNode )
122         out(result; result == -1 || result < ItemsPerNode)
123         {
124             if (_count == ItemsPerNode )
125             {
126                 return cast(int)n;
127             }
128             if ( _count <= n )
129             {
130                 return -1;
131             }
132             int p = 0;
133             foreach(i; bsf(_bitmap)..ItemsPerNode)
134             {
135                 if ( !test_bit(i)) continue;
136                 if (p == n)
137                 {
138                     return i;
139                 }
140                 p++;
141             }
142             assert(0);
143         }
144     }
145 
146     Node* _free_list;
147     int   _free_list_count;
148 
149     Node* makeNode()
150     {
151         if ( _free_list_count > 0 )
152         {
153             Node* n = _free_list;
154             _free_list_count--;
155             _free_list = n._next_node;
156             n._prev_node = n._next_node = null;
157             n._count = n._bitmap = 0;
158             return n;
159         }
160         Node* node = make!Node(allocator);
161         static if ( UseGCRanges!(Allocator, T, GCRangesAllowed) ) {
162             () @trusted {
163                 GC.addRange(&node._items[0], T.sizeof * ItemsPerNode);
164             }();
165         }
166         return node;
167     }
168     void deallocNode(Node *p)
169     {
170         if (_free_list_count < 100)
171         {
172             _free_list_count++;
173             p._next_node = _free_list;
174             _free_list = p;
175             return;
176         }
177         () @trusted {
178             static if ( UseGCRanges!(Allocator,T, GCRangesAllowed) ) {
179                 GC.removeRange(&p._items[0]);
180             }
181             dispose(allocator, p);
182         }();
183     }
184     enum Sig
185     {
186         CLEAR = 0,
187         REMOVE,
188         INSERT
189     }
190     /++
191     +/
192     public struct Iterator(I)
193     {
194         private I*  _impl;
195         package this(Args...)(auto ref Args args, string file = __FILE__, int line = __LINE__) @trusted
196         {
197             import std.functional: forward;
198             import std.conv: emplace;
199             _impl = cast(typeof(_impl)) allocator.allocate((*_impl).sizeof);
200             emplace(_impl, forward!args);
201         }
202         this(this) @safe
203         {
204             if (!_impl)
205             {
206                 return;
207             }
208             auto _new_impl = () @trusted {return cast(typeof(_impl)) allocator.allocate((*_impl).sizeof);}();
209             _new_impl._list = null;
210             _new_impl._ptr = null;
211             *_new_impl = *_impl;
212             _impl = _new_impl;
213         }
214         ~this()
215         {
216             _impl.reset();
217             () @trusted {allocator.dispose(_impl);}();
218         }
219         /// test on emptiness
220         bool empty()
221         {
222             return _impl.empty();
223         }
224         /// return front element of iterator
225         auto front()
226         {
227             return _impl.front();
228         }
229         /// pop front element
230         void popFront()
231         {
232             _impl.popFront();
233         }
234         // save
235         auto save()
236         {
237             return this;
238         }
239         /// reset iterator
240         void reset()
241         {
242             _impl.reset();
243         }
244         int opApply(scope int delegate(T) dg)
245         {
246             int result = 0;
247             while(!empty)
248             {
249                 result = dg(front);
250                 popFront;
251                 if (result)
252                     break;
253             }
254             return result;
255         }
256         static if (is(I == Impl!"mut"))
257         {
258             void set(T v)
259             {
260                 auto list = _impl._list;
261                 assert(list._constRanges_counter == 0);
262                 auto node = _impl._currentNode;
263                 auto pos = _impl._currentNodeItemPosition;
264                 assert(node.test_bit(pos));
265                 node._items[pos] = v;
266             }
267             ///
268             /// remove current front Item from list
269             /// +--------------+-----------------------+-----------------+
270             /// | this         | other                 | list            |
271             /// | Iter         | Iter                  |                 |
272             /// +--------------+-----------------------+-----------------+
273             /// | remove list  | if points to removed: | free item;      |
274             /// | item;        |   mark invalid        | adjust counters |
275             /// | do popFront; | else:                 |                 |
276             /// |              |   adjust everything   |                 |
277             /// +--------------+-----------------------+-----------------+
278             ///
279             void remove()
280             {
281                 auto list = _impl._list;
282                 assert(list._constRanges_counter == 0);
283                 auto node = _impl._currentNode;
284                 auto pos = _impl._currentNodeItemPosition;
285                 //debug infof("before remove item: %d, node= %s, pos=%s", _impl._item, _impl._currentNode, _impl._currentNodeItemPosition);
286                 assert(node.test_bit(pos));
287                 if ( list._mutRanges_counter > 0) foreach(mr; list._mutRanges)
288                 {
289                     if (mr !is null && mr != this._impl)
290                     {
291                         // debug infof("callback %x", mr);
292                         mr.signal(Sig.REMOVE, _impl._item, node, _impl._currentNodeItem);
293                     }
294                 }
295                 list._count--;
296                 node._count--;
297                 //_impl._item--;
298                 _impl._end--;
299                 _impl._currentNodeItemsTotal--;
300                 node.clear_bit(pos);
301                 node._items[pos] = T.init;
302                 // debug infof("after remove item: %d", _impl._item);
303                 if ( _impl._item == _impl._end)
304                 {
305                     // debug info("become empty");
306                     _impl._empty = true;
307                     return;
308                 }
309                 if ( _impl._currentNodeItem == node._count )
310                 {
311                     // debug info("jump next node");
312                     node = node._next_node;
313                     while (node && node._count == 0 )
314                     {
315                         // debug info("jump next node");
316                         auto next_node = node._next_node;
317                         if ( list._constRanges_counter == 0 && list._mutRanges_counter == 1)
318                         {
319                             // safe to remove empty node
320                             if ( _impl._currentNode )
321                             {
322                                 _impl._currentNodeItemsTotal = _impl._currentNode._count;
323                             }
324                             if ( node == list._first_node )
325                             {
326                                 list._first_node = node._next_node;
327                             }
328                             if ( node == list._last_node )
329                             {
330                                 list._last_node = node._prev_node;
331                             }
332                             if ( node._prev_node )
333                             {
334                                 node._prev_node._next_node = node._next_node;
335                             }
336                             if ( node._next_node )
337                             {
338                                 node._next_node._prev_node = node._prev_node;
339                             }
340                             list._nodes_counter--;
341                             list.deallocNode(node);
342                         }
343                         node = next_node;
344                     }
345                     _impl._currentNodeItem = 0;
346                     _impl._currentNode = node;
347                     _impl._currentNodeItemsTotal = node._count;
348                 }
349                 _impl._currentNodeItemPosition = node.translate_pos(_impl._currentNodeItem);
350                 // debug infof("after remove item: %d, node= %s, pos=%s", _impl._item, _impl._currentNode, _impl._currentNodeItemPosition);
351             }
352             void insert(T v)
353             {
354                 auto list = _impl._list;
355                 Node* node = _impl._currentNode;
356                 int pos = _impl._currentNodeItemPosition;
357                 if ( list._mutRanges_counter > 0) foreach(mr; list._mutRanges)
358                 {
359                     if (mr !is null && mr != this._impl)
360                     {
361                         // debug infof("callback %x", mr);
362                         mr.signal(Sig.INSERT, _impl._item, node, _impl._currentNodeItem);
363                     }
364                 }
365                 if ( _impl._empty )
366                 {
367                     // debug info("insert to empty range");
368                     // debug infof("it_item: %s, it_end: %s, it_nodeItem: %s", _impl._item, _impl._end, _impl._currentNodeItem);
369                     // debug infof("list_end: %s", _impl._list._count);
370                     list._doRealPushBack(v);
371                     _impl._end++;
372                     _impl._item++;
373                     return;
374                 }
375                 _impl._end++;
376                 _impl._item++;
377                 assert(_impl._currentNodeItemPosition>=0);
378                 int lo_mask = node._lo_mask(pos);
379                 int hi_mask = node._hi_mask(pos);
380                 int lo_shift = lo_mask != 0 ? bsf(lo_mask ^ uint.max) :
381                                 pos == 0 ? uint.max : 0;
382                 int hi_shift = hi_mask == 0 ? uint.max : bsf(hi_mask ^ uint.max);
383                 auto lo_overflow = lo_shift < hi_shift  && lo_shift >= pos;
384                 auto hi_overflow = hi_shift <= lo_shift && pos + hi_shift >= ItemsPerNode;
385                 auto nodeItem = _impl._currentNodeItem;
386                 // debug infof("nodeItemPos: %s", pos);
387                 // debug infof("nodeItem: %s", nodeItem);
388                 // debug infof("bitmap %32.32b", node._bitmap);
389                 // debug infof("lomask %32.32b", lo_mask);
390                 // debug infof("himask %32.32b", hi_mask);
391                 // debug infof("lo_shift: %d, hi shift: %d", lo_shift, hi_shift);
392                 // debug infof("lo_over:  %s, hi overfl: %s", lo_overflow, hi_overflow);
393 
394                 _impl._list._doRealInsert(node, nodeItem, v);
395 
396                 if (!lo_overflow && !hi_overflow && lo_shift != -1)
397                 {
398                     _impl._currentNodeItem++;
399                     _impl._currentNodeItemsTotal++;
400                     if ( lo_shift >= hi_shift)
401                     {
402                         _impl._currentNodeItemPosition++;
403                     }
404                 }
405                 if ( hi_overflow )
406                 {
407                     _impl._currentNodeItem++;
408                     _impl._currentNodeItemPosition++;
409                 }
410                 if (_impl._currentNodeItem >= _impl._currentNodeItemsTotal)
411                 {
412                     _impl._currentNodeItem = 0;
413                     _impl._currentNode = _impl._currentNode._next_node;
414                     if ( _impl._currentNode )
415                     {
416                         _impl._currentNodeItemPosition = _impl._currentNode.translate_pos(0);
417                         _impl._currentNodeItemsTotal = _impl._currentNode._count;
418                     }
419                 }
420                 // debug infof("nodeItem: %s", _impl._currentNodeItem);
421             }
422         }
423     }
424 
425     template Impl(string kind) if (kind == "mut" || kind == "const")
426     {
427         alias ListType = typeof(this);
428         alias NodeType = ListType.Node;
429         struct Impl
430         {
431             alias T = typeof(this);
432             T**         _ptr;
433             ListType*   _list;
434             bool        _empty;
435             NodeType*   _currentNode;
436             int         _currentNodeItem;
437             int         _currentNodeItemPosition; // in bitmap
438             int         _currentNodeItemsTotal;
439             int         _item;
440             size_t      _end;
441 
442             static if (kind == "mut")
443             {
444                 private auto refc()
445                 {
446                     return &_list._mutRanges_counter;
447                 }
448                 private auto refptr(int i)
449                 {
450                     return &_list._mutRanges[i];
451                 }
452                 // Params: sig - signal type
453                 //         i - index of the item inside node
454                 //         n - node
455                 void signal(Sig sig, int item, Node* n, int nodeItem) nothrow
456                 {
457                     final switch(sig)
458                     {
459                         case Sig.CLEAR:
460                             _item = 0;
461                             _end = 0;
462                             _empty = true;
463                             _currentNode = null;
464                             _currentNodeItem = 0;
465                             return;
466                         case Sig.REMOVE:
467                             if ( _empty )
468                             {
469                                 // nothing to do
470                                 return;
471                             }
472                             // debug infof("signal remove: old item# %s, i'm at %s, end: %s", item, _item, _end);
473                             if ( item <= _item )
474                             {
475                                 //    ,-remove
476                                 // ___X___b....e___
477                                 _item--;
478                                 _end--;
479                                 if ( n != _currentNode )
480                                 {
481                                     return;
482                                 }
483                                 _currentNodeItem--;
484                                 _currentNodeItemsTotal--;
485                                 if (_currentNodeItemsTotal == 0)
486                                 {
487                                     // goto next node
488                                     while(n && n._next_node && n._next_node._count == 0)
489                                     {
490                                         n = n._next_node;
491                                     }
492                                     n = n._next_node;
493                                     _currentNode = n;
494                                     _currentNodeItem = -1;
495                                     //_currentNodeItemPosition = cast(ubyte)bsf(n._bitmap);
496                                     if ( n ) _currentNodeItemsTotal = cast(short)n._count;
497                                 }
498                                 return;
499                             }
500                             if ( _item <= item && item < _end )
501                             {
502                                 //    ,-remove
503                                 // _b.X....e___
504                                 _end--;
505                                 if ( n != _currentNode )
506                                 {
507                                     return;
508                                 }
509                                 _currentNodeItemsTotal--;
510                                 return;
511                             }
512                             //           ,-remove
513                             // _b.....e__X__
514                             // nothing to do
515                             break;
516                         case Sig.INSERT:
517                             // debug infof("signal insert: old item# %s, i'm at %s, end: %s", item, _item, _end);
518                             if ( item >= _end)
519                             {
520                                 // debug info("insert after end");
521                                 return;
522                             }
523                             if ( item <= _item )
524                             {
525                                 _item++;
526                                 if (n == _currentNode)
527                                 {
528                                     _currentNodeItem++;
529                                 }
530                             }
531                             if (n !is null && n == _currentNode)
532                             {
533                                 auto pos   = n.translate_pos(nodeItem);
534 
535                                 int lo_mask = n._lo_mask(pos);
536                                 int hi_mask = n._hi_mask(pos);
537 
538                                 int lo_shift = lo_mask != 0 ? bsf(lo_mask ^ uint.max) :
539                                                 pos == 0 ? uint.max : 0;
540                                 int hi_shift = hi_mask == 0 ? uint.max : bsf(hi_mask ^ uint.max);
541                                 auto lo_overflow = lo_shift < hi_shift  && lo_shift >= pos;
542                                 auto hi_overflow = hi_shift <= lo_shift && pos + hi_shift >= ItemsPerNode;
543                                 // debug infof("lomask %32.32b", lo_mask);
544                                 // debug infof("himask %32.32b", hi_mask);
545                                 // debug infof("lo_shift: %d, hi shift: %d", lo_shift, hi_shift);
546                                 // debug infof("lo_over:  %s, hi overfl: %s", lo_overflow, hi_overflow);
547 
548 
549                                 if ( lo_overflow && _currentNodeItemPosition == 0) 
550                                 {
551                                     // debug info("going to move left");
552                                     // this item becomes highest item in the prev node
553                                     Node* prev_node = n._prev_node;
554                                     int prev_pos = prev_node.translate_pos(prev_node._count-1)+1;
555                                     // debug infof("my new position: %d", prev_pos);
556                                     _currentNode = prev_node;
557                                     _currentNodeItem = _currentNode._count;
558                                     _currentNodeItemsTotal = _currentNode._count+1;
559                                     _currentNodeItemPosition = prev_pos;
560                                 }
561                                 else
562                                 {
563                                     int p = n.translate_pos(nodeItem);
564                                     if ( (_currentNodeItemPosition < p) && (lo_shift < hi_shift))
565                                     {
566                                         // we might be affectd by the left shift
567                                         // debug infof("my pos = %s, his pos = %s", _currentNodeItemPosition, p);
568                                         if ( p - _currentNodeItemPosition < lo_shift )
569                                         {
570                                             // we shifted left
571                                             _currentNodeItemPosition--;
572                                             assert(_currentNodeItemPosition>=0);
573                                         }
574                                     }
575                                     if (!hi_overflow)
576                                     {
577                                         _currentNodeItemsTotal = _currentNode._count+1;
578                                     }
579                                 }
580                                 _end++;
581                                 // debug infof("_item: %d, _nodeItem: %d, _currentNodeItemsTotal: %s", _item, _currentNodeItem, _currentNodeItemsTotal);
582                                 return;
583                             }
584                             if ( n !is null && n == _currentNode._next_node )
585                             {
586                                 n = _currentNode._next_node;
587                                 auto pos   = n.translate_pos(nodeItem);
588 
589                                 int lo_mask = n._lo_mask(pos);
590                                 int hi_mask = n._hi_mask(pos);
591 
592                                 int lo_shift = lo_mask != 0 ? bsf(lo_mask ^ uint.max) :
593                                                 pos == 0 ? uint.max : 0;
594                                 int hi_shift = hi_mask == 0 ? -1 : bsf(hi_mask ^ uint.max);
595                                 auto lo_overflow = lo_shift < hi_shift  && lo_shift >= pos;
596                                 auto hi_overflow = hi_shift <= lo_shift && pos + hi_shift >= ItemsPerNode;
597 
598                                 // debug infof("lomask2 %32.32b", lo_mask);
599                                 // debug infof("himask2 %32.32b", hi_mask);
600                                 // debug infof("lo_shift2: %d, hi shift2: %d", lo_shift, hi_shift);
601                                 // debug infof("lo_over2:  %s, hi overfl2: %s", lo_overflow, hi_overflow);
602 
603                                 if ( (lo_overflow || lo_shift==-1) && _currentNode.count_free_high_bits()>0)
604                                 {
605                                     // debug infof("will overflow to me, new _currentNodeItemsTotal: %s", _currentNodeItemsTotal+1);
606                                     // overflow to my node from
607                                     _currentNodeItemsTotal++;
608                                 }
609                                 _end++;
610                                 return;
611                             }
612                             _end++;
613                             // debug infof("signal insert: new item# %d, new end: %d", item, _end);
614                             break;
615                     }
616                 }
617             }
618             else
619             {
620                 private auto refc()
621                 {
622                     return &_list._constRanges_counter;
623                 }
624                 private auto refptr(int i)
625                 {
626                     return &_list._constRanges[i];
627                 }
628             }
629         public:
630             this(T** p, ListType* list = null, int item = 0, int end = 0, NodeType* node = null, int nodeItem = 0) @nogc
631             {
632                 _ptr = p;
633                 if (p)
634                 {
635                     *_ptr = &this;
636                 }
637                 _list = list;
638                 _item = item;
639                 _end = end;
640                 _currentNode = node;
641                 _currentNodeItem = nodeItem;
642                 if (node)
643                 {
644                     _currentNodeItemsTotal = node._count;
645                     _currentNodeItemPosition = node.translate_pos(nodeItem);
646                 }
647             }
648             /// create and register another instance of stable range
649             this(this)
650             {
651                 if ( !_list || !_ptr )
652                 {
653                     return;
654                 }
655                 for(auto i=0; i<MaxRanges; i++)
656                 {
657                     if ( *refptr(i) is null )
658                     {
659                         (*refc)++;
660                         *refptr(i) = &this;
661                         _ptr = refptr(i);
662                         return;
663                     }
664                 }
665                 assert(0, "Too much active stable ranges");
666             }
667             ~this() @safe
668             {
669                 if ( _list !is null )
670                 {
671                     (*refc)--;
672                     assert((*refc) >= 0);
673                 }
674                 if (_ptr !is null)
675                 {
676                     *_ptr = null;
677                 }
678             }
679             auto opAssign(V)(auto ref V other) if (is(V==typeof(this)))
680             {
681                 if ( other is this )
682                 {
683                     return;
684                 }
685                 if ( _list && other._list != _list )
686                 {
687                     reset();
688                 }
689                 if ( _ptr is null && other._list !is null )
690                 {
691                     // register
692                     assert(_list is null);
693                     _list = other._list;
694                     for(auto i=0; i<MaxRanges; i++)
695                     {
696                         if ( *refptr(i) is null )
697                         {
698                             (*refc)++;
699                             assert(*refc < _list.MaxRanges);
700                             *refptr(i) = &this;
701                             _ptr = refptr(i);
702                             break;
703                         }
704                     }
705                 }
706                 _item = other._item;
707                 _end = other._end;
708                 _currentNode = other._currentNode;
709                 _currentNodeItem = other._currentNodeItem;
710                 _currentNodeItemsTotal = other._currentNodeItemsTotal;
711                 _currentNodeItemPosition = other._currentNodeItemPosition;
712                 _empty = other._empty;
713             }
714             void reset()
715             {
716                 if (_list is null || _ptr is null )
717                 {
718                     assert(_list is null && _ptr is null);
719                     return;
720                 }
721                 assert(_list !is null);
722                 (*refc)--;
723                 assert(*refc >= 0);
724                 if ( _ptr !is null )
725                 {
726                     assert(*_ptr == &this);
727                     *_ptr = null;
728                     _ptr = null;
729                 }
730                 _list = null;
731             }
732             auto front()
733             {
734                 assert(_list && _currentNode);
735                 auto n = _currentNode;
736                 auto p = _currentNodeItemPosition;
737                 assert(_item >= 0);
738                 assert(n.test_bit(p), "You tried to access empty item.");
739                 return n._items[p];
740             }
741             void popFront()
742             {
743                 // if ( !_list || !_ptr )
744                 // {
745                 //     return;
746                 // }
747                 // debug infof("popping from item %s, nodeItem: %s", _item, _currentNodeItem);
748                 _item++;
749                 if ( _item >= _end )
750                 {
751                     _empty = true;
752                     static if (kind == "const")
753                     {
754                         reset();
755                     }
756                     return;
757                 }
758                 auto n = _currentNode;
759                 if ( !n )
760                 {
761                     debug throw new Exception("y");
762                 }
763                 assert(n);
764                 _currentNodeItem++;
765                 // debug infof("_item=%s, _end=%s, _currentnodeItem now =%s, _currentNodeItems = %s", _item, _end, _currentNodeItem, _currentNodeItemsTotal);
766                 if (  _currentNodeItem == _currentNodeItemsTotal )
767                 {
768                     // debug infof("jump next node");
769                     // goto next node
770                     while(n && n._next_node && n._next_node._count == 0)
771                     {
772                         //debug infof("skip empty node");
773                         n = n._next_node;
774                     }
775                     n = n._next_node;
776                     _currentNode = n;
777                     _currentNodeItem = 0;
778                     _currentNodeItemPosition = cast(ubyte)bsf(n._bitmap);
779                     _currentNodeItemsTotal = cast(short)n._count;
780                 }
781                 else
782                 {
783                     if ( n._count == ItemsPerNode )
784                     {   // full node, each token position equals it's number
785                         _currentNodeItemPosition = _currentNodeItem;
786                     }
787                     else
788                     {
789                         // find next non-zero bit in bitmask
790                         auto m = 0xffff_ffff ^ ((1<<(_currentNodeItemPosition+1)) - 1);
791                         // debug infof("m: %32.32b", bitswap(m));
792                         // debug infof("b: %32.32b", bitswap(n._bitmap));
793                         // debug infof("r: %32.32b", bitswap(n._bitmap&m));
794                         _currentNodeItemPosition = cast(ubyte)bsf(n._bitmap & m);
795                         // debug infof("nodeItem: %s, cp: %d, itemsTotal: %s", _currentNodeItem, _currentNodeItemPosition, _currentNodeItemsTotal);
796                     }
797                 }
798             }
799             bool empty()
800             {
801                 return _empty;
802             }
803         }
804     }
805 
806 
807 public:
808     auto makeRange(string R)(int start=0, int end=int.max) @safe
809     {
810         static if (R == "mut")
811         {
812             alias _rCounter = _mutRanges_counter;
813             alias _rArray = _mutRanges;
814             alias T = Impl!"mut";
815         }
816         else static if (R == "const")
817         {
818             alias _rCounter = _constRanges_counter;
819             alias _rArray = _constRanges;
820             alias T = Impl!"const";
821         }
822         else
823         {
824             static assert(0, "Wrong type");
825         }
826         //
827 
828 
829         T** slot;
830         assert(_rCounter < MaxRanges-1);
831         for(auto i=0; i<MaxRanges; i++)
832         {
833             if ( _rArray[i] is null )
834             {
835                 slot = &_rArray[i];
836                 break;
837             }
838         }
839         if ( slot is null )
840         {
841             assert(0, "Too much active ranges");
842         }
843 
844         _rCounter++;
845 
846         auto result = Iterator!T(slot, &this);
847         if ( _count == 0)
848         {
849             // empty list
850             result._impl._empty = true;
851             return result;
852         }
853 
854         if ( start < 0 )
855         {
856             start = _count + start;
857         }
858         if ( end < 0 )
859         {
860             end = _count + end;
861         }
862         // if end greater than list length - use list length
863         if ( end > _count )
864         {
865             end = _count;
866         }
867         if ( start == end )
868         {
869             result._impl._empty = true;
870             return result;
871         }
872         assert(start < _count && end <= _count && start < end);
873         auto node = _first_node;
874         auto item = 0;
875         auto items = end - start;
876         auto nodeItem = 0;
877         while( node !is null && item + node._count <= start )
878         {
879             item += node._count;
880             node = node._next_node;
881         }
882         nodeItem = start - item;
883         result._impl._currentNode = node;
884         result._impl._currentNodeItem = nodeItem;
885         result._impl._currentNodeItemPosition = node.translate_pos(nodeItem);
886         result._impl._currentNodeItemsTotal = node._count;
887         result._impl._item = start;
888         result._impl._end = end;
889         return result;
890     }
891     alias mutRange = makeRange!("mut");
892     /++
893     +   Create new const range. Const range preserve it's correctness by
894     +   preventing you from any list mutations.
895     +
896     +   const range is `value `type` - assignment and initializations create its copy.
897     +
898     +   const range can't make warranties on it's correctnes if you make any list mutation.
899     +   So, while you have any active const range you can't make any mutation to list. At any
900     +   atempt to remove, insert or clear list while const range active you'll get AssertionError.
901     +   To make constRange inactive you have to consume it to the end or call `reset` on it.
902     +
903     +   Params:
904     +   start = start position in list (default value - head of the list)
905     +   end = end positions in list (default value - end of the list)
906     + --------------------------------------------------------------------
907     +     UnrolledList!int l;
908     + 
909     +     foreach(i; 0..50)
910     +     {
911     +         l.pushBack(i);
912     +     }
913     +     auto r = l.constRange();
914     +     assert(equal(r, iota(50)));   // copy of range created 
915     +     assertThrown!AssertError(l.clear); // r still active
916     +     assertThrown!AssertError(l.remove(0)); // r still active
917     +     assertThrown!AssertError(l.pushBack(0)); // r still active
918     +     assertThrown!AssertError(l.pushFront(0)); // r still active
919     +     assertThrown!AssertError(l.popBack()); // r still active
920     +     assertThrown!AssertError(l.popFront()); // r still active
921     +     r.reset();    // deactivate r
922     +     l.clear();    // it is safe to clear list
923     + -------------------------------------------------------------------
924     +/
925     alias constRange = makeRange!"const";
926 
927     this(this)
928     {
929         auto n = _first_node;
930         _first_node = _last_node = null;
931         _count = 0;
932 
933         _constRanges_counter = 0;
934         _constRanges = _constRanges.init;
935 
936         _mutRanges_counter = 0;
937         _mutRanges = _mutRanges.init;
938 
939         _free_list = null;
940         _free_list_count = 0;
941 
942         while(n)
943         {
944             auto nn = n._next_node;
945             for(auto i=0; i<ItemsPerNode; i++)
946             {
947                 if ( n.test_bit(i) )
948                 {
949                     pushBack(n._items[i]);
950                 }
951             }
952             n = nn;
953         }
954     }
955 
956     ~this()
957     {
958         foreach(r; _constRanges)
959         {
960             if ( r !is null )
961             {
962                 r._empty = true;
963                 r._list = null;
964                 r._ptr = null;
965             }
966         }
967         foreach(r; _mutRanges)
968         {
969             if ( r !is null )
970             {
971                 r._empty = true;
972                 r._list = null;
973                 r._ptr = null;
974             }
975         }
976         auto n = _first_node;
977         while(n)
978         {
979             auto nn = n._next_node;
980             deallocNode(n);
981             n = nn;
982             _nodes_counter--;
983         }
984 
985         while(_free_list_count)
986         {
987             Node* p = _free_list;
988             _free_list = p._next_node;
989             _free_list_count--;
990             () @trusted {
991                 static if ( UseGCRanges!(Allocator,T, GCRangesAllowed) ) {
992                     GC.removeRange(&p._items[0]);
993                 }
994                 dispose(allocator, p);
995             }();
996         }
997     }
998 
999     auto dump()
1000     {
1001         string[] s;
1002         s ~= "<<<";
1003         s ~= "length: %d".format(_count);
1004         s ~= "nodes: %d".format(_nodes_counter);
1005         s ~= "density: %f".format(_nodes_counter>0?1e0*_count/_nodes_counter/ItemsPerNode:0e0);
1006         s ~= "first_node: %x".format(_first_node);
1007         s ~= "last_node: %x".format(_last_node);
1008         auto n = _first_node;
1009         while(n !is null)
1010         {
1011             s ~= "Page %2.2d nodes, %032b bitmap(swapped)".format(n._count, bitswap(n._bitmap));
1012             s ~= "               0....o....1....o....2....o....3.";
1013             s ~= "Prev page ptr: %x".format(n._prev_node);
1014             s ~= "Next page ptr: %x".format(n._next_node);
1015             s ~= "%s".format(n._items);
1016             s ~= "---";
1017             n = n._next_node;
1018         }
1019         s ~= ">>>";
1020         return s;
1021     }
1022 
1023     void clear()
1024     {
1025         assert(_constRanges_counter == 0, "You can't call mutating methods while constRange active. Use stableRange");
1026         if (_mutRanges_counter)
1027             sendnotify(Sig.CLEAR, 0, null, 0);
1028         auto n = _first_node;
1029         while(n)
1030         {
1031             auto nn = n._next_node;
1032             deallocNode(n);
1033             _nodes_counter--;
1034             n = nn;
1035         }
1036         _count = 0;
1037         _first_node = _last_node = null;
1038     }
1039 
1040     private auto _node_and_index(size_t i)
1041         in(i<_count)
1042         out(r; r.node !is null && r.index < ItemsPerNode)
1043         do
1044     {
1045         Node *n;
1046         // select iteration direcion
1047         if ( i > ItemsPerNode && i > _count /2 )
1048         {
1049             // iterate from end to beg
1050             n = _last_node;
1051             auto b = _count;
1052             while ( b - n._count > i )
1053             {
1054                 b -= n._count;
1055                 n = n._prev_node;
1056             }
1057             i = i - b + n._count;
1058         }
1059         else
1060         {
1061             // iterate from beg to end
1062             n = _first_node;
1063             while(i >= n._count)
1064             {
1065                 i -= n._count;
1066                 n = n._next_node;
1067             }
1068         }
1069         return Tuple!(Node*, "node", int, "index")(n, cast(int)i);
1070     }
1071     /++
1072         Get item at some position.
1073 
1074         To be @nogc it do not throw, but return tuple with bool `ok`member.
1075 
1076         Params:
1077         i = position
1078         Returns:
1079         tuple with succes indicator and value
1080         -------------------------------------
1081         UnrolledList!int l;
1082         foreach(i; 0..50)
1083         {
1084             l.pushBack(i);
1085         }
1086         auto v = l.get(25);
1087         assert(v.ok);
1088         assert(v.value == 25);
1089         -------------------------------------
1090     +/
1091     auto get(size_t i)
1092     {
1093         if (_count == 0 || i >= _count )
1094         {
1095             return Tuple!(bool, "ok", StoredT, "value")(false, T.init);
1096         }
1097         auto ni = _node_and_index(i);
1098         auto n = ni.node;
1099         auto pos = n.translate_pos(ni.index);
1100         assert(n.test_bit(pos));
1101         return Tuple!(bool, "ok", StoredT, "value")(true, n._items[pos]);
1102     }
1103     // O(N)
1104     auto opIndex(size_t i)
1105     {
1106         auto v = get(i);
1107         if ( !v.ok )
1108         {
1109             throw new RangeError("index %d out of range".format(i));
1110         }
1111         return v.value;
1112     }
1113     // O(N)
1114     void opAssign(ref typeof(this) other)
1115     {
1116         if (other is this)
1117         {
1118             return;
1119         }
1120         clear();
1121         auto n = other._first_node;
1122         while(n)
1123         {
1124             auto nn = n._next_node;
1125             for(auto i=0; i<ItemsPerNode; i++)
1126             {
1127                 if ( n.test_bit(i) )
1128                 {
1129                     pushBack(n._items[i]);
1130                 }
1131             }
1132             n = nn;
1133         }
1134     }
1135     // O(N)
1136     void opIndexAssign(V)(V v, size_t i)
1137     {
1138         if (_count == 0 || i >= _count )
1139         {
1140             throw new RangeError("index %d out of range".format(i));
1141         }
1142         auto ni = _node_and_index(i);
1143         auto n = ni.node;
1144         auto pos = n.translate_pos(ni.index);
1145         assert(n.test_bit(pos));
1146         n._items[pos] = v;
1147     }
1148     // O(1)
1149     bool empty()
1150     {
1151         return _count == 0;
1152     }
1153     // O(1)
1154     auto length() pure @safe @nogc nothrow
1155     {
1156         return _count;
1157     }
1158     // O(1)
1159     auto front()
1160     {
1161         assert(_count > 0, "Attempting to fetch the front of an empty list");
1162         auto n = _first_node;
1163         while(n && n._count == 0)
1164         {
1165             n = n._next_node;
1166         }
1167         auto p = bsf(n._bitmap);
1168         return n._items[p];
1169     }
1170     /++
1171     + Get last item. O(1)
1172     +
1173     + Returns: last item.
1174     + Throws: AssertError when list is empty.
1175     +/
1176     auto back()
1177     {
1178         assert(_count > 0, "Attempting to fetch the front of an empty list");
1179         auto n = _last_node;
1180         while(n && n._count == 0)
1181         {
1182             n = n._prev_node;
1183         }
1184         auto p = bsr(n._bitmap);
1185         return n._items[p];
1186     }
1187     ///
1188     /// send notifications to mutrange's
1189     /// Params: 
1190     ///  s=    - Sig type
1191     ///  item= - number of the item in the list, where we place new item(this would be its number).
1192     ///  n=    - current node (where we hope to place new item)
1193     ///  nodeItem= - number of the new item for this node
1194     //
1195     private void sendnotify(Sig s, int item, Node* n, int nodeItem) pure @nogc @safe nothrow
1196     {
1197         auto mcs = _mutRanges_counter;
1198         for(int mr; mcs>0 && mr < MaxRanges; mr++)
1199         {
1200             if (_mutRanges[mr] !is null)
1201             {
1202                 _mutRanges[mr].signal(s, item, n, nodeItem);
1203                 mcs--;
1204             }
1205         }
1206     }
1207     /++
1208     + Append item to the list. O(1)
1209     +
1210     + Throws: AssertError if any const range is registered.
1211     +/
1212     void pushBack(V)(V v)
1213     {
1214         assert(_constRanges_counter == 0, "You can't mutate list while there are active const ranges");
1215         if (_mutRanges_counter>0)
1216         {
1217             sendnotify(Sig.INSERT, _count, _last_node, _last_node?_last_node._count:-1);
1218         }
1219         _doRealPushBack(v);
1220     }
1221     /++
1222     + Prepend list with item v. O(1)
1223     +
1224     + Throws: AssertError if any const range is registered.
1225     +/
1226     void pushFront(V)(V v)
1227     {
1228         assert(_constRanges_counter == 0, "You can't mutate list while there are active const ranges");
1229         if (_mutRanges_counter)
1230             sendnotify(Sig.INSERT, 0, _first_node, 0);
1231         _doRealInsert(_first_node, 0, v);
1232     }
1233     /++
1234     + Pop first item from the list. O(1)
1235     +
1236     + No action if list is empty.
1237     +
1238     + Throws: AssertError if any const range is registered.
1239     +/
1240     void popFront()
1241     {
1242         assert(_constRanges_counter == 0, "You can't mutate list while there are active const ranges");
1243         if ( _count == 0 )
1244         {
1245             return;
1246         }
1247         assert(_first_node);
1248         auto node = _first_node;
1249         while(node._count == 0)
1250         {
1251             node = node._next_node;
1252         }
1253         if (_mutRanges_counter>0)
1254             sendnotify(Sig.REMOVE, 0, node, 0);
1255         _count--;
1256         auto pos = bsf(node._bitmap);
1257         node._count--;
1258         node.clear_bit(pos);
1259         node._items[pos] = T.init;
1260         if (_first_node._count == 0)
1261         {
1262             // release this page
1263             auto n = _first_node;
1264             _first_node = n._next_node;
1265             if ( _first_node is null )
1266             {
1267                 _last_node = null;
1268             }
1269             else
1270             {
1271                 _first_node._prev_node = null;
1272             }
1273             deallocNode(n);
1274             _nodes_counter--;
1275         }
1276     }
1277     /++
1278     + Pop last item from the list. O(1)
1279     +
1280     + No action if list is empty.
1281     +
1282     + Throws: AssertError if any const range is registered.
1283     +/
1284     void popBack()
1285     {
1286         assert(_constRanges_counter == 0, "You can't mutate list while there are active const ranges");
1287         if ( _count == 0 )
1288         {
1289             return;
1290         }
1291         if (_mutRanges_counter>0)
1292             sendnotify(Sig.REMOVE, _count - 1, _last_node, _last_node._count - 1);
1293         _count--;
1294         auto node = _last_node;
1295         while(node && node._count == 0)
1296         {
1297             node = node._prev_node;
1298         }
1299         auto pos = bsr(node._bitmap);
1300         node._count--;
1301         assert(node._count>=0 && node._count < ItemsPerNode);
1302         node.clear_bit(pos);
1303         node._items[pos] = T.init;
1304         if (_last_node._count == 0 && _mutRanges_counter == 0)
1305         {
1306             // release this node
1307             auto n = _last_node;
1308             _last_node._next_node = null;
1309             _last_node = n._prev_node;
1310             if ( _last_node is null )
1311             {
1312                 _first_node = null;
1313             }
1314             else
1315             {
1316                 _last_node._next_node = null;
1317             }
1318             deallocNode(n);
1319             _nodes_counter--;
1320         }
1321     }
1322     /++
1323     + Remove item from the list by item index. O(N)
1324     +
1325     + No action if list is empty.
1326     + Returns: True if item were removed.
1327     + Throws: AssertError if any const range is registered.
1328     +/
1329     bool remove(int i)
1330     {
1331         assert(_constRanges_counter == 0, "You can't mutate list while there are active const ranges");
1332         if ( i >= _count )
1333         {
1334             return false;
1335         }
1336         if ( i == 0 )
1337         {
1338             popFront();
1339             return true;
1340         }
1341         if ( i == _count - 1)
1342         {
1343             popBack();
1344             return true;
1345         }
1346         auto ni = _node_and_index(i);
1347         auto index = ni.index;
1348         auto node  = ni.node;
1349         auto pos   = node.translate_pos(index);
1350         int mcs = _mutRanges_counter;
1351         for(int mr; mcs>0 && mr < MaxRanges; mr++)
1352         {
1353             if (_mutRanges[mr] !is null)
1354             {
1355                 _mutRanges[mr].signal(Sig.REMOVE, i, node, index);
1356                 mcs--;
1357             }
1358         }
1359     _count--;
1360         node._count--;
1361         node.clear_bit(pos);
1362         node._items[pos] = T.init;
1363         return true;
1364     }
1365     pragma(inline, true):
1366     private void _doRealPushBack(V)(V v)
1367     {
1368         int pos;
1369         Node* node = _last_node;
1370         while( node && node._count == 0 && node._prev_node )
1371         {
1372             node = node._prev_node;
1373         }
1374 
1375         if ( node && !node.test_bit(ItemsPerNode-1))
1376         {
1377             pos = node._bitmap ? bsr(node._bitmap) + 1 : 0;
1378         }
1379         else
1380         {
1381             node = makeNode();
1382             if ( !_last_node )
1383             {
1384                 assert(!_first_node);
1385                 _first_node = _last_node = node;
1386             }
1387             else
1388             {
1389                 node._prev_node = _last_node;
1390                 _last_node._next_node = node;
1391                 _last_node = node;
1392             }
1393             _nodes_counter++;
1394             pos = 0;
1395         }
1396         node._count++;
1397         // take most significant free bit
1398         node.mark_bit(pos);
1399         node._items[pos] = v;
1400         _count++;
1401     }
1402     private bool _doRealInsert(V)(Node* node, int index, V v)
1403     {
1404         int pos;
1405         if (node is null)
1406         {
1407             assert(_first_node is null && _last_node is null, "head and tail must be null");
1408             node = makeNode();
1409             pos = NewItemPosition;
1410             _first_node = _last_node = node;
1411             _nodes_counter++;
1412         }
1413         else
1414         {
1415             pos   = node.translate_pos(index);
1416         }
1417 
1418         int lo_mask = node._lo_mask(pos);
1419         int hi_mask = node._hi_mask(pos);
1420 
1421         int lo_shift = lo_mask != 0 ? bsf(lo_mask ^ uint.max) :
1422                         pos == 0 ? -1 : 0;
1423         int hi_shift = hi_mask == 0 ? uint.max : bsf(hi_mask ^ uint.max);
1424         auto lo_overflow = lo_shift < hi_shift  && lo_shift >= pos;
1425         auto hi_overflow = hi_shift <= lo_shift && pos + hi_shift >= ItemsPerNode;
1426 
1427         // debug infof("itemPos: %s", pos);
1428         // debug infof("index: %s", index);
1429         // debug infof("bitmap %32.32b", node._bitmap);
1430         // debug infof("lomask %32.32b", lo_mask);
1431         // debug infof("himask %32.32b", hi_mask);
1432         // debug infof("lo_shift: %d, hi shift: %d", lo_shift, hi_shift);
1433         // debug infof("lo_over:  %s, hi overfl: %s", lo_overflow, hi_overflow);
1434         if ( lo_overflow )
1435         {
1436             debug(ikodcontainers) tracef("low overflow");
1437             if ( node._prev_node
1438                 && node._prev_node.count_free_high_bits() > 0 )
1439             {
1440                 Node* n = node._prev_node;
1441                 debug(ikodcontainers) tracef("low overflow to existent node with %s free high bits", n.count_free_high_bits());
1442                 // find free bit _0000100000^ _111v1111^
1443                 int fp = n._bitmap ? bsf(bitswap(n._bitmap)) : NewItemPosition;
1444                 debug(ikodcontainers) tracef("overflow to %s", ItemsPerNode - fp);
1445                 int p = ItemsPerNode - fp;
1446                 n._count++;
1447                 n.mark_bit(p);
1448                 n._items[p] = node._items[0];
1449                 // now do shift left for lo_shift-1
1450                 for(int i=0;i < lo_shift - 1; i++)
1451                 {
1452                     node._items[i] = node._items[i+1];
1453                 }
1454                 node._items[index-1] = v;
1455                 _count++;
1456                 return true;
1457             }
1458             else
1459             {
1460                 debug(ikodcontainers) tracef("low overflow to new node");
1461                 auto new_node = makeNode();
1462                 auto new_p = NewItemPosition;
1463                 new_node.mark_bit(new_p);
1464                 new_node._items[new_p] = node._items[0];
1465                 new_node._count = 1;
1466                 for(int i=0;i < lo_shift - 1; i++)
1467                 {
1468                     node._items[i] = node._items[i+1];
1469                 }
1470                 node._items[index-1] = v;
1471                 if ( _first_node == node )
1472                 {
1473                     _first_node = new_node;
1474                 }
1475                 else
1476                 {
1477                     node._prev_node._next_node = new_node;
1478                     new_node._prev_node = node._prev_node;
1479                 }
1480                 new_node._next_node = node;
1481                 node._prev_node = new_node;
1482                 _count++;
1483                 _nodes_counter++;
1484                 return true;
1485             }
1486         }
1487         if ( hi_overflow )
1488         {
1489             debug(ikodcontainers) tracef("high overflow");
1490             if (node._next_node && node._next_node.count_free_low_bits() > 0)
1491             {
1492                 debug(ikodcontainers) tracef("high overflow to next existent node");
1493                 auto next_node = node._next_node;
1494                 auto next_node_pos = next_node._bitmap ? bsf(next_node._bitmap)-1 : NewItemPosition;
1495                 next_node.mark_bit(next_node_pos);
1496                 next_node._count++;
1497                 next_node._items[next_node_pos] = node._items[ItemsPerNode-1];
1498                 for(auto s=hi_shift; s>0; s--)
1499                 {
1500                     node._items[pos+s-1] = node._items[pos+s-2];
1501                 }
1502                 node._items[pos] = v;
1503                 _count++;
1504                 return true;
1505             }
1506             else
1507             {
1508                 debug(ikodcontainers) tracef("high overflow to new node");
1509                 auto new_node = makeNode();
1510                 auto new_p = NewItemPosition;
1511                 new_node.mark_bit(new_p);
1512                 new_node._items[new_p] = node._items[ItemsPerNode-1];
1513                 new_node._count++;
1514                 for(auto s=hi_shift; s>0; s--)
1515                 {
1516                     node._items[pos+s-1] = node._items[pos+s-2];
1517                 }
1518                 node._items[pos] = v;
1519                 // link right
1520                 if ( _last_node == node)
1521                 {
1522                     _last_node = new_node;
1523                 }
1524                 else
1525                 {
1526                     node._next_node._prev_node = new_node;
1527                     new_node._next_node = node._next_node;
1528                 }
1529                 new_node._prev_node = node;
1530                 node._next_node = new_node;
1531                 _count++;
1532                 _nodes_counter++;
1533                 return true;
1534             }
1535         }
1536         if ( lo_shift == 0 )
1537         {
1538             // we have free space to insert
1539             assert(!node.test_bit(pos-1));
1540             node._count++;
1541             assert(node._count <= ItemsPerNode);
1542             node._items[pos-1] = v;
1543             node.mark_bit(pos-1);
1544             _count++;
1545             return true;
1546         }
1547         if ( lo_shift == -1 )
1548         {
1549             // +-- insert here
1550             // v
1551             // XXXXXXXX
1552             if ( node._prev_node )
1553             {
1554                 immutable fhb = node._prev_node.count_free_high_bits();
1555                 if ( fhb>0 )
1556                 {
1557                     // we can store it in prev node
1558                     node = node._prev_node;
1559                     auto new_p = ItemsPerNode - fhb;
1560                     assert(!node.test_bit(new_p));
1561                     node.mark_bit(new_p);
1562                     node._items[new_p] = v;
1563                     node._count++;
1564                     _count++;
1565                     return true;
1566                 }
1567             }
1568             auto new_node = makeNode();
1569             auto new_p = NewItemPosition;
1570             if ( _first_node == node )
1571             {
1572                 _first_node = new_node;
1573             }
1574             else
1575             {
1576                 node._prev_node._next_node = new_node;
1577                 new_node._prev_node = node._prev_node;
1578             }
1579             new_node._next_node = node;
1580             node._prev_node = new_node;
1581             new_node._count = 1;
1582             new_node._items[new_p] = v;
1583             new_node.mark_bit(new_p);
1584             _count++;
1585             _nodes_counter++;
1586             return true;
1587         }
1588         if ( lo_shift < hi_shift )
1589         {
1590             assert(!node.full);
1591             // shift to low items
1592             auto new_pos = pos-lo_shift - 1;
1593             for(auto s=0; s<lo_shift+1; s++)
1594             {
1595                 node._items[new_pos+s] = node._items[new_pos+s+1];
1596             }
1597             node.mark_bit(new_pos);
1598             node._count++;
1599             assert(node._count <= ItemsPerNode);
1600             node._items[pos-1] = v;
1601             // node.mark_bit(pos);
1602             _count++;
1603             return true;
1604         }
1605         else
1606         {
1607             assert(!node.full);
1608             // shift to hight items
1609             auto new_pos = pos+hi_shift;
1610             for(auto s=hi_shift; s>0; s--)
1611             {
1612                 node._items[pos+s] = node._items[pos+s-1];
1613             }
1614             node.mark_bit(new_pos);
1615             node._count++;
1616             assert(node._count <= ItemsPerNode);
1617             node._items[pos] = v;
1618             // node.mark_bit(pos);
1619             _count++;
1620             return true;
1621         }
1622         assert(0);
1623     }
1624     /++
1625     + Insert item at position i. O(N)
1626     +
1627     + Params:
1628     + v = value to insert
1629     + i = position for this value
1630     +
1631     + Returns: True if item were inserted (false if index is > list.length+1)
1632     + Throws: AssertError if any const range is registered.
1633     +/
1634     bool insert(V)(int i, V v)
1635     {
1636         assert(_constRanges_counter == 0, "You can't mutate list while there are active const ranges");
1637         debug(ikodcontainers) tracef("insert %s at %s", v, i);
1638         if ( i > _count )
1639         {
1640             return false;
1641         }
1642         if ( i == 0 )
1643         {
1644             pushFront(v);
1645             return true;
1646         }
1647         if ( i == _count )
1648         {
1649             pushBack(v);
1650             return true;
1651         }
1652         auto  ni    = _node_and_index(i);
1653         int   index = ni.index;
1654         Node* node  = ni.node;
1655 
1656         if ( _mutRanges_counter>0)
1657             sendnotify(Sig.INSERT, i, node, index);
1658 
1659         return _doRealInsert(node, index, v);
1660     }
1661 }
1662 @("ul0")
1663 unittest
1664 {
1665     UnrolledList!int list;
1666     list.pushFront(1);
1667     assert(list.length == 1);
1668     assert(list.front == 1);
1669     assert(list.back == 1);
1670     list.pushFront(0);
1671     assert(list.length == 2);
1672     assert(list.front == 0);
1673     assert(list.back == 1);
1674     list.pushBack(2);
1675     assert(list.length == 3);
1676     assert(list.front == 0);
1677     assert(list.back == 2);
1678     list.pushBack(3);
1679     assert(list.length == 4);
1680     assert(list.front == 0);
1681     assert(list.back == 3);
1682 
1683     list.popFront();
1684     assert(list.length == 3);
1685     assert(list.front == 1);
1686     assert(list.back == 3);
1687     list.popFront();
1688     assert(list.length == 2);
1689     assert(list.front == 2);
1690     assert(list.back == 3);
1691     list.popFront();
1692     assert(list.length == 1);
1693     assert(list.front == 3);
1694     assert(list.back == 3);
1695     list.popFront();
1696     assert(list.empty);
1697     foreach(int i; 0..1000)
1698     {
1699         list.pushBack(i);
1700     }
1701     assert(list.length == 1000);
1702     assert(list.front == 0, "<%s>".format(list.front));
1703     assert(list.back == 999, "<%s>".format(list.back));
1704     foreach(int i; 0..1000)
1705     {
1706         assert(list[i] == i);
1707     }
1708     list.popFront();
1709     foreach(int i; 1..1000)
1710     {
1711         assert(list[i-1] == i);
1712     }
1713     foreach(int i; 1..1000)
1714     {
1715         list.popBack();
1716     }
1717     assert(list.length == 0);
1718     // fill it again
1719     foreach(int i; 0..1000)
1720     {
1721         list.pushBack(i);
1722     }
1723     list.remove(100);
1724     assert(list[100] == 101);
1725     foreach(_;0..list.ItemsPerNode)
1726     {
1727         list.remove(0);
1728     }
1729     assert(list[0] == list.ItemsPerNode);
1730     assert(list.length == 1000 - list.ItemsPerNode - 1);
1731     // test clear
1732     list.clear();
1733     assert(list.length == 0);
1734     // test inserts
1735     list.insert(0, 1);  // |1| |
1736     list.insert(0, 0);  // |0|1|
1737     assert(list.length == 2);
1738     assert(list[0] == 0);
1739     assert(list[1] == 1);
1740     list.clear();
1741     foreach(int i; 0..list.ItemsPerNode)
1742     {
1743         list.pushBack(i);
1744     }
1745     assert(list.length == list.ItemsPerNode); // |0|1|...|14|15|
1746     list.remove(14);        // |0|1|...|__|15|
1747     assert(list[14] == 15);
1748     list.insert(14,14);
1749     assert(list[14] == 14); // |0|1|...|14|15|
1750     list.popBack();         // |0|1|...|14|__|
1751     list[14] = 15;
1752     assert(list[14] == 15); // |0|1|...|15|__|
1753     list.insert(14,14);
1754     assert(list[14] == 14); // |0|1|...|14|15|
1755     assert(list[15] == 15); // |0|1|...|14|15|
1756     assert(list.length == list.ItemsPerNode);
1757     list.insert(2, 16);
1758     assert(list[2] == 16);
1759     assert(list.length == list.ItemsPerNode+1);
1760     assert(list.back == list.ItemsPerNode-2);
1761     list.insert(5, 17);
1762     list.insert(3,55);
1763     list.insert(17, 88);
1764     list.insert(15, 99);
1765     assert(list[15] == 99);
1766 }
1767 
1768 @("ul1")
1769 @safe unittest
1770 {
1771     UnrolledList!int l;
1772     assert(l.length == 0);
1773     l.pushBack(0);
1774     assert(l.length == 1);
1775     assert(l.front == 0);
1776     assert(l.back == 0);
1777     l.pushBack(1);
1778     assert(l.length == 2);
1779     assert(l.front == 0);
1780     assert(l.back == 1);
1781     l.pushFront(2);
1782     assert(l.length == 3);
1783     assert(l.front == 2);
1784     assert(l.back == 1);
1785     l.pushFront(3);
1786     assert(l.length == 4);
1787     assert(l.front == 3);
1788     assert(l.back == 1);
1789     l.popBack();
1790     assert(l.length == 3);
1791     assert(l.front == 3);
1792     assert(l.back == 0);
1793     l.popBack();
1794     assert(l.length == 2);
1795     assert(l.front == 3);
1796     assert(l.back == 2);
1797 }
1798 @("ul2")
1799 @safe @nogc unittest
1800 {
1801     UnrolledList!int l0, l1;
1802     foreach(i;0..1_000)
1803     {
1804         l0.pushBack(i);
1805     }
1806     l1 = l0;
1807     foreach(i;0..1_000)
1808     {
1809         immutable v = l1.get(i);
1810         assert(v.ok);
1811         assert(v.value == i);
1812     }
1813     l1 = l0;
1814     foreach(i;0..1_000)
1815     {
1816         immutable v = l1.get(i);
1817         assert(v.ok);
1818         assert(v.value == i);
1819     }
1820     auto l2 = l1;
1821     foreach(i;0..1_000)
1822     {
1823         immutable v = l2.get(i);
1824         assert(v.ok);
1825         assert(v.value == i);
1826     }
1827 }
1828 
1829 @("ul2")
1830 @safe @nogc unittest
1831 {
1832     UnrolledList!int l;
1833     foreach(i;0..1_000)
1834     {
1835         l.pushBack(i);
1836     }
1837     foreach(i;0..1_000)
1838     {
1839         immutable v = l.get(i);
1840         assert(v.ok);
1841         assert(v.value == i);
1842     }
1843 }
1844 
1845 @("ul3")
1846 unittest
1847 {
1848     import std.exception;
1849     UnrolledList!int l;
1850     assertThrown!RangeError(l[0]);
1851     foreach(i; 0..1_000)
1852     {
1853         l.pushBack(i);
1854     }
1855     assertThrown!RangeError(l[1000]);
1856     foreach(i; 0..1_000)
1857     {
1858         l[i] = i * 2;
1859     }
1860     foreach(i;0..1_000)
1861     {
1862         assert(l[i] == i * 2);
1863     }
1864 }
1865 @("ul4")
1866 @safe unittest
1867 {
1868     UnrolledList!int l;
1869     foreach(i;0..2*l.ItemsPerNode)
1870     {
1871         l.pushBack(i);
1872     }
1873     //          ↓ ins B
1874     // XXX....XXA->XXX....XXX
1875     l.insert(l.ItemsPerNode-1, 1000);
1876     // XXX....XXB->OOO..A..OOO->XXX....XXX
1877     assert(l[l.ItemsPerNode - 1] == 1000);
1878     assert(l.length == l.ItemsPerNode*2 + 1);
1879 }
1880 @("ul5")
1881 @safe unittest
1882 {
1883     UnrolledList!int l;
1884     foreach(i;0..2*l.ItemsPerNode)
1885     {
1886         l.pushBack(i);
1887     }
1888     l.remove(l.ItemsPerNode);
1889     //     ins B↓
1890     // XXX....XXA -> OXX....XXX
1891     l.insert(l.ItemsPerNode - 1, 1000);
1892     //
1893     // XXX....XXB -> AXX....XXX
1894     assert(l[l.ItemsPerNode - 1] == 1000);
1895     assert(l.length == 2 * l.ItemsPerNode);
1896 }
1897 @("ul6")
1898 @safe unittest
1899 {
1900     UnrolledList!int l;
1901     foreach(i;0..2*l.ItemsPerNode)
1902     {
1903         l.pushBack(i);
1904     }
1905     //          ins B↓
1906     // XXX....XXX -> XXX....XXX
1907     l.insert(l.ItemsPerNode, 1000);
1908     // XXX....XXX->OOO..B..OOO->XXX....XXX
1909     assert(l[l.ItemsPerNode] == 1000);
1910     assert(l.length == 2 * l.ItemsPerNode + 1);
1911 }
1912 
1913 @("ul7")
1914 @safe unittest
1915 {
1916     UnrolledList!int l;
1917     foreach(i;0..l.ItemsPerNode)
1918     {
1919         l.pushBack(i);
1920     }
1921     l.remove(2);
1922     //   B↓
1923     // XXOX..XXX
1924     l.insert(2, 1000);
1925     // XXBX..XXX
1926     assert(l[2] == 1000);
1927     assert(l.length == l.ItemsPerNode);
1928 }
1929 
1930 @("ul8")
1931 @safe unittest
1932 {
1933     UnrolledList!int l;
1934     foreach(i;0..l.ItemsPerNode)
1935     {
1936         l.pushBack(i);
1937     }
1938     l.remove(2);
1939     // B↓
1940     // XAOX..XXX
1941     l.insert(1, 1000);
1942     // XBAX..XXX
1943     assert(l[1] == 1000);
1944     assert(l.length == l.ItemsPerNode);
1945 }
1946 
1947 @("ul9")
1948 @safe unittest
1949 {
1950     UnrolledList!int l;
1951     foreach(i;0..l.ItemsPerNode)
1952     {
1953         l.pushBack(i);
1954     }
1955     l.remove(l.ItemsPerNode-2);
1956     l.remove(0);
1957     l.remove(1);
1958     //    B↓
1959     // OXOXXX..XXO
1960     l.insert(2, 1000);
1961     // XBAX..XXX
1962     l.insert(27, 2000);
1963     assert(l[27] == 2000);
1964     assert(l.length == l.ItemsPerNode-1);
1965 }
1966 @("ul10")
1967 @safe unittest
1968 {
1969     UnrolledList!int l;
1970     foreach(i;0..l.ItemsPerNode)
1971     {
1972         l.pushBack(i);
1973     }
1974     l.remove(0);
1975     l.insert(30,1000);
1976     assert(l[0]==1);
1977     assert(l[30] == 1000);
1978 }
1979 
1980 @("mutIterator1")
1981 unittest
1982 {
1983     import std.stdio;
1984     import std.range;
1985     import std.exception;
1986     import std.math;
1987 
1988     UnrolledList!int l;
1989 
1990     foreach(i; 0..50)
1991     {
1992         l.pushBack(i);
1993     }
1994     auto r = l.mutRange(1, -1);
1995     foreach(v; r)
1996     {
1997         assert(v>=0);
1998     }
1999     r = l.mutRange();
2000     while(!r.empty)
2001     {
2002         auto v = r.front;
2003         if ( v % 2 )
2004         {
2005             r.remove();
2006         }
2007         else
2008         {
2009             r.popFront;
2010         }
2011     }
2012     assert(equal(l.constRange,iota(0, 50, 2)));
2013     l.clear;
2014     //
2015     // Build Eratosphenes seed, compare with correct list and clear it
2016     //
2017     enum limit = 100_500;
2018     uint[] sieve(in uint limit) nothrow @safe {
2019         // https://rosettacode.org/wiki/Sieve_of_Eratosthenes#Simpler_Version
2020         if (limit < 2)
2021             return [];
2022         auto composite = new bool[limit];
2023     
2024         foreach (immutable uint n; 2 .. cast(uint)(limit ^^ 0.5) + 1)
2025             if (!composite[n])
2026                 for (uint k = n * n; k < limit; k += n)
2027                     composite[k] = true;
2028     
2029         return iota(2, limit).filter!(i => !composite[i]).array;
2030     }
2031     foreach(i; 2..limit)
2032     {
2033         l.pushBack(i);
2034     }
2035     foreach(index,value; l.mutRange(0, cast(int)sqrt(real(limit))+1).enumerate)
2036     {
2037         for(auto r1 = l.mutRange(cast(int)index); !r1.empty;)
2038         {
2039             if (r1.front > value && r1.front % value == 0)
2040             {
2041                 r1.remove;
2042             }
2043             else
2044             {
2045                 r1.popFront;
2046             }
2047         }
2048     }
2049     // foreach(s; l.dump)
2050     // {
2051     //     info(s);
2052     // }
2053     assert(equal(l.constRange, sieve(limit)));
2054     l.popFront;
2055     l.popBack;
2056     r = l.mutRange();
2057     while(!r.empty)
2058     {
2059         r.remove();
2060     }
2061     assert(r.empty);
2062     assert(r.count == 0);
2063     assert(l.length == 0);
2064     //
2065     // test popFront/popBack handling by mutRange
2066     foreach(i; 0..50)
2067     {
2068         l.pushBack(i);
2069     }
2070     // foreach(s; l.dump)
2071     // {
2072     //     info(s);
2073     // }
2074     r = l.mutRange();
2075     while(!l.empty)
2076     {
2077         l.popFront;
2078         l.popBack;
2079         assertThrown!AssertError(r.front); // you tried to access deleted item
2080         r.popFront;
2081         assert(equal(r, l.constRange));
2082     }
2083 }
2084 @("mutIterator2")
2085 unittest
2086 {
2087     import std.stdio;
2088     import std.range;
2089     import std.exception;
2090 
2091     auto l = UnrolledList!int();
2092     foreach(i; iota(1, 50, 2))
2093     {
2094         l.pushBack(i);
2095     }
2096     assert(equal(l.constRange(0, 5), [1,3,5,7,9]));
2097     auto r0 = l.mutRange();
2098     auto r1 = r0;
2099     // foreach(s; l.dump)
2100     // {
2101     //     info(s);
2102     // }
2103     while(!r0.empty)
2104     {
2105         // infof("---insert %s", r0.front-1);
2106         r0.insert(r0.front - 1);
2107         r0.popFront;
2108     }
2109     assert(equal(l.constRange(0, 5), [0,1,2,3,4]));
2110     assert(equal(l.constRange(), iota(50)));
2111     // foreach(s; l.dump)
2112     // {
2113     //     info(s);
2114     // }
2115     // while(!r1.empty)
2116     // {
2117     //     writeln(r1.front);
2118     //     r1.popFront;
2119     // }
2120     assert(equal(r1, iota(1,50)));
2121     assert(equal(l.constRange, iota(50)));
2122     r0 = l.mutRange();
2123     while(!r0.empty)
2124     {
2125         // infof("front %s", r0.front);
2126         if ( r0.front % 2 == 0)
2127         {
2128             // infof("remove %s", r0.front);
2129             r0.remove();
2130         }
2131         else
2132         {
2133             r0.popFront;
2134         }
2135         // foreach(s; l.dump)
2136         // {
2137         //     info(s);
2138         // }
2139     }
2140     assert(equal(r1, iota(1, 50, 2)));
2141     r0 = l.mutRange();
2142     int x = 0;
2143     while(!r0.empty)
2144     {
2145         // infof("---insert %s", x);
2146         r0.insert(x);
2147         x += 2;
2148         r0.popFront;
2149         // foreach(s; l.dump)
2150         // {
2151         //     info(s);
2152         // }
2153     }
2154     assert(equal(l.constRange(), iota(50)));
2155     // while(!r1.empty)
2156     // {
2157     //     writeln(r1.front);
2158     //     r1.popFront;
2159     // }
2160     assert(equal(r1, iota(1, 50)));
2161 }
2162 @("mutIterator3")
2163 unittest
2164 {
2165     import std.stdio;
2166     import std.range;
2167     import std.exception;
2168     import std.random;
2169     auto rnd = Random(19);
2170 
2171     auto l = UnrolledList!int();
2172     while(l.length < 5)
2173     {
2174         int v = uniform(0, 10000, rnd);
2175         auto i = l.mutRange();
2176         while(!i.empty && i.front > v)
2177         {
2178             i.popFront;
2179         }
2180         i.insert(v);
2181     }
2182 }
2183 
2184 @("constIterator")
2185 unittest
2186 {
2187     import std.range;
2188     import std.exception;
2189     import std.algorithm;
2190     import std.stdio;
2191 
2192     UnrolledList!int l;
2193 
2194     foreach(i; 0..50)
2195     {
2196         l.pushBack(i);
2197     }
2198     auto r = l.constRange();
2199     assert(equal(r, iota(50)));
2200     assertThrown!AssertError(l.clear); // r still active
2201     assertThrown!AssertError(l.remove(0)); // r still active
2202     assertThrown!AssertError(l.pushBack(0)); // r still active
2203     assertThrown!AssertError(l.pushFront(0)); // r still active
2204     assertThrown!AssertError(l.popBack()); // r still active
2205     assertThrown!AssertError(l.popFront()); // r still active
2206     r.reset();  // deactivate r
2207     l.clear();
2208     foreach(i; 0..50)
2209     {
2210         l.pushBack(i);
2211     }
2212     r = l.constRange();
2213     auto r1 = r;
2214     r.reset();
2215     assert(equal(r1.take(10), iota(10))); // still can use r1
2216     r1 = l.constRange();
2217     r1 = r1;
2218     r.reset();
2219     assert(l._constRanges_counter == 1); // r1 only
2220     assert(equal(r1, iota(50)));
2221     // test negative indexing
2222     assert(equal(l.constRange(25), iota(25,50)));
2223     assert(l.constRange(-3, -3).count == 0);
2224     assertThrown!AssertError(l.constRange(0, -10000));
2225     assert(l._constRanges_counter == 1); // r1 only, temp ranges unregistered
2226 
2227     r = l.constRange();
2228     assert(l._constRanges_counter == 2); // r and r1
2229     foreach(i, v; r.enumerate)
2230     {
2231         r1 = l.constRange(cast(int)i, 50);
2232         assert(equal(r1, iota(i, 50)));
2233     }
2234     r1.reset();
2235     r.reset();
2236     assert(l._constRanges_counter == 0); // we cleared everything
2237 
2238     // test unregister on list destruction
2239     {
2240         UnrolledList!int l1;
2241         foreach(i; 0..50)
2242         {
2243             l1.pushBack(i);
2244         }
2245         r1 = l1.constRange();
2246         assert(r1.count == 50);
2247         foreach(i,v; r1.enumerate)
2248         {
2249             auto r2 = l1.constRange(cast(int)i);
2250             assert(equal(r2, iota(i, 50)));
2251         }
2252         assert(r1.count == 50);
2253     }
2254     assert(r1.count == 0); // lost container
2255     r = l.constRange();
2256     assertThrown!AssertError(l.clear);
2257     while(!r.empty)
2258     {
2259         r.popFront;
2260     }
2261     l.clear;
2262 
2263     foreach(i; 0..50)
2264     {
2265         l.pushBack(i);
2266     }
2267     r = l.constRange();
2268     assertThrown!AssertError(l.clear);
2269     foreach(i; r)
2270     {
2271         assert(i>=0);
2272     }
2273     // iterator consumed by opApply
2274     l.clear;
2275 }
2276 @("classes")
2277 @safe
2278 unittest
2279 {
2280     import std.range;
2281     class C
2282     {
2283         int c;
2284         this(int i)
2285         {
2286             c = i;
2287         }
2288     }
2289     UnrolledList!C l;
2290     foreach(i; 0..50)
2291     {
2292         l.pushBack(new C(i));
2293     }
2294     auto r = l.constRange;
2295     assert(equal(r.map!(c => c.c), iota(50)));
2296 }
2297 @("structs")
2298 @safe
2299 unittest
2300 {
2301     import std.format: format;
2302     import std.range;
2303     struct S
2304     {
2305         int s;
2306         string ss;
2307         this(int i)
2308         {
2309             s = i;
2310             ss = "%s".format(i);
2311         }
2312     }
2313     UnrolledList!(S) l;
2314     foreach(i; 0..50)
2315     {
2316         S s = S(i);
2317         l.pushBack(s);
2318     }
2319     auto r = l.constRange;
2320     assert(equal(r.map!(s => s.s), iota(50)));
2321 }
The OpenD Programming Language
