ocean.util.container.ebtree.model.KeylessMethods source code

1 /*******************************************************************************
2 
3     Elastic binary tree methods
4 
5     Used as mixin in the EBTree classes, contains the methods that do not use
6     keys.
7 
8     Copyright:
9         Copyright (c) 2009-2016 dunnhumby Germany GmbH.
10         All rights reserved.
11 
12     License:
13         Boost Software License Version 1.0. See LICENSE_BOOST.txt for details.
14         Alternatively, this file may be distributed under the terms of the Tango
15         3-Clause BSD License (see LICENSE_BSD.txt for details).
16 
17 *******************************************************************************/
18 
19 module ocean.util.container.ebtree.model.KeylessMethods;
20 
21 /*******************************************************************************
22 
23     Template with keyless methods.
24 
25     Template parameters:
26         Node = tree node struct type; expected to be an instance of the Node
27                struct template in ocean.util.container.ebtree.model.Node.
28 
29         eb_first = eb_node* ( eb_root* root ); returns the first node
30         eb_last  = eb_node* ( eb_root* root ); returns the last node
31 
32 *******************************************************************************/
33 
34 template KeylessMethods ( Node, alias eb_first, alias eb_last )
35 {
36     /***************************************************************************
37 
38         Removes a node from the tree.
39 
40         Params:
41             node = pointer to node to remove
42 
43     ***************************************************************************/
44 
45     public void remove ( ref Node node )
46     {
47         this.node_pool.recycle(node.remove());
48 
49         this.decreaseNodeCount(1);
50     }
51 
52     /***************************************************************************
53 
54         Returns:
55             pointer to node with lowest value in the tree
56 
57     ***************************************************************************/
58 
59     public Node* first ( )
60     out (node)
61     {
62         if (this.length)
63         {
64             assert (node, typeof (this).stringof ~
65                     ".first: got a null node but the tree is not empty");
66         }
67         else
68         {
69             assert (!node, typeof (this).stringof ~
70                            ".first: got a node but the tree is empty");
71         }
72     }
73     do
74     {
75         return this.ebCall!(eb_first)();
76     }
77 
78 
79     /***************************************************************************
80 
81         Returns:
82             pointer to node with highest value in the tree
83 
84     ***************************************************************************/
85 
86     public Node* last ( )
87     out (node)
88     {
89         if (this.length)
90         {
91             assert (node, typeof (this).stringof ~
92                     ".last: got a null node but the tree is not empty");
93         }
94         else
95         {
96             assert (!node, typeof (this).stringof ~
97                            ".last: got a node but the tree is empty");
98         }
99     }
100     do
101     {
102         return this.ebCall!(eb_last)();
103     }
104 
105 
106     /***************************************************************************
107 
108         foreach iterator over nodes in the tree. Any tree modification is
109         permitted during iteration.
110 
111     ***************************************************************************/
112 
113     public int opApply ( scope int delegate ( ref Node node ) dg )
114     {
115         int ret = 0;
116 
117         for (Node* node = this.first; node && !ret; node = node.next)
118         {
119             ret = dg(*node);
120         }
121 
122         return ret;
123     }
124 
125     /***************************************************************************
126 
127         foreach_reverse iterator over nodes in the tree. Any tree modification
128         is permitted during iteration.
129 
130     ***************************************************************************/
131 
132     public int opApply_reverse ( scope int delegate ( ref Node node ) dg )
133     {
134         int ret = 0;
135 
136         for (Node* node = this.last; node && !ret; node = node.prev)
137         {
138             ret = dg(*node);
139         }
140 
141         return ret;
142     }
143 
144     /**********************************************************************
145 
146         Library function call wrapper. Invokes eb_func with this &this.root
147         as first argument.
148 
149         Params:
150             eb_func = library function
151             args = additional eb_func arguments
152 
153         Returns:
154             passes through the return value of eb_func, which may be null.
155 
156      **********************************************************************/
157 
158     private Node* ebCall ( alias eb_func, T ... ) ( T args )
159     {
160         static assert (is (typeof (eb_func(&this.root, args)) ==
161                            typeof (Node.node_)*));
162 
163         return cast (Node*) eb_func(&this.root, args);
164     }
165 }