1 module dvector; 2 pragma(LDC_no_moduleinfo); 3 4 import core.stdc.stdlib; 5 6 private enum CAPACITY = 4; 7 8 struct Dvector(T) { 9 private T* chunks; 10 size_t total; 11 size_t capacity; 12 13 size_t length() @nogc nothrow { 14 return total; 15 } 16 17 this(T* chunks, size_t total, size_t capacity) @nogc nothrow { 18 this.chunks = chunks; 19 this.total = total; 20 this.capacity = capacity; 21 } 22 23 void pBack(T elem) @nogc nothrow { 24 if (capacity == total) 25 resize(capacity * 2); 26 chunks[total++] = elem; 27 } 28 29 ref T opIndex(size_t i) @nogc nothrow { 30 return chunks[i]; 31 } 32 33 void opIndexAssign(T elem, size_t i) @nogc nothrow { 34 chunks[i] = elem; 35 } 36 37 void remove(size_t index) @nogc nothrow { 38 for (size_t i = index; i < total - 1; i++) { 39 chunks[i] = chunks[i + 1]; 40 } 41 42 total--; 43 44 if (total > 0 && total == capacity / 4){ 45 resize(capacity / 2); 46 } 47 } 48 49 void allocIfneeded() @nogc nothrow { 50 if(chunks == null){ 51 capacity = CAPACITY; 52 T* _chunks = cast(T*)malloc(T.sizeof * CAPACITY); 53 this.chunks = _chunks; 54 } 55 } 56 57 void resize(size_t capacity) @nogc nothrow { 58 version(Debug){ 59 import core.stdc.stdio; 60 printf("resize: %d to %d\n", this.capacity, capacity); 61 } 62 63 T* chunks = cast(T*)realloc(this.chunks, T.sizeof * capacity); 64 if (chunks) { 65 this.chunks = chunks; 66 this.capacity = capacity; 67 } 68 } 69 70 void free() @nogc nothrow { 71 total = 0; 72 capacity = CAPACITY; 73 core.stdc.stdlib.free(chunks); 74 chunks = null; 75 } 76 77 int opApply(int delegate(ref T) @nogc nothrow dg) @nogc nothrow{ 78 int result = 0; 79 80 for (size_t k = 0; k < total; ++k) { 81 result = dg(chunks[k]); 82 83 if (result) { 84 break; 85 } 86 } 87 return result; 88 } 89 90 int opApply(int delegate(size_t i, ref T) @nogc nothrow dg) @nogc nothrow{ 91 int result = 0; 92 93 for (size_t k = 0; k < total; ++k) { 94 result = dg(k, chunks[k]); 95 96 if (result) { 97 break; 98 } 99 } 100 return result; 101 } 102 103 // overloads for gc usages: 104 int opApply(int delegate(ref T) dg){ 105 int result = 0; 106 107 for (size_t k = 0; k < total; ++k) { 108 result = dg(chunks[k]); 109 110 if (result) { 111 break; 112 } 113 } 114 return result; 115 } 116 117 int opApply(int delegate(size_t i, ref T) dg){ 118 int result = 0; 119 120 for (size_t k = 0; k < total; ++k) { 121 result = dg(k, chunks[k]); 122 123 if (result) { 124 break; 125 } 126 } 127 return result; 128 } 129 130 Dvector!T opBinary(string op)(ref Dvector!T rhs) @nogc nothrow{ 131 static if (op == "~"){ 132 allocIfneeded(); 133 foreach(elem; rhs) 134 pBack(elem); 135 return this; 136 } 137 else static assert(0, "Operator "~op~" not implemented"); 138 } 139 140 Dvector!T opBinary(string op)(T rhs) @nogc nothrow { 141 static if (op == "~"){ 142 allocIfneeded(); 143 pBack(rhs); 144 return this; 145 } 146 else static assert(0, "Operator "~op~" not implemented"); 147 } 148 149 @nogc nothrow Dvector!T opOpAssign(string op)(ref Dvector!T rhs) if (op == "~"){ 150 allocIfneeded(); 151 foreach(elem; rhs) 152 pBack(elem); 153 return this; 154 } 155 156 @nogc nothrow Dvector!T opOpAssign(string op)(ref T rhs) if (op == "~"){ 157 allocIfneeded(); 158 pBack(rhs); 159 return this; 160 } 161 162 void pFront(T elem) @nogc nothrow{ 163 allocIfneeded(); 164 pBack(T.init); 165 166 for(size_t i = length-1; i > 0; i--){ 167 chunks[i] = chunks[i - 1]; 168 } 169 chunks[0] = elem; 170 } 171 172 void insert(T elem, size_t position) @nogc nothrow{ 173 allocIfneeded(); 174 pBack(T.init); 175 176 for (size_t k = length-1; k > position; k--) 177 chunks[k] = chunks[k - 1]; 178 chunks[position] = elem; 179 } 180 181 T[] slice() @nogc nothrow{ 182 return chunks[0..length]; 183 } 184 } 185 186 unittest { 187 import core.stdc.stdio; 188 struct Person { string name; uint score;} 189 190 Dvector!(Person) prs1; 191 192 auto p1 = Person("ferhat", 5); 193 auto p2 = Person("Mike", 3); 194 auto p3 = Person("Rajneesh", 1); 195 auto p4 = Person("Ce", 2); 196 197 prs1 ~= p1; 198 prs1 ~= p2; 199 prs1 ~= p3; 200 prs1 ~= p4; 201 202 Dvector!(Person) prs2; 203 auto s1 = Person("Ezgi", 15); 204 auto s2 = Person("Emine", 36); 205 206 prs2 ~= s1; 207 prs2 ~= s2; 208 209 auto comb = prs1 ~ prs2; 210 211 comb.remove(2); 212 213 assert(comb[2].name == "Ce"); 214 215 auto cn = Person("Chuck", 100); 216 comb.pFront(cn); 217 218 assert(comb[0].name == "Chuck"); 219 220 auto srv = Person("SRV", 100); 221 comb.insert(srv, 3); 222 223 assert(comb[3].name == "SRV"); 224 225 foreach(i, p; comb){ 226 printf("%d: %s \n", i, p.name.ptr); 227 } 228 229 comb.free; 230 prs2.free; 231 }