Ledger Nano X - The secure hardware wallet
SHARE
TWEET

DLLEntry

a guest Mar 30th, 2020 192 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package prog08;
  2.  
  3. import java.util.AbstractMap;
  4. import java.util.Map;
  5. import java.util.Map.Entry;
  6.  
  7. import prog04.DLLEntry;
  8.  
  9. import java.util.AbstractSet;
  10. import java.util.Set;
  11. import java.util.Iterator;
  12.  
  13. public class DLLMap<K extends Comparable<K>, V> extends AbstractMap<K, V> {
  14.  
  15.   protected class Entry implements Map.Entry<K, V> {
  16.  
  17.     K key;
  18.     Object value;
  19.     Entry previous, next;
  20.  
  21.     Entry(K key, Object value) {
  22.       this.key = key;
  23.       this.value = value;
  24.     }
  25.  
  26.     public K getKey() {
  27.       return key;
  28.     }
  29.  
  30.     public V getValue() {
  31.       return (V) value;
  32.     }
  33.  
  34.     public V setValue(V newValue) {
  35.       V oldValue = (V) value;
  36.       value = newValue;
  37.       return oldValue;
  38.     }
  39.  
  40.     protected boolean isSkipEntry() {
  41.       return value != null && value instanceof DLLMap.Entry;
  42.     }
  43.  
  44.     protected Entry getEntry() {
  45.       return (Entry) value;
  46.     }
  47.   }
  48.  
  49.   protected Entry first, last;
  50.  
  51.   /**
  52.    * Starting from entry, find an Entry with key nearest to key.
  53.    *
  54.    * @param startAt The entry to start from.
  55.    * @param key     The Key to be found.
  56.    * @return Entry with key or, if not there, neighboring key in list.
  57.    */
  58.   protected Entry find(Entry startAt, K key) {
  59.     if (startAt == null)
  60.       return null;
  61.     Entry nearest = startAt;
  62.  
  63.     // EXERCISE
  64.     // Move nearest to the nearest key to key (same or a neighbor).
  65.     // forwardsssssssssss
  66.     if (nearest.getKey().compareTo(key) < 0) {
  67.       while (nearest.getKey().compareTo(key) < 0 && nearest.next != null)
  68.         nearest = nearest.next;
  69.     }
  70.     // backwardssssssssssssssssss
  71.     else if (nearest.getKey().compareTo(key) > 0) {
  72.       while (nearest.getKey().compareTo(key) > 0 && nearest.previous != null)
  73.         nearest = nearest.previous;
  74.     }
  75.     return nearest;
  76.     // return nearest;
  77.     // return nearest;
  78.   }
  79.  
  80.   public boolean containsKey(Object keyAsObject) {
  81.     K key = (K) keyAsObject;
  82.     Entry entry = find(first, key);
  83.     return entry != null && entry.key.equals(key);
  84.   }
  85.  
  86.   // like containskey() but returns the value of entry if it's there
  87.   // otherwise turn null
  88.   public V get(Object keyAsObject) {
  89.     // EXERCISE
  90.     // Look at containsKey and fix this.
  91.     ///
  92.     K key = (K) keyAsObject;
  93.     Entry entry = find(last, key);
  94.  
  95.     if (entry != null && entry.getKey() == key) {
  96.       return entry.getValue();
  97.  
  98.     }
  99.     return null;
  100.   }
  101.  
  102.   /**
  103.    * Add newEntry before or after neighbor depending on the order of their Keys.
  104.    *
  105.    * @param neighbor The Entry to insert before or after. null if the list is
  106.    *                 empty.
  107.    * @param newEntry The new Entry to be inserted.
  108.    * @return newEntry
  109.    */
  110.  
  111.   /*
  112.    * 1. Implement the missing part of the add method in DLLMap. Read the Javadoc.
  113.    * It is the same idea as add in prog02.SortedDLLPD. Follow the directions. I
  114.    * have handled updating first and last for you. Do not read or write these
  115.    * variables in your part of the exercise. Output should look like step01.txt.
  116.    */
  117.  
  118.   protected Entry add(Entry neighbor, Entry newEntry) {
  119.     Entry previous = null;
  120.     Entry next = null;
  121.  
  122.     if (neighbor != null) {
  123.       if (neighbor.getKey().compareTo(newEntry.getKey()) >= 0) {
  124.         next = neighbor;
  125.         previous = neighbor.previous;
  126.       }
  127.       // setting previous and next
  128.       else if (neighbor.getKey().compareTo(newEntry.getKey()) < 0) {
  129.         previous = neighbor;
  130.         next = neighbor.next;
  131.       }
  132.       // setting newEntry's previous and next
  133.       newEntry.previous = previous;
  134.       newEntry.next = next;
  135.       // setting previous.next and next.previous, careful of nulls
  136.       if (previous != null)
  137.         previous.next = newEntry;
  138.       if (next != null)
  139.         next.previous = newEntry;
  140.     }
  141.  
  142.     if (first == next)
  143.       first = newEntry;
  144.     if (last == previous)
  145.       last = newEntry;
  146.  
  147.     return newEntry;
  148.   }
  149.  
  150. //like addOrChangeEntry()
  151.   public V put(K key, V value) {
  152.     Entry entry = find(first, key);
  153.     // EXERCISE
  154.     // Look at containsKey and then fix this.
  155.     ///
  156.     // entry's key equals key, we update it's value
  157.     if (entry != null && entry.getKey().equals(key)) {
  158.       V firstOne = entry.getValue();
  159.       entry.setValue(value);
  160.       return firstOne;
  161.  
  162.     }
  163.     ///
  164.     // if it's normal we return null
  165.     else {
  166.       add(entry, new Entry(key, value));
  167.       return null;
  168.     }
  169.   }
  170.  
  171.   /**
  172.    * Remove Entry entry from list.
  173.    *
  174.    * @param entry The entry to remove.
  175.    */
  176.   protected void remove(Entry entry) {
  177.     // EXERCISE
  178.     // ONLY modify first IF entry==first. Ditto last.
  179.     ///
  180.     if (entry == first) {
  181.       first = first.next;
  182.     } else if (entry == last) {
  183.       last = last.previous;
  184.     } else {
  185.       if (find(first, entry.getKey()) == entry) {
  186.         entry.previous.next = entry.next;
  187.         entry.next.previous = entry.previous;
  188.       }
  189.     }
  190.     ///
  191.   }
  192.  
  193.   public V remove(Object keyAsObject) {
  194.     // EXERCISE
  195.     // If it is not there:
  196.     ///
  197.     K key = (K) keyAsObject;
  198.     Entry entry = find(first, key);
  199.     if (entry == null || entry.key != key) {
  200.       ///
  201.       return null;
  202.     }
  203.  
  204.     // Otherwise remove it and return the right thing.
  205.     // EXERCISE
  206.     ///
  207.     else {
  208.       if (entry == first && entry == last) {
  209.         first = null;
  210.         last = null;
  211.       } else if (entry == first) {
  212.         Entry placeholder = first.next;
  213.         placeholder.previous = null;
  214.         first = placeholder;
  215.       } else if (entry == last && entry != first) {
  216.         Entry placeholder = last.previous;
  217.         placeholder.next = null;
  218.         last = placeholder;
  219.       } else {
  220.         Entry previous = entry.previous;
  221.         Entry next = entry.next;
  222.         previous.next = next;
  223.         next.previous = previous;
  224.       }
  225.       return entry.getValue();
  226.     }
  227.     ///
  228.   }
  229.  
  230.   protected class Iter implements Iterator<Map.Entry<K, V>> {
  231.     Entry next = first;
  232.  
  233.     public boolean hasNext() {
  234.       return next != null;
  235.     }
  236.  
  237.     public Map.Entry<K, V> next() {
  238.       Map.Entry<K, V> ret = next;
  239.       next = next.next;
  240.       return ret;
  241.     }
  242.  
  243.     public void remove() {
  244.       throw new UnsupportedOperationException();
  245.     }
  246.   }
  247.  
  248.   protected class Setter extends AbstractSet<Map.Entry<K, V>> {
  249.     public Iterator<Map.Entry<K, V>> iterator() {
  250.       return new Iter();
  251.     }
  252.  
  253.     public int size() {
  254.       return DLLMap.this.size();
  255.     }
  256.   }
  257.  
  258.   public Set<Map.Entry<K, V>> entrySet() {
  259.     return new Setter();
  260.   }
  261.  
  262.   public static void main(String[] args) {
  263.     Map<String, Integer> map = new DLLMap<String, Integer>();
  264.  
  265.     if (false) {
  266.       map.put("Victor", 50);
  267.       map.put("Irina", 45);
  268.       map.put("Lisa", 47);
  269.  
  270.       for (Map.Entry<String, Integer> pair : map.entrySet())
  271.         System.out.println(pair.getKey() + " " + pair.getValue());
  272.  
  273.       System.out.println(map.put("Irina", 55));
  274.  
  275.       for (Map.Entry<String, Integer> pair : map.entrySet())
  276.         System.out.println(pair.getKey() + " " + pair.getValue());
  277.  
  278.       System.out.println(map.remove("Irina"));
  279.       System.out.println(map.remove("Irina"));
  280.       System.out.println(map.get("Irina"));
  281.  
  282.       for (Map.Entry<String, Integer> pair : map.entrySet())
  283.         System.out.println(pair.getKey() + " " + pair.getValue());
  284.     } else {
  285.       String[] keys = { "Vic", "Ira", "Sue", "Zoe", "Bob", "Ann", "Moe" };
  286.       for (int i = 0; i < keys.length; i++) {
  287.         System.out.print("put(" + keys[i] + ", " + i + ") = ");
  288.         System.out.println(map.put(keys[i], i));
  289.         System.out.println(map);
  290.         System.out.print("put(" + keys[i] + ", " + -i + ") = ");
  291.         System.out.println(map.put(keys[i], -i));
  292.         System.out.println(map);
  293.         System.out.print("get(" + keys[i] + ") = ");
  294.         System.out.println(map.get(keys[i]));
  295.         System.out.print("remove(" + keys[i] + ") = ");
  296.         System.out.println(map.remove(keys[i]));
  297.         System.out.println(map);
  298.         System.out.print("get(" + keys[i] + ") = ");
  299.         System.out.println(map.get(keys[i]));
  300.         System.out.print("remove(" + keys[i] + ") = ");
  301.         System.out.println(map.remove(keys[i]));
  302.         System.out.println(map);
  303.         System.out.print("put(" + keys[i] + ", " + i + ") = ");
  304.         System.out.println(map.put(keys[i], i));
  305.         System.out.println(map);
  306.       }
  307.     }
  308.   }
  309. }
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