1/** 2This module contains some common utilities used by containers. 3 4This module is a submodule of $(MREF std, container). 5 6Source: $(PHOBOSSRC std/container/util.d) 7 8Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders. 9 10License: Distributed under the Boost Software License, Version 1.0. 11(See accompanying file LICENSE_1_0.txt or copy at $(HTTP 12boost.org/LICENSE_1_0.txt)). 13 14Authors: $(HTTP erdani.com, Andrei Alexandrescu) 15 16$(SCRIPT inhibitQuickIndex = 1;) 17*/ 18module std.container.util; 19 20/** 21Returns an initialized object. This function is mainly for eliminating 22construction differences between structs and classes. It allows code to not 23worry about whether the type it's constructing is a struct or a class. 24 */ 25template make(T) 26if (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 */ 105template make(alias Container, Args...) 106if (!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} 190