Mercurial > projects > dynamin

annotate dynamin/core/list.d @ 113:4636a64afabc default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add reverse() function.
author Jordan Miner <jminer7@gmail.com>
date Sat, 19 Jan 2013 21:08:52 -0600
parents acdbb30fee7e
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
1
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
2 /*
103
73060bc3f004 Change license to Boost 1.0 and MPL 2.0.
Jordan Miner <jminer7@gmail.com>
parents: 87
diff changeset
3 * Copyright Jordan Miner
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
4 *
103
73060bc3f004 Change license to Boost 1.0 and MPL 2.0.
Jordan Miner <jminer7@gmail.com>
parents: 87
diff changeset
5 * Distributed under the Boost Software License, Version 1.0.
73060bc3f004 Change license to Boost 1.0 and MPL 2.0.
Jordan Miner <jminer7@gmail.com>
parents: 87
diff changeset
6 * (See accompanying file BOOST_LICENSE.txt or copy at
73060bc3f004 Change license to Boost 1.0 and MPL 2.0.
Jordan Miner <jminer7@gmail.com>
parents: 87
diff changeset
7 * http://www.boost.org/LICENSE_1_0.txt)
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
8 *
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
9 */
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
10
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
11 module dynamin.core.list;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
12
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
13 import dynamin.core.global;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
14 import dynamin.core.string;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
15 import dynamin.core.math;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
16 import tango.io.Stdout;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
17
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
18 // TODO: QuickSearch()
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
19 // TODO: BinarySearch()
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
20 // MUST use (high + low) >>> 1 to find the average
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
21 // TODO: Search()
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
22 // TODO: QuickSort()
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
23 // TODO: HeapSort()
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
24 // TODO: Sort() - calls HeapSort() so stable sort is default
83
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
25
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
26 /// Represents the ways items can be changed in a list.
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
27 enum ListChangeType {
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
28 /// An item was added to the list.
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
29 Added,
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
30 /// An item was removed from the list.
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
31 Removed,
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
32 /// An item was replaced with another item.
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
33 Replaced
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
34 }
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
35
84
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
36 /**
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
37 * A list of items backed by an array. If changeNotification is true, then a delegate is passed
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
38 * into the constructor as a callback. The delegate will be called when any item is added to or
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
39 * removed from the list. Also, when changeNotfication is true, some methods are not
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
40 * available. These are marked in their documentation.
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
41 */
83
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
42 class List(T, bool changeNotification = false) {
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
43 protected:
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
44 T[] _data;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
45 uint _count;
83
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
46 static if(changeNotification)
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
47 void delegate(ListChangeType, T, T, uint) whenChanged;
106
acdbb30fee7e Port to D2.
Jordan Miner <jminer7@gmail.com>
parents: 103
diff changeset
48 enum int DefaultCapacity = 16;
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
49 public:
84
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
50 /**
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
51 * Creates a list with the specified capacity.
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
52 *
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
53 * Only available if changeNotification is false.
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
54 */
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
55 this() {
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
56 static if(changeNotification)
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
57 throw new Exception("not available");
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
58 this(DefaultCapacity);
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
59 }
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
60 /// ditto
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
61 this(uint capacity) {
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
62 static if(changeNotification)
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
63 throw new Exception("not available");
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
64 _data = new T[capacity];
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
65 }
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
66
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
67 /**
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
68 * Creates a list with the specified capacity and with a delegate that will be called
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
69 * when an item is added to or removed from the list. The type specifies whether an
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
70 * item was added, removed, or replaced. oldItem contains the item that was removed,
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
71 * and newItem contains the item that was added. So if type is ListChangeType.Added,
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
72 * oldItem will be T.init (which is null for reference types). If type is
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
73 * ListChangeType.Removed, newItem will be T.init. The index of the item after being
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
74 * added or before being removed is also passed to the delegate.
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
75 *
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
76 * Only available if changeNotification is true.
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
77 */
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
78 this(void delegate(ListChangeType type, T oldItem, T newItem, uint index) whenChanged) {
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
79 static if(changeNotification) {
83
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
80 this(DefaultCapacity, whenChanged);
84
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
81 } else {
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
82 throw new Exception("not available");
55
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
83 }
84
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
84 }
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
85 /// ditto
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
86 this(uint capacity,
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
87 void delegate(ListChangeType type, T oldItem, T newItem, uint index) whenChanged) {
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
88 static if(changeNotification) {
80
f1e176a76c00 Rearrange List constructors and add a constant for the default capacity.
Jordan Miner <jminer7@gmail.com>
parents: 56
diff changeset
89 _data = new T[capacity];
83
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
90 this.whenChanged = whenChanged;
84
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
91 } else {
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
92 throw new Exception("not available");
80
f1e176a76c00 Rearrange List constructors and add a constant for the default capacity.
Jordan Miner <jminer7@gmail.com>
parents: 56
diff changeset
93 }
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
94 }
84
7653269724db Add comments for the List class and its constructors.
Jordan Miner <jminer7@gmail.com>
parents: 83
diff changeset
95
55
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
96 static List!(T) fromArray(T[] arr...) {
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
97 auto list = new List!(T)();
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
98 list._data = arr.dup;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
99 list._count = arr.length;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
100 return list;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
101 }
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
102 uint count() {
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
103 return _count;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
104 }
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
105 uint capacity() {
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
106 return _data.length;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
107 }
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
108 T[] toArray() {
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
109 return _data[0.._count].dup;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
110 }
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
111 T[] data() {
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
112 return _data[0.._count];
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
113 }
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
114 /*string toString() {
106
acdbb30fee7e Port to D2.
Jordan Miner <jminer7@gmail.com>
parents: 103
diff changeset
115 mstring str = "[";
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
116 if(Count > 0)
106
acdbb30fee7e Port to D2.
Jordan Miner <jminer7@gmail.com>
parents: 103
diff changeset
117 str ~= toString(this[0]);
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
118 foreach(item; this) {
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
119 str ~= ", ";
106
acdbb30fee7e Port to D2.
Jordan Miner <jminer7@gmail.com>
parents: 103
diff changeset
120 str ~= toString(item);
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
121 }
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
122 str ~= "]";
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
123 return str;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
124 }*/
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
125 protected void maybeEnlarge(uint neededCap) {
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
126 if(neededCap <= capacity)
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
127 return;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
128 _data.length = max(neededCap, (capacity+1)*2);
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
129 }
106
acdbb30fee7e Port to D2.
Jordan Miner <jminer7@gmail.com>
parents: 103
diff changeset
130 ref T opIndex(uint index) {
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
131 return _data[0.._count][index];
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
132 }
83
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
133 void opIndexAssign(T item, uint index) {
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
134 T oldItem = _data[0.._count][index];
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
135 _data[0.._count][index] = item;
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
136 static if(changeNotification)
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
137 whenChanged(ListChangeType.Replaced, oldItem, item, index);
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
138 }
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
139 void push(T item) {
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
140 add(item);
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
141 }
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
142 T pop() {
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
143 if(_count < 1)
56
c2566ab82535 Edit comments and fix a typo.
Jordan Miner <jminer7@gmail.com>
parents: 55
diff changeset
144 throw new Exception("List.pop() - List is empty");
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
145 T item = _data[_count-1];
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
146 // must null out to allow to be collected
87
7cf356729515 Set removed items in a List to T.init. T could be a struct containing a pointer
Jordan Miner <jminer7@gmail.com>
parents: 84
diff changeset
147 _data[_count-1] = T.init;
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
148 --_count;
83
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
149 static if(changeNotification)
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
150 whenChanged(ListChangeType.Removed, item, T.init, _count);
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
151 return item;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
152 }
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
153 void add(T item) {
55
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
154 insert(item, _count);
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
155 }
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
156 void remove(T item) {
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
157 uint i = find(item);
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
158 if(i == -1)
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
159 return;
81
de94552446ab Add List.removeAt() and tests for it.
Jordan Miner <jminer7@gmail.com>
parents: 80
diff changeset
160 removeAt(i);
de94552446ab Add List.removeAt() and tests for it.
Jordan Miner <jminer7@gmail.com>
parents: 80
diff changeset
161 }
de94552446ab Add List.removeAt() and tests for it.
Jordan Miner <jminer7@gmail.com>
parents: 80
diff changeset
162 void removeAt(uint index) {
de94552446ab Add List.removeAt() and tests for it.
Jordan Miner <jminer7@gmail.com>
parents: 80
diff changeset
163 T item = _data[index];
55
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
164
81
de94552446ab Add List.removeAt() and tests for it.
Jordan Miner <jminer7@gmail.com>
parents: 80
diff changeset
165 for(uint i = index + 1; i < _count; ++i)
55
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
166 _data[i-1] = _data[i];
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
167 // must null out to allow to be collected
87
7cf356729515 Set removed items in a List to T.init. T could be a struct containing a pointer
Jordan Miner <jminer7@gmail.com>
parents: 84
diff changeset
168 _data[_count-1] = T.init;
55
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
169 --_count;
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
170
83
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
171 static if(changeNotification)
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
172 whenChanged(ListChangeType.Removed, item, T.init, index);
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
173 }
55
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
174 void insert(T item, uint index) {
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
175 maybeEnlarge(_count+1);
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
176 arrayCopy!(T)(_data, index, _data, index+1, _count - index);
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
177 _data[index] = item;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
178 ++_count;
83
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
179 static if(changeNotification)
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
180 whenChanged(ListChangeType.Added, T.init, item, index);
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
181 }
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
182 void clear() {
55
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
183 for(; _count > 0; --_count) {
83
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
184 static if(changeNotification)
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
185 whenChanged(ListChangeType.Removed, _data[_count-1], T.init, _count-1);
55
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
186 // must null out to allow to be collected
87
7cf356729515 Set removed items in a List to T.init. T could be a struct containing a pointer
Jordan Miner <jminer7@gmail.com>
parents: 84
diff changeset
187 data[_count-1] = T.init;
55
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
188 }
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
189 }
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
190 uint find(T item) {
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
191 foreach(i, item2; _data)
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
192 if(item == item2) // if(item2 == item) would crash on a null item
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
193 return i;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
194 return -1;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
195 }
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
196 //trimCapacity()
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
197 //opConcat
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
198 //opEquals
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
199 //opSlice
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
200 //opSliceAssign
106
acdbb30fee7e Port to D2.
Jordan Miner <jminer7@gmail.com>
parents: 103
diff changeset
201 int opApply(int delegate(ref T item) dg) {
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
202 for(uint i = 0; i < _count; ++i) {
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
203 if(int result = dg(_data[i]))
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
204 return result;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
205 }
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
206 return 0;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
207 }
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
208 //so you can do:
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
209 //foreach(i, item; list)
106
acdbb30fee7e Port to D2.
Jordan Miner <jminer7@gmail.com>
parents: 103
diff changeset
210 int opApply(int delegate(ref uint index, ref T item) dg) {
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
211 for(uint i = 0; i < _count; ++i) {
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
212 if(int result = dg(i, _data[i]))
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
213 return result;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
214 }
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
215 return 0;
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
216 }
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
217
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
218 }
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
219 unittest {
106
acdbb30fee7e Port to D2.
Jordan Miner <jminer7@gmail.com>
parents: 103
diff changeset
220 auto list = List!(char).fromArray("Hello, Mat".dup);
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
221 list.add('t');
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
222 assert(list.data == "Hello, Matt");
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
223 assert(list.pop() == 't');
55
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
224 assert(list.data == "Hello, Mat");
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
225 list.insert('!', 5);
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
226 assert(list.data == "Hello!, Mat");
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
227 list.remove('l');
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
228 assert(list.data == "Helo!, Mat");
81
de94552446ab Add List.removeAt() and tests for it.
Jordan Miner <jminer7@gmail.com>
parents: 80
diff changeset
229 list.removeAt(0);
de94552446ab Add List.removeAt() and tests for it.
Jordan Miner <jminer7@gmail.com>
parents: 80
diff changeset
230 assert(list.data == "elo!, Mat");
de94552446ab Add List.removeAt() and tests for it.
Jordan Miner <jminer7@gmail.com>
parents: 80
diff changeset
231 list.removeAt(8);
de94552446ab Add List.removeAt() and tests for it.
Jordan Miner <jminer7@gmail.com>
parents: 80
diff changeset
232 assert(list.data == "elo!, Ma");
de94552446ab Add List.removeAt() and tests for it.
Jordan Miner <jminer7@gmail.com>
parents: 80
diff changeset
233 list.removeAt(1);
de94552446ab Add List.removeAt() and tests for it.
Jordan Miner <jminer7@gmail.com>
parents: 80
diff changeset
234 assert(list.data == "eo!, Ma");
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
235 list.clear();
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
236 assert(list.data == "");
55
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
237
83
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
238 int a = 0, r = 0, r2 = 0;
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
239 void changed(ListChangeType t, string o, string n, uint) {
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
240 if(t == ListChangeType.Added) {
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
241 a++;
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
242 assert(o == "" && n != "");
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
243 }
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
244 if(t == ListChangeType.Removed) {
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
245 r++;
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
246 assert(n == "" && o != "");
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
247 }
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
248 if(t == ListChangeType.Replaced) {
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
249 r2++;
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
250 }
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
251 };
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
252 auto list2 = new List!(string, true)(&changed);
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
253 assert(a == 0 && r == 0 && r2 == 0);
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
254 list2.add("hello");
83
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
255 assert(a == 1 && r == 0 && r2 == 0);
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
256 assert(list2.pop() == "hello");
83
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
257 assert(a == 1 && r == 1 && r2 == 0);
55
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
258
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
259 list2.add("Hi");
83
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
260 list2.add("Jacob");
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
261 assert(a == 3 && r == 1 && r2 == 0);
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
262 list2[1] = "Matt";
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
263 assert(a == 3 && r == 1 && r2 == 1);
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
264 list2.insert("John", 1);
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
265 list2.insert("Pete", 3);
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
266 assert(list2.data == ["Hi", "John", "Matt", "Pete"]);
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
267 assert(a == 5 && r == 1 && r2 == 1);
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
268 list2.removeAt(0);
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
269 assert(list2.data == ["John", "Matt", "Pete"]);
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
270 assert(a == 5 && r == 2 && r2 == 1);
55
c138461bf845 Add focusing and other changes that are related
Jordan Miner <jminer7@gmail.com>
parents: 0
diff changeset
271 list2.clear();
83
3cfc83a99cbc Add List.opIndexAssign and switch to one callback for change notification.
Jordan Miner <jminer7@gmail.com>
parents: 81
diff changeset
272 assert(a == 5 && r == 5 && r2 == 1);
0
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
273 }
aa4efef0f0b1 Initial commit of code.
Jordan Miner <jminer7@gmail.com>
parents:
diff changeset
274