1 module prova.util.linkedlist;
2 
3 import std.typecons;
4 
5 /**
6  * Linked list node
7  */
8 class Node(T)
9 {
10   private LinkedList!T list;
11   private Node!T next;
12   private Node!T last;
13   private Nullable!T _value;
14 
15   /**
16    * Retrieves the stored value
17    */
18   @property T value()
19   {
20     return _value;
21   }
22 
23   /**
24    * Modifies the stored value
25    */
26   @property void value(T value)
27   {
28     _value = value;
29   }
30 
31   /**
32    * Gets the node previous in order
33    */
34   Node!T getLast()
35   {
36     return last;
37   }
38 
39   /**
40    * Gets the node next in order
41    */
42   Node!T getNext()
43   {
44     return next;
45   }
46 
47   /**
48    * Detaches the node from the list
49    */
50   void remove()
51   {
52     if(last)
53       last.next = next;
54 
55     if(next)
56       next.last = last;
57 
58     if(list.last == this)
59       list.last = null;
60 
61     if(list.first == this)
62       list.first = null;
63 
64     list.count--;
65   }
66 }
67 
68 /**
69   * LinkedList template
70   */
71 class LinkedList(T)
72 {
73   private Node!T first;
74   private Node!T last;
75   private int count = 0;
76 
77   /**
78     * Returns the node count
79     */
80   @property int length()
81   {
82     return count;
83   }
84 
85   ///
86   Node!T getFirstNode()
87   {
88     return first;
89   }
90 
91   ///
92   Node!T getLastNode()
93   {
94     return last;
95   }
96 
97   /**
98     * Creates a node and places it at the start of the list
99     */
100   Node!T insertFront(T value)
101   {
102     return insertBefore(value, first);
103   }
104 
105   /**
106     * Creates a node and places it at the end of the list
107     */
108   Node!T insertBack(T value)
109   {
110     return insertAfter(value, last);
111   }
112 
113   /**
114     * Creates a node in the list placed before the specified node
115     */
116   Node!T insertBefore(T value, Node!T node)
117   {
118     if(!node && first)
119       return insertBefore(value, first);
120 
121     Node!T storedNode = new Node!T;
122     storedNode.value = value;
123     storedNode.list = this;
124 
125     if(node) {
126       storedNode.last = node.last;
127       node.last = storedNode;
128       storedNode.next = node;
129     } else {
130       first = last = storedNode;
131     }
132 
133     if(storedNode.last)
134       storedNode.last.next = storedNode;
135 
136     count++;
137     return storedNode;
138   }
139 
140   /**
141     * Creates a node in the list placed after the specified node
142     */
143   Node!T insertAfter(T value, Node!T node)
144   {
145     if(!node && last)
146       return insertAfter(value, last);
147 
148     Node!T storedNode = new Node!T;
149     storedNode.value = value;
150     storedNode.list = this;
151 
152     if(node) {
153       storedNode.next = node.next;
154       node.next = storedNode;
155       storedNode.last = node;
156     } else {
157       first = last = storedNode;
158     }
159 
160     if(storedNode.next)
161       storedNode.next.last = storedNode;
162 
163     count++;
164     return storedNode;
165   }
166 
167   /**
168     * Tests if the list contains a node with the specified value
169     */
170   bool contains(T value)
171   {
172     foreach(Node!T node; this)
173       if(node.value == value)
174         return true;
175 
176     return false;
177   }
178 
179   /**
180     * Removes the first node with the specified value
181     */
182   void remove(T value)
183   {
184     foreach(Node!T node; this) {
185       if(node.value == value) {
186         node.remove();
187         break;
188       }
189     }
190   }
191 
192   /**
193     * Empties the LinkedList
194     */
195   void clear()
196   {
197     first = null;
198     last = null;
199     count = 0;
200   }
201 
202   int opApply(int delegate(Node!T result) dg)
203   {
204     int result = 0;
205 
206     for(Node!T node = first; node; node = node.next) {
207       result = dg(node);
208 
209       if(result)
210         break;
211     }
212 
213     return result;
214   }
215 
216   int opApply(int delegate(ref T result) dg)
217   {
218     int result = 0;
219 
220     for(Node!T node = first; node; node = node.next) {
221       T value = node.value;
222       result = dg(value);
223       node.value = value;
224 
225       if(result)
226         break;
227     }
228 
229     return result;
230   }
231 }