Libraryless. Click here for Pure Java version (9152L/50K).
// AppendableChain has one "smart" head element (with size counter // and pointer to the chain's last element), all the other nodes are // maximally simple (MinimalChain). // This allows O(1) front insertion, front removal and back insertion // (not removal at the back though) which is fine for what I need this // for (event queues). // // Stefan Reich, Oct 21 sclass AppendableChain<A> extends MinimalChain<A> is Iterable<A>, IntSize { MinimalChain<A> last; // pointer to last element in chain (which may be us) gettable int size; // total length of chain *() {} // only used internally *(A *element) { size = 1; last = this; } // intermediate constructor called by itemPlusChain() *(A *element, AppendableChain<A> *next) { if (next == null) ret; new MinimalChain<A> b; b.element = next.element; b.next = next.next; this.next = b; last = next.last; size = next.size+1; } toString { ret str(toList()); } // append at the end bool add(A a) { MinimalChain newLast = new MinimalChain(a); last.next = newLast; last = newLast; ++size; true; } // drop first element AppendableChain<A> popFirst() { if (next == null) null; element = next.element; if (last == next) last = this; next = next.next; --size; this; } ArrayList<A> toList() { ArrayList<A> l = emptyList(size); MinimalChain<A> c = this; while (c != null) { l.add(c.element); c = c.next; } ret l; } //public Iterator<A> iterator() { ret toList().iterator(); } class ACIt > ItIt<A> { MinimalChain<A> c = AppendableChain.this; public bool hasNext() { ret c != null; } public A next() { var a = c.element; c = c.next; ret a; } } public ItIt<A> iterator() { ret new ACIt; } }
Began life as a copy of #1027968
download show line numbers debug dex old transpilations
Travelled to 4 computer(s): bhatertpkbcr, mowyntqkapby, mqqgnosmbjvj, wnsclhtenguj
No comments. add comment
Snippet ID: | #1032858 |
Snippet name: | AppendableChain - singly-linked cons list (forward connected) with a pointer to the end so you can append cheaply |
Eternal ID of this version: | #1032858/22 |
Text MD5: | fece5fa7a6eb51a45bd6b0112313d864 |
Transpilation MD5: | 3751c0557823aaf817656fbe42f85aa8 |
Author: | stefan |
Category: | javax |
Type: | JavaX fragment (include) |
Public (visible to everyone): | Yes |
Archived (hidden from active list): | No |
Created/modified: | 2022-07-19 19:34:05 |
Source code size: | 1937 bytes / 79 lines |
Pitched / IR pitched: | No / No |
Views / Downloads: | 310 / 531 |
Version history: | 21 change(s) |
Referenced in: | [show references] |