Job id storage

You are given a list of jobs, each job has an ID number(type is long).
Implement two functions,
1.expire(long jobid) to set a job as "expired"
2.isexpired(long jobid) to check if a job is "expired"

merge interval

lower_bound:the first num not less than
upper_bound:the first num greater than
所以如果没有相等的元素，lower和upper返回的结果是一样的

// lower_bound/upper_bound example
#include <iostream>     // std::cout
#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort
#include <vector>       // std::vector

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  std::vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20

  std::sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

  std::vector<int>::iterator low,up;
  low=std::lower_bound (v.begin(), v.end(), 20); //          ^
  up= std::upper_bound (v.begin(), v.end(), 20); //                   ^

  std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
  std::cout << "upper_bound at position " << (up - v.begin()) << '\n';

  return 0;
}

Bloom Filter: http://www.cnblogs.com/heaad/archive/2011/01/02/1924195.html

//哈希函数个数k、位数组大小m、加入的字符串数量n的关系:当 k = ln(2)* m/n 时出错的概率是最小的。

import java.util.BitSet;

public class BloomFilter {
    /* BitSet初始分配2^24个bit */ 
    private static finalint DEFAULT_SIZE =1<<25; 
    /* 不同哈希函数的种子，一般应取质数 */
    private static finalint[] seeds =newint[] { 5, 7, 11, 13, 31, 37, 61 };
    private BitSet bits =new BitSet(DEFAULT_SIZE);
    /* 哈希函数对象 */ 
    private SimpleHash[] func =new SimpleHash[seeds.length];

    public BloomFilter() {
        for (int i =0; i < seeds.length; i++)
            func[i] =new SimpleHash(DEFAULT_SIZE, seeds[i]);
    }

    // 将字符串标记到bits中
    public void add(String value) {
        for (SimpleHash f : func) 
            bits.set(f.hash(value), true);
    }

    //判断字符串是否已经被bits标记
    public boolean contains(String value) {
        if (value ==null) 
            returnfalse;
        boolean ret =true;
        for (SimpleHash f : func) 
            ret = ret && bits.get(f.hash(value));
        return ret;
    }

    /* 哈希函数类 */
    public static class SimpleHash {
        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        //hash函数，采用简单的加权和hash
        public int hash(String value) {
            int result =0;
            int len = value.length();
            for (int i =0; i < len; i++) 
                result = seed * result + value.charAt(i);
            return (cap - 1) & result;
        }
    }
}

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <set>

using namespace std;
struct Interval {
    long s, e;
    Interval(int s, int e) : s(s), e(e){}    //failed to write a structure!!!
};
class jobIdStorage {
private:
    set<pair<int, int>> expired;
public:
    void expire(long jobID) {
        pair<int, int> curr = make_pair(jobID, jobID);
        auto it = expired.upper_bound(curr);
        //反正把empty当成特殊情况不用想太多！
        if (expired.empty()) {
            expired.insert(curr);
            return;
        }

        //先判断后面的！
        if (it != expired.end() && it->first == jobID + 1) {
            curr.second = it->second;
            expired.erase(it);
        }

        if (it != expired.begin()) {
            it--;
            if (it->second + 1 == jobID) {
                curr.first = it->first;    //pay attention to '.' and "->"
                expired.erase(it);
            }
            if (it->second >= jobID) return;
        }

        expired.insert(curr);
    }
    bool isExpire(long jobID) {
        if (expired.empty()) return false;
        auto it = expired.upper_bound(make_pair(jobID, jobID));
        if (it == expired.begin() || (--it)->second < jobID) return false;
        return true;
    }
    void checkitv() {
        for (auto it = expired.begin(); it != expired.end(); it++)
            cout<<it->first<<"->"<<it->second<<endl;
    }
};
int main(int argc, char *argv[]) {
    jobIdStorage* job = new jobIdStorage();
    job->expire(1);
    job->expire(5);
    job->expire(5);
    job->expire(4);
    job->expire(3);
    job->expire(8);
    job->expire(10);
    job->checkitv();    //for test
    cout<<job->isExpire(4)<<endl;
    cout<<job->isExpire(2)<<endl;
    cout<<job->isExpire(10)<<endl;
}