SHARE
TWEET

Untitled

a guest Jun 25th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class FloorsArrayList implements DynamicSet {
  2. //@TODO: add fields
  3. private int bound;
  4. private int size;
  5. private FloorsArrayLink ninf;
  6. private FloorsArrayLink pinf;
  7. private int roof;
  8.  
  9. /*
  10. * create a list with positive and negative infinity nodes
  11. * set a bound on the number of items in the list
  12. * initiates array with values pointing forward at POSITIVE INFINITY for NEGATIVE INFINITY
  13. *  and values pointing backwards at NEGATIVE INFINITY for POSITIVE INFINITY
  14. * */
  15. public FloorsArrayList(int N){
  16.     //@TODO: implement
  17.     this.bound = N;
  18.     this.size = 0;
  19.     this.roof = 0;
  20.     ninf = new FloorsArrayLink(Double.NEGATIVE_INFINITY , N+1);
  21.     pinf = new FloorsArrayLink(Double.POSITIVE_INFINITY , N+1);
  22.     for(int i = ninf.getArrSize() ; i > 0 ; i-- ) {
  23.         ninf.setNext(i, pinf) ;
  24.         pinf.setPrev(i, ninf);
  25.     }
  26.  
  27. }
  28.  
  29. @Override
  30. /*
  31. * returns the number of items in the list.
  32. * @return number of items in the list.
  33. * */
  34. public int getSize(){
  35.     //@TODO: implement
  36.     return size;
  37. }
  38.  
  39. @Override
  40. /*
  41. * method that takes a key value and an array size value
  42. * inserts a node with those value to the list in a sorted order
  43. * by key ( small - large)
  44. * updates , if needed , the size of the largest array in the list
  45. * */
  46. public void insert(double key, int arrSize){
  47.     //@TODO: implement
  48.     FloorsArrayLink toInsert = new FloorsArrayLink(key, arrSize);
  49.     int i = arrSize;
  50.     FloorsArrayLink curr = ninf;
  51.     FloorsArrayLink next = curr.getNext(i);
  52.  
  53.  
  54.     while(i>0) {
  55.  
  56.         while( next.getKey() < key ) {
  57.             curr = next;
  58.             next = curr.getNext(i);
  59.  
  60.         }
  61.         toInsert.setPrev(i, curr);
  62.         toInsert.setNext(i, next);
  63.         next.setPrev(i, toInsert);
  64.         curr.setNext(i, toInsert);
  65.  
  66.         i=i-1;
  67.  
  68.         if(i>0) {
  69.             next = curr.getNext(i);
  70.         }
  71.  
  72.     }
  73.     if(arrSize > roof){
  74.         roof = arrSize;
  75.     }
  76.     size++;
  77.  
  78.  
  79. }
  80.  
  81. @Override
  82. /*
  83. * removes existing node from the list and update the pointer values
  84. * */
  85. public void remove(FloorsArrayLink toRemove) {
  86.     //@TODO: implement
  87.  
  88.     for(int i = 1; i<= toRemove.getArrSize(); i++){
  89.         (toRemove.getNext(i)).setPrev(i, toRemove.getPrev(i));
  90.         (toRemove.getPrev(i)).setNext(i, toRemove.getNext(i));
  91.     }
  92. }
  93.  
  94. @Override
  95. /*
  96. * search for a node with the specified key value and return
  97. * the node containing it . returns null if such node does not exist.
  98. * @return a node with a specified key value.
  99. * @return null if there is no such node.
  100. * */
  101. public FloorsArrayLink lookup(double key) {
  102.     //@TODO: implement
  103.     int i = roof;
  104.     FloorsArrayLink curr = ninf;
  105.     FloorsArrayLink next = curr.getNext(i);
  106.  
  107.     while(i>=0) {
  108.  
  109.         while( next.getKey() <= key ) {
  110.             curr = next;
  111.             next = curr.getNext(i);
  112.  
  113.         }
  114.         i=i-1;
  115.         if(i>0) {
  116.             next = curr.getNext(i);
  117.         }
  118.  
  119.     }
  120.     if(curr.getKey() == key) {
  121.         return curr;
  122.     }
  123.     return null;
  124. }
  125.  
  126. @Override
  127. /*
  128. * returns the successor of a given link. returns NEGATIVE INFINITY
  129. * if link does not have a successor.
  130. * @return the successor of given link. @return NEGATIVE INFINITY if
  131. * link has no successor.
  132. * */
  133. public double successor(FloorsArrayLink link) {
  134.     //@TODO: implement
  135.     if(link.getNext(1).getKey() != Double.POSITIVE_INFINITY ){
  136.         return link.getNext(1).getKey();
  137.     }
  138.     return Double.NEGATIVE_INFINITY;
  139. }
  140.  
  141. @Override /*
  142.  * returns the predecessor of a given link. returns POSITIVE INFINITY
  143.  * if link does not have a predecessor.
  144.  * @return the predecessor of given link. @return POSITIVE INFINITY if
  145.  * link has no predecessor.
  146.  * */
  147. public double predecessor(FloorsArrayLink link) {
  148.     //@TODO: implement
  149.     if(link.getPrev(1).getKey() != Double.NEGATIVE_INFINITY ){
  150.         return link.getPrev(1).getKey();
  151.     }
  152.     return Double.POSITIVE_INFINITY;
  153. }
  154.  
  155. @Override
  156. /*
  157. * returns minimum key value from the list.
  158. * @return minimum key value from the list.
  159. * */
  160. public double minimum() {
  161.     //@TODO: implement
  162.     if(size == 0){
  163.         return Double.POSITIVE_INFINITY;
  164.     }
  165.     return ninf.getNext(1).getKey();
  166. }
  167.  
  168. @Override
  169. /*
  170.  * returns maximum key value from the list.
  171.  * @return maximum key value from the list.
  172.  * */
  173. public double maximum() {
  174.     //@TODO: implement
  175.     if(size == 0){
  176.         return Double.NEGATIVE_INFINITY;
  177.     }
  178.     return pinf.getPrev(1).getKey();
  179. }
  180. }
  181.      
  182. public class FloorsArrayLink {
  183. //@TODO: add fields
  184. private double key;
  185. private int arrSize;
  186. private FloorsArrayLink[] fArray;
  187. private FloorsArrayLink[] bArray;
  188.  
  189.  
  190. public FloorsArrayLink(double key, int arrSize){
  191.     //@TODO: implement
  192.     this.key = key;
  193.     this.arrSize = arrSize;
  194.     this.fArray = new FloorsArrayLink[arrSize];
  195.     this.bArray = new FloorsArrayLink[arrSize];
  196.  
  197. }
  198. /*
  199. * returns key value
  200. * @return key value
  201. * */
  202. public double getKey() {
  203.     //@TODO: implement
  204.     return this.key;
  205. }
  206. /*
  207. * returns the next node in the list on the same level as i.
  208. * @return the next node in the list on the same level as i.
  209. * */
  210. public FloorsArrayLink getNext(int i) {
  211.     //@TODO: implement
  212.     return this.fArray[i-1];
  213. }
  214. /*
  215.  * returns the previous node in the list on the same level as i.
  216.  * @return the previous node in the list on the same level as i.
  217.  * */
  218. public FloorsArrayLink getPrev(int i) {
  219.     //@TODO: implement
  220.     return this.bArray[i-1];
  221. }
  222. /*
  223.  * sets the next node in the list at level i to next.
  224.  * */
  225. public void setNext(int i, FloorsArrayLink next) {
  226.     //@TODO: implement
  227.     if(i>this.arrSize) {
  228.         return;
  229.     }
  230.     fArray[i-1]=next;
  231.  
  232. }
  233. /*
  234.  * sets the previous node in the list at level i to previous.
  235.  * */
  236. public void setPrev(int i, FloorsArrayLink prev) {
  237.     //@TODO: implement
  238.     if(i>this.arrSize) {
  239.         return;
  240.     }
  241.     bArray[i-1]=prev;
  242. }
  243. /*
  244. * return the size of the arrays storing the pointers.
  245. * @return size of arrays storing the pointers.
  246. * */
  247. public int getArrSize(){
  248.     //@TODO: implement
  249.     return arrSize;
  250. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top