hw5

optional的懒得写了_(:з」∠)_，然后set是interface不知道怎么处理所以擅自加了hashset，之前忘记up上来了。所以这门课。。。。。人呢！！！2015SPRING也没讲那么差_(:з」∠)_

/** A linked list class that stores items of type Object. */
public class GenericList<Zerp> {

    /** Inner class used to represent a single node in this linked list. */
    private class Node {

        /** Constructs a new Node with head VALUE and a null tail. */
        public Node(Zerp value) {
            this(value, null);
        }

        /** Constructs a new Node with head VALUE and tail NEXT. */
        public Node(Zerp value, Node next) {
            this.value = value;
            this.next = next;
        }

        /** Returns the element at index i starting at this node in
         *  the linked list. */
        public Zerp get(int i) {
            if (i == 0) return value;
            if (next == null) {
                throw new IllegalArgumentException("Index out of bounds");
            } else {
                return next.get(i - 1);
            }
        }

        /** The value stored in this node */
        Zerp value;
        /** The next node in the list */
        Node next;
    }

    /** Returns a string representation of this list of the form:
     *  [item1, item2, ..., itemN]. */
    @Override
    public String toString() {
        String rep = "[";
        Node cur = head;
        while (cur != null && cur.next != null) {
            rep += cur.value + ", ";
            cur = cur.next;
        }
        if (cur != null) {
            rep += cur.value;
        }
        rep += "]";
        return rep;
    }

    /** Returns number of items in this list. */
    public int length() {
        return length;
    }

    /** Returns ith element of this list, throwing an exception if it
     *  does not exist. */
    public Zerp get(int i) {
        if (head == null) {
            throw new IllegalArgumentException("Index out of bounds");
        }
        return head.get(i);
    }

    /** Inserts VAL into the front of this list. */
    public void insert(Zerp val) {
        head = new Node(val, head);
        length += 1;
    }

    /** The head of this linked list. */
    private Node head;
    /** The number of elements in this linked list */
    private int length;

}

import java.util.Set;
import java.util.NoSuchElementException;
import java.util.Iterator;
import java.util.HashSet;

public class ULLMap<K,V> implements  Map61B<K,V> , Iterable<K>{

    private Entry front;
    private int N;

    public Iterator<K> iterator(){
        return new ULLMapIter();
    }

    private class ULLMapIter implements Iterator<K>{
      //  front=new()
        private Entry e=front;

        public boolean hasNext(){
            return (e.next!=null);
        }

        public K next(){

            if(e==null) return null;

            K key=e.key;
            e=e.next;

            return key;
        }

        public void remove(){
            throw new UnsupportedOperationException();
        }
    }

    private class Entry {

        private K key;
        private V val;
        private Entry next;

        public Entry(K k,V v, Entry n) {
            key = k;
            val = v;
            next = n;
        }

        public Entry get(K k) {
            if(this.key.equals(k)) return this;
            return null;
        }

        public K getKey(){
            return this.key;
        }

        public V getValue(){
            return this.val;
        }

    }

    @Override
    public V get(K key) {
        for(Entry e=front; e!=null; e=e.next){
            if(key.equals(e.key)) return e.val;
        }
        return null;
    }

    @Override
    public void put(K key, V val) {
        for(Entry e=front; e!=null; e=e.next){
            if(key.equals(e.key)){
                e.val=val;
                return;
            }
        }
        front =new Entry(key,val,front);

        //front.next=new Entry(key,val,null);
        N++;
    }


    @Override
    public boolean containsKey(K key) {
        return get(key) !=null;
    }

    @Override
    public int size() {
        return N;
    }

    @Override
    public void clear() {
       for(Entry e=front; e!=null; e=e.next){
            e=null;
        }

    }



    /* Methods below are all challenge problems. Will not be graded in any way.
     * Autograder will not test these. */
    @Override
    public V remove(K key) { //FIX ME SO I COMPILE
        throw new UnsupportedOperationException();
    }

    @Override
    public V remove(K key, V value) { //FIX ME SO I COMPILE
        throw new UnsupportedOperationException();
    }

    @Override
    public Set<K> keySet() { //FIX ME SO I COMPILE
        //throw new UnsupportedOperationException();
        Set<K> keyset=new HashSet<K>();
        for(Entry e=front; e!=null; e=e.next){
            keyset.add(e.key);
        }
        return keyset;
    }


