1 /** 2 License: public domain 3 Authors: Simon Bürger 4 */ 5 6 module jive.priorityarray; 7 8 private import std.algorithm; 9 private import std.range; 10 private import jive.array; 11 12 /** 13 * Array-like structure with fast access to the smallest element. 14 * 15 * Implemented using a segment tree. 16 * TODO: more array-like operations (e.g. pushBack, popBack, maybe iteration) 17 */ 18 struct PriorityArray(V) 19 { 20 // NOTE: seg[0] is unused, all unused are set to -1. length of seg is always an even power of 2 21 private Array!int seg; 22 23 private Array!V data; 24 25 /** constructor for given size */ 26 this(size_t size) 27 { 28 data.resize(size); 29 30 size_t sizeRounded = 2; 31 while(sizeRounded < size) 32 sizeRounded *= 2; 33 seg.resize(sizeRounded, -1); 34 for(int i = 0; i < length/2; ++i) 35 seg[seg.length/2 + i] = i*2; 36 for(int i = cast(int)seg.length/2-1; i >= 0; --i) 37 seg[i] = seg[2*i]; 38 } 39 40 /** constructor taking a range */ 41 this(Stuff)(Stuff data) 42 if(isInputRange!Stuff && is(ElementType!Stuff:V) && hasLength!Stuff) 43 { 44 this(data.length); 45 size_t i = 0; 46 foreach(x; data) 47 this[i++] = x; 48 } 49 50 /** number of elements in the array */ 51 size_t length() const @property 52 { 53 return data.length; 54 } 55 56 /** ditto */ 57 size_t opDollar() const @property 58 { 59 return data.length; 60 } 61 62 /** read-only access to the i'th element */ 63 inout(V) opIndex(size_t i) inout 64 { 65 return data[i]; 66 } 67 68 /** read-only access to all elements */ 69 const(V)[] opSlice() const 70 { 71 return data[]; 72 } 73 74 /** set element at i to value v ( O(log n) ) */ 75 void opIndexAssign(V v, size_t _i) 76 { 77 data[_i] = move(v); // this performs the bounds check, so that the conversion to int is fine 78 int i = cast(int)_i; 79 80 int k = cast(int)i/2 + cast(int)seg.length/2; 81 82 if((i^1) < length && data[i^1] < data[i]) 83 seg[k] = i^1; 84 else 85 seg[k] = i; 86 87 for(; k != 1; k /= 2) 88 if(seg[k^1] != -1 && data[seg[k^1]] < data[seg[k]]) 89 seg[k/2] = seg[k^1]; 90 else 91 seg[k/2] = seg[k]; 92 } 93 94 /** returns index of smallest element ( O(1) ) */ 95 size_t minIndex() const 96 { 97 return seg[1]; 98 } 99 100 /** returns smallest element ( O(1) ) */ 101 ref const(V) min() const 102 { 103 return data[seg[1]]; 104 } 105 } 106 107 /// 108 /+@nogc+/ nothrow pure @safe unittest 109 { 110 auto a = PriorityArray!int([7,9,2,3,4,1,6,5,8,0]); 111 assert(a[] == [7,9,2,3,4,1,6,5,8,0]); 112 113 assert(a.minIndex == 9); 114 assert(a.min == 0); 115 116 a[9] = 100; 117 118 assert(a.minIndex == 5); 119 assert(a.min == 1); 120 121 a[2] = -3; 122 123 assert(a.minIndex == 2); 124 assert(a.min == -3); 125 }