dsa

Data Structures & Algorithms - Spring 2018
Log | Files | Refs | README

AscendinglyOrderedStringList.java (3087B)

      1 package lab8;
      2 
      3 public class AscendinglyOrderedStringList implements AscendinglyOrderedStringListInterface {
      4     private static final int MAX_LIST = 3;
      5     protected String []items;
      6     protected int numItems;
      7 
      8     public AscendinglyOrderedStringList()
      9     {
     10         items = new String[MAX_LIST];
     11         numItems = 0;
     12     }
     13 
     14     public boolean isEmpty()
     15     {
     16         return (numItems == 0);
     17     }
     18 
     19     public int size()
     20     {
     21         return numItems;
     22     }
     23 
     24     public String get(int index)
     25             throws ListIndexOutOfBoundsException
     26     {
     27         if (index >= 0 && index < numItems)
     28         {
     29             return items[index];
     30         }
     31         else
     32         {
     33             throw new ListIndexOutOfBoundsException(
     34                     "ListIndexOutOfBoundsException on get");
     35         }
     36     }
     37 
     38     public void add(String item) {
     39         int index;
     40 
     41         if (numItems == items.length) {
     42             resize();
     43         }
     44 
     45         index = search(item);
     46         if (index <= 0) {
     47             index = -index;
     48             for (int pos = numItems - 1; pos >= index; pos--)
     49             {
     50                 items[pos + 1] = items[pos];
     51             }
     52             items[index] = item;
     53             System.out.println("Item " + item + "inserted in position " + (index));
     54             numItems++;
     55         } else {
     56             System.out.println("Item already exists");
     57         }
     58     }
     59 
     60     public void remove(int index)
     61             throws ListIndexOutOfBoundsException
     62     {
     63         if (index >= 0 && index < numItems)
     64         {
     65             for (int pos = index+1; pos < numItems; pos++)
     66 
     67             {
     68                 items[pos-1] = items[pos];
     69             }
     70             items[numItems - 1] = null;
     71             numItems--;
     72         }
     73         else
     74         {
     75             throw new ListIndexOutOfBoundsException(
     76                     "ListIndexOutOfBoundsException on remove");
     77         }
     78     }
     79 
     80     /*
     81      * Using binary method II
     82      */
     83 
     84     public int search(String item) {
     85         int low = 0;
     86         int high = items.length-1;
     87         while (low < high) {
     88             int mid = (low+high)/2;
     89             String midKey = items[mid];
     90 
     91             if (items[mid] == null || midKey.compareTo(item) >= 0) {
     92                 high = mid;
     93             }
     94             else {
     95                 low = mid + 1;
     96             }
     97         }
     98 
     99         if (item.equals(items[low])) {
    100             low = low +  1;
    101                 return low;
    102         }
    103         else {
    104             low = -low;
    105             return low;
    106         }
    107     }
    108 
    109     public void clear()
    110     {
    111         items = new String[MAX_LIST];
    112         numItems = 0;
    113     }
    114 
    115     public void resize() {
    116         String []tmp;
    117         tmp = new String[numItems*2 + 1];
    118         for (int i = 0; i < numItems; i++) {
    119             tmp[i] = items[i];
    120         }
    121         items = tmp;
    122     }
    123 
    124     @Override
    125     public String toString() {
    126         String result = "List of size " + size() + " has the following items : ";
    127 
    128         for (int i = 0; i < size(); i++) {
    129             if (items[i] != null)
    130                 result += items[i] + " ";
    131         }
    132 
    133         return result;
    134     }
    135 }