CS1020 Segmented Linked List Lab3 Ex3

Link to the question – Segmented Linked List Lab 3 Ex 3

import java.util.*;

public class SegmentedLinkedList {
	static LinkedList<LinkedList> list = new LinkedList<LinkedList>();
	static LinkedList linked = new LinkedList();
	
	public static void main(String[] args) 
	{
		list.add(linked);
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		if(N <= 50000)
		{
			for(int i = 0; i < N; i++)
			{
				String type = sc.next();
				int value = sc.nextInt();
				
				switch(type)
				{
					case ("Insert"):
						{
							if(list.size() == 1)
							{
								linked.add(value);
								Collections.sort(linked);
								if(linked.size() >= 120)
								{
									//spilt into two here
									LinkedList spilt = new LinkedList();
									for(int j = 61; j <=120; j++)
									{
										spilt.add(linked.get(j-1));
									}
									for(int j = 120; j >=61; j--)
									{
										linked.remove(j-1);
									}
									//copy 60 to 120 to the new LinkedList();
									//remove 60 to 120 from the inital linkedlist
									//replace the first index in the arraylist with the updated.
									list.set(0, linked);
									list.add(spilt);
								}
							}
							else
							{
								boolean in = false; 
								for(int j = 0; j < list.size(); j++)
								{
									LinkedList seg = (LinkedList) list.get(j);
									int head = (int) seg.peekFirst();
									int tail = (int) seg.peekLast();
									//check if value should be within any of the segment
									if(value >= head && value <= tail)
									{
										in = true;
										seg.add(value);
										Collections.sort(seg);
										if(seg.size() >=120)
										{
											LinkedList spilt = new LinkedList();
											for(int z = 61; z <=120; z++)
											{
												spilt.add(seg.get(z-1));

											}
											for(int z = 120; z >=61; z--)
											{
												seg.remove(z-1);
											}
											list.set(j, seg);
											list.add(spilt);
											break;
										}
										else
										{
											list.set(j, seg);
											break;
										}
									}
								}
								//value is smaller than the smallest or largest value in the segmented linkedlist
								if(!in)
								{
									int head = (int) list.get(0).peekFirst();
									int tail = (int) list.get(list.size()-1).peekLast();
									if(value <= head)
									{
										in = true;
										LinkedList headList = (LinkedList) list.get(0);
										headList.addFirst(value);
										if(headList.size() >= 120)
										{
											LinkedList spilt = new LinkedList();
											for(int z = 61; z <= 120; z++)
											{
												spilt.add(headList.get(z-1));
											}
											for(int z = 120; z >= 61; z--)
											{
												headList.remove(z-1);
											}
											list.set(0, headList);
											list.add(spilt);
										}
									}
									else if(value >= tail)
									{
										in = true;
										LinkedList tailList = (LinkedList) list.get(list.size()-1);
										tailList.add(value);
										list.set(list.size()-1,tailList);
										if(tailList.size() >= 120)
										{
											LinkedList spilt = new LinkedList();
											for(int z = 61; z <= 120; z++)
											{
												spilt.add(tailList.get(z-1));
											}
											for(int z = 120; z >= 61; z--)
											{
												tailList.remove(z-1);
											}
											list.set(list.size()-1,tailList);
											list.add(spilt);
										}
									}
								}
								if(!in)
								{

									//if value is more than tail of a seg and less than the head of next seg, add it to the tail of the current seg
									for(int j = 0; j < list.size()-1;j++)
									{
										LinkedList s1 = (LinkedList) list.get(j);
										LinkedList s2 = (LinkedList) list.get(j+1);
										int tail = (int) s1.peekLast();
										int head = (int) s2.peekFirst();
										if(value >= tail && value <= head)
										{
											s1.add(value);
											if(list.get(j).size() >= 120)
											{
												LinkedList spilt = new LinkedList();
												for(int z = 61; z <= 120; z++)
												{
													spilt.add(s1.get(z-1));
												}
												for(int z = 120; z >= 61; z--)
												{
													s1.remove(z-1);
												}
												list.set(j, s1);
												list.add(spilt);
												break;
											}
										}
									}
								}
								//sort the linkedlist of linkedlist
								boolean sorted = false;
								do{
									sorted = false;
									for(int j = 0; j < list.size()-1; j++)
									{
										LinkedList set1 = (LinkedList) list.get(j);
										LinkedList set2 = (LinkedList) list.get(j+1);
										if((int) set1.peekFirst() > (int) set2.peekFirst())
										{
											list.set(j, set2);
											list.set(j+1, set1);
											sorted = true;
										}
									}
								}while(sorted);
							}
							break;
						}
					case ("Query"):
						{
							int index = value;
							for(int j = 0; j < list.size(); j++)
							{
								LinkedList seg = (LinkedList)list.get(j);
								int segSize = seg.size();
								if(index > segSize)
								{
									index = index - segSize;
								}
								else
								{
									LinkedList correctSeg = (LinkedList) list.get(j);
									System.out.println(seg.get(index-1));
									break;
								}
							}
							break;
						}
				}
			}
		}
		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