FRIHOST FORUMS SEARCH FAQ TOS BLOGS COMPETITIONS
You are invited to Log in or Register a free Frihost Account!


Exceptions in Java





davidv
I've implemented my own adapter class for the Queue ADT in Java. I've not quite sure if I'm done it correctly so if there are major laughable mistakes, conceptually or just YOU'RE DOING IT WRONG type mistakes, point them out please Smile I'm here to learn. Anyway here's the queue class.

MyQueue.java

Code:
import java.util.ArrayList;

class MyQueue<E> implements QueueInterface<E>{
   
   private ArrayList<E> storage;

   public MyQueue(){
      storage = new ArrayList<E>();
   }

   public E front() throws Exception{
      if (isEmpty()){
         throw new Exception("Queue is empty.");
      }
      return storage.get(0);
   }
   
   public void enqueue(E e){
      // It will never throw a FullQueueException because it's an ArrayList
      storage.add(e);
   }
   
   public E dequeue() throws Exception{
      if (isEmpty()){
         throw new Exception("Queue is empty.");
      }
      E e = storage.get(0);
      storage.remove(0);
      return e;
   }
   
   public boolean isEmpty(){
      return storage.isEmpty();
   }
   
   public int size(){
      return storage.size();
   }
}


and I've done it using an ArrayList (which makes it so simple). Here's the interface that I've made:

QueueInterface.java

Code:
interface QueueInterface<E> {
   public boolean isEmpty();
   public int size();
   public void enqueue(E e);
   public E front() throws Exception;
   public E dequeue() throws Exception;
}


The thing is, I want to create my own Exception in the QueueInterface. Something like EmptyQueueException rather than just Exception. Say if I changed front() to:

Code:
public E front() throws EmptyQueueException;


Code:
public E front() throws EmptyQueueException{
      if (isEmpty()){
         throw new EmptyQueueException("Queue is empty.");
      }
      return storage.get(0);
   }


I get this:

