CS1020 Balls Lab3 Ex1

Link to the question – Balls Lab 3 Ex 1

import java.util.*;

// use ListNode to represent the balls.
class ListNode {
	public int iDate;
	public ListNode next;
	public ListNode prev;

	public ListNode(int id)
	{
		iDate = id;
	}
	
	public int getNodeData()
	{
		return iDate;
	}
}

class MyLinkedList {
	
    // declare the member field
	private ListNode first;
	private ListNode last;
    // declare the constructor
	public MyLinkedList()
	{
		first = null;
		last = null;
	}
	
	public boolean isEmpty()
	{
		return first == null;
	}
	
	public void insertLast(int dd)
	{
		ListNode node = new ListNode(dd);
		if(isEmpty())
		{
			first = node;
		}
		else
		{
			last.next = node;
			node.prev = last;
		}
		last = node;
	}

	public boolean insertAfter(int key, int dd)
	{
		ListNode current = first;
		while(current.iDate != key)
		{
			current = current.next;
			if(current == null)
			{
				return false;
			}
		}
		ListNode node = new ListNode(dd);
		if(current == last)
		{
			node.next = null;
			last = node;
		}
		else
		{
			node.next = current.next;
			current.next.prev = node;
		}
		node.prev = current;
		current.next = node;
		return true;
	}

	public boolean insertBefore(int key, int dd)
	{
		ListNode current = last;
		while(current.iDate != key)
		{
			current = current.prev;
			if(current == null)
			{
				return false;
			}
		}
		ListNode node = new ListNode(dd);
		if(current == first)
		{
			node.prev = null;
			first = node;
		}
		else
		{
			node.prev = current.prev;
			current.prev.next = node;
		}
		node.next = current;
		current.prev = node;
		return true;
	}

	public ListNode deleteKey(int key)
	{
		ListNode current = first;
		while(current.iDate != key)
		{
			current = current.next;
			if(current == null)
			{
				return null;
			}
		}
		if(current == first)
		{
			first = current.next;
		}
		else
		{
			current.prev.next = current.next;
		}
		if(current == last)
		{
			last = current.prev;
		}
		else
		{
			current.next.prev = current.prev;
		}
		return current;
	}

	public void displayForward()
	{
		ListNode current = first;
		String x = "";
		while(current != null)
		{
			int data = current.getNodeData();
			System.out.print(data + " ");
			current = current.next;
		}
		System.out.println();
	}
	
	//return true if X is before Y;
	public boolean checkXBeforeY(int x, int y)
	{
		boolean xBeforeY = false;
		ListNode current = first;
		while(current.iDate != y)
		{
			current = current.next;
			if(current.iDate == x)
			{
				xBeforeY = true;
				break;
			}
		}
		return xBeforeY;
	}
}

class Balls {
	
	public static void main(String[] args) {
        
		// declare the necessary variables
		MyLinkedList list = new MyLinkedList();
		// declare a Scanner object to read input
		Scanner sc = new Scanner(System.in);
		// read input and process them accordingly
		int N = sc.nextInt();
		if(N >=1 && N <= 1000)
		{
			for(int i = 1; i <= N; i++)
			{
				list.insertLast(i);
			}
			int M = sc.nextInt();
			if(M >= 1 && M <= 1000)
			{
				for(int i = 0; i < M; i++)
				{
					String type = sc.next();
					if(type.equals("A"))
					{
						int x = sc.nextInt();
						int y = sc.nextInt();
						if(x != y)
						{
								list.deleteKey(x);
								list.insertBefore(y,x);
						}
					}
					else if(type.equals("B"))
					{
						int x = sc.nextInt();
						int y = sc.nextInt();
						if(x != y)
						{
								list.deleteKey(x);
								list.insertAfter(y,x);
						}
					}
					else if(type.equals("R"))
					{
						int x = sc.nextInt();
						list.deleteKey(x);
					}
				}
				list.displayForward();
			}
			else
			{
				return;
			}
		}
		else
		{
			return;
		}


	}
}
Advertisements
This entry was posted in NUS, SoC and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s