    public static <V,K> ULLMap<V,K> InvertMap(ULLMap<K,V> map){

        ULLMap<V,K> invertMap=new ULLMap<V,K>();

        for(K key:map.keySet()){
            V val=map.get(key);
            invertMap.put(val,key);
        }
        return invertMap;
    }

}
import java.util.AbstractList;
import java.util.NoSuchElementException;

public class ArrayList61B extends AbstractList<T>{
/*This constructor should initialize the size of the internal array to be initialCapacity
  *and throw an IllegalArgumentException if initialCapacity is less than 1.
  */
public T[] a;
public int size;
public int capacity;

public ArrayList61B(int initialCapacity){
        capacity=initialCapacity;
        if(capacity<1){
                throw new IllegalArgumentException();
        }

        T[] a=(T[]) new Object[capacity];
        size=0;
}

/*This constructor should initialize the size of the internal array to be 1.*/
public ArrayList61B(){
        capacity=1;
        T[] a=(T[]) new Object[capacity];
        size=0;
}

/*This method should return the ith element in the list.
*This method should throw an IllegalArgumentException if i is less than 0 or greater
*than or equal to the number of elements in the list.
*/
public E get(int i){
        if((i<0) ||(i>=size)){
                throw new IllegalArgumentException();
        }
        return a[i];

}

/* This method should add item to the end of the list, resizing the internal array if necessary.
* This method should always return true (if you are curious about this, read the api for
* AbstractList).
*/
public boolean add(E item){
  if(size==capacity) this.resize();

   size=size+1;
   a[size]=item;

}

private void resize(){

          T[] b=(T[]) new Object[2*capacity];
          for(int i=0;i<size;i++){
      b[i]=a[i];
          }

          a=b;

}

/*This method should return the number of elements in the list. Note that this is not necessarily the same as the number of elements in the internal array.
*/
public int size(){
  return size;
}


}

/** A linked list class that stores items of type Object. */
public class GenericList<T>{

    /** Inner class used to represent a single node in this linked list. */
    private class Node{
        
        /** Constructs a new Node with head VALUE and a null tail. */
        public Node(T value) {
            this(value, null);
        }

        /** Constructs a new Node with head VALUE and tail NEXT. */
        public Node(T value, Node next) {
            this.value = value;
            this.next = next;
        }

        /** Returns the element at index i starting at this node in
         *  the linked list. */
        public T get(int i) {
            if (i == 0) return value;
            if (next == null) {
                throw new IllegalArgumentException("Index out of bounds");
            } else {
                return next.get(i - 1);
            }
        }

        /** The value stored in this node */
        T value;
        /** The next node in the list */
        Node next;
    }

    /** Returns a string representation of this list of the form:
     *  [item1, item2, ..., itemN]. */
    @Override
    public String toString() {
        String rep = "[";
        Node cur = head;
        while (cur != null && cur.next != null) {
            rep += cur.value + ", ";
            cur = cur.next;
        }
        if (cur != null) {
            rep += cur.value;
        }
        rep += "]";
        return rep;
    }

    /** Returns number of items in this list. */
    public int length() {
        return length;
    }

    /** Returns ith element of this list, throwing an exception if it
     *  does not exist. */
    public Object get(int i) {
        if (head == null) {
            throw new IllegalArgumentException("Index out of bounds");
        }
        return head.get(i);
    }

    /** Inserts VAL into the front of this list. */
    public void insert(T val) {
        head = new Node(val, head);
        length += 1;
    }

    /** The head of this linked list. */
    private Node head;
    /** The number of elements in this linked list */
    private int length;

}

import java.util.*; /* java.util.Set needed only for challenge problem. */

/** A data structure that uses a linked list to store pairs of keys and values.
*  Any key must appear at most once in the dictionary, but values may appear multiple
*  times. Supports get(key), put(key, value), and contains(key) methods. The value
*  associated to a key is the value in the last call to put with that key.
*
*  For simplicity, you may assume that nobody ever inserts a null key or value
*  into your map.
*/
public class ULLMap<K,V> implements Map61B<K, V>,Iterable<K>{
    /** Keys and values are stored in a linked list of Entry objects.
      * This variable stores the first pair in this linked list. You may
      * point this at a sentinel node, or use it as a the actual front item
      * of the linked list.
      */
    private Entry front;
    private int size;

