SCIP in C++11 ― 2.3.3節その2

順序付けられた集合と問題2.61～2.62

Listに新たにoperator>とoperator<を実装（略）。

Listの内部的にはstringなので、数値の比較をするときは、

stoiやstodで変換が必要。

こういう基本的なところでいちいち分岐してたら、パフォーマンスはガタ落ちだから、

実際に使う時にはListの内部実装を見なおしたり、

doubleとintの比較では丸めのことを真剣に考えたり、

テンプレートも使ったりしてもっと良い実装にするところだが、

さしあたってはそういうことは気にしない事にする。

----

//element-of-set?

const bool isElementOfSet(const List& x,const List& setList)

{

    if(isNull(setList)){return(false);}

    if(x==car(setList)){return(true);}

    if(x<car(setList)){return(false);}

    return(isElementOfSet(x,cdr(setList)));

}

template<typename ElementType>

const bool isElementOfSet(const ElementType& x,const List& setList)

{return(isElementOfSet(makeLeaf(x),setList));}

//adjoin-set

const List adjoinSet(const List& x,const List& setList)

{

    if(isNull(setList)){return(cons(x,setList));}

    if(x==car(setList)){return(setList);}

    if(x<car(setList)){return(cons(x,setList));}

    return(cons(car(setList),adjoinSet(x,cdr(setList))));

}

template<typename ElementType>

const List adjoinSet(const ElementType& x,const List& setList)

{return(adjoinSet(makeLeaf(x),setList));}

//intersection-set

const List intersectionSet(const List& set1, const List& set2)

{

    if(isNull(set1)||isNull(set2)){return(makeList());}

    const List x1(car(set1));

    const List x2(car(set2));

    if(x1==x2){return(cons(x1,intersectionSet(cdr(set1),cdr(set2))));}

    if(x1<x2){return(intersectionSet(cdr(set1),set2));}

    return(intersectionSet(set1,cdr(set2)));

}

//union-set

const List unionSet(const List& set1, const List& set2)

{

    if(isNull(set1)){return(makeCopyList(set2));}

    if(isNull(set2)){return(makeCopyList(set1));}

    const List x1(car(set1));

    const List x2(car(set2));

    if(x1==x2){return(cons(x1,unionSet(cdr(set1),cdr(set2))));}

    if(x1<x2){return(cons(x1,unionSet(cdr(set1),set2)));}

    return(cons(x2,unionSet(set1,cdr(set2))));

}

//---------abstraction barrier---------

int main(int argc, char** argv)

{

    const auto set1(makeList(1,3,6,10));

    const auto element1(6);

    cout<<"(element-of-set? "<<element1<<" "<<listString(set1)<<") = "

        <<isElementOfSet(element1,set1)<<endl;

    const auto element2(4);

    cout<<"(element-of-set? "<<element2<<" "<<listString(set1)<<") = "

        <<isElementOfSet(element2,set1)<<endl;

   

    const auto set2(makeList(2,4,6,8));

    cout<<"(intersection-set "<<listString(set1)

        <<" "<<listString(set2)<<") = "

        <<listString(intersectionSet(set1,set2))<<endl;

   

    cout<<endl<<"Excersize 2.61:"<<endl;

    cout<<"(adjoin-set "<<element1<<" "<<listString(set1)<<") ="

        <<listString(adjoinSet(element1,set1))<<endl;

    cout<<"(adjoin-set "<<element2<<" "<<listString(set1)<<") ="

        <<listString(adjoinSet(element2,set1))<<endl;

    cout<<endl<<"Excersize 2.62:"<<endl;

    cout<<"(union-set "<<listString(set1)

        <<" "<<listString(set2)<<") = "

        <<listString(unionSet(set1,set2))<<endl;

    return(0);

}

----

出力

----

(element-of-set? 6 (1 3 6 10)) = 1

(element-of-set? 4 (1 3 6 10)) = 0

(intersection-set (1 3 6 10) (2 4 6 8)) = (6)

Excersize 2.61:

(adjoin-set 6 (1 3 6 10)) =(1 3 6 10)

(adjoin-set 4 (1 3 6 10)) =(1 3 4 6 10)

Excersize 2.62:

(union-set (1 3 6 10) (2 4 6 8)) = (1 2 3 4 6 8 10)