← Back to branch summary

~ubuntu-branches/ubuntu/vivid/elki/vivid

« back to all changes in this revision

Viewing changes to src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TiedTopBoundedHeap.java

  • Committer: Package Import Robot
  • Author(s): Erich Schubert
  • Date: 2012-06-02 17:47:03 UTC
  • mfrom: (1.1.4)
  • Revision ID: package-import@ubuntu.com-20120602174703-1dxjcaak8v40xdu5
Tags: 0.5.0~beta2-1
* New upstream beta release.
* Needs GNU Trove 3, in NEW.
* Build with OpenJDK7, as OpenJDK6 complains.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/de/lmu/ifi/dbs/elki/utilities/datastructures/heap/TiedTopBoundedHeap.java
4
4
 This file is part of ELKI:
5
5
 Environment for Developing KDD-Applications Supported by Index-Structures
6
6
 
7
 
 Copyright (C) 2011
 
7
 Copyright (C) 2012
8
8
 Ludwig-Maximilians-Universität München
9
9
 Lehr- und Forschungseinheit für Datenbanksysteme
10
10
 ELKI Development Team
23
23
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
24
24
 */
25
25
 
 
26
import java.util.ArrayList;
26
27
import java.util.Comparator;
27
28
import java.util.Iterator;
28
 
import java.util.LinkedList;
 
29
import java.util.List;
29
30
 
30
31
import de.lmu.ifi.dbs.elki.utilities.iterator.MergedIterator;
31
32
 
32
33
/**
33
 
 * A size-limited heap similar to {@link TopBoundedHeap}, discarding elements with
34
 
 * the highest value. However, this variation keeps a list of tied elements.
 
34
 * A size-limited heap similar to {@link TopBoundedHeap}, discarding elements
 
35
 * with the highest value. However, this variation keeps a list of tied
 
36
 * elements.
35
37
 * 
36
38
 * @author Erich Schubert
37
39
 * 
46
48
  /**
47
49
   * List to keep ties in.
48
50
   */
49
 
  private LinkedList<E> ties = new LinkedList<E>();
 
51
  private List<E> ties = new ArrayList<E>();
50
52
 
51
53
  /**
52
54
   * Constructor with comparator.
90
92
  }
91
93
 
92
94
  @Override
93
 
  public synchronized E peek() {
94
 
    if (ties.isEmpty()) {
 
95
  public E peek() {
 
96
    if(ties.isEmpty()) {
95
97
      return super.peek();
96
 
    } else {
97
 
      return ties.peek() ;
 
98
    }
 
99
    else {
 
100
      return ties.get(ties.size() - 1);
98
101
    }
99
102
  }
100
103
 
101
104
  @Override
102
105
  public E poll() {
103
 
    if (ties.isEmpty()) {
 
106
    if(ties.isEmpty()) {
104
107
      return super.poll();
105
 
    } else {
106
 
      return ties.poll();
 
108
    }
 
109
    else {
 
110
      return ties.remove(ties.size() - 1);
107
111
    }
108
112
  }
109
113
 
110
114
  @Override
111
115
  protected void handleOverflow(E e) {
112
 
    if (super.compareExternal(e, 0) == 0) {
113
 
      if (!ties.isEmpty() && super.compareExternalExternal(e, ties.peek()) < 0) {
114
 
        ties.clear();
115
 
      }
 
116
    boolean tied = false;
 
117
    if(comparator == null) {
 
118
      @SuppressWarnings("unchecked")
 
119
      Comparable<Object> c = (Comparable<Object>) e;
 
120
      if(c.compareTo(queue[0]) == 0) {
 
121
        tied = true;
 
122
      }
 
123
    }
 
124
    else {
 
125
      if(comparator.compare(e, queue[0]) == 0) {
 
126
        tied = true;
 
127
      }
 
128
    }
 
129
    if(tied) {
116
130
      ties.add(e);
117
 
    } else {
 
131
    }
 
132
    else {
118
133
      // Also remove old ties.
119
134
      ties.clear();
120
135
    }