Algorithmen & Datenstrukturen mit Java: ds.destructive.list.LinkedRing

1package ds.destructive.list;

3/** A linked ring is an efficient implementation

4 for FIFO buffers (queues).

6 A ring is always a destructive data structure,

7 every modifying operation changes some references

8 in the LinkedRing objects.

9 */

11import ds.interfaces.List;

12import ds.util.NullIterator;

13import ds.util.E;

14import java.util.Iterator;

16import static ds.util.Undef.undefined;

18public abstract class LinkedRing

19 implements List {

21 //----------------------------------------

22 // the smart constructors

24 // empty ring

25 public static LinkedRing empty() {

26 return

27 EMPTY;

28 }

30 // singleton ring

31 public static LinkedRing singleton(E e) {

32 return

33 new Node(e);

34 }

36 // list from iterator

37 public static LinkedRing fromIterator(Iterator<E> elems) {

38 LinkedRing acc = empty();

39 while ( elems.hasNext() ) {

40 E info = elems.next();

41 acc = acc.append(info);

42 }

43 return

44 acc;

45 }

47 //----------------------------------------

49 public boolean inv() {

50 return

51 true;

52 }

54 public abstract LinkedRing concat(List l2);

56 public LinkedRing append(E e) {

57 return

58 this.concat(singleton(e));

59 }

61 public LinkedRing cons(E e) {

62 return

63 singleton(e).concat(this);

64 }

66 //----------------------------------------

67 // generally usable methods

68 // working with iterators

70 public E at(int i) {

71 Iterator<E> xs = iterator();

72 while ( i != 0 ) {

73 xs.next();

74 --i;

75 }

76 return

77 xs.next();

78 }

80 public boolean member(E e) {

81 for (E x : this)

82 if ( e.equalTo(x) )

83 return

84 true;

85 return

86 false;

87 }

89 public int length() {

90 int res = 0;

91 for (E x : this)

92 ++res;

93 return

94 res;

95 }

97 public LinkedRing copy() {

98 LinkedRing res = empty();

99 for (E x : this)

100 res = res.append(x);

101 return

102 res;

103 }

104

105 public String toString() {

106 return

107 iterator().toString();

108 }

109

110 //----------------------------------------

111 // the empty ring

112

113 // the "generic" empty ring object

114

115 private static final LinkedRing EMPTY

116 = new Empty();

117

118 // the singleton class for the empty list object

119

120 private static final

121 class Empty

122 extends LinkedRing {

123

124 public boolean isEmpty() {

125 return true;

126 }

127

128 public boolean member(E e) {

129 return false;

130 }

131

132 public int length() {

133 return 0;

134 }

135

136 public E head() {

137 return

138 undefined("head of empty list");

139 }

140

141 public LinkedRing tail() {

142 return

143 undefined("tail of empty list");

144 }

145

146 public E last() {

147 return

148 undefined("last of empty list");

149 }

150

151 public LinkedRing init() {

152 return

153 undefined("init of empty list");

154 }

155

156 public LinkedRing concat(List l2) {

157 // only linked rings are allowed for l2

158 return

159 (LinkedRing)l2;

160 }

161 public LinkedRing reverse() {

162 return

163 this;

164 }

165 public LinkedRing copy() {

166 return

167 this;

168 }

169

170 public Iterator<E> iterator() {

171 ++cntIter;

172 return

173 new NullIterator<E>();

174 }

175

176 //----------------------------------------

177 // not public stuff

178

179 Empty() { }

180 }

181

182 // downcast from LinkedRing to Node

183 Node node() {

184 return

185 undefined("Node expected");

186 }

187

188 //----------------------------------------

189 // the none empty list class

190

191 private static final

192 class Node

193 extends LinkedRing {

194

195 public boolean isEmpty() {

196 return false;

197 }

198

199 public E head() {

200 return

201 next.info;

202 }

203

204 public LinkedRing tail() {

205 if ( next == this ) // singleton ring

206 return

207 empty();

208 next = next.next;

209 return

210 this;

211 }

212

213 public E last() {

214 return

215 info;

216 }

217

218 public LinkedRing init() {

219 if ( next == this ) // singleton ring

220 return

221 empty();

222

223 // search the node in front of this

224 Node cur = this.next.node();

225 while ( cur.next != this ) {

226 cur = cur.next.node();

227 }

228 cur.next = this.next;

229 return

230 cur;

231 }

232

233 public LinkedRing concat(List l2) {

234 // only linked rings are allowed for l2

235 LinkedRing r2 = (LinkedRing)l2;

236

237 if ( r2.isEmpty() )

238 return

239 this;

240

241 Node n2 = r2.node();

242 Node t = n2.next;

243 n2 .next = next;

244 this.next = t;

245 return

246 n2;

247 }

248

249 public LinkedRing reverse() {

250 Node cur = this.next.node();

251 Node prv = this;

252 while ( cur != this ) {

253 Node tmp = cur.next.node();

254 cur.next = prv;

255 prv = cur;

256 cur = tmp;

257 }

258 Node res = this.next;

259 this.next = prv;

260 return

261 res;

262 }

263

264 public Iterator<E> iterator() {

265 ++cntIter;

266 return

267 new NodeIterator(this);

268 }

269

270 //----------------------------------------

271 // not public stuff

272

273 private E info;

274 private Node next;

275

276 Node(E e) {

277 info = e;

278 next = this;

279 ++cntNode;

280 }

281

282 // downcast from LinkedRing to Node

283 Node node() {

284 return this;

285 }

286

287 // iterator for none empty rings

288 private static final

289 class NodeIterator

290 extends ds.util.Iterator<E> {

291

292 Node r;

293 Node cur;

294 boolean first;

295

296 NodeIterator(Node r) {

297 this.r = r;

298 this.cur = r;

299 this.first = true;

300 }

301

302 public boolean hasNext() {

303 return

304 first || r != cur;

305 }

306

307 public E next() {

308 if ( ! hasNext() )

309 return

310 undefined("ring exhausted");

311

312 first = false;

313 cur = cur.next;

314 return

315 cur.info;

316 }

317 }

318 }

319

320 //----------------------------------------

321 // profiling

322

323 private static int cntNode = 0;

324 private static int cntIter = 0;

325

326 public static String stats() {

327 return

328 "stats for ds.destructive.list.LinkedRing:\n" +

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

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

331 }

332}