OPENNLP-1054: Remove deprecated Heap and HeapList
Project: http://git-wip-us.apache.org/repos/asf/opennlp/repo Commit: http://git-wip-us.apache.org/repos/asf/opennlp/commit/dd25a691 Tree: http://git-wip-us.apache.org/repos/asf/opennlp/tree/dd25a691 Diff: http://git-wip-us.apache.org/repos/asf/opennlp/diff/dd25a691 Branch: refs/heads/LangDetect Commit: dd25a69102d3f3b17663763fc4172764622c3d4c Parents: 217f5eb Author: Jörn Kottmann <[email protected]> Authored: Wed May 10 16:48:09 2017 +0200 Committer: Jörn Kottmann <[email protected]> Committed: Fri May 19 12:02:24 2017 +0200 ---------------------------------------------------------------------- .../src/main/java/opennlp/tools/util/Heap.java | 80 -------- .../main/java/opennlp/tools/util/ListHeap.java | 197 ------------------- 2 files changed, 277 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/opennlp/blob/dd25a691/opennlp-tools/src/main/java/opennlp/tools/util/Heap.java ---------------------------------------------------------------------- diff --git a/opennlp-tools/src/main/java/opennlp/tools/util/Heap.java b/opennlp-tools/src/main/java/opennlp/tools/util/Heap.java deleted file mode 100644 index 83f3315..0000000 --- a/opennlp-tools/src/main/java/opennlp/tools/util/Heap.java +++ /dev/null @@ -1,80 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package opennlp.tools.util; - -import java.util.Iterator; - -/** Interface for interacting with a Heap data structure. - * This implementation extract objects from smallest to largest based on either - * their natural ordering or the comparator provided to an implementation. - * While this is a typical of a heap it allows this objects natural ordering to - * match that of other sorted collections. - * - * This is now deprecated and will be removed in Release 1.8.1 - * */ -@Deprecated -public interface Heap<E> { - - /** - * Removes the smallest element from the heap and returns it. - * @return The smallest element from the heap. - */ - E extract(); - - /** - * Returns the smallest element of the heap. - * @return The top element of the heap. - */ - E first(); - - /** - * Returns the largest element of the heap. - * @return The largest element of the heap. - */ - E last(); - - /** - * Adds the specified object to the heap. - * @param o The object to add to the heap. - */ - void add(E o); - - /** - * Returns the size of the heap. - * @return The size of the heap. - */ - int size(); - - /** - * Returns whether the heap is empty. - * @return true if the heap is empty; false otherwise. - */ - boolean isEmpty(); - - /** - * Returns an iterator over the elements of the heap. No specific ordering of these - * elements is guaranteed. - * @return An iterator over the elements of the heap. - */ - Iterator<E> iterator(); - - /** - * Clears the contents of the heap. - */ - void clear(); -} http://git-wip-us.apache.org/repos/asf/opennlp/blob/dd25a691/opennlp-tools/src/main/java/opennlp/tools/util/ListHeap.java ---------------------------------------------------------------------- diff --git a/opennlp-tools/src/main/java/opennlp/tools/util/ListHeap.java b/opennlp-tools/src/main/java/opennlp/tools/util/ListHeap.java deleted file mode 100644 index 92744e0..0000000 --- a/opennlp-tools/src/main/java/opennlp/tools/util/ListHeap.java +++ /dev/null @@ -1,197 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package opennlp.tools.util; - -import java.util.ArrayList; -import java.util.Comparator; -import java.util.Iterator; -import java.util.List; - -/** - * This class implements the heap interface using a {@link java.util.List} as the underlying - * data structure. This heap allows values which are equals to be inserted. The heap will - * return the top K values which have been added where K is specified by the size passed to - * the constructor. K+1 values are not gaurenteed to be kept in the heap or returned in a - * particular order. - * - * This is now deprecated and will be removed in Release 1.8.1 - */ -@Deprecated -public class ListHeap<E extends Comparable<E>> implements Heap<E> { - private List<E> list; - - private Comparator<E> comp; - - private int size; - - private E max = null; - - /** - * Creates a new heap with the specified size using the sorted based on the - * specified comparator. - * @param sz The size of the heap. - * @param c The comparator to be used to sort heap elements. - */ - public ListHeap(int sz, Comparator<E> c) { - size = sz; - comp = c; - list = new ArrayList<>(sz); - } - - /** - * Creates a new heap of the specified size. - * @param sz The size of the new heap. - */ - public ListHeap(int sz) { - this(sz, null); - } - - private int parent(int i) { - return (i - 1) / 2; - } - - private int left(int i) { - return (i + 1) * 2 - 1; - } - - private int right(int i) { - return (i + 1) * 2; - } - - public int size() { - return list.size(); - } - - private void swap(int x, int y) { - E ox = list.get(x); - E oy = list.get(y); - - list.set(y, ox); - list.set(x, oy); - } - - private boolean lt(E o1, E o2) { - if (comp != null) { - return comp.compare(o1, o2) < 0; - } - else { - return o1.compareTo(o2) < 0; - } - } - - private boolean gt(E o1, E o2) { - if (comp != null) { - return comp.compare(o1, o2) > 0; - } - else { - return o1.compareTo(o2) > 0; - } - } - - private void heapify(int i) { - while (true) { - int l = left(i); - int r = right(i); - int smallest; - - if (l < list.size() && lt(list.get(l), list.get(i))) - smallest = l; - else - smallest = i; - - if (r < list.size() && lt(list.get(r), list.get(smallest))) - smallest = r; - - if (smallest != i) { - swap(smallest, i); - i = smallest; - } - else - break; - } - } - - public E extract() { - if (list.size() == 0) { - throw new RuntimeException("Heap Underflow"); - } - E top = list.get(0); - int last = list.size() - 1; - if (last != 0) { - list.set(0, list.remove(last)); - heapify(0); - } - else { - list.remove(last); - } - - return top; - } - - public E first() { - if (list.size() == 0) { - throw new RuntimeException("Heap Underflow"); - } - return list.get(0); - } - - public E last() { - if (list.size() == 0) { - throw new RuntimeException("Heap Underflow"); - } - return max; - } - - public void add(E o) { - /* keep track of max to prevent unnecessary insertion */ - if (max == null) { - max = o; - } - else if (gt(o, max)) { - if (list.size() < size) { - max = o; - } - else { - return; - } - } - list.add(o); - - int i = list.size() - 1; - - //percolate new node to correct position in heap. - while (i > 0 && gt(list.get(parent(i)), o)) { - list.set(i, list.get(parent(i))); - i = parent(i); - } - - list.set(i, o); - } - - public void clear() { - list.clear(); - } - - public Iterator<E> iterator() { - return list.iterator(); - } - - public boolean isEmpty() { - return this.list.isEmpty(); - } -}
