what's this Ullmanset Class?

[lilzz]

Code: Select all

#include "vector.hh"

#include <cstddef>
#include <cassert>

template<unsigned B>
class BasedUllmanSet
{
  size_t n;
  std::vector<int> key;
  BasedVector<unsigned, B> pos;
  
public:
  BasedUllmanSet()
    : n(0)
  {}
  BasedUllmanSet(size_t cap)
    : n(0), key(cap), pos(cap)
  {}
  
  size_t capacity() const { return key.size(); }
  size_t size() const { return n; }
  bool empty() const { return n == 0; }
  void clear() { n = 0; }
  void resize(size_t cap)
  {
    key.resize(cap);
    pos.resize(cap);
    n = 0;
  }
  
  bool contains(int k) const
  {
    unsigned p = pos[k];
    return (p < n
            && key[p] == k);
  }
  
  void insert(int k)
  {
    if (contains(k))
      return;
    
    unsigned p = n++;
    key[p] = k;     
    pos[k] = p;
  }
  
  void extend(int k)
  {
    assert(!contains(k));
    
    unsigned p = n++;
    key[p] = k;
    pos[k] = p;
  }
  
  void erase(int k)
  {
    if (!contains(k))
      return;
    
    unsigned p = pos[k];
    --n;
    if (p != n)
      {
        int ell = key[n];
        pos[ell] = p;
        key[p] = ell;
      }
  }
  
  int ith(int i)
  {
    assert(i >= 0 && i < (int)n);
    return key[i];
  }
};

using UllmanSet = BasedUllmanSet<0>;
using UllmanSet1 = BasedUllmanSet<1>;

what's the significance of this class?
key[p] = k; pos[k] = p; seems kind of recursive to me.

[Paeryn]

The significance in the context which you have (as always) given is that it insignificant. Where is this code from? What uses it?

What part of the code don't you understand? If you can't work it out from there then look at how the class is used, that might give you some insight.

As for the key[p] = k; pos[k]= p part, one lets you quickly look up the value if you know the position, the other lets you look up the position if you know the value.