fork download
copy 
  1. import java.util.*;
  2.  
  3. interface sortedList{
  4. 	public boolean isEmpty();
  5. 	public int size();
  6. 	public void add(Object o);
  7. 	public void remove(Object o);
  8. 	public int locateIndex(Object o);
  9. 	public Vector<Object>get();
  10. }
  11. class A02Q01 implements sortedList{
  12. 	private int k = 100;
  13. 	protected static final int NOTHING = -1;
  14. 	protected Object[]data=new Object[k];
  15. 	protected int[]prev=new int[k];
  16. 	protected int[]next=new int[k];
  17. 	protected int count=0;
  18. 	protected int start=0;
  19. 	public A02Q01(){
  20. 		for(int i=0;i<k;i++){
  21. 			prev[i]=NOTHING;
  22. 			next[i]=NOTHING;
  23. 		}
  24. 	}
  25. 	public boolean isEmpty(){
  26. 		return count==0;
  27. 	}
  28. 	public int size(){
  29. 		return count;
  30. 	}
  31. 	public 	void add(Object o){
  32. 		if(count==k-1)return;
  33. 		int where = NOTHING;
  34. 		for(int i=0;i<k;i++){
  35. 			if(data[i]==null){
  36. 				where=i;
  37. 				break;
  38. 			}
  39. 		}
  40. 		if(where==NOTHING)return;
  41. 		add(o,start,where);
  42. 		count++;
  43. 	}
  44. 	protected void add(Object o,int from,int where){
  45. 		Comparable<Object>a=(Comparable<Object>)data[from];
  46. 		Comparable<Object>b=(Comparable<Object>)o;
  47. 		if(data[from]==null){
  48. 			data[where]=o;
  49. 			prev[where]=NOTHING;
  50. 			next[where]=NOTHING;
  51. 		}else if(a.compareTo(b)>0){
  52. 			data[where]=o;
  53. 			next[where]=from;
  54. 			if(from==start){
  55. 				start=where;
  56. 				prev[where]=NOTHING;
  57. 			}else{
  58. 				prev[where]=prev[next[where]];
  59. 				next[prev[where]]=where;
  60. 			}
  61. 			prev[next[where]]=where;
  62. 		}else if(next[from]==NOTHING){
  63. 			data[where]=o;
  64. 			prev[where]=from;
  65. 			next[where]=NOTHING;
  66. 			next[prev[where]]=where;
  67. 		}else{
  68. 			add(o,next[from],where);
  69. 		}
  70. 	}
  71. 	public void remove(Object o){
  72. 		int where = locateIndex(o);
  73. 		if(where==NOTHING)return;
  74. 		if(prev[where]==NOTHING){
  75. 			start=next[where];
  76. 			if(next[where]!=NOTHING){
  77. 				prev[next[where]]=NOTHING;
  78. 				next[where]=NOTHING;
  79. 			}
  80. 		}else{
  81. 			if(next[where]!=NOTHING){
  82. 				prev[next[where]]=prev[where];
  83. 				next[prev[where]]=next[where];
  84. 				next[where]=NOTHING;
  85. 			}
  86. 			prev[where]=NOTHING;
  87. 		}
  88. 		data[where]=null;
  89. 		count--;
  90. 	}
  91. 	public int locateIndex(Object o){
  92. 		return recursiveSearchFunction(o,start);
  93. 	}
  94. 	protected int recursiveSearchFunction(Object target,int where){
  95. 		if(size()==0)return NOTHING;
  96. 		if(target.equals(data[where]))return where;
  97. 		if(where==NOTHING)return NOTHING;
  98. 		return recursiveSearchFunction(target,next[where]);
  99. 	}
  100. 	public Vector<Object>get(){
  101. 		Vector<Object>v=new Vector<Object>();
  102. 		for(int i=start;i!=NOTHING;i=next[i]){
  103. 			v.add(data[i]);
  104. 		}
  105. 		return v;
  106. 	}
  107. }
  108. public class Main{
  109. 	public static void main(String[]args){
  110. 		A02Q01 obj=new A02Q01();
  111. 		obj.add((Object)"3");
  112. 		obj.add((Object)"1");
  113. 		obj.add((Object)"2");
  114. 		for(Object o:obj.get()){
  115. 			System.out.println(o);
  116. 		}
  117. 		System.out.println("---");
  118. 		obj.remove((Object)"2");
  119. 		for(Object o:obj.get()){
  120. 			System.out.println(o);
  121. 		}
  122. 		System.out.println("---");
  123. 		obj.add((Object)"4");
  124. 		for(Object o:obj.get()){
  125. 			System.out.println(o);
  126. 		}
  127. 	}
  128. }
  129.  
Success #stdin #stdout 0.09s 212416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
2
3
---
1
3
---
1
3
4
https://ideone.com/Kgp4B
language:
Java (HotSpot 12)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!