Ignore:
Timestamp:
2016-07-27T03:10:06+02:00 (8 years ago)
Author:
donvip
Message:

update to JOSM 10658

Location:
applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/Bag.java

    r28116 r32725  
    1414
    1515/**
    16  *  The <tt>Bag</tt> class represents a bag (or multiset) of 
    17  *  generic items. It supports insertion and iterating over the 
     16 *  The <tt>Bag</tt> class represents a bag (or multiset) of
     17 *  generic items. It supports insertion and iterating over the
    1818 *  items in arbitrary order.
    1919 *  <p>
    20  *  The <em>add</em>, <em>isEmpty</em>, and <em>size</em>  operation 
     20 *  The <em>add</em>, <em>isEmpty</em>, and <em>size</em>  operation
    2121 *  take constant time. Iteration takes time proportional to the number of items.
    2222 *  <p>
    … …  
    3434    }
    3535
    36    /**
     36    /**
    3737     * Create an empty stack.
    3838     */
    … …  
    4343    }
    4444
    45    /**
     45    /**
    4646     * Is the BAG empty?
    4747     */
    … …  
    5050    }
    5151
    52    /**
     52    /**
    5353     * Return the number of items in the bag.
    5454     */
    … …  
    5757    }
    5858
    59    /**
     59    /**
    6060     * Add the item to the bag.
    6161     */
    … …  
    9090
    9191        return true;
    92     } 
     92    }
    9393
    94 
    95    /**
     94    /**
    9695     * Return an iterator that iterates over the items in the bag.
    9796     */
     97    @Override
    9898    public Iterator<Item> iterator()  {
    99         return new ListIterator(); 
     99        return new ListIterator();
    100100    }
    101101
    … …  
    104104        private Node current = first;
    105105
     106        @Override
    106107        public boolean hasNext()  { return current != null;                     }
     108        @Override
    107109        public void remove()      { throw new UnsupportedOperationException();  }
    108110
     111        @Override
    109112        public Item next() {
    110113            if (!hasNext()) throw new NoSuchElementException();
    111114            Item item = current.item;
    112             current = current.next; 
     115            current = current.next;
    113116            return item;
    114117        }
    115118    }
    116 
    117119}

  • applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/DirectedEdge.java

    r28116 r32725  
    1717 */
    1818
    19 public class DirectedEdge { 
     19public class DirectedEdge {
    2020    private final int v;
    2121    private final int w;
    2222    private final double weight;
    2323
    24    /**
     24    /**
    2525     * Create a directed edge from v to w with given weight.
    2626     */
    … …  
    3131    }
    3232
    33    /**
     33    /**
    3434     * Return the vertex where this edge begins.
    3535     */
    … …  
    3838    }
    3939
    40    /**
     40    /**
    4141     * Return the vertex where this edge ends.
    4242     */
    … …  
    4545    }
    4646
    47    /**
     47    /**
    4848     * Return the weight of this edge.
    4949     */
    5050    public double weight() { return weight; }
    5151
    52    /**
     52    /**
    5353     * Return a string representation of this edge.
    5454     */
     55    @Override
    5556    public String toString() {
    5657        return v + "->" + w + " " + String.format("%5.2f", weight);
    5758    }
    58 
    59    /**
    60      * Test client.
    61      */
    62 //    public static void main(String[] args) {
    63 //        DirectedEdge e = new DirectedEdge(12, 23, 3.14);
    64 //        StdOut.println(e);
    65 //    }
    6659}

  • applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/EdgeWeightedDigraph.java

    r30737 r32725  
    2525    private int E;
    2626    private Bag<DirectedEdge>[] adj;
    27    
     27
    2828    /**
    2929     * Create an empty edge-weighted digraph with V vertices.
    … …  
    3434        this.V = V;
    3535        this.E = 0;
    36         adj = (Bag<DirectedEdge>[]) new Bag[V];
     36        adj = new Bag[V];
    3737        for (int v = 0; v < V; v++)
    3838            adj[v] = new Bag<>();
    3939    }
    4040
    41    /**
     41    /**
    4242     * Create a edge-weighted digraph with V vertices and E edges.
    4343     */
    … …  
    5757     * Create an edge-weighted digraph from input stream.
    5858     */
    59 //    public EdgeWeightedDigraph(In in) {
    60 //        this(in.readInt());
    61 //        int E = in.readInt();
    62 //        for (int i = 0; i < E; i++) {
    63 //            int v = in.readInt();
    64 //            int w = in.readInt();
    65 //            double weight = in.readDouble();
    66 //            addEdge(new DirectedEdge(v, w, weight));
    67 //        }
    68 //    }
     59    //    public EdgeWeightedDigraph(In in) {
     60    //        this(in.readInt());
     61    //        int E = in.readInt();
     62    //        for (int i = 0; i < E; i++) {
     63    //            int v = in.readInt();
     64    //            int w = in.readInt();
     65    //            double weight = in.readDouble();
     66    //            addEdge(new DirectedEdge(v, w, weight));
     67    //        }
     68    //    }
    6969
    70    /**
     70    /**
    7171     * Copy constructor.
    7272     */
    … …  
    8686    }
    8787
    88    /**
     88    /**
    8989     * Return the number of vertices in this digraph.
    9090     */
    … …  
    9393    }
    9494
    95    /**
     95    /**
    9696     * Return the number of edges in this digraph.
    9797     */
    … …  
    100100    }
    101101
    102    /**
     102    /**
    103103     * Add the edge e to this digraph.
    104104     */
    … …  
    109109    }
    110110
    111    /**
     111    /**
    112112     * Return the edges leaving vertex v as an Iterable.
    113113     * To iterate over the edges leaving vertex v, use foreach notation:
    … …  
    118118    }
    119119
    120    /**
     120    /**
    121121     * Return all edges in this graph as an Iterable.
    122122     * To iterate over the edges, use foreach notation:
    … …  
    131131        }
    132132        return list;
    133     } 
     133    }
    134134
    135    /**
     135    /**
    136136     * Return number of edges leaving v.
    137137     */
    … …  
    140140    }
    141141
    142    /**
     142    /**
    143143     * Return a string representation of this graph.
    144144     */
     145    @Override
    145146    public String toString() {
    146147        String NEWLINE = System.getProperty("line.separator");

  • applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/IndexMinPQ.java

    r30737 r32725  
    5151
    5252    // return the index associated with a minimal key
    53     public int minIndex() { 
     53    public int minIndex() {
    5454        if (N == 0) throw new NoSuchElementException("Priority queue underflow");
    55         return pq[1];       
     55        return pq[1];
    5656    }
    5757
    5858    // return a minimal key
    59     public Key minKey() { 
     59    public Key minKey() {
    6060        if (N == 0) throw new NoSuchElementException("Priority queue underflow");
    61         return keys[pq[1]];       
     61        return keys[pq[1]];
    6262    }
    6363
    6464    // delete a minimal key and returns its associated index
    65     public int delMin() { 
     65    public int delMin() {
    6666        if (N == 0) throw new NoSuchElementException("Priority queue underflow");
    67         int min = pq[1];       
    68         exch(1, N--); 
     67        int min = pq[1];
     68        exch(1, N--);
    6969        sink(1);
    7070        qp[min] = -1;            // delete
    7171        keys[pq[N+1]] = null;    // to help with garbage collection
    7272        pq[N+1] = -1;            // not needed
    73         return min; 
     73        return min;
    7474    }
    7575
    … …  
    121121
    122122
    123    /**************************************************************
    124     * General helper functions
    125     **************************************************************/
     123    /**************************************************************
     124     * General helper functions
     125     **************************************************************/
    126126    private boolean greater(int i, int j) {
    127127        return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
    … …  
    134134
    135135
    136    /**************************************************************
    137     * Heap helper functions
    138     **************************************************************/
     136    /**************************************************************
     137     * Heap helper functions
     138     **************************************************************/
    139139    private void swim(int k)  {
    140140        while (k > 1 && greater(k/2, k)) {
    … …  
    155155
    156156
    157    /***********************************************************************
    158     * Iterators
    159     **********************************************************************/
     157    /***********************************************************************
     158     * Iterators
     159     **********************************************************************/
    160160
    161    /**
     161    /**
    162162     * Return an iterator that iterates over all of the elements on the
    163163     * priority queue in ascending order.
    … …  
    165165     * The iterator doesn't implement <tt>remove()</tt> since it's optional.
    166166     */
     167    @Override
    167168    public Iterator<Integer> iterator() { return new HeapIterator(); }
    168169
    … …  
    179180        }
    180181
     182        @Override
    181183        public boolean hasNext()  { return !copy.isEmpty();                     }
     184        @Override
    182185        public void remove()      { throw new UnsupportedOperationException();  }
    183186
     187        @Override
    184188        public Integer next() {
    185189            if (!hasNext()) throw new NoSuchElementException();

  • applications/editors/josm/plugins/utilsplugin2/src/edu/princeton/cs/algs4/Stack.java

    r28116 r32725  
    88 *  A generic stack, implemented using a linked list. Each stack
    99 *  element is of type Item.
    10  * 
    11  *  % more tobe.txt 
     10 *
     11 *  % more tobe.txt
    1212 *  to be or not to - be - - that - - - is
    1313 *
    … …  
    4242    }
    4343
    44    /**
     44    /**
    4545     * Create an empty stack.
    4646     */
    … …  
    5151    }
    5252
    53    /**
     53    /**
    5454     * Is the stack empty?
    5555     */
    … …  
    5858    }
    5959
    60    /**
     60    /**
    6161     * Return the number of items in the stack.
    6262     */
    … …  
    6565    }
    6666
    67    /**
     67    /**
    6868     * Add the item to the stack.
    6969     */
    … …  
    7777    }
    7878
    79    /**
     79    /**
    8080     * Delete and return the item most recently added to the stack.
    8181     * Throw an exception if no such item exists because the stack is empty.
    … …  
    9191
    9292
    93    /**
     93    /**
    9494     * Return the item most recently added to the stack.
    9595     * Throw an exception if no such item exists because the stack is empty.
    … …  
    100100    }
    101101
    102    /**
     102    /**
    103103     * Return string representation.
    104104     */
     105    @Override
    105106    public String toString() {
    106107        StringBuilder s = new StringBuilder();
    … …  
    109110        return s.toString();
    110111    }
    111        
     112
    112113
    113114    // check internal invariants
    … …  
    132133
    133134        return true;
    134     } 
     135    }
    135136
    136137
    137    /**
     138    /**
    138139     * Return an iterator to the stack that iterates through the items in LIFO order.
    139140     */
     141    @Override
    140142    public Iterator<Item> iterator()  { return new ListIterator();  }
    141143
    … …  
    143145    private class ListIterator implements Iterator<Item> {
    144146        private Node current = first;
     147        @Override
    145148        public boolean hasNext()  { return current != null;                     }
     149        @Override
    146150        public void remove()      { throw new UnsupportedOperationException();  }
    147151
     152        @Override
    148153        public Item next() {
    149154            if (!hasNext()) throw new NoSuchElementException();
    150155            Item item = current.item;
    151             current = current.next; 
     156            current = current.next;
    152157            return item;
    153158        }
    … …  
    155160
    156161
    157    /**
     162    /**
    158163     * A test client.
    159164     */
    160 //    public static void main(String[] args) {
    161 //        Stack<String> s = new Stack<String>();
    162 //        while (!StdIn.isEmpty()) {
    163 //            String item = StdIn.readString();
    164 //            if (!item.equals("-")) s.push(item);
    165 //            else if (!s.isEmpty()) StdOut.print(s.pop() + " ");
    166 //        }
    167 //        StdOut.println("(" + s.size() + " left on stack)");
    168 //    }
     165    //    public static void main(String[] args) {
     166    //        Stack<String> s = new Stack<String>();
     167    //        while (!StdIn.isEmpty()) {
     168    //            String item = StdIn.readString();
     169    //            if (!item.equals("-")) s.push(item);
     170    //            else if (!s.isEmpty()) StdOut.print(s.pop() + " ");
     171    //        }
     172    //        StdOut.println("(" + s.size() + " left on stack)");
     173    //    }
    169174}
    170175
Note: See TracChangeset for help on using the changeset viewer.