Advertisement
Guest User

SkipMap

a guest
Mar 30th, 2020
175
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.92 KB | None | 0 0
  1. package prog08;
  2.  
  3. import java.util.Random;
  4.  
  5. public class SkipMap<K extends Comparable<K>, V> extends DLLMap<K, V> {
  6.   protected Entry top;
  7.  
  8.   /**
  9.    * Find (recursively) the Entry at the bottom level with the key.
  10.    *
  11.    * @param startAt The Entry to start from, usually at a higher level, but null
  12.    *                if Map is empty.
  13.    * @param key     The key to be found.
  14.    * @return Bottom level Entry with the key or null if not there.
  15.    */
  16.   protected Entry rFind(Entry startAt, K key) {
  17.     if (startAt == null)
  18.       return null;
  19.     // EXERCISE 6
  20.     ///
  21.     // Use find (not rFind) to get the nearest Entry to the key in the same list as
  22.     // startAt.
  23.     Entry entry = find(startAt, key);
  24.     if (entry != null && entry.isSkipEntry()) {
  25.       entry = rFind(entry.getEntry(), key);
  26.     }
  27.     if (entry != null && !entry.isSkipEntry() && entry.getKey() == key)
  28.       return entry;
  29.     return null;
  30.   }
  31.  
  32.   public boolean containsKey(Object keyAsObject) {
  33.     K key = (K) keyAsObject;
  34.     Entry entry = rFind(top, key);
  35.     return entry != null;
  36.   }
  37.  
  38.   public V get(Object keyAsObject) {
  39.     K key = (K) keyAsObject;
  40.     Entry entry = find(last, key);
  41.     if (entry != null && entry.getKey() == key) {
  42.       return entry.getValue();
  43.     }
  44.     return null;
  45.   }
  46.  
  47.   /**
  48.    * Add (recursively) a new Entry at the bottom level plus additional levels to
  49.    * be determined by coin flips.
  50.    *
  51.    * @param startAt The entry to start from, usually at a higher level, but null
  52.    *                if Map is empty.
  53.    * @param key     The key to be added.
  54.    * @param value   The value to be added.
  55.    * @return Entry that was added at the same level as startAt or null if one was
  56.    *         not added at that level.
  57.    */
  58.   protected Entry rAdd(Entry startAt, K key, V value) {
  59.     if (startAt == null)
  60.       return null;
  61.     // EXERCISE 8
  62.     ///
  63.     // Use find (not rFind) to get the nearest Entry to the key in the
  64.     // same list as startAt.
  65.  
  66.     Entry entry = find(startAt, key);
  67.     Entry newE = new Entry(key, value);
  68.     // If the Entry is on the bottom, just use add (not rAdd) and
  69.     // return the new Entry.
  70.     if (entry.isSkipEntry()) {
  71.       add(entry, newE); // neighbor, new
  72.       return newE;
  73.     }
  74.  
  75.     // Otherwise, use rAdd on the Entry below the Entry.
  76.     else if (!entry.isSkipEntry()) {
  77.       rAdd(entry.getEntry(), key, value);
  78.     }
  79.  
  80.     // If rAdd returns an Entry and if you flip heads (heads() is true),
  81.     // use add to add a new Entry on this level with that Entry
  82.     // as its value.
  83.  
  84.     return null;
  85.   }
  86.  
  87.   // Return the new Entry (on this level).
  88.  
  89.   ///
  90.  
  91.   public V put(K key, V value) {
  92.     if (top == null) // Change to false in Step 9.
  93.       return super.put(key, value);
  94.     if (top == null) {
  95.       top = add(null, new Entry(key, value));
  96.       return null;
  97.     }
  98.     // EXERCISE 8
  99.     ///
  100.     // Use rFind to check if the key is there already, and if it
  101.     // is, use setValue.
  102.  
  103.     // Otherwise, use rAdd to add it.
  104.  
  105.     Entry entry = rFind(top, key);
  106.     if (entry != null)
  107.       entry.setValue(value);
  108.  
  109.     else
  110.       rAdd(entry, key, value);
  111.  
  112.     // EXERCISE 9
  113.     ///
  114.     // If rAdd returned an Entry, set top to it.
  115.     // While you flip heads, set top to an Entry on top of top.
  116.  
  117.     ///
  118.     return null;
  119.   }
  120.  
  121.   Random random = new Random(1);
  122.  
  123.   boolean heads() {
  124.     return random.nextInt() % 2 == 0;
  125.   }
  126.  
  127.   public String toString() {
  128.     if (top == null)
  129.       return "empty\n";
  130.     String s = "";
  131.     Entry head = top;
  132.     while (true) {
  133.       Entry entry = head;
  134.       while (entry.previous != null)
  135.         entry = entry.previous;
  136.       Entry bot = first;
  137.       for (; entry != null; entry = entry.next) {
  138.         while (bot.key != entry.key) {
  139.           int n = bot.key.toString().length();
  140.           for (int i = 0; i <= n; i++)
  141.             s = s + " ";
  142.           bot = bot.next;
  143.         }
  144.         bot = bot.next;
  145.         s = s + entry.key + " ";
  146.       }
  147.       s = s + "\n";
  148.       if (head.isSkipEntry())
  149.         head = head.getEntry();
  150.       else
  151.         break;
  152.     }
  153.     for (Entry entry = first; entry != null; entry = entry.next) {
  154.       String k = "" + entry.key;
  155.       String v = "" + entry.value;
  156.       int d = k.length() - v.length();
  157.       for (int i = 0; i < d; i++)
  158.         s += " ";
  159.       s += v + " ";
  160.     }
  161.     s += "\n";
  162.     return s;
  163.   }
  164.  
  165.   void skipify() {
  166.     if (top != null || first == null)
  167.       return;
  168.     Entry newFirst = first;
  169.     while (newFirst != null) {
  170.       top = newFirst;
  171.       newFirst = null;
  172.       if (top.next != null)
  173.         top = top.next;
  174.       else
  175.         break;
  176.       Entry newTop = null;
  177.       while (true) {
  178.         if (newTop == null)
  179.           newFirst = newTop = new Entry(top.key, top);
  180.         else {
  181.           newTop.next = new Entry(top.key, top);
  182.           newTop.next.previous = newTop;
  183.           newTop = newTop.next;
  184.         }
  185.         if (top.next != null && top.next.next != null)
  186.           top = top.next.next;
  187.         else
  188.           break;
  189.       }
  190.     }
  191.   }
  192.  
  193.   public static void main(String[] args) {
  194.     String[] keys = { "Zoe", "Bob", "Eve", "Hal", "Abe", "Boo", "Eve", "Sam", "Kit", "Kat", "Pam", "Joe", "Ari", "Doc",
  195.         "Hen", "Guy" };
  196.     SkipMap map = new SkipMap();
  197.     for (int i = 0; i < keys.length; i++)
  198.       map.put(keys[i], i);
  199.     map.skipify();
  200.     System.out.println(map);
  201.  
  202.     String[] keys2 = { "Aaa", "Abe", "Guy", "Hal", "Joe", "Mxy", "Zoe", "Zzz" };
  203.     for (String key : keys2) {
  204.       System.out.print("containsKey(" + key + ") = ");
  205.       System.out.println(map.containsKey(key));
  206.       System.out.print("get(" + key + ") = ");
  207.       System.out.println(map.get(key));
  208.     }
  209.  
  210.     String[] keys3 = { "Vic", "Ira", "Sue", "Ann", "Moe", "Cat", "Dog", "Pig", "Cow", "Dot" };
  211.     for (int i = 0; i < keys3.length; i++)
  212.       map.put(keys3[i], keys.length + i);
  213.     System.out.println(map);
  214.   }
  215. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement