sjzset.h

ALGAE是一个快速创建算法演示的框架。目前支持的算法实现语言包括java和c

#ifndef SET_H
#define SET_H

#include <algae/config.h>
#include <utils/list.h>
#include <utils/sjzalgo.h>


#define typename

template <class Key, class Compare>
class set {
public:
// typedefs:
    typedef Key key_type;
    typedef Key value_type;
    typedef Compare key_compare;
    typedef Compare value_compare;
    typedef list<key_type> rep_type;

    typedef typename const Key& reference;
    typedef typename rep_type::const_reference const_reference;
    typedef typename rep_type::const_iterator const_iterator;

    typedef typename rep_type::const_iterator iterator;
    typedef typename rep_type::size_type size_type;
    typedef typename rep_type::difference_type difference_type;
private:
    rep_type t;
    Compare cmp;

    iterator lookFor(const key_type& x) const
    {
     iterator i = begin();
     while (i != end() && cmp(*i, x)) ++i;
     return i;
    }

    rep_type::iterator nonConst(iterator i) const
    {
      rep_type::iterator m = ((rep_type&)t).begin();
      iterator b = begin();
      while (b != i)
        {
         ++b;
         ++m;
        }
      return m;
    }
public:

// allocation/deallocation

    set(const Compare& comp = Compare()) : cmp(comp) {}

    set(const set<Key, Compare>& x) : t(x.t), cmp(x.cmp) {}
    set<Key, Compare>& operator=(const set<Key, Compare>& x) {
        t = x.t;
        return *this;
    }

// accessors:

    key_compare key_comp() const { return cmp; }
    value_compare value_comp() const { return cmp; }
    iterator begin() const { return t.begin(); }
    iterator end() const { return t.end(); }

    bool empty() const { return t.empty(); }
    size_type size() const { return t.size(); }
    size_type max_size() const { return t.max_size(); }
    void swap(set<Key, Compare>& x) { t.swap(x.t); }

// insert/erase
    typedef  pair<iterator, bool> pair_iterator_bool;

    pair<iterator,bool> insert(const value_type& x) {
        rep_type::iterator i = nonConst(lookFor(x));
        if (i == t.end())
          return pair<iterator,bool>(t.insert(t.end(), x), false);
        else if (cmp(x,*i))
          return pair<iterator,bool>(t.insert(i,x), true);
        else
          return pair<iterator,bool>(i, false);
        }

    iterator insert(iterator position, const value_type& x) {
        return insert (x).first;
    }

    void erase(iterator position) {
        t.erase(nonConst(position));
    }

    size_type erase(const key_type& x) {
        iterator i = find(x);
        if (i != t.end())
          erase(i);
    }

    void erase(iterator first, iterator last) {
      t.erase (nonConst(first), nonConst(last));
    }

    void clear() { t.erase(t.begin(), t.end()); }

// set operations:

    iterator find(const key_type& x) const
    {
     iterator i = lookFor (x);
     if (i != end() && !cmp(x,*i))
       return i;
     else
       return end();
    }

    size_type count(const key_type& x) const {
      return (find(x) == end()) ? 0 : 1;}

    iterator lower_bound(const key_type& x) const {
        return find(x);
    }
    iterator upper_bound(const key_type& x) const {
        iterator i = find(x);
        if (i != end())
          ++i;
        return i;
    }
    pair<iterator,iterator> equal_range(const key_type& x) const {
        iterator i = find(x);
        iterator j = i;
        if (j != end())
          ++j;
        return pair<iterator,iterator>(i,j);
    }

  friend bool operator==(const set<Key,Compare>&, const set<Key,Compare>&);
  friend bool operator<(const set<Key,Compare>&, const set<Key,Compare>&);
};


template <class Key, class Compare>
inline bool operator==(const set<Key, Compare>& x,
                       const set<Key, Compare>& y) {
  return operator==(x.t,y.t);
}

template <class Key, class Compare>
inline bool operator<(const set<Key, Compare>& x,
                      const set<Key, Compare>& y) {
  return x.t < y.t ;
}


#endif