SList.java

Go to the documentation of this file.

package aud;
 
import java.util.NoSuchElementException;
 
import aud.util.Graphvizable;
 
//@<slist:class
public class SList<T> implements Iterable<T>,
                                 Graphvizable {
  protected class Node {
    T    data_ = null;
    Node next_ = null;
 
    public Node(T data,Node next) {
      data_=data; next_=next;
    }
  }
 
  protected Node head_=null;
  //@>slist:class
 
  //
  // NOTE: Nested class Node and attribute head_ are defined protected
  //       (not package private) for use in an assignment.
  //
 
  //@<slist:ctor
  public SList() {}
  //@>slist:ctor
 
  //@<slist:size
  public int size() {
    int n=0;
    Node node=head_;
    while (node!=null) {
      node=node.next_;
      ++n;
    }
    return n;
  }
  //@>slist:size
 
  public boolean empty() {
    return head_==null;
  }
 
  //@<slist:check
  Node check(Node node) {
    if (node==null)
      throw new IndexOutOfBoundsException();
    return node;
  }
  //@>slist:check
 
  //@<slist:front
  public T front() {
    return check(head_).data_;
  }
  //@>slist:front
 
 
  public T back() {
    check(head_);
    Node node=head_;
    while (node.next_!=null)
      node=node.next_;
    return node.data_;
  }
 
  //@<slist:at
  public T at(int i) {
    Node node=head_;
    for (int j=0;node!=null && j<i;++j)
      node=node.next_;
    return check(node).data_;
  }
  //@>slist:at
 
  //@<slist:push_front
  public void push_front(T obj) {
    head_=new Node(obj,head_);
  }
  //@>slist:push_front
 
  //@<slist:push_back
  public void push_back(T obj) {
    if (head_==null)        // special case!
      head_=new Node(obj,null);
    else {
      Node node=head_;
      while (node.next_!=null)
        node=node.next_;
      node.next_=new Node(obj,null);
    }
  }
  //@>slist:push_back
 
  //@<slist:insert_after
  void insert_after(Node node,T obj) {
    if (node==null)
      head_=new Node(obj,head_);
    else {
      Node nxt=node.next_;
      node.next_=new Node(obj,nxt);
    }
  }
  //@>slist:insert_after
 
  //@<slist:insert
  public void insert(int i,T obj) {
    if (i==0)
      insert_after((Node) null,obj);
    else {
      Node node=head_;
      for (int j=0;j<i-1 && node!=null;++j)
        node=node.next_;
      insert_after(check(node),obj);
    }
  }
  //@>slist:insert
 
  //@<slist:pop_front
  public void pop_front() {
    head_=check(head_).next_;
  }
  //@>slist:pop_front
 
  //@<slist:pop_back
  public void pop_back() {
    Node node=check(head_), prv=null;
    while (node.next_!=null) {
      prv=node;
      node=node.next_;
    }
    if (prv==null)
      head_=null;
    else
      prv.next_=null;
  }
  //@>slist:pop_back
 
  //@<slist:erase
  public void erase(int i) {
    if (i==0)
      head_=check(head_).next_;
    else {
      Node node=head_;
      for (int j=0;j<i-1 && node!=null;++j)
        node=node.next_;
      check(node);
      check(node.next_);
 
      node.next_=node.next_.next_;
    }
  }
  //@>slist:erase
 
  //@<slist:clear
  public void clear() { head_=null; }
  //@>slist:clear
 
  //
  // iterators
  //
 
  //@<slist:iterator:class
  public class Iterator implements java.util.Iterator<T> {
 
    Node node_ = null;
    Iterator(Node node) { node_=node; }
    //@>slist:iterator:class
 
    @Override
    //@<slist:iterator:hasnext
    public boolean hasNext() {
      return node_!=null;
    }
    //@>slist:iterator:hasnext
 
    @Override
    //@<slist:iterator:next
    public T next() {
      if (node_==null)
        throw new NoSuchElementException();
      T data=node_.data_;
      node_=node_.next_;
      return data;
    }
    //@>slist:iterator:next
    @Override
    //@<slist:iterator:remove
    public void remove() {
      throw new UnsupportedOperationException();
    }
    //@>slist:iterator:remove
    @Override
    @SuppressWarnings("unchecked")
    public boolean equals(Object other) {
      return node_==((Iterator) other).node_;
    }
  }
 
  public void insert_after(Iterator i,T object) {
    check(i.node_);
    insert_after(i.node_,object);
  }
 
  @Override
  //@<slist:iterator
  public Iterator iterator() {
    return new Iterator(head_);
  }
  //@>slist:iterator
 
  //
  // output
  //
 
  @Override
  public String toString() {
    String rv="[";
    Node node=head_;
    while (node!=null) {
      rv+=node.data_.toString();
      if (node.next_!=null)
        rv+=",";
      node=node.next_;
    }
    rv+="]";
    return rv;
  }
 
  @Override
  public String toDot() {
    String rv="digraph SList {\n\t\n\tnode [shape=box];\n\t";
    Node node=head_;
 
    while (node!=null) {
      String nxt=node.next_!=null ? node.next_.data_.toString() : "null";
      rv+="\""+node.data_.toString()+"\"";
      rv+=" -> \""+nxt+ "\" [color=blue,label=next];\n\t";
      node=node.next_;
    }
    rv+="\n}\n";
    return rv;
  }
}