Unofficial Dub Package Documentation 
1 module decs.collections;
2 
3 import decs.dbg;
4 import decs.memory;
5 
6 struct Array(T)
7 {
8     Allocator* allocator;
9 
10     T[] _items;
11     private size_t _count = 0;
12     size_t capacity = 0;
13 
14     static Array createWith(Allocator* allocator, size_t capacity = 16)
15     {
16         Array ret;
17         ret.allocator = allocator;
18         ret._count = 0;
19         ret.capacity = capacity;
20         ret._items = allocator.alloc_array!T(capacity);
21         return ret;
22     }
23 
24     void create(Allocator* allocator, size_t capacity = 16)
25     {
26         this.allocator = allocator;
27         this._count = 0;
28         this.capacity = capacity;    
29         _items = allocator.alloc_array!T(capacity);    
30     }
31 
32     void destroy()
33     {
34         allocator.free(_items.ptr);
35     }
36 
37     size_t length()
38     {
39         return _count;
40     }
41 
42     bool empty()
43     {
44         return _count == 0;
45     }
46 
47     ref T opIndex(size_t index)
48     {
49         if ((index < 0) || (index >= _count))
50             panic("out of bound");
51         return _items[index];
52     }
53 
54     void opIndexAssign(T value, in size_t index)
55     {
56         if (index >= _count)
57             panic("out of bound");
58         _items[index] = value;
59     }
60 
61     int opApply(int delegate(ref T) dg)
62     {
63         int result;
64         //foreach (ref T item; _items)
65         for (int i = 0; i < _count; i++)
66             if ((result = dg(_items[i])) != 0)
67                 break;
68         return result;
69     }
70 
71     int opApply(int delegate(T*) dg)
72     {
73         int result;
74         //foreach (ref T item; _items)
75         for (int i = 0; i < _count; i++)
76             if ((result = dg(&_items[i])) != 0)
77                 break;
78         return result;
79     }
80 
81     int opApply(int delegate(size_t, T*) dg)
82     {
83         int result;
84         //foreach (ref T item; _items)
85         for (size_t i = 0; i < _count; i++)
86             if ((result = dg(i, &_items[i])) != 0)
87                 break;
88         return result;
89     }
90 
91     T get(size_t index)
92     {
93         if ((index < 0) || (index >= _count))
94             panic("out of bound");
95         return _items[index];
96     }
97 
98     void set(size_t index, ref T value)
99     {
100         if (index >= _count)
101             panic("out of bound");
102         _items[index] = value;
103     }
104 
105     void ensureTotalCapacity(size_t new_capacity)
106     {
107          size_t better_capacity = capacity;
108          if (better_capacity >= new_capacity) return;
109 
110          while (true) {
111              better_capacity += better_capacity / 2 + 8;
112              if (better_capacity >= new_capacity) break;
113          }
114 
115          size_t originalLength = _items.length;
116          size_t diff = new_capacity - capacity;
117 
118          // TODO This can be optimized to avoid needlessly copying undefined memory.
119          T[] new_memory = allocator.reallocate_array(_items.ptr, better_capacity);
120          _items = new_memory;
121          capacity = new_memory.length;
122         
123         if (diff > 0)
124         {
125             // todo: fill stuff with default values
126             for (size_t i = originalLength; i < originalLength + diff; i++)
127             {
128                 _items[i] = T.init;
129             }
130         }
131     }
132 
133     void expandToCapacity()
134     {
135         _count = capacity;
136     }
137 
138     void resize(size_t newSize)
139     {
140         ensureTotalCapacity(cast(int)newSize);
141         _count = cast(int) newSize;
142     }
143 
144     void clear()
145     {
146         for (int i = 0; i < _items.length; i++)
147         {
148             _items[i] = T.init;
149         }
150 
151         _count = 0;
152     }
153 
154     void add(T item)
155     {
156         auto length = cast(int) _items.length;
157         if (_count + 1 > length)
158         {
159             auto expand = (length < 1000) ? (length + 1) * 4 : 1000;
160 
161             ensureTotalCapacity(length + expand);
162         }
163 
164         _items[_count++] = item;
165     }
166 
167     void add_all(ref Array!T items)
168     {
169         // todo: optimize
170         for (int i = 0; i < items.length(); i++)
171             add(items[i]);
172     }
173 
174     bool remove(T item)
175     {
176         for (int i = 0; i < _count; i++)
177         {
178             if (_items[i] == item)
179             {
180                 return remove_at(i);
181             }
182         }
183         return false;
184     }
185 
186 
187     // TODO: add tests for both of them
188     T removeSwap(size_t index)
189     {
190         if (length - 1 == index) return pop();
191         
192          auto old_item = _items[index];
193          _items[index] = pop();
194          return old_item;
195     }
196 
197     T pop()
198     {
199         auto val = _items[length - 1];
200         _count -= 1;
201         return val;
202     }
203 
204     int index_of(T item)
205     {
206         for (int i = 0; i < _count; i++)
207             if (_items[i] == item)
208                 return i;
209         return -1;
210     }
211 
212     bool remove_at(size_t index)
213     {
214         import core.stdc..string : memmove;
215 
216         T val = _items[index];
217         _count--;
218 
219         static if (__traits(isPOD, T))
220         {
221             memmove(_items.ptr + index, // dest
222                     _items.ptr + index + 1, // src
223                     (_count - index) * T.sizeof); // num bytes
224         }
225         else
226         {
227             for (auto j = index; j < _count; j++)
228             {
229                 _items[j] = _items[j + 1];
230             }
231         }
232         return true;
233     }
234 
235     bool remove_back()
236     {
237         return remove_at(_count - 1);
238     }
239 
240     T[] get_slice()
241     {
242         return _items[0 .. _count];
243     }
244 }
245 
246 struct HashMap(Key, Value,
247         Hasher = HashFunc!(Key), Comparer = HashComp!(Key),
248         ubyte MIN_HASH_TABLE_POWER = 3, ubyte RELATIONSHIP = 8)
249 {
250 
251     static struct Pair
252     {
253         Key key;
254         Value value;
255     }
256 
257     static struct Element
258     {
259         uint hash = 0;
260         Element* next = null;
261         Pair pair;
262     }
263 
264     Element** hash_table = null;
265     ubyte hash_table_power = 0;
266     uint elements = 0;
267     Allocator* allocator = null;
268 
269     static HashMap create(Allocator* alloc)
270     {
271         HashMap ret;
272         ret.allocator = alloc;
273         return ret;
274     }
275 
276 private:
277     void make_hash_table()
278     {
279         if (!allocator)
280             allocator = &MALLOCATOR.base;
281 
282         hash_table = cast(Element**) allocator.allocate((Element*).sizeof * (1 << MIN_HASH_TABLE_POWER));
283         hash_table_power = MIN_HASH_TABLE_POWER;
284         elements = 0;
285         for (int i = 0; i < (1 << MIN_HASH_TABLE_POWER); i++)
286         {
287             hash_table[i] = null;
288         }
289     }
290 
291     void erase_hash_table()
292     {
293         //ERR_FAIL_COND_MSG(elements, "Cannot erase hash table if there are still elements inside.");
294         //memdelete_arr(hash_table);
295 
296         allocator.free(hash_table);
297         hash_table = null;
298         hash_table_power = 0;
299         elements = 0;
300     }
301 
302     void check_hash_table()
303     {
304         int new_hash_table_power = -1;
305 
306         if (cast(int) elements > ((1 << hash_table_power) * RELATIONSHIP))
307         {
308             /* rehash up */
309             new_hash_table_power = hash_table_power + 1;
310 
311             while (cast(int) elements > ((1 << new_hash_table_power) * RELATIONSHIP))
312             {
313                 new_hash_table_power++;
314             }
315 
316         }
317         else if ((hash_table_power > cast(int) MIN_HASH_TABLE_POWER) && (
318                 cast(int) elements < ((1 << (hash_table_power - 1)) * RELATIONSHIP)))
319         {
320             /* rehash down */
321             new_hash_table_power = hash_table_power - 1;
322 
323             while (cast(int) elements < ((1 << (new_hash_table_power - 1)) * RELATIONSHIP))
324             {
325                 new_hash_table_power--;
326             }
327 
328             if (new_hash_table_power < cast(int) MIN_HASH_TABLE_POWER)
329             {
330                 new_hash_table_power = MIN_HASH_TABLE_POWER;
331             }
332         }
333 
334         if (new_hash_table_power == -1)
335         {
336             return;
337         }
338 
339         //Element **new_hash_table = memnew_arr(Element*, (cast(ulong)1 << new_hash_table_power));
340         Element** new_hash_table = cast(Element**) allocator.allocate((Element*).sizeof * (cast(ulong) 1 << new_hash_table_power));
341         //ERR_FAIL_COND_MSG(!new_hash_table, "Out of memory.");
342 
343         for (int i = 0; i < (1 << new_hash_table_power); i++)
344         {
345             new_hash_table[i] = null;
346         }
347 
348         if (hash_table)
349         {
350             for (int i = 0; i < (1 << hash_table_power); i++)
351             {
352                 while (hash_table[i])
353                 {
354                     Element* se = hash_table[i];
355                     hash_table[i] = se.next;
356                     int new_pos = se.hash & ((1 << new_hash_table_power) - 1);
357                     se.next = new_hash_table[new_pos];
358                     new_hash_table[new_pos] = se;
359                 }
360             }
361             //memdelete_arr(hash_table);
362             allocator.free(hash_table);
363         }
364         hash_table = new_hash_table;
365         hash_table_power = cast(ubyte) new_hash_table_power;
366     }
367 
368     const Element* get_element(const ref Key p_key)
369     {
370 
371         if (!hash_table)
372             return null;
373 
374         uint hash = Hasher.hash(p_key);
375         uint index = hash & ((1 << hash_table_power) - 1);
376 
377         Element* e = cast(Element*) hash_table[index];
378 
379         while (e)
380         {
381             /* checking hash first avoids comparing key, which may take longer */
382             if (e.hash == hash && Comparer.compare(e.pair.key, p_key))
383             {
384                 /* the pair exists in this hashtable, so just update data */
385                 return e;
386             }
387             e = e.next;
388         }
389 
390         return null;
391     }
392 
393     Element* create_element(const ref Key p_key)
394     {
395         /* if element doesn't exist, create it */
396         Element* e = cast(Element*) allocator.allocate(Element.sizeof);
397         //ERR_FAIL_COND_V_MSG(!e, nullptr, "Out of memory.");
398         uint hash = Hasher.hash(p_key);
399         uint index = hash & ((1 << hash_table_power) - 1);
400         e.next = hash_table[index];
401         e.hash = hash;
402         e.pair.key = cast(Key)p_key; // TODO: when i use pointer as key, i need this
403         e.pair.value = Value.init;
404 
405         hash_table[index] = e;
406         elements++;
407         return e;
408     }
409 
410 public:
411     Element* set(const ref Key key, const ref Value value)
412     {
413         Element* e = null;
414         if (!hash_table)
415         {
416             make_hash_table(); // if no table, make one
417         }
418         else
419         {
420             e = cast(Element*)(get_element(key));
421         }
422 
423         /* if we made it up to here, the pair doesn't exist, create and assign */
424 
425         if (!e)
426         {
427             e = create_element(key);
428             if (!e)
429             {
430                 return null;
431             }
432             check_hash_table(); // perform mantenience routine
433         }
434 
435         e.pair.value = cast(Value) value;
436         return e;
437     }
438 
439     ref Value get(const ref Key p_key)
440     {
441         Value* res = getptr(p_key);
442         //CRASH_COND_MSG(!res, "Map key not found.");
443         return *res;
444     }
445 
446     Value* getptr(const ref Key p_key)
447     {
448         if (!hash_table)
449         {
450             return null;
451         }
452 
453         Element* e = cast(Element*)(get_element(p_key));
454 
455         if (e)
456         {
457             return &e.pair.value;
458         }
459 
460         return null;
461     }
462 
463     bool erase(const ref Key p_key)
464     {
465         if (!hash_table)
466         {
467             return false;
468         }
469 
470         uint hash = Hasher.hash(p_key);
471         uint index = hash & ((1 << hash_table_power) - 1);
472 
473         Element* e = hash_table[index];
474         Element* p = null;
475         while (e)
476         {
477             /* checking hash first avoids comparing key, which may take longer */
478             if (e.hash == hash && Comparer.compare(e.pair.key, p_key))
479             {
480                 if (p)
481                 {
482                     p.next = e.next;
483                 }
484                 else
485                 {
486                     //begin of list
487                     hash_table[index] = e.next;
488                 }
489 
490                 allocator.free(e);
491                 elements--;
492 
493                 if (elements == 0)
494                 {
495                     erase_hash_table();
496                 }
497                 else
498                 {
499                     check_hash_table();
500                 }
501                 return true;
502             }
503 
504             p = e;
505             e = e.next;
506         }
507 
508         return false;
509     }
510 
511     bool has(const ref Key p_key)
512     {
513         return getptr(p_key) != null;
514     }
515 
516     uint size() const {
517 		return elements;
518 	}
519 
520 	bool is_empty() const {
521 		return elements == 0;
522 	}
523 
524     void clear()
525     {
526 		/* clean up */
527 		if (hash_table) {
528 			for (int i = 0; i < (1 << hash_table_power); i++) {
529 				while (hash_table[i]) {
530 					Element *e = hash_table[i];
531 					hash_table[i] = e.next;
532                     allocator.free(e);
533 				}
534 			}
535             allocator.free(hash_table); // TODO: check if that's the right way to delete T**
536 		}
537 
538 		hash_table = null;
539 		hash_table_power = 0;
540 		elements = 0;
541     }
542 
543     int opApply(int delegate(Pair*) dg)
544     {
545         if(!hash_table) return 0;
546 
547         int result;
548         for (int i = 0; i < (1 << hash_table_power); i++) {
549             Element* e = hash_table[i];
550             while(e) {
551                 if ((result = dg(&e.pair)) != 0)
552                     break;
553                 e = e.next;
554             }
555         }
556         return result;
557     }
558 
559     int opApply(int delegate(Key*, Value*) dg)
560     {
561         if(!hash_table) return 0;
562 
563         int result;
564         for (int i = 0; i < (1 << hash_table_power); i++) {
565             Element* e = hash_table[i];
566             while(e) {
567                 if ((result = dg(&e.pair.key, &e.pair.value)) != 0)
568                     break;
569                 e = e.next;
570             }
571         }
572         return result;
573     }
574 
575     void opIndexAssign(const ref Value value, const Key key) {
576         set(key, value);
577     }
578 
579     // TODO: how to handle error
580     ref Value opIndex(const ref Key key) {
581         if(!has(key)) panic("key not found");
582         return get(key);
583     }
584 
585 }
586 
587 struct HashFunc(T)
588 {
589     static uint hash(const ref T v)
590     {
591         static if(is(T == U*, U) && __traits(isScalar, T)) 
592         {
593             return hash_one_uint64(cast(ulong) v);
594         }
595         else static if( is(T == int) || is(T == uint)) 
596         {
597             return cast(uint) v;
598         }
599         else static if( is(T == long) || is(T == ulong) ) 
600         {
601             return hash_one_uint64(cast(ulong) v);
602         }
603         else static if( is(T == float) || is(T == double) ) 
604         {
605             return hash_djb2_one_float(v);
606         }
607         else static if ( is (T == string) )
608         {
609             return cast(int) hashOf(v);
610         }
611         else static assert(0, "not supported");
612     }
613 /*
614     static uint hash(const(char)* p_cstr)
615     {
616         return hash_djb2(p_cstr);
617     }
618 
619     static uint hash(const ulong p_int)
620     {
621         return hash_one_uint64(p_int);
622     }
623 
624     static uint hash(const long p_int)
625     {
626         return hash(cast(ulong)(p_int));
627     }
628 
629     static uint hash(const float p_float)
630     {
631         return hash_djb2_one_float(p_float);
632     }
633 
634     static uint hash(const double p_double)
635     {
636         return hash_djb2_one_float(p_double);
637     }
638 
639     static uint hash(const uint p_int)
640     {
641         return p_int;
642     }
643 
644     static uint hash(const int p_int)
645     {
646         return cast(uint) p_int;
647     }
648 
649     static uint hash(const ushort p_int)
650     {
651         return p_int;
652     }
653 
654     static uint hash(const short p_int)
655     {
656         return cast(uint) p_int;
657     }
658 
659     static uint hash(const ubyte p_int)
660     {
661         return p_int;
662     }
663 
664     static uint hash(const byte p_int)
665     {
666         return cast(uint) p_int;
667     }
668 
669     static uint hash(const char p_uchar)
670     {
671         return cast(uint) p_uchar;
672     }
673 
674     static uint hash(const wchar p_wchar)
675     {
676         return cast(uint) p_wchar;
677     }
678 
679     static uint hash(const dchar p_uchar)
680     {
681         return cast(uint) p_uchar;
682     }
683 */
684 }
685 
686 struct HashComp(T)
687 {
688     static bool compare()(const ref T p_lhs, const ref T p_rhs)
689     {
690         static if(is(T == U*, U) && __traits(isScalar, T)) 
691         {
692             return p_lhs == p_rhs;
693         }
694         else static if( is(T == int) || is(T == uint)) 
695         {
696             return p_lhs == p_rhs;
697         }
698         else static if( is(T == ulong) || is(T == ulong)) 
699         {
700             return p_lhs == p_rhs;
701         }
702         else static if( is(T == float) || is(T == double) ) 
703         {
704             return (p_lhs == p_rhs) || (is_nan(p_lhs) && is_nan(p_rhs));
705         } 
706         else static if ( is (T == string) )
707         {
708             return (p_lhs == p_rhs);
709         }
710         
711         else static assert(0, "not supported");
712     }
713 }
714 
715 
716 private static uint hash_djb2(const(char)* p_cstr)
717 {
718     const(ubyte)* chr = cast(const(ubyte)*) p_cstr;
719     uint hash = 5381;
720     uint c;
721 
722     while ((c = *chr++) == 1)
723     { // TODO: check == 1
724         hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
725     }
726 
727     return hash;
728 }
729 
730 private static ulong hash_djb2_one_float_64(double p_in, ulong p_prev = 5381)
731 {
732     union U
733     {
734         double d;
735         ulong i;
736     }
737 
738     U u;
739 
740     // Normalize +/- 0.0 and NaN values so they hash the same.
741     if (p_in == 0.0f)
742     {
743         u.d = 0.0;
744     }
745     else if (is_nan(p_in))
746     {
747         u.d = float.nan;
748     }
749     else
750     {
751         u.d = p_in;
752     }
753 
754     return ((p_prev << 5) + p_prev) + u.i;
755 }
756 
757 private static ulong hash_djb2_one_64(ulong p_in, ulong p_prev = 5381)
758 {
759     return ((p_prev << 5) + p_prev) + p_in;
760 }
761 
762 private static uint hash_one_uint64(const ulong p_int)
763 {
764     ulong v = p_int;
765     v = (~v) + (v << 18); // v = (v << 18) - v - 1;
766     v = v ^ (v >> 31);
767     v = v * 21; // v = (v + (v << 2)) + (v << 4);
768     v = v ^ (v >> 11);
769     v = v + (v << 6);
770     v = v ^ (v >> 22);
771     return cast(int) v;
772 }
773 
774 private static uint hash_djb2_one_float(double p_in, uint p_prev = 5381)
775 {
776     union U
777     {
778         double d;
779         ulong i;
780     }
781 
782     U u;
783 
784     // Normalize +/- 0.0 and NaN values so they hash the same.
785     if (p_in == 0.0f)
786     {
787         u.d = 0.0;
788     }
789     else if (is_nan(p_in))
790     {
791         u.d = float.nan;
792     }
793     else
794     {
795         u.d = p_in;
796     }
797 
798     return ((p_prev << 5) + p_prev) + hash_one_uint64(u.i);
799 }
800 
801 
802 T nextPOT(T)(T x) {
803 	--x;
804 	x |= x >> 1;
805 	x |= x >> 2;
806 	x |= x >> 4;
807 	static if (T.sizeof >= 16) x |= x >>  8;
808 	static if (T.sizeof >= 32) x |= x >> 16;
809 	static if (T.sizeof >= 64) x |= x >> 32;
810 	++x;
811 
812 	return x;
813 }

Page generated by adrdox