Quote:
MyQueue.java:11: cannot find symbol
symbol : class EmptyQueueException
location: class MyQueue<E>
public E front() throws EmptyQueueException{
^
QueueInterface.java:5: cannot find symbol
symbol : class EmptyQueueException
location: interface QueueInterface<E>
public E front() throws EmptyQueueException;
^
MyQueue.java:13: cannot find symbol
symbol : class EmptyQueueException
location: class MyQueue<E>
throw new EmptyQueueException("Queue is empty.");
^
3 errors


I wanted to know how do I create my own exceptions. Thanks.
Peterssidan
You need to create a class named EmptyQueueException that extends Exception or one of its subclasses.
davidv
Peterssidan wrote:
You need to create a class named EmptyQueueException that extends Exception or one of its subclasses.


A new class for every new exception I want to make? What goes in the class? Examples?
Peterssidan
The class can be very simple.
Code:
class EmptyQueueException extends Exception {
    public EmptyQueueException() {}
    public EmptyQueueException(String msg) {super(msg);}
}


I hope you are doing this only for learning purposes because Java already have queue classes that's more efficient than yours.
davidv
Peterssidan wrote:
The class can be very simple.
Code:
class EmptyQueueException extends Exception {
    public EmptyQueueException() {}
    public EmptyQueueException(String msg) {super(msg);}
}


I hope you are doing this only for learning purposes because Java already have queue classes that's more efficient than yours.


Yes, this is only for learning purposes. No point reinventing the wheel. Thanks for the response.
Fire Boar
I hate to say "you're doing it wrong", so I won't. Instead, I'll say "you're doing it inefficiently", and explain why.

ArrayList is a poor choice of backend because removal involves moving each subsequent item up a slot. That's called an O(n) operation, which means the time taken increases linearly with every item in the list. The great thing about queues is that all operations are theoretically O(1) operations - that is, operations that take constant time (the same no matter how much data is stored), so a good implementation of a queue should ideally have all operations constant.

A LinkedList is a better backend, because adding and removing is constant at both front and back. Indeed, LinkedList<E> implements the java Queue<E> interface. But since this is for learning, it's a good idea to write your own.

To write your own, you need to consider the requirements. At minimum, at all times a Queue must know where its first element is (for removing or polling), and where its last element is (for adding). With this in mind, there are generally two approaches:

The first is an array approach, where you store the index of the first and last element. Adding an element involves incrementing the "last" index by 1 and adding it to the array, removing one involves decrementing the "first" index by 1 - deleting the element is unnecessary. This approach has a flaw: you'll need to either decide on a fixed size for the array and "loop around" when you get to the end, or have a dynamically expanding array (like ArrayList) which gets bigger and bigger the more it's used, with all the early indices becoming wasted. It's possible to overcome this flaw, but difficult.

Alternatively, you can go for a linked list approach. This involves wrapping each E in a Node<E> class (which is typically a private inner class), where each Node<E> has a reference to the next Node<E> in the queue. The Queue class then stores a reference to the first and last Node<E> (with edge cases for empty queues). I prefer this approach and provide a sample implementation (which might not compile - I've not tested it) below:

Code:
class LinkedListQueue<E> implements QueueInterface<E>
{
  private Node<E> front = null;
  private Node<E> back = null;
  private int size = 0;

  public boolean isEmpty()
  {
    return size == 0;
  }

  public int size()
  {
    return size;
  }

  public void enqueue(E e)
  {
    Node<E> oldBack = back;
    back = new Node<E>(e);
    size++;

    if (oldBack == null) // Edge case for empty queue.
    {
      front = back;
    }
    else
    {
      oldBack.setNext(back);
    }
  }

  public E front() throws Exception
  {
    if (front == null) throw new Exception("Empty queue");
    return front.get();
  }

  public E dequeue() throws Exception
  {
    if (front == null) throw new Exception("Empty queue");
    E ret = front.get();
    front = front.next();
    size--;

    if (front == null) // Edge case for queue becoming empty.
    {
      back = null;
    }
  }

  private class Node<E>
  {
    private E data;
    private Node<E> next = null;

    public Node<E>(E data)
    {
      this.data = data;
    }

    public E get()
    {
      return data;
    }

    public void setNext(Node<E> next)
    {
      this.next = next;
    }

    public Node<E> next()
    {
      return next;
    }
  }
}
davidv
Fire Boar wrote:
I hate to say "you're doing it wrong", so I won't. Instead, I'll say "you're doing it inefficiently", and explain why.

ArrayList is a poor choice of backend because removal involves moving each subsequent item up a slot. That's called an O(n) operation, which means the time taken increases linearly with every item in the list. The great thing about queues is that all operations are theoretically O(1) operations - that is, operations that take constant time (the same no matter how much data is stored), so a good implementation of a queue should ideally have all operations constant.

A LinkedList is a better backend, because adding and removing is constant at both front and back. Indeed, LinkedList<E> implements the java Queue<E> interface. But since this is for learning, it's a good idea to write your own.

To write your own, you need to consider the requirements. At minimum, at all times a Queue must know where its first element is (for removing or polling), and where its last element is (for adding). With this in mind, there are generally two approaches:

The first is an array approach, where you store the index of the first and last element. Adding an element involves incrementing the "last" index by 1 and adding it to the array, removing one involves decrementing the "first" index by 1 - deleting the element is unnecessary. This approach has a flaw: you'll need to either decide on a fixed size for the array and "loop around" when you get to the end, or have a dynamically expanding array (like ArrayList) which gets bigger and bigger the more it's used, with all the early indices becoming wasted. It's possible to overcome this flaw, but difficult.

Alternatively, you can go for a linked list approach. This involves wrapping each E in a Node<E> class (which is typically a private inner class), where each Node<E> has a reference to the next Node<E> in the queue. The Queue class then stores a reference to the first and last Node<E> (with edge cases for empty queues).


Yep, you're absolutely right. ArrayList was a very poor choice because O(n) sucks. I would of used a singly linked list if I was doing it properly but I chose an ArrayList instead because it was quick to implement. All I wanted to do was pose an example that resembled adaptors and exceptions so I could ask a question about it. Time complexity wasn't something I cared about in the example. Obviously O(1) is better than O(n).

I liked how you had the node class nested in your linked list (never used nested classes in Java before) and it leads me to a follow up question. Why isn't it static?

Code:
private static class Node<E>
Related topics
Java Game
Java
Add to favorites script - Java
Problems with Java
Java Programming Introductory
Language
DSP Tutorial with Java Applets
Java
[JAVA TUTORIALS & FILES] - Java Scripting world
JAVA Forums
JAva HELP
SQL in java
Java hosting
Constructors in Java, help
Reply to topic    Frihost Forum Index -> Scripting -> Others

FRIHOST HOME | FAQ | TOS | ABOUT US | CONTACT US | SITE MAP
© 2005-2011 Frihost, forums powered by phpBB.