1 /*
2  * This file is part of ELKI:
3  * Environment for Developing KDD-Applications Supported by Index-Structures
4  *
5  * Copyright (C) 2018
6  * ELKI Development Team
7  *
8  * This program is free software: you can redistribute it and/or modify
9  * it under the terms of the GNU Affero General Public License as published by
10  * the Free Software Foundation, either version 3 of the License, or
11  * (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU Affero General Public License for more details.
17  *
18  * You should have received a copy of the GNU Affero General Public License
19  * along with this program. If not, see <http://www.gnu.org/licenses/>.
20  */
21 package de.lmu.ifi.dbs.elki.utilities.datastructures.heap;
22 
23 import java.util.ArrayList;
24 import java.util.Comparator;
25 import java.util.List;
26 
27 /**
28  * A size-limited heap similar to {@link TopBoundedHeap}, discarding elements
29  * with the highest value. However, this variation keeps a list of tied
30  * elements.
31  *
32  * @author Erich Schubert
33  * @since 0.4.0
34  *
35  * @has - - - UnorderedIter
36  *
37  * @param <E> Object type
38  */
39 public class TiedTopBoundedHeap<E> extends TopBoundedHeap<E> {
40   /**
41    * List to keep ties in.
42    */
43   private List<E> ties = new ArrayList<>();
44 
45   /**
46    * Constructor with comparator.
47    *
48    * @param maxsize Maximum size of heap (unless tied)
49    * @param comparator Comparator
50    */
TiedTopBoundedHeap(int maxsize, Comparator<? super E> comparator)51   public TiedTopBoundedHeap(int maxsize, Comparator<? super E> comparator) {
52     super(maxsize, comparator);
53   }
54 
55   /**
56    * Constructor for Comparable objects.
57    *
58    * @param maxsize Maximum size of heap (unless tied)
59    */
TiedTopBoundedHeap(int maxsize)60   public TiedTopBoundedHeap(int maxsize) {
61     this(maxsize, null);
62   }
63 
64   @Override
size()65   public int size() {
66     return super.size() + ties.size();
67   }
68 
69   @Override
clear()70   public void clear() {
71     super.clear();
72     ties.clear();
73   }
74 
75   @Override
peek()76   public E peek() {
77     if (ties.isEmpty()) {
78       return super.peek();
79     } else {
80       return ties.get(ties.size() - 1);
81     }
82   }
83 
84   @Override
poll()85   public E poll() {
86     if (ties.isEmpty()) {
87       return super.poll();
88     } else {
89       return ties.remove(ties.size() - 1);
90     }
91   }
92 
93   @Override
replaceTopElement(E e)94   public E replaceTopElement(E e) {
95     if (ties.isEmpty()) {
96       return super.replaceTopElement(e);
97     }
98     // Fall back to classic emulation via poll and offer:
99     E prev = poll();
100     add(e);
101     return prev;
102   }
103 
104   @Override
handleOverflow(E e)105   protected void handleOverflow(E e) {
106     boolean tied = false;
107     if (comparator == null) {
108       @SuppressWarnings("unchecked")
109       Comparable<Object> c = (Comparable<Object>) e;
110       if (c.compareTo(queue[0]) == 0) {
111         tied = true;
112       }
113     } else {
114       if (comparator.compare(e, queue[0]) == 0) {
115         tied = true;
116       }
117     }
118     if (tied) {
119       ties.add(e);
120     } else {
121       // Also remove old ties.
122       ties.clear();
123     }
124   }
125 
126   /**
127    * Get an unordered heap iterator.
128    *
129    * @return Iterator.
130    */
131   @Override
unorderedIter()132   public UnorderedIter unorderedIter() {
133     return new UnorderedIter();
134   }
135 
136   /**
137    * Unordered heap iterator class.
138    *
139    * @author Erich Schubert
140    *
141    */
142   public class UnorderedIter extends Heap<E>.UnorderedIter {
143     /**
144      * Constructor.
145      */
UnorderedIter()146     protected UnorderedIter() {
147       super();
148     }
149 
150     @Override
valid()151     public boolean valid() {
152       return pos < size();
153     }
154 
155     @Override
get()156     public E get() {
157       final int ssize = TiedTopBoundedHeap.super.size();
158       if (pos < ssize) {
159         return super.get();
160       } else {
161         return ties.get(pos - ssize);
162       }
163     }
164   }
165 }
166