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

二進木としての集合と問題2.63～2.65

順序付けられた二進木となると、STLのsetを使いたくなるし、

実際に使うときは効率を考えて多分そうするだろうが、

ここは頑張って、今までどおり自前のListで行こう。

問題2.63はtree->list-2が、appendが噛まないので効率が良いことと、

反復の方がメモリ消費量が少ないと思うので、

tree->list-2の方を実装。

----

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

typedef List Entry; //Leaf

typedef List BinaryTree;

template<typename EntryType>

const Entry makeEntry(const EntryType x)

{return(makeLeaf(x));}

template<>

const Entry makeEntry<Entry>(const Entry x)

{return(x);}

const BinaryTree makeNullTree(void){return(makeList());}

const Entry entry(const BinaryTree& tree){return(car(tree));}

const BinaryTree leftBranch(const BinaryTree& tree){return(cadr(tree));}

const BinaryTree rightBranch(const BinaryTree& tree){return(caddr(tree));}

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

//make-tree

template <typename EntryType>

const BinaryTree makeTree

(const EntryType& entry,const BinaryTree& left,const BinaryTree& right)

{return(makeList(makeEntry(entry),left,right));}

const BinaryTree makeTree(void){return(makeNullTree());}

//element-of-set?

template <typename EntryType>

const bool isElementOfSet(const EntryType& x,const BinaryTree& setList)

{

    const Entry xEntry(makeEntry(x));

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

    if(xEntry==entry(setList)){return(true);}

    if(xEntry<entry(setList)){

        return(isElementOfSet(xEntry,leftBranch(setList)));}

    return(isElementOfSet(xEntry,rightBranch(setList)));

}

//adjoin-set

template <typename EntryType>

const BinaryTree adjoinSet(const EntryType& x,const BinaryTree& setList)

{

    const Entry xEntry(makeEntry(x));

    if(isNull(setList)){

        return(makeTree(xEntry,makeNullTree(),makeNullTree()));

    }

    if(xEntry==entry(setList)){return(setList);}

    if(xEntry<entry(setList)){

        return(makeTree(entry(setList),

                        adjoinSet(xEntry,leftBranch(setList)),

                        rightBranch(setList)));

    }

    return(makeTree(entry(setList),

                    leftBranch(setList),

                    adjoinSet(xEntry,rightBranch(setList))));

}

//tree->list-2

const List tree2List(const BinaryTree& tree)

{

    function<List(BinaryTree,List)> copyToList;

    copyToList=[&copyToList]

        (const BinaryTree& tree,const List& resultList)

        {

            if(isNull(tree)){return(resultList);}

            return(copyToList

                   (leftBranch(tree),

                    cons(entry(tree),

                         copyToList(rightBranch(tree),resultList))));

        };

    return(copyToList(tree,makeNullTree()));

}

//list->tree

const BinaryTree partialTree(const List& elts,const int n)

{

    if(0==n){return(cons(makeList(),elts));}

    else{

        const int leftSize((n-1)/2);

        const BinaryTree leftResult(partialTree(elts,leftSize));

        const BinaryTree leftTree(car(leftResult));

        const List nonLeftElts(cdr(leftResult));

        const Entry thisEntry(car(nonLeftElts));

        const int rightSize(n-(leftSize+1));

        const BinaryTree rightResult

            (partialTree(cdr(nonLeftElts),rightSize));

        const BinaryTree rightTree(car(rightResult));

        const BinaryTree remainingElts(cdr(rightResult));

        return(cons(makeTree(thisEntry,leftTree,rightTree),

                    remainingElts));

    }

}

const BinaryTree list2Tree(const List& elements)

{

    return(car(partialTree(elements,length(elements))));

}

//intersection-set for list

const List intersectionSetList(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,intersectionSetList(cdr(set1),cdr(set2))));}

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

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

   

}

//union-set for list

const List unionSetList(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,unionSetList(cdr(set1),cdr(set2))));}

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

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

 }

// intersection-set for binary tree

const BinaryTree intersectionSet(const BinaryTree binaryTree1,

                                 const BinaryTree binaryTree2)

{

    const List list1(tree2List(binaryTree1));

    const List list2(tree2List(binaryTree2));

    return(list2Tree(intersectionSetList(list1,list2)));

}

// union-set for binary tree

const BinaryTree unionSet(const BinaryTree binaryTree1,

                          const BinaryTree binaryTree2)

{

    const List list1(tree2List(binaryTree1));

    const List list2(tree2List(binaryTree2));

    return(list2Tree(unionSetList(list1,list2)));

}

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

int main(int argc, char** argv)

{

    const BinaryTree nil(makeTree());

    const auto binaryTree1

        (makeTree(7,

                  makeTree(3,

                           makeTree(1,nil,nil),

                           makeTree(5,nil,nil)),

                  makeTree(9,

                           nil,

                           makeTree(11,nil,nil))));

    cout<<"binaryTree1 = "<<listString(binaryTree1)<<endl;

    const auto element1(9);

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

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

    const auto element2(4);

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

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

   

    cout<<"(adjoin-set "<<element1<<" binaryTree1) ="

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

    cout<<"(adjoin-set "<<element2<<" binaryTree1) ="

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

   

    cout<<endl<<"Excersize 2.63:"<<endl;

    cout<<"(tree->list-2 binaryTree1) = "

        <<listString(tree2List(binaryTree1))<<endl;

    cout<<"(tree->list-2 (adjoin-set "<<element2<<" binaryTree1))"

        <<listString(tree2List(adjoinSet(element2,binaryTree1)))<<endl;

   

    cout<<endl<<"Excersize 2.64:"<<endl;

    const List list2(makeList(1,3,5,7,9,11));

    const BinaryTree binaryTree2(list2Tree(list2));

    cout<<"list2 = "<<listString(list2)<<endl;

    cout<<"(list->tree list2) = "

        <<listString(binaryTree2)<<endl;

    cout<<endl<<"Excersize 2.65:"<<endl;

    const List list3(makeList(1,4,7,10,11));

    cout<<"list3 = "<<listString(list3)<<endl;

    const BinaryTree binaryTree3(list2Tree(list3));

    cout<<"(intersection-set (list->tree list2) (list->tree list3) = "

        <<listString(intersectionSet(binaryTree2,binaryTree3))<<endl;

    cout<<"(union-set (list->tree list2) (list->tree list3) = "

        <<listString(unionSet(binaryTree2,binaryTree3))<<endl;

    return(0);

}

----

出力

----

binaryTree1 = (7 (3 (1 () ()) (5 () ())) (9 () (11 () ())))

(element-of-set? 9 binaryTree1) = 1

(element-of-set? 4 binaryTree1) = 0

(adjoin-set 9 binaryTree1) =(7 (3 (1 () ()) (5 () ())) (9 () (11 () ())))

(adjoin-set 4 binaryTree1) =(7 (3 (1 () ()) (5 (4 () ()) ())) (9 () (11 () ())))

Excersize 2.63:

(tree->list-2 binaryTree1) = (1 3 5 7 9 11)

(tree->list-2 (adjoin-set 4 binaryTree1))(1 3 4 5 7 9 11)

Excersize 2.64:

list2 = (1 3 5 7 9 11)

(list->tree list2) = (5 (1 () (3 () ())) (9 (7 () ()) (11 () ())))

Excersize 2.65:

list3 = (1 4 7 10 11)

(intersection-set (list->tree list2) (list->tree list3) = (7 (1 () ()) (11 () ()))

(union-set (list->tree list2) (list->tree list3) = (5 (3 (1 () ()) (4 () ())) (9 (7 () ()) (10 () (11 () ()))))