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 }