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