Merge pull request #152 from dlang-community/tree-tweaks

dlang-bot · web-flow · commit 3f1b64e29c0c · 2019-09-26T23:33:14.000+02:00
Make some enhancements to the treemap structure, and to the T-Tree do…
merged-on-behalf-of: Richard Andrew Cattermole &lt;alphaglosined@gmail.com&gt;
diff --git a/src/containers/treemap.d b/src/containers/treemap.d
@@ -218,6 +218,26 @@ struct TreeMap(K, V, Allocator = Mallocator, alias less = "a < b",
 		return tree[].map!(n => KeyValue(n.key, cast(CETV) n.value));
 	}
 
+    /**
+     * Returns: The value associated with the first key in the map.
+     */
+    auto front(this This)() inout pure @trusted
+    {
+        alias CETV = ContainerElementType!(This, V);
+
+        return cast(CETV) tree.front.value;
+    }
+
+    /**
+     * Returns: The value associated with the last key in the map.
+     */
+    auto back(this This)() inout pure @trusted
+    {
+        alias CETV = ContainerElementType!(This, V);
+
+        return cast(CETV) tree.back.value;
+    }
+
 private:
 
 	import containers.ttree : TTree;
diff --git a/src/containers/ttree.d b/src/containers/ttree.d
@@ -16,10 +16,14 @@ private import stdx.allocator.mallocator : Mallocator;
  *
  * T-tree Nodes are (by default) sized to fit within a 64-byte
  * cache line. The number of items stored per node can be read from the
- * `nodeCapacity` field. Each node has 0, 1, or 2 children. Each node has between
+ * `nodeCapacity` enum. Each node has 0, 1, or 2 children. Each node has between
  * 1 and `nodeCapacity` items, or it has `nodeCapacity` items and 0 or
  * more children.
  *
+ * Inserting or removing items while iterating a range returned from `opSlice`,
+ * `upperBound`, `equalRange`, or other similar functions will result in
+ * unpredicable and likely invalid iteration orders.
+ *
  * Params:
  *     T = the element type
  *     Allocator = the allocator to use. Defaults to `Mallocator`.
@@ -254,7 +258,7 @@ struct TTree(T, Allocator = Mallocator, bool allowDuplicates = false,
 	/**
 	 * Returns: the first element in the tree.
 	 */
-	inout(T) front(this This)() inout pure @trusted @property
+	auto front(this This)() inout pure @trusted @property
 	{
 		import std.exception : enforce;
 
@@ -269,7 +273,7 @@ struct TTree(T, Allocator = Mallocator, bool allowDuplicates = false,
 	/**
 	 * Returns: the last element in the tree.
 	 */
-	inout(T) back(this This)() inout pure @trusted @property
+	auto back(this This)() inout pure @trusted @property
 	{
 		import std.exception : enforce;
 
@@ -465,6 +469,9 @@ struct TTree(T, Allocator = Mallocator, bool allowDuplicates = false,
 
 	mixin AllocatorState!Allocator;
 
+	/// The number of values that can be stored in a single T-Tree node.
+	enum size_t nodeCapacity = N[0];
+
 private:
 
 	import containers.internal.element_type : ContainerElementType;
@@ -478,7 +485,6 @@ private:
 
 	alias N = FatNodeInfo!(T.sizeof, 3, cacheLineSize, ulong.sizeof);
 	alias Value = ContainerStorageType!T;
-	enum size_t nodeCapacity = N[0];
 	alias BookkeepingType = N[1];
 	enum HEIGHT_BIT_OFFSET = 48UL;
 	enum fullBitPattern = fullBits!(ulong, nodeCapacity);
