Libraryless. Click here for Pure Java version (3963L/23K).
// 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> { MinimalChain<A> last; // pointer to last element in chain (which may be us) 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 3 computer(s): bhatertpkbcr, mowyntqkapby, mqqgnosmbjvj
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/21 |
Text MD5: | bdb09b1d25bb8dc21040510c7ea22e46 |
Transpilation MD5: | 7f0ff33f5e0ab73a5ab6b081b303eb5a |
Author: | stefan |
Category: | javax |
Type: | JavaX fragment (include) |
Public (visible to everyone): | Yes |
Archived (hidden from active list): | No |
Created/modified: | 2021-10-07 13:30:05 |
Source code size: | 1919 bytes / 79 lines |
Pitched / IR pitched: | No / No |
Views / Downloads: | 134 / 284 |
Version history: | 20 change(s) |
Referenced in: | [show references] |