Not logged in.  Login/Logout/Register | List snippets | | Create snippet | Upload image | Upload data

79
LINES

< > BotCompany Repo | #1032858 // AppendableChain - singly-linked cons list (forward connected) with a pointer to the end so you can append cheaply

JavaX fragment (include) [tags: use-pretranspiled]

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;
  }
}

Author comment

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]