As we have seen in a prior entry, swo extensions are an alternative formulation of the partition-based semantics used to describe the acceptable arguments to C++ binary search algorithms. This means that if a sequence `[start, finish)`

of elements of type `A`

is ordered with respect to some swo `less_A`

and we have an swo extension `less_AB`

with interface:

struct less_ABthen we can use C++ binary search algorithms with arguments of type

{

bool operator()(const A&,const B&);

bool operator()(const B&,const A&);

};

`B`

, using `less_AB`

as the comparison predicate.The following are examples of swo extensions with some practical interest:

If `A`

= `std::tuple<A1,...,An>`

and `less_A`

is a lexicographical swo on `A`

, we can define a swo extension `less_AB`

on `B`

= `std::tuple<A1,...,Am>`

, `m`

≤`n`

, as follows: comparing `a`

= `(a1,...,an)`

and `b`

= `(b1,...bm)`

is equivalent to comparing `b'`

= `(a1,...,am)`

and `b`

with the lexicographical order on `B`

obtained by using the first `m`

componenents of `less_A`

.

Let `A1`

,...,`An`

be types forming a single-inheritance hierarchy tree T` rooted at `

`A1`

, <_{T} a swo between types induced by a preorder traversal of T and a predicate `less_A`

on polymorphic objects of base type `A1`

such that `less_A()(x,y)`

iff type(`x`

) <_{T} type(`y`

). Given a fixed `Ai`

we define the predicate `less_Ai`

by `less_Ai()(x,y)`

= `less_A()(x,y)`

if either `x`

or `y`

is not of type `Ai`

or derived, `false`

otherwise. Technically speaking, `less_Ai`

is not a swo extension of `less_A`

because ranges coincide, but it can be shown to be equivalent in all respects to a true swo extension (replace the left and right arguments by some set isomorphic to the original but different to it). In practical terms, the existence of this swo extension shows that we can binary search for all objects derived from some fixed type `Ai`

if the objects are sorted according to a preorder traversal of their type hierarchy. This is obvious once we observe that preorder traversals "pack" elements belonging to the same hierarchy subtree, i.e. they render them adjacently. This property of preorder traversals with respect to single inheritance hierarchies is used in some languages for implementing efficient dispatch algorithms.

## No comments :

## Post a Comment