    public ULLMap(){
            front = new Entry(null,null,null);
            size =0;
    }
    public Iterator<K> iterator(){
            return new ULLMapIter(this);
    }
   
    public class ULLMapIter implements Iterator<K>{
            public Entry p;
            public ULLMapIter(ULLMap<K,V> u){
                    p = front.next;
            }
           
            public K next(){
                    if (hasNext()){
                            K key = p.key;
                            p = p.next;
                            return key;
                    }
                    throw new NoSuchElementException();
            }
            public boolean hasNext(){
                    return (p!=null);
            }
    public void remove() {
        throw new UnsupportedOperationException();
    }
    }
   

    @Override
    public V get(K key) {
    Entry p = front.next.get(key);
    if (p!=null && p.val!=null){
            return p.val;
    }
        return null;
    }

    @Override
    public void put(K key, V val) {
    Entry p = front;
    while(p.next!=null){
            if (p.next.key.equals(key)){
                    p.next.val = val;
                    return;
            }
            p = p.next;
    }
    p.next = new Entry(key,val,null);
    size++;
    }

    @Override
    public boolean containsKey(K key) {   
        return front.next.get(key)!=null;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void clear() {
            size = 0;
            front.next = null;
    }


    /** Represents one node in the linked list that stores the key-value pairs
     *  in the dictionary. */
    private class Entry {
   
        /** Stores KEY as the key in this key-value pair, VAL as the value, and
         *  NEXT as the next node in the linked list. */
        public Entry(K k,V v, Entry n) {
            key = k;
            val = v;
            next = n;
        }

        /** Returns the Entry in this linked list of key-value pairs whose key
         *  is equal to KEY, or null if no such Entry exists. */
        public Entry get(K k) {
            Entry p = this;
            while(p!=null){
                    if(p.key.equals(k)){
                            return p;
                    }
                    p = p.next;
            }
            return null;
        }

        /** Stores the key of the key-value pair of this node in the list. */
        private K key;
        /** Stores the value of the key-value pair of this node in the list. */
        private V val;
        /** Stores the next Entry in the linked list. */
        private Entry next;
   
    }

    /* Methods below are all challenge problems. Will not be graded in any way.
     * Autograder will not test these. */
    @Override
    public V remove(K key) {
        Entry p = front.next.get(key);
        if (p!=null){
                V v = p.val;
                p.val = null;
                return v;
        }
        return null;
    }

    @Override
    public V remove(K key, V value) {
        Entry p = front.next;
        V r = null;
        while(p.next!=null){
                if(p.next.key==key&&p.next.val==value){
                        r = p.next.val;
                        p.next = p.next.next;
                }else{
                p = p.next;
                }
        }
        size--;
        return r;
    }

    @Override
    public Set<K> keySet() {
            Set<K> set=new HashSet<K>();
            Entry p = front.next;
            while(p!=null){
                    set.add(p.key);
            }
            return set;
    }
   
    public static <K,V> ULLMap<V,K> invert(ULLMap<K,V> umap){
            ULLMap<V,K> newmap = new ULLMap<V,K>();
            for (K i : umap){
                    newmap.put(umap.get(i), i);
            }
            return newmap;
    }


}


import java.util.AbstractList;
public class ArrayList61B<ele> extends AbstractList<ele>{
        private ele[] array;
        private int number;
       
        public ArrayList61B(int initialCapacity){
                if (initialCapacity>=1){
                array = (ele[]) new Object[initialCapacity];
                number = 0;
                }
                throw new IllegalArgumentException();
        }
        public ArrayList61B(){
                array = (ele[]) new Object[1];
                number =0;
        }
        public ele get(int i){
                if (i>=0 && i<number){
                        return array[i];
                }
                throw new IllegalArgumentException();
        }
        public boolean add(ele item){
                if (size()>=array.length){
                        ele[] newarray = (ele[]) new Object[array.length*2];
                        for(int i =0;i<size();i++){
                                newarray[i] = array[i];
                        }
                        array = newarray;
                }
                array[size()] = item;
                number++;
                return true;
        }
       
        public int size(){
                return number;
        }

}