1 /** 2 This module contains some common utilities used by containers. 3 4 This module is a submodule of $(MREF std, container). 5 6 Source: $(PHOBOSSRC std/container/util.d) 7 8 Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders. 9 10 License: Distributed under the Boost Software License, Version 1.0. 11 (See accompanying file LICENSE_1_0.txt or copy at $(HTTP 12 boost.org/LICENSE_1_0.txt)). 13 14 Authors: $(HTTP erdani.com, Andrei Alexandrescu) 15 16 $(SCRIPT inhibitQuickIndex = 1;) 17 */ 18 module std.container.util; 19 20 /** 21 Returns an initialized object. This function is mainly for eliminating 22 construction differences between structs and classes. It allows code to not 23 worry about whether the type it's constructing is a struct or a class. 24 */ 25 template make(T) 26 if (is(T == struct) || is(T == class)) 27 { 28 T make(Args...)(Args arguments) 29 if (is(T == struct) && __traits(compiles, T(arguments))) 30 { 31 // constructing an std.container.Array without arguments, 32 // does not initialize its payload and is equivalent 33 // to a null reference. We therefore construct an empty container 34 // by passing an empty array to its constructor. 35 // https://issues.dlang.org/show_bug.cgi?id=13872. 36 static if (arguments.length == 0) 37 { 38 import std.range.primitives : ElementType; 39 alias ET = ElementType!(T.Range); 40 return T(ET[].init); 41 } 42 else 43 return T(arguments); 44 } 45 46 T make(Args...)(Args arguments) 47 if (is(T == class) && __traits(compiles, new T(arguments))) 48 { 49 return new T(arguments); 50 } 51 } 52 53 54 /// 55 @system unittest 56 { 57 import std.algorithm.comparison : equal; 58 import std.container; 59 60 auto arr = make!(Array!int)([4, 2, 3, 1]); 61 assert(equal(arr[], [4, 2, 3, 1])); 62 63 auto rbt = make!(RedBlackTree!(int, "a > b"))([4, 2, 3, 1]); 64 assert(equal(rbt[], [4, 3, 2, 1])); 65 66 alias makeList = make!(SList!int); 67 auto slist = makeList(1, 2, 3); 68 assert(equal(slist[], [1, 2, 3])); 69 } 70 71 @system unittest 72 { 73 import std.algorithm.comparison : equal; 74 import std.container; 75 76 auto arr1 = make!(Array!dchar)(); 77 assert(arr1.empty); 78 auto arr2 = make!(Array!dchar)("hello"d); 79 assert(equal(arr2[], "hello"d)); 80 81 auto rtb1 = make!(RedBlackTree!dchar)(); 82 assert(rtb1.empty); 83 auto rtb2 = make!(RedBlackTree!dchar)('h', 'e', 'l', 'l', 'o'); 84 assert(equal(rtb2[], "ehlo"d)); 85 } 86 87 // https://issues.dlang.org/show_bug.cgi?id=8895 88 @safe unittest 89 { 90 import std.algorithm.comparison : equal; 91 import std.container; 92 93 auto a = make!(DList!int)(1,2,3,4); 94 auto b = make!(DList!int)(1,2,3,4); 95 auto c = make!(DList!int)(1,2,3,5); 96 auto d = make!(DList!int)(1,2,3,4,5); 97 assert(a == b); // this better terminate! 98 assert(a != c); 99 assert(a != d); 100 } 101 102 /** 103 * Convenience function for constructing a generic container. 104 */ 105 template make(alias Container, Args...) 106 if (!is(Container)) 107 { 108 import std.range : isInputRange, isInfinite; 109 import std.traits : isDynamicArray; 110 111 auto make(Range)(Range range) 112 if (!isDynamicArray!Range && isInputRange!Range && !isInfinite!Range) 113 { 114 import std.range : ElementType; 115 return .make!(Container!(ElementType!Range, Args))(range); 116 } 117 118 auto make(T)(T[] items...) 119 if (!isInfinite!T) 120 { 121 return .make!(Container!(T, Args))(items); 122 } 123 } 124 125 /// forbid construction from infinite range 126 @safe unittest 127 { 128 import std.container.array : Array; 129 import std.range : only, repeat; 130 import std.range.primitives : isInfinite; 131 static assert(__traits(compiles, { auto arr = make!Array(only(5)); })); 132 static assert(!__traits(compiles, { auto arr = make!Array(repeat(5)); })); 133 } 134 135 /// 136 @system unittest 137 { 138 import std.algorithm.comparison : equal; 139 import std.container.array, std.container.rbtree, std.container.slist; 140 import std.range : iota; 141 142 auto arr = make!Array(iota(5)); 143 assert(equal(arr[], [0, 1, 2, 3, 4])); 144 145 auto rbtmax = make!(RedBlackTree, "a > b")(iota(5)); 146 assert(equal(rbtmax[], [4, 3, 2, 1, 0])); 147 148 auto rbtmin = make!RedBlackTree(4, 1, 3, 2); 149 assert(equal(rbtmin[], [1, 2, 3, 4])); 150 151 alias makeList = make!SList; 152 auto list = makeList(1, 7, 42); 153 assert(equal(list[], [1, 7, 42])); 154 } 155 156 @safe unittest 157 { 158 import std.algorithm.comparison : equal; 159 import std.container.rbtree; 160 161 auto rbtmin = make!(RedBlackTree, "a < b", false)(3, 2, 2, 1); 162 assert(equal(rbtmin[], [1, 2, 3])); 163 } 164 165 // https://issues.dlang.org/show_bug.cgi?id=13872 166 @system unittest 167 { 168 import std.container; 169 170 auto tree1 = make!(RedBlackTree!int)(); 171 auto refToTree1 = tree1; 172 refToTree1.insert(1); 173 assert(1 in tree1); 174 175 auto array1 = make!(Array!int)(); 176 auto refToArray1 = array1; 177 refToArray1.insertBack(1); 178 assert(!array1.empty); 179 180 auto slist = make!(SList!int)(); 181 auto refToSlist = slist; 182 refToSlist.insert(1); 183 assert(!slist.empty); 184 185 auto dlist = make!(DList!int)(); 186 auto refToDList = dlist; 187 refToDList.insert(1); 188 assert(!dlist.empty); 189 }