fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10.     static class RandomSet<E> extends AbstractSet<E> {
  11.  
  12.         List<E> dta = new ArrayList<E>();
  13.         Map<E, Integer> idx = new HashMap<E, Integer>();
  14.  
  15.         public RandomSet() {
  16.         }
  17.  
  18.         public RandomSet(Collection<E> items) {
  19.             for (E item : items) {
  20.                 idx.put(item, dta.size());
  21.                 dta.add(item);
  22.             }
  23.         }
  24.  
  25.         @Override
  26.         public boolean add(E item) {
  27.             if (idx.containsKey(item)) {
  28.                 return false;
  29.             }
  30.             idx.put(item, dta.size());
  31.             dta.add(item);
  32.             return true;
  33.         }
  34.  
  35.         /**
  36.          * Override element at position <code>id</code> with last element.
  37.          * @param id
  38.          */
  39.         public E removeAt(int id) {
  40.             if (id >= dta.size()) {
  41.                 return null;
  42.             }
  43.             E res = dta.get(id);
  44.             idx.remove(res);
  45.             E last = dta.remove(dta.size() - 1);
  46.             // skip filling the hole if last is removed
  47.             if (id < dta.size()) {
  48.                 idx.put(last, id);
  49.                 dta.set(id, last);
  50.             }
  51.             return res;
  52.         }
  53.  
  54.         @Override
  55.         public boolean remove(Object item) {
  56.             @SuppressWarnings(value = "element-type-mismatch")
  57.             Integer id = idx.get(item);
  58.             if (id == null) {
  59.                 return false;
  60.             }
  61.             removeAt(id);
  62.             return true;
  63.         }
  64.  
  65.         public E get(int i) {
  66.             return dta.get(i);
  67.         }
  68.  
  69.         public E pollRandom(Random rnd) {
  70.             if (dta.isEmpty()) {
  71.                 return null;
  72.             }
  73.             int id = rnd.nextInt(dta.size());
  74.             return removeAt(id);
  75.         }
  76.  
  77.         @Override
  78.         public int size() {
  79.             return dta.size();
  80.         }
  81.  
  82.         @Override
  83.         public Iterator<E> iterator() {
  84.             return dta.iterator();
  85.         }
  86.     }
  87.     public static void main (String[] args) throws java.lang.Exception
  88.     {
  89.         RandomSet<Integer> rs = new RandomSet<Integer>();
  90.         for (int i = 0; i < 20; ++i) {
  91.             rs.add(i);
  92.         }
  93.  
  94.         int count = 50;
  95.  
  96.         Random r = new Random();
  97.  
  98.         for (int i = 0; i < count; i++) {
  99.             System.out.println(rs.pollRandom(r));
  100.             rs.remove(i);
  101.             rs.add(i + 20);
  102.         }
  103.     }
  104. }
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
16
4
20
19
7
23
8
14
26
18
25
28
30
21
29
33
17
36
32
37
27
34
38
35
41
40
43
46
47
44
39
50
51
49
48
54
53
45
56
42
55
58
59
60
52
57
62
66
63
https://ideone.com/Sfltr7
language:
Java (12.0.1)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!