Algorithmen & Datenstrukturen mit Java: ds.persistent.list.LinkedList

1package ds.persistent.list;

3/** Implementation of single linked lists.

4 The element type is the example class E

5 In real world java progs, this would be a

6 generic type parameter.

8 This implementation is a PERSISTENT one.

9*/

11import ds.interfaces.List;

12import ds.util.E;

13import java.util.Iterator;

15import static ds.util.Undef.undefined;

17public abstract class LinkedList

18 implements List {

20 //----------------------------------------

21 // the smart constructors

23 // empty list

24 public static

25 LinkedList empty() {

27 return

28 EMPTY;

29 }

31 // singleton list

32 public static

33 LinkedList singleton(E e) {

34 return

35 EMPTY.cons(e);

36 }

38 // list from iterator

39 public static

40 LinkedList fromIterator(Iterator<E> elems) {

42 if ( elems.hasNext() ) {

43 E info = elems.next();

44 return

45 fromIterator(elems).cons(info);

46 }

47 return

48 empty();

49 }

51 //----------------------------------------

52 // public methods

54 public boolean inv() {

55 return true;

56 }

58 public abstract LinkedList init();

59 public abstract LinkedList tail();

61 public abstract LinkedList concat(List l2);

63 public LinkedList append(E e) {

64 return

65 concat(singleton(e));

66 }

68 public Node cons(E e) {

69 return

70 new Node(e, this);

71 }

73 public LinkedList reverse() {

74 return

75 reverse1(empty());

76 }

77 abstract protected LinkedList reverse1(LinkedList res);

79 // default impementation for copy

80 public LinkedList copy() {

81 return

82 this;

83 }

85 public Iterator<E> iterator() {

86 return

87 new ListIterator(this);

88 }

90 public String toString() {

91 return

92 (new ListIterator(this)).toString();

93 }

95 //----------------------------------------

96 // the empty list

98 // the "generic" empty list object, (the singleton has a raw type)

100 private static final LinkedList EMPTY

101 = new Empty();

102

103 // the singleton class for the empty list object

104

105 private static final

106 class Empty

107 extends LinkedList {

108

109 public boolean isEmpty() {

110 return true;

111 }

112 public boolean member(E e) {

113 return false;

114 }

115 public int length() {

116 return 0;

117 }

118 public E head() {

119 return

120 undefined("head of empty list");

121 }

122 public LinkedList tail() {

123 return

124 undefined("tail of empty list");

125 }

126 public E last() {

127 return

128 undefined("last of empty list");

129 }

130 public LinkedList init() {

131 return

132 undefined("init of empty list");

133 }

134 public E at(int i) {

135 return

136 undefined("at of empty list");

137 }

138 public LinkedList concat(List l2) {

139 return

140 (LinkedList)l2;

141 }

142

143 //----------------------------------------

144 // not public stuff

145

146 Empty() { }

147

148 protected LinkedList reverse1(LinkedList acc) {

149 return

150 acc;

151 }

152 }

153

154 //----------------------------------------

155 // the none empty list class

156

157 private static final

158 class Node

159 extends LinkedList {

160

161 public boolean isEmpty() {

162 return

163 false;

164 }

165

166 public boolean member(E e) {

167 return

168 e.equalTo(info)

169 ||

170 next.member(e);

171 }

172

173 public int length() {

174 return

175 1 + next.length();

176 }

177

178 public E head() {

179 return

180 info;

181 }

182

183 public LinkedList tail() {

184 return

185 next;

186 }

187

188 public E last() {

189 if ( next.isEmpty() )

190 return

191 info;

192 return

193 next.last();

194 }

195

196 public LinkedList init() {

197 if ( next.isEmpty() )

198 return

199 empty();

200 return

201 setNext(next.init());

202 }

203

204 public E at(int i) {

205 if ( i == 0 )

206 return

207 info;

208 return

209 next.at(i - 1);

210 }

211

212 public LinkedList concat(List l2) {

213 return

214 setNext(next.concat(l2));

215 }

216

217 /* destructive *

218 public LinkedList copy() { // duplicate all nodes

219 return

220 next.copy().cons(info);

221 }

222 /**/

223

224 //----------------------------------------

225 // not public stuff

226

227 private final E info;

228 private

229 /* persistent */ final /**/

230 LinkedList next;

231

232 Node(E i, LinkedList n) {

233 info = i;

234 next = n;

235 ++cntNode;

236 }

237

238 protected LinkedList reverse1(LinkedList acc) {

239 return

240 next.reverse1(setNext(acc));

241 }

242

243 Node setNext(LinkedList l2) {

244 /* persistent */

245 if ( l2 == next )

246 return

247 this;

248 return

249 l2.cons(info);

250

251 /* destructive *

252 next = l2;

253 return

254 this;

255 /**/

256 }

257 }

258

259 //----------------------------------------

260 // iterator class

261

262 private static

263 class ListIterator

264 extends ds.util.Iterator<E> {

265

266 List cur;

267

268 ListIterator(List l) {

269 cur = l;

270 ++cntIter;

271 }

272

273 public boolean hasNext() {

274 return

275 ! cur.isEmpty();

276 }

277

278 public E next() {

279 if ( cur.isEmpty() )

280 return

281 undefined("iterator exhausted");

282

283 E res = cur.head();

284 cur = cur.tail();

285 return

286 res;

287 }

288 }

289

290 //----------------------------------------

291 // profiling

292

293 private static int cntNode = 0;

294 private static int cntIter = 0;

295

296 public static String stats() {

297 return

298 "stats for ds.persistent.list.List:\n" +

299 "# new Node() : " + cntNode + "\n" +

300 "# new ListIterator() : " + cntIter + "\n";

301 }

302}