source/coresort.cc

   1 /* This file is part of Shapes.
   2  *
   3  * Shapes is free software: you can redistribute it and/or modify
   4  * it under the terms of the GNU General Public License as published by
   5  * the Free Software Foundation, either version 3 of the License, or
   6  * any later version.
   7  *
   8  * Shapes is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public License
  14  * along with Shapes.  If not, see <http://www.gnu.org/licenses/>.
  15  *
  16  * Copyright 2014 Henrik Tidefelt
  17  */
  18
  19 #include <cmath>
  20
  21 #include "shapescore.h"
  22 #include "globals.h"
  23 #include "shapesexceptions.h"
  24 #include "astfun.h"
  25 #include "continuations.h"
  26
  27 #include <vector>
  28
  29 using namespace Shapes;
  30
  31
  32 namespace Shapes
  33 {
  34   namespace Kernel
  35   {
  36
  37     class Core_leiographicSort_cont_values : public Kernel::Continuation
  38     {
  39       RefCountPtr< const Lang::SingleList > keys_;
  40       const Ast::SourceLocation & keysLoc_;
  41       Kernel::ContRef cont_;
  42     public:
  43       Core_leiographicSort_cont_values( RefCountPtr< const Lang::SingleList > keys, const Ast::SourceLocation & keysLoc, const Kernel::ContRef & cont, const Ast::SourceLocation & valuesLoc )
  44       : Kernel::Continuation( valuesLoc ), keys_( keys ), keysLoc_( keysLoc ), cont_( cont )
  45       { }
  46       virtual ~Core_leiographicSort_cont_values( ) { }
  47       virtual void takeValue( const RefCountPtr< const Lang::Value > & keysUntyped, Kernel::EvalState * evalState, bool dummy ) const;
  48       virtual Kernel::ContRef up( ) const
  49       {
  50         return cont_;
  51       }
  52       virtual RefCountPtr< const char > description( ) const
  53       {
  54         return strrefdup( "force list of values associated with keys to be sorted" );
  55       }
  56       virtual void gcMark( Kernel::GCMarkedSet & marked )
  57       {
  58         const_cast< Lang::SingleList * >( keys_.getPtr( ) )->gcMark( marked );
  59         cont_->gcMark( marked );
  60       }
  61     };
  62
  63     class Core_leiographicSort_cont_keys : public Kernel::Continuation
  64     {
  65       RefCountPtr< const Lang::Value > values_;
  66       const Ast::SourceLocation & valuesLoc_;
  67       Kernel::ContRef cont_;
  68     public:
  69       Core_leiographicSort_cont_keys( RefCountPtr< const Lang::Value > values, const Ast::SourceLocation & valuesLoc, const Kernel::ContRef & cont, const Ast::SourceLocation & keysLoc )
  70       : Kernel::Continuation( keysLoc ), values_( values ), valuesLoc_( valuesLoc ), cont_( cont )
  71       { }
  72       virtual ~Core_leiographicSort_cont_keys( ) { }
  73       virtual void takeValue( const RefCountPtr< const Lang::Value > & keysUntyped, Kernel::EvalState * evalState, bool dummy ) const;
  74       virtual Kernel::ContRef up( ) const
  75       {
  76         return cont_;
  77       }
  78       virtual RefCountPtr< const char > description( ) const
  79       {
  80         return strrefdup( "force list of keys to be sorted" );
  81       }
  82       virtual void gcMark( Kernel::GCMarkedSet & marked )
  83       {
  84         const_cast< Lang::Value * >( values_.getPtr( ) )->gcMark( marked );
  85         cont_->gcMark( marked );
  86       }
  87     };
  88
  89     class Core_mergeSort_cont_sort: public Kernel::Continuation
  90     {
  91       bool reversed_;
  92       RefCountPtr< const Lang::Function > precedes_;
  93       const Ast::SourceLocation & precedesLoc_;
  94       Kernel::PassedDyn dyn_;
  95       Kernel::ContRef cont_;
  96     public:
  97       Core_mergeSort_cont_sort( bool reversed, RefCountPtr< const Lang::Function > precedes, const Ast::SourceLocation & precedesLoc, const Kernel::PassedDyn & dyn, const Kernel::ContRef & cont, const Ast::SourceLocation & callLoc )
  98       : Kernel::Continuation( callLoc ), reversed_( reversed ), precedes_( precedes ), precedesLoc_( precedesLoc ), dyn_( dyn ), cont_( cont )
  99       { }
 100       virtual ~Core_mergeSort_cont_sort( ) { }
 101       virtual void takeValue( const RefCountPtr< const Lang::Value > & valuesUntyped, Kernel::EvalState * evalState, bool dummy ) const;
 102       virtual Kernel::ContRef up( ) const
 103       {
 104         return cont_;
 105       }
 106       virtual RefCountPtr< const char > description( ) const
 107       {
 108         return strrefdup( "mergesort split in two, and sort first part" );
 109       }
 110       virtual void gcMark( Kernel::GCMarkedSet & marked )
 111       {
 112         const_cast< Lang::Function * >( precedes_.getPtr( ) )->gcMark( marked );
 113         dyn_->gcMark( marked );
 114         cont_->gcMark( marked );
 115       }
 116     };
 117
 118     class Core_mergeSort_cont_sortSecond: public Kernel::Continuation
 119     {
 120       bool reversed_;
 121       RefCountPtr< const Lang::Function > precedes_;
 122       const Ast::SourceLocation & precedesLoc_;
 123       RefCountPtr< const Lang::SingleListPair > secondUnsorted_;
 124       Kernel::PassedDyn dyn_;
 125       Kernel::ContRef cont_;
 126     public:
 127       Core_mergeSort_cont_sortSecond( bool reversed, RefCountPtr< const Lang::Function > precedes, const Ast::SourceLocation & precedesLoc, const RefCountPtr< const Lang::SingleListPair > & secondUnsorted, const Kernel::PassedDyn & dyn, const Kernel::ContRef & cont, const Ast::SourceLocation & callLoc )
 128       : Kernel::Continuation( callLoc ), reversed_( reversed ), precedes_( precedes ), precedesLoc_( precedesLoc ), secondUnsorted_( secondUnsorted ), dyn_( dyn ), cont_( cont )
 129       { }
 130       virtual ~Core_mergeSort_cont_sortSecond( ) { }
 131       virtual void takeValue( const RefCountPtr< const Lang::Value > & valUntyped, Kernel::EvalState * evalState, bool dummy ) const;
 132       virtual Kernel::ContRef up( ) const
 133       {
 134         return cont_;
 135       }
 136       virtual RefCountPtr< const char > description( ) const
 137       {
 138         return strrefdup( "mergesort sort second part" );
 139       }
 140       virtual void gcMark( Kernel::GCMarkedSet & marked )
 141       {
 142         const_cast< Lang::Function * >( precedes_.getPtr( ) )->gcMark( marked );
 143         const_cast< Lang::SingleListPair * >( secondUnsorted_.getPtr( ) )->gcMark( marked );
 144         dyn_->gcMark( marked );
 145         cont_->gcMark( marked );
 146       }
 147     };
 148
 149     class Core_mergeSort_cont_merge: public Kernel::Continuation
 150     {
 151       bool reversed_;
 152       RefCountPtr< const Lang::Function > precedes_;
 153       const Ast::SourceLocation & precedesLoc_;
 154       RefCountPtr< const Lang::SingleListPair > firstSorted_;
 155       Kernel::PassedDyn dyn_;
 156       Kernel::ContRef cont_;
 157     public:
 158       Core_mergeSort_cont_merge( bool reversed, RefCountPtr< const Lang::Function > precedes, const Ast::SourceLocation & precedesLoc, const RefCountPtr< const Lang::SingleListPair > & firstSorted, const Kernel::PassedDyn & dyn, const Kernel::ContRef & cont, const Ast::SourceLocation & callLoc )
 159       : Kernel::Continuation( callLoc ), reversed_( reversed ), precedes_( precedes ), precedesLoc_( precedesLoc ), firstSorted_( firstSorted ), dyn_( dyn ), cont_( cont )
 160       { }
 161       virtual ~Core_mergeSort_cont_merge( ) { }
 162       virtual void takeValue( const RefCountPtr< const Lang::Value > & valUntyped, Kernel::EvalState * evalState, bool dummy ) const;
 163       virtual Kernel::ContRef up( ) const
 164       {
 165         return cont_;
 166       }
 167       virtual RefCountPtr< const char > description( ) const
 168       {
 169         return strrefdup( "mergesort merge" );
 170       }
 171       virtual void gcMark( Kernel::GCMarkedSet & marked )
 172       {
 173         const_cast< Lang::Function * >( precedes_.getPtr( ) )->gcMark( marked );
 174         const_cast< Lang::SingleListPair * >( firstSorted_.getPtr( ) )->gcMark( marked );
 175         dyn_->gcMark( marked );
 176         cont_->gcMark( marked );
 177       }
 178     };
 179
 180     class Core_mergeSort_cont_mergeShortcut: public Kernel::Continuation
 181     {
 182       bool reversed_;
 183       RefCountPtr< const Lang::Function > precedes_;
 184       const Ast::SourceLocation & precedesLoc_;
 185       RefCountPtr< const Lang::SingleListPair > firstSorted_;
 186       RefCountPtr< const Lang::SingleListPair > secondSorted_;
 187       Kernel::PassedDyn dyn_;
 188       Kernel::ContRef cont_;
 189       const Ast::SourceLocation & callLoc_;
 190     public:
 191       Core_mergeSort_cont_mergeShortcut( bool reversed, RefCountPtr< const Lang::Function > precedes, const Ast::SourceLocation & precedesLoc, const RefCountPtr< const Lang::SingleListPair > & firstSorted, const RefCountPtr< const Lang::SingleListPair > & secondSorted, const Kernel::PassedDyn & dyn, const Kernel::ContRef & cont, const Ast::SourceLocation & callbackLoc, const Ast::SourceLocation & callLoc )
 192       : Kernel::Continuation( callbackLoc ), reversed_( reversed ), precedes_( precedes ), precedesLoc_( precedesLoc ), firstSorted_( firstSorted ), secondSorted_( secondSorted ), dyn_( dyn ), cont_( cont ), callLoc_( callLoc )
 193       { }
 194       virtual ~Core_mergeSort_cont_mergeShortcut( ) { }
 195       virtual void takeValue( const RefCountPtr< const Lang::Value > & secondSortedUntyped, Kernel::EvalState * evalState, bool dummy ) const;
 196       virtual Kernel::ContRef up( ) const
 197       {
 198         return cont_;
 199       }
 200       virtual RefCountPtr< const char > description( ) const
 201       {
 202         return strrefdup( "mergesort merge possibly shortcut" );
 203       }
 204       virtual void gcMark( Kernel::GCMarkedSet & marked )
 205       {
 206         const_cast< Lang::Function * >( precedes_.getPtr( ) )->gcMark( marked );
 207         const_cast< Lang::SingleListPair * >( firstSorted_.getPtr( ) )->gcMark( marked );
 208         const_cast< Lang::SingleListPair * >( secondSorted_.getPtr( ) )->gcMark( marked );
 209         dyn_->gcMark( marked );
 210         cont_->gcMark( marked );
 211       }
 212     };
 213
 214     class Core_mergeSort_cont_mergeStep: public Kernel::Continuation
 215     {
 216       bool reversed_;
 217       bool firstAtStart_;
 218       RefCountPtr< const Lang::Function > precedes_;
 219       const Ast::SourceLocation & precedesLoc_;
 220       RefCountPtr< const Lang::SingleListPair > first_;
 221       RefCountPtr< const Lang::SingleListPair > second_;
 222       RefCountPtr< const Lang::SingleList > reverseResult_;
 223       Kernel::VariableHandle lastInResult_;
 224       Kernel::PassedDyn dyn_;
 225       Kernel::ContRef cont_;
 226       const Ast::SourceLocation & callLoc_;
 227     public:
 228       Core_mergeSort_cont_mergeStep( bool reversed, RefCountPtr< const Lang::Function > precedes, const Ast::SourceLocation & precedesLoc, const RefCountPtr< const Lang::SingleListPair > & first, const RefCountPtr< const Lang::SingleListPair > & second, bool firstAtStart, const RefCountPtr< const Lang::SingleList > & reverseResult, const Kernel::VariableHandle & lastInResult, const Kernel::PassedDyn & dyn, const Kernel::ContRef & cont, const Ast::SourceLocation & callbackLoc, const Ast::SourceLocation & callLoc )
 229       : Kernel::Continuation( callbackLoc ), reversed_( reversed ), firstAtStart_( firstAtStart ), precedes_( precedes ), precedesLoc_( precedesLoc ), first_( first ), second_( second ), reverseResult_( reverseResult ), lastInResult_( lastInResult ), dyn_( dyn ), cont_( cont ), callLoc_( callLoc )
 230       { }
 231       virtual ~Core_mergeSort_cont_mergeStep( ) { }
 232       virtual void takeValue( const RefCountPtr< const Lang::Value > & precedesResUntyped, Kernel::EvalState * evalState, bool dummy ) const;
 233       virtual Kernel::ContRef up( ) const
 234       {
 235         return cont_;
 236       }
 237       virtual RefCountPtr< const char > description( ) const
 238       {
 239         return strrefdup( "mergesort merge step" );
 240       }
 241       virtual void gcMark( Kernel::GCMarkedSet & marked )
 242       {
 243         const_cast< Lang::Function * >( precedes_.getPtr( ) )->gcMark( marked );
 244         const_cast< Lang::SingleListPair * >( first_.getPtr( ) )->gcMark( marked );
 245         const_cast< Lang::SingleListPair * >( second_.getPtr( ) )->gcMark( marked );
 246         const_cast< Lang::SingleList * >( reverseResult_.getPtr( ) )->gcMark( marked );
 247         dyn_->gcMark( marked );
 248         cont_->gcMark( marked );
 249       }
 250       static void callback( bool reversed, RefCountPtr< const Lang::Function > precedes, const Ast::SourceLocation & precedesLoc, const RefCountPtr< const Lang::SingleListPair > & first, const RefCountPtr< const Lang::SingleListPair > & second, bool firstAtStart, RefCountPtr< const Lang::SingleList > reverseResult, const Kernel::VariableHandle & lastInResult, const Kernel::PassedDyn & dyn, const Kernel::ContRef & cont, const Ast::SourceLocation & callLoc, Kernel::EvalState * evalState );
 251     };
 252
 253     class Core_mergeSort_cont_finish: public Kernel::Continuation
 254     {
 255       Kernel::ContRef cont_;
 256     public:
 257       Core_mergeSort_cont_finish( const Kernel::ContRef & cont, const Ast::SourceLocation & callLoc )
 258       : Kernel::Continuation( callLoc ), cont_( cont )
 259       { }
 260       virtual ~Core_mergeSort_cont_finish( ) { }
 261       virtual void takeValue( const RefCountPtr< const Lang::Value > & valuesSortedUntyped, Kernel::EvalState * evalState, bool dummy ) const;
 262       virtual Kernel::ContRef up( ) const
 263       {
 264         return cont_;
 265       }
 266       virtual RefCountPtr< const char > description( ) const
 267       {
 268         return strrefdup( "mergesort finish" );
 269       }
 270       virtual void gcMark( Kernel::GCMarkedSet & marked )
 271       {
 272         cont_->gcMark( marked );
 273       }
 274     };
 275
 276   }
 277
 278   namespace Lang
 279   {
 280
 281     class Core_lexiographicSort : public Lang::CoreFunction
 282     {
 283     public:
 284       Core_lexiographicSort( const RefCountPtr< const Ast::NamespacePath > & ns, const char * name )
 285         : CoreFunction( ns, name, new Kernel::EvaluatedFormals( Ast::FileID::build_internal( name ), true ) )
 286       {
 287         formals_->appendEvaluatedCoreFormal( "keys", Kernel::THE_SLOT_VARIABLE );
 288         formals_->appendEvaluatedCoreFormal( "values", Kernel::THE_VOID_VARIABLE );
 289       }
 290
 291       virtual void
 292       call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
 293       {
 294         args.applyDefaults( callLoc );
 295
 296         size_t argsi = 0;
 297         size_t keysi = argsi;
 298         RefCountPtr< const Lang::Value > keys = args.getValue( keysi );
 299
 300         ++argsi;
 301         size_t valuesi = argsi;
 302         RefCountPtr< const Lang::Value > values = args.getValue( valuesi );
 303
 304         Kernel::ContRef cont = Kernel::ContRef
 305           ( new Kernel::ForcingListContinuation
 306             ( Kernel::ContRef( new Kernel::Core_leiographicSort_cont_keys
 307                                 ( values, args.getLoc( valuesi ), evalState->cont_, args.getLoc( keysi ) ) ),
 308               args.getLoc( keysi ),
 309               false /* don't force structures */,
 310               true /* consify */) );
 311         evalState->cont_ = cont;
 312         cont->takeValue( keys, evalState );
 313       }
 314
 315       template< class T >
 316       static RefCountPtr< const Lang::SingleList > sortTyped( const RefCountPtr< const Lang::SingleList > & keys, const Ast::SourceLocation & keysLoc, const RefCountPtr< const Lang::SingleList > & values, const Ast::SourceLocation & valuesLoc );
 317       static RefCountPtr< const Lang::SingleList > sort( const RefCountPtr< const Lang::SingleList > & keys, const Ast::SourceLocation & keysLoc, const RefCountPtr< const Lang::SingleList > & values, const Ast::SourceLocation & valuesLoc );
 318     };
 319
 320     class Core_mergeSort : public Lang::CoreFunction
 321     {
 322     public:
 323       Core_mergeSort( const RefCountPtr< const Ast::NamespacePath > & ns, const char * name )
 324         : CoreFunction( ns, name, new Kernel::EvaluatedFormals( Ast::FileID::build_internal( name ), true ) )
 325       {
 326         formals_->appendEvaluatedCoreFormal( "values", Kernel::THE_SLOT_VARIABLE );
 327         formals_->appendEvaluatedCoreFormal( "precedes?", Kernel::THE_SLOT_VARIABLE );
 328       }
 329
 330       virtual void
 331       call( Kernel::EvalState * evalState, Kernel::Arguments & args, const Ast::SourceLocation & callLoc ) const
 332       {
 333         args.applyDefaults( callLoc );
 334
 335         size_t argsi = 0;
 336         size_t valuesi = argsi;
 337         RefCountPtr< const Lang::Value > values = args.getValue( valuesi );
 338
 339         ++argsi;
 340         size_t precedesi = argsi;
 341         typedef const Lang::Function PredType;
 342         RefCountPtr< PredType > precedes = Helpers::down_cast_CoreArgument< PredType >( id_, args, argsi, callLoc );
 343
 344         Kernel::ContRef finishCont = Kernel::ContRef( new Kernel::Core_mergeSort_cont_finish( evalState->cont_, callLoc ) );
 345
 346         Kernel::ContRef cont = Kernel::ContRef
 347           ( new Kernel::ForcingListContinuation
 348             ( Kernel::ContRef( new Kernel::Core_mergeSort_cont_sort( true, precedes, args.getLoc( precedesi ), evalState->dyn_, finishCont, callLoc ) ),
 349               args.getLoc( valuesi ),
 350               false /* don't sort structures */,
 351               true /* consify */ ) );
 352         evalState->cont_ = cont;
 353         cont->takeValue( values, evalState );
 354       }
 355     };
 356
 357   }
 358 }
 359
 360
 361 void
 362 Kernel::Core_leiographicSort_cont_values::takeValue( const RefCountPtr< const Lang::Value > & keysUntyped, Kernel::EvalState * evalState, bool dummy ) const
 363 {
 364   typedef const Lang::SingleList ArgType;
 365   RefCountPtr< ArgType > values = Helpers::down_cast< ArgType >( keysUntyped, "< Internal error situation in Core_leiographicSort_cont_values >" );
 366
 367   RefCountPtr< const Lang::SingleList > res = Lang::Core_lexiographicSort::sort( keys_, keysLoc_, values, traceLoc_ );
 368   evalState->cont_ = cont_;
 369   cont_->takeValue( res, evalState );
 370 }
 371
 372 void
 373 Kernel::Core_leiographicSort_cont_keys::takeValue( const RefCountPtr< const Lang::Value > & keysUntyped, Kernel::EvalState * evalState, bool dummy ) const
 374 {
 375   typedef const Lang::SingleList ArgType;
 376   RefCountPtr< ArgType > keys = Helpers::down_cast< ArgType >( keysUntyped, "< Internal error situation in Core_leiographicSort_cont_keys >" );
 377
 378   if( values_ == Lang::THE_VOID ){
 379
 380     RefCountPtr< const Lang::SingleList > res = Lang::Core_lexiographicSort::sort( keys, traceLoc_, keys, traceLoc_ );
 381     evalState->cont_ = cont_;
 382     cont_->takeValue( res, evalState );
 383     return;
 384
 385   }else{
 386
 387     Kernel::ContRef cont = Kernel::ContRef
 388       ( new Kernel::ForcingListContinuation
 389         ( Kernel::ContRef( new Kernel::Core_leiographicSort_cont_values( keys, traceLoc_, cont_, valuesLoc_ ) ),
 390           valuesLoc_,
 391           false /* don't force structures */,
 392           true /* consify */ ) );
 393     evalState->cont_ = cont;
 394     cont->takeValue( values_, evalState );
 395
 396   }
 397 }
 398
 399 namespace Shapes
 400 {
 401   namespace Lang
 402   {
 403
 404     template< class T >
 405     struct ElementarySortItem
 406     {
 407       std::vector< T > key_;
 408       RefCountPtr< const Lang::Value > val_;
 409
 410       ElementarySortItem( const RefCountPtr< const Lang::Value > & val, size_t keySize )
 411       : val_( val )
 412       {
 413         key_.reserve( keySize );
 414       }
 415     };
 416
 417     template< class T >
 418     class ElementarySortItemLess
 419     {
 420     public:
 421       bool operator () ( const ElementarySortItem< T > * x, const ElementarySortItem< T > * y ) const
 422       {
 423         typedef typeof x->key_ VecType;
 424         typename VecType::const_iterator i = x->key_.begin( );
 425         typename VecType::const_iterator xEnd = x->key_.end( );
 426         typename VecType::const_iterator j = y->key_.begin( );
 427         typename VecType::const_iterator yEnd = y->key_.end( );
 428         for( ; i != xEnd && j != yEnd; ++i, ++j ){
 429           if( *i < *j )
 430             return true;
 431           if( *i > *j )
 432             return false;
 433         }
 434         return j != yEnd;
 435       }
 436     };
 437
 438     template< class T >
 439     RefCountPtr< const Lang::SingleList >
 440     Lang::Core_lexiographicSort::sortTyped( const RefCountPtr< const Lang::SingleList > & keys, const Ast::SourceLocation & keysLoc, const RefCountPtr< const Lang::SingleList > & values, const Ast::SourceLocation & valuesLoc )
 441     {
 442       typedef T KeySymbolType;
 443       typedef ElementarySortItem< typename KeySymbolType::ValueType > SortItem;
 444
 445       /* Initialize items to be sorted.
 446        */
 447       PtrOwner_back_Access< std::list< ElementarySortItem< typename KeySymbolType::ValueType > * > > itemsMem;
 448
 449       RefCountPtr< const Lang::SingleListPair > k = keys.down_cast< const Lang::SingleListPair >( );
 450       RefCountPtr< const Lang::SingleListPair > v = values.down_cast< const Lang::SingleListPair >( );
 451       while( k != NullPtr< const Lang::SingleListPair >( ) ){
 452         if( v == NullPtr< const Lang::SingleListPair >( ) ){
 453           throw Exceptions::MiscellaneousRequirement( valuesLoc, "Values cannot be associated with keys since the number of elements differ." );
 454         }
 455         RefCountPtr< const Lang::VectorFunction > kvec = k->car_->getVal< const Lang::VectorFunction >( "Element in list of keys to be sorted." );
 456         RefCountPtr< const Lang::VectorFunction::vector_type > kmem = kvec->mem( );
 457         SortItem * item = new SortItem( v->car_->getUntyped( ), kmem->size( ) );
 458         itemsMem.push_back( item );
 459         typedef typeof *kmem VecType;
 460         for( typename VecType::const_iterator i = kmem->begin( ); i != kmem->end( ); ++i ){
 461           const KeySymbolType * sym = dynamic_cast< const KeySymbolType * >( i->getPtr( ) );
 462           if( sym == NULL ){
 463             throw Exceptions::TypeMismatch( keysLoc, "(element of key to be sorted, expected all to be of same type)", (*i)->getTypeName( ), KeySymbolType::staticTypeName( ) );
 464           }
 465           item->key_.push_back( sym->val_ );
 466         }
 467         k = k->cdr_.down_cast< const Lang::SingleListPair >( );
 468         v = v->cdr_.down_cast< const Lang::SingleListPair >( );
 469       }
 470       if( v != NullPtr< const Lang::SingleListPair >( ) ){
 471         throw Exceptions::MiscellaneousRequirement( valuesLoc, "Values cannot be associated with keys since the number of elements differ." );
 472       }
 473
 474       /* Place items in vector and sort.
 475        */
 476       std::vector< SortItem * > items;
 477       items.reserve( itemsMem.size( ) );
 478       {
 479         typedef typeof itemsMem ListType;
 480         for( typename ListType::const_iterator i = itemsMem.begin( ); i != itemsMem.end( ); ++i ){
 481           items.push_back( *i );
 482         }
 483       }
 484       std::stable_sort( items.begin( ), items.end( ), ElementarySortItemLess< typename KeySymbolType::ValueType >( ) );
 485
 486       /* Construct result.
 487        */
 488       RefCountPtr< const Lang::SingleList > result = Lang::THE_CONS_NULL;
 489       {
 490         typedef typeof items VecType;
 491         for( typename VecType::const_reverse_iterator i = items.rbegin( ); i != items.rend( ); ++i ){
 492           result = Helpers::SingleList_cons( (*i)->val_, result );
 493         }
 494       }
 495
 496       return result;
 497     }
 498
 499   }
 500 }
 501
 502
 503 RefCountPtr< const Lang::SingleList >
 504 Lang::Core_lexiographicSort::sort( const RefCountPtr< const Lang::SingleList > & keys, const Ast::SourceLocation & keysLoc, const RefCountPtr< const Lang::SingleList > & values, const Ast::SourceLocation & valuesLoc )
 505 {
 506   /* Currently, all keys must be of type Lang::VectorFunction, and we just need to find one
 507    * non-empty key in order to find the vector element type.
 508    */
 509   RefCountPtr< const Lang::Value > firstSymbol = RefCountPtr< const Lang::Value >( NullPtr< const Lang::Value >( ) );
 510
 511   {
 512     size_t count = 0;
 513     RefCountPtr< const Lang::SingleListPair > k = keys.down_cast< const Lang::SingleListPair >( );
 514     while( k != NullPtr< const Lang::SingleListPair >( ) ){
 515       ++count;
 516       RefCountPtr< const Lang::VectorFunction > kvec = k->car_->getVal< const Lang::VectorFunction >( "Element in list of keys to be sorted." );
 517       RefCountPtr< const Lang::VectorFunction::vector_type > kmem = kvec->mem( );
 518       if( kmem->empty( ) ){
 519         k = k->cdr_.down_cast< const Lang::SingleListPair >( );
 520         continue;
 521       }
 522       firstSymbol = kmem->front( );
 523       break;
 524     }
 525
 526     if( k == NullPtr< const Lang::SingleListPair >( ) ){
 527       /* All keys were empty, hence already in order.  We just need to check that the number of values match the number of keys. */
 528       RefCountPtr< const Lang::SingleListPair > v = values.down_cast< const Lang::SingleListPair >( );
 529       while( v != NullPtr< const Lang::SingleListPair >( ) ){
 530         if( count == 0){
 531           throw Exceptions::MiscellaneousRequirement( valuesLoc, "Values cannot be associated with keys since the number of elements differ." );
 532         }
 533         --count;
 534         v = v->cdr_.down_cast< const Lang::SingleListPair >( );
 535       }
 536       if( count != 0 ){
 537         throw Exceptions::MiscellaneousRequirement( valuesLoc, "Values cannot be associated with keys since the number of elements differ." );
 538       }
 539       return values;
 540     }
 541   }
 542
 543   /* Dispatch based on the type of vector elements. */
 544   {
 545     typedef Lang::Integer KeySymbolType;
 546     if( dynamic_cast< const KeySymbolType * >( firstSymbol.getPtr( ) ) != NULL )
 547       return sortTyped< KeySymbolType >( keys, keysLoc, values, valuesLoc );
 548   }
 549   {
 550     typedef Lang::Float KeySymbolType;
 551     if( dynamic_cast< const KeySymbolType * >( firstSymbol.getPtr( ) ) != NULL )
 552       return sortTyped< KeySymbolType >( keys, keysLoc, values, valuesLoc );
 553   }
 554
 555   throw Exceptions::TypeMismatch( keysLoc, "(element of key to be sorted)", firstSymbol->getTypeName( ), Helpers::typeSetString( Lang::Integer::staticTypeName( ), Lang::Float::staticTypeName( ) ) );
 556 }
 557
 558
 559 void
 560 Kernel::Core_mergeSort_cont_sort::takeValue( const RefCountPtr< const Lang::Value > & valuesUntyped, Kernel::EvalState * evalState, bool dummy ) const
 561 {
 562   typedef const Lang::SingleList ArgType;
 563   RefCountPtr< ArgType > valuesMaybeNil = Helpers::down_cast< ArgType >( valuesUntyped, "< Internal error situation in Core_mergeSort_cont_sort >" );
 564
 565   RefCountPtr< const Lang::SingleListPair > values = valuesMaybeNil.down_cast< const Lang::SingleListPair >( );
 566   if( values == NullPtr< const Lang::SingleListPair >( ) ){
 567     /* Special case of empty input, never happens during recursion.
 568      */
 569     evalState->cont_ = cont_;
 570     /* The Kernel::THE_VOID_VARIABLE is just a dummy below.  It will just be discared by the receiving continuation. */
 571     cont_->takeValue( RefCountPtr< const Lang::SingleList >( new Lang::SingleListPair( Kernel::THE_VOID_VARIABLE, Lang::THE_CONS_NULL ) ),
 572                       evalState );
 573     return;
 574   }
 575
 576   /* Split in half, with each part reversed. */
 577   RefCountPtr< const Lang::SingleListPair > p = values.down_cast< const Lang::SingleListPair >( );
 578   RefCountPtr< const Lang::SingleListPair > q = p;
 579   std::stack< Kernel::VariableHandle > leftReversed;
 580   while( q != NullPtr< const Lang::SingleListPair >( ) ){
 581     leftReversed.push( p->car_ );
 582     p = p->cdr_.down_cast< const Lang::SingleListPair >( );
 583     q = q->cdr_.down_cast< const Lang::SingleListPair >( );
 584     if( q == NullPtr< const Lang::SingleListPair >( ) )
 585       break;
 586     q = q->cdr_.down_cast< const Lang::SingleListPair >( );
 587   }
 588   if( p == NullPtr< const Lang::SingleListPair >( ) ){
 589     /* There was just a single element.
 590      * First and only element is at the same time the last element of the sorted sequence.
 591      */
 592     evalState->cont_ = cont_;
 593     cont_->takeValue( RefCountPtr< const Lang::SingleList >( new Lang::SingleListPair( values->car_, values ) ),
 594                       evalState );
 595     return;
 596   }
 597
 598   /* There's at least one element in each part.
 599    */
 600   RefCountPtr< const Lang::SingleListPair > left =
 601     RefCountPtr< const Lang::SingleListPair >( new Lang::SingleListPair( leftReversed.top( ), Lang::THE_CONS_NULL ) );
 602   leftReversed.pop( );
 603   while( ! leftReversed.empty( ) ){
 604     left = RefCountPtr< const Lang::SingleListPair >( new Lang::SingleListPair( leftReversed.top( ), left ) );
 605     leftReversed.pop( );
 606   }
 607   RefCountPtr< const Lang::SingleListPair > right = p.down_cast< const Lang::SingleListPair >( );
 608
 609   /* Now is the time to decide in which order to sort the left and right parts.  The goal is to be able to
 610    * shortcut the merge if values are sorted from the beginning.
 611    * The part sorted first will have only one end value available, while the part sorted second, just before
 612    * the merge begins, will have both first and last values available.  The order will depend on whether the merge
 613    * proceeds with values in increasing order or decreasing order.
 614    *
 615    * Decreasing order (reversed_):
 616    * Consider the input { 1 2 3 4 5 6 }.  It will be split and after sorting we will have the left part sorted as ( 3 ; 2 ; 1 )
 617    * and the right part sorted as ( 6 ; 5 ; 4 ).  The values that need to be compared are 3 and 4 (4 < 3 would mean that the merge
 618    * cannot be shortcut).  Since 4 is at the and of the sorted right part, this must be the second part to be sorted.
 619    * First: left, ( 3 ; 2 ; 1 ).  Second: right, ( 6 ; 5 ; 4 ).
 620    *
 621    * Increasing order (not reversed_):
 622    * Consider the input { 1 2 3 4 5 6 }.  It will be split and after sorting we will have the left part sorted as ( 1 ; 2 ; 3 )
 623    * and the right part sorted as ( 4 ; 5 ; 6 ).  The values that need to be compared are 3 and 4 (4 < 3 would mean that the merge
 624    * cannot be shortcut).  Since 3 is at the and of the sorted left part, this must be the second part to be sorted.
 625    * First: right, ( 4 ; 5 ; 6 ).  Second: left, ( 1 ; 2 ; 3 ).
 626    */
 627   if( reversed_ ){
 628     RefCountPtr< const Lang::SingleListPair > tmp = right;
 629     right = left;
 630     left = tmp;
 631   }
 632
 633   /* Initiate sorting of first part.
 634    */
 635   Kernel::ContRef cont = Kernel::ContRef
 636     ( new Kernel::Core_mergeSort_cont_sort
 637       ( ! reversed_, precedes_, precedesLoc_, dyn_,
 638         Kernel::ContRef( new Kernel::Core_mergeSort_cont_sortSecond( reversed_, precedes_, precedesLoc_, left, dyn_, cont_, traceLoc_ ) ),
 639         traceLoc_ ) );
 640   evalState->cont_ = cont;
 641   cont->takeValue( right, evalState );
 642 }
 643
 644 void
 645 Kernel::Core_mergeSort_cont_sortSecond::takeValue( const RefCountPtr< const Lang::Value > & valUntyped, Kernel::EvalState * evalState, bool dummy ) const
 646 {
 647   /* The value received by this continuation shall be a SingleListPair where
 648    *   cdr_ is the sorted first part, reversed
 649    *   car_ is the last element in the cdr_ sequence
 650    */
 651   typedef const Lang::SingleListPair ArgType;
 652   RefCountPtr< ArgType > val = Helpers::down_cast< ArgType >( valUntyped, "< Internal error situation in Core_mergeSort_cont_sortSecond::takeValue >" );
 653
 654   RefCountPtr< ArgType > firstSorted = Helpers::down_cast< ArgType >( val->cdr_, "< Internal error situation in Core_mergeSort_cont_sortSecond::takeValue >" );
 655
 656   /* Initiate sorting of second part.
 657    */
 658   Kernel::ContRef cont = Kernel::ContRef
 659     ( new Kernel::Core_mergeSort_cont_sort
 660       ( ! reversed_, precedes_, precedesLoc_, dyn_,
 661         Kernel::ContRef( new Kernel::Core_mergeSort_cont_merge
 662                           ( reversed_, precedes_, precedesLoc_, firstSorted, dyn_, cont_, traceLoc_ ) ),
 663         traceLoc_ ) );
 664   evalState->cont_ = cont;
 665   cont->takeValue( secondUnsorted_, evalState );
 666 }
 667
 668 void
 669 Kernel::Core_mergeSort_cont_merge::takeValue( const RefCountPtr< const Lang::Value > & valUntyped, Kernel::EvalState * evalState, bool dummy ) const
 670 {
 671   /* The value received by this continuation shall be a SingleListPair where
 672    *   cdr_ is the sorted second part, reversed
 673    *   car_ is the last element in the cdr_ sequence
 674    */
 675   typedef const Lang::SingleListPair ArgType;
 676   RefCountPtr< ArgType > val = Helpers::down_cast< ArgType >( valUntyped, "< Internal error situation in Core_mergeSort_cont_merge::takeValue >" );
 677
 678   RefCountPtr< ArgType > secondSorted = Helpers::down_cast< ArgType >( val->cdr_, "< Internal error situation in Core_mergeSort_cont_merge::takeValue >" );
 679   Kernel::VariableHandle lastInSecond = val->car_;
 680
 681   static Ast::SourceLocation callbackLoc( Ast::FileID::build_internal( "< mergesort callback >" ) );
 682
 683   evalState->cont_ = Kernel::ContRef( new Kernel::Core_mergeSort_cont_mergeShortcut( reversed_, precedes_, precedesLoc_, firstSorted_, secondSorted, dyn_, cont_, callbackLoc, traceLoc_ ) );
 684   evalState->dyn_ = dyn_;
 685
 686   if( dynamic_cast< const Lang::UserFunction * >( precedes_.getPtr( ) ) == NULL ){
 687     /* Compare the use of RelaxContinuation in Core_mergeSort_cont_mergeStep::callback.
 688      */
 689     evalState->cont_ = Kernel::ContRef( new Kernel::RelaxContinuation( evalState->cont_ ) );
 690   }
 691
 692   if( reversed_ )
 693     precedes_->call( precedes_, evalState, lastInSecond, firstSorted_->car_, callbackLoc );
 694   else
 695     precedes_->call( precedes_, evalState, firstSorted_->car_, lastInSecond, callbackLoc );
 696 }
 697
 698 void
 699 Kernel::Core_mergeSort_cont_mergeShortcut::takeValue( const RefCountPtr< const Lang::Value > & precUntyped, Kernel::EvalState * evalState, bool dummy ) const
 700 {
 701   bool prec = Helpers::down_cast_ContinuationArgument< const Lang::Boolean >( precUntyped, this )->val_;
 702
 703   if( prec ){
 704
 705     /* First element in _second_ list precedes last element in _first_ list, cannot shortcut.
 706      * However, if both lists have only one element, we know how they shall be ordered.
 707      */
 708     if( dynamic_cast< const Lang::SingleListNull * >( firstSorted_->cdr_.getPtr( ) ) != NULL
 709         && dynamic_cast< const Lang::SingleListNull * >( secondSorted_->cdr_.getPtr( ) ) != NULL ){
 710       RefCountPtr< const Lang::SingleList > result = Lang::THE_CONS_NULL;
 711       result = RefCountPtr< const Lang::SingleList >( new Lang::SingleListPair( firstSorted_->car_, result ) );
 712       result = RefCountPtr< const Lang::SingleList >( new Lang::SingleListPair( secondSorted_->car_, result ) );
 713       evalState->cont_ = cont_;
 714       cont_->takeValue( RefCountPtr< const Lang::SingleList >( new Lang::SingleListPair( firstSorted_->car_, result ) ),
 715                         evalState );
 716       return;
 717     }else{
 718       Core_mergeSort_cont_mergeStep::callback( reversed_, precedes_, precedesLoc_, firstSorted_, secondSorted_, true,
 719                                                Lang::THE_CONS_NULL, Kernel::THE_SLOT_VARIABLE, dyn_, cont_, callLoc_,
 720                                                evalState );
 721       return;
 722     }
 723
 724   }else{
 725
 726     /* Otherwise, shortcut by just appending sequences in reverse and return. */
 727     RefCountPtr< const Lang::SingleListPair > p = secondSorted_;
 728     RefCountPtr< const Lang::SingleList > result = Lang::THE_CONS_NULL;
 729     Kernel::VariableHandle lastInResult = p->car_;
 730     while( p != NullPtr< const Lang::SingleListPair >( ) ){
 731       result = RefCountPtr< const Lang::SingleList >( new Lang::SingleListPair( p->car_, result ) );
 732       p = p->cdr_.down_cast< const Lang::SingleListPair >( );
 733     }
 734     p = firstSorted_;
 735     while( p != NullPtr< const Lang::SingleListPair >( ) ){
 736       result = RefCountPtr< const Lang::SingleList >( new Lang::SingleListPair( p->car_, result ) );
 737       p = p->cdr_.down_cast< const Lang::SingleListPair >( );
 738     }
 739     evalState->cont_ = cont_;
 740     cont_->takeValue( RefCountPtr< const Lang::SingleList >( new Lang::SingleListPair( lastInResult, result ) ),
 741                       evalState );
 742     return;
 743
 744   }
 745 }
 746
 747 void
 748 Kernel::Core_mergeSort_cont_mergeStep::callback( bool reversed, RefCountPtr< const Lang::Function > precedes, const Ast::SourceLocation & precedesLoc, const RefCountPtr< const Lang::SingleListPair > & first, const RefCountPtr< const Lang::SingleListPair > & second, bool firstAtStart, RefCountPtr< const Lang::SingleList > reverseResult, const Kernel::VariableHandle & lastInResult, const Kernel::PassedDyn & dyn, const Kernel::ContRef & cont, const Ast::SourceLocation & callLoc, Kernel::EvalState * evalState )
 749 {
 750   static Ast::SourceLocation callbackLoc( Ast::FileID::build_internal( "< mergesort callback >" ) );
 751
 752   if( firstAtStart && dynamic_cast< const Lang::SingleListNull * >( second->cdr_.getPtr( ) ) != NULL ){
 753     /* We would not get here if it would have been possible to shortcut the merge.
 754      * This means that the first element in the first list is next in turn.
 755      */
 756     reverseResult = RefCountPtr< const Lang::SingleListPair >( new Lang::SingleListPair( first->car_, reverseResult ) );
 757     RefCountPtr< const Lang::SingleListPair > rest = first->cdr_.down_cast< const Lang::SingleListPair >( );
 758
 759     if( rest == NullPtr< const Lang::SingleListPair >( ) ){
 760       /* Only one value in second remains. */
 761
 762       reverseResult = RefCountPtr< const Lang::SingleList >( new Lang::SingleListPair( second->car_, reverseResult ) );
 763       evalState->cont_ = cont;
 764       cont->takeValue( RefCountPtr< const Lang::SingleList >( new Lang::SingleListPair( lastInResult, reverseResult ) ),
 765                        evalState );
 766       return;
 767
 768     }else{
 769
 770       /* Continue merge. */
 771       Core_mergeSort_cont_mergeStep::callback( reversed, precedes, precedesLoc, rest, second, false, reverseResult, lastInResult, dyn, cont, callLoc,
 772                                                evalState );
 773       return;
 774
 775     }
 776
 777   }
 778
 779   evalState->cont_ = Kernel::ContRef( new Kernel::Core_mergeSort_cont_mergeStep( reversed, precedes, precedesLoc, first, second, firstAtStart, reverseResult, lastInResult, dyn, cont, callbackLoc, callLoc ) );
 780   evalState->dyn_ = dyn;
 781
 782   if( dynamic_cast< const Lang::UserFunction * >( precedes.getPtr( ) ) == NULL ){
 783     /* We are not sure that calling precedes will allow the evaluation call chain to unwind.
 784      * Relax after precedes has produced a result.
 785      * (We could do more elaborate testing here to determine more exactly when we need to relax
 786      * the evaluation, what we have now is just a rough approximation that is expected to catch
 787      * the most important cases.  We just have to be sure that we don't fail to relax the evaluation
 788      * when needed -- better safe than sorry.)
 789      */
 790     evalState->cont_ = Kernel::ContRef( new Kernel::RelaxContinuation( evalState->cont_ ) );
 791   }
 792
 793   /* Recall that the merge is constructing a reversed result.  That is, when in reversed mode, the resulting list is
 794    * actually increasing.  This means that we shall take the element from the right (!) part in case of a tie.
 795    * When not inreversed mode, it is the opposite since we are constructing a reversed result.
 796    *
 797    * Decreasing order (reversed):
 798    * First: left, ( 3 ; 2 ; 1 ).  Second: right, ( 6 ; 5 ; 4 ).
 799    * Thus, pick element from first only if 3 > 6, that is 6 < 3.
 800    *
 801    * Increasing order (not reversed):
 802    * First: right, ( 4 ; 5 ; 6 ).  Second: left, ( 1 ; 2 ; 3 ).
 803    * This, pick element from first only if 4 < 1.
 804    *
 805    * In both cases, the comparison is the same.
 806    */
 807   if( reversed )
 808     precedes->call( precedes, evalState, second->car_, first->car_, callbackLoc );
 809   else
 810     precedes->call( precedes, evalState, first->car_, second->car_, callbackLoc );
 811 }
 812
 813
 814 void
 815 Kernel::Core_mergeSort_cont_mergeStep::takeValue( const RefCountPtr< const Lang::Value > & precUntyped, Kernel::EvalState * evalState, bool dummy ) const
 816 {
 817   bool prec = Helpers::down_cast_ContinuationArgument< const Lang::Boolean >( precUntyped, this )->val_;
 818
 819   if( prec ){
 820
 821     /* Pick value from first.
 822      */
 823     RefCountPtr< const Lang::SingleListPair > reverseResult = RefCountPtr< const Lang::SingleListPair >( new Lang::SingleListPair( first_->car_, reverseResult_ ) );
 824     RefCountPtr< const Lang::SingleListPair > rest = first_->cdr_.down_cast< const Lang::SingleListPair >( );
 825
 826     Kernel::VariableHandle lastInResult = (lastInResult_ == Kernel::THE_SLOT_VARIABLE) ? first_->car_ : lastInResult_;
 827
 828     if( rest == NullPtr< const Lang::SingleListPair >( ) ){
 829       /* Only values in second remain. */
 830
 831       RefCountPtr< const Lang::SingleListPair > p = second_;
 832       while( p != NullPtr< const Lang::SingleListPair >( ) ){
 833         reverseResult = RefCountPtr< const Lang::SingleList >( new Lang::SingleListPair( p->car_, reverseResult ) );
 834         p = p->cdr_.down_cast< const Lang::SingleListPair >( );
 835       }
 836       evalState->cont_ = cont_;
 837       cont_->takeValue( RefCountPtr< const Lang::SingleList >( new Lang::SingleListPair( lastInResult, reverseResult ) ),
 838                         evalState );
 839       return;
 840
 841     }else{
 842
 843       /* Continue merge. */
 844       Core_mergeSort_cont_mergeStep::callback( reversed_, precedes_, precedesLoc_, rest, second_, firstAtStart_, reverseResult, lastInResult, dyn_, cont_, callLoc_,
 845                                                evalState );
 846       return;
 847
 848     }
 849
 850   }else{
 851
 852     /* Pick value from second.
 853      */
 854     RefCountPtr< const Lang::SingleListPair > reverseResult = RefCountPtr< const Lang::SingleListPair >( new Lang::SingleListPair( second_->car_, reverseResult_ ) );
 855     RefCountPtr< const Lang::SingleListPair > rest = second_->cdr_.down_cast< const Lang::SingleListPair >( );
 856
 857     Kernel::VariableHandle lastInResult = (lastInResult_ == Kernel::THE_SLOT_VARIABLE) ? second_->car_ : lastInResult_;
 858
 859     if( rest == NullPtr< const Lang::SingleListPair >( ) ){
 860       /* Only values in first remain. */
 861
 862       RefCountPtr< const Lang::SingleListPair > p = first_;
 863       while( p != NullPtr< const Lang::SingleListPair >( ) ){
 864         reverseResult = RefCountPtr< const Lang::SingleList >( new Lang::SingleListPair( p->car_, reverseResult ) );
 865         p = p->cdr_.down_cast< const Lang::SingleListPair >( );
 866       }
 867       evalState->cont_ = cont_;
 868       cont_->takeValue( RefCountPtr< const Lang::SingleList >( new Lang::SingleListPair( lastInResult, reverseResult ) ),
 869                         evalState );
 870       return;
 871
 872     }else{
 873
 874       /* Continue merge. */
 875       Core_mergeSort_cont_mergeStep::callback( reversed_, precedes_, precedesLoc_, first_, rest, false, reverseResult, lastInResult, dyn_, cont_, callLoc_,
 876                                                evalState );
 877       return;
 878
 879     }
 880
 881   }
 882 }
 883
 884 void
 885 Kernel::Core_mergeSort_cont_finish::takeValue( const RefCountPtr< const Lang::Value > & valUntyped, Kernel::EvalState * evalState, bool dummy ) const
 886 {
 887   /* The value received by this continuation shall be a SingleListPair where
 888    *   cdr_ is the sorted sequence, reversed
 889    *   car_ is the last element in the cdr_ sequence
 890    */
 891   typedef const Lang::SingleListPair ArgType;
 892   RefCountPtr< ArgType > val = Helpers::down_cast< ArgType >( valUntyped, "< Internal error situation in Core_mergeSort_cont_finish::takeValue >" );
 893
 894   evalState->cont_ = cont_;
 895   cont_->takeValue( val->cdr_, evalState );
 896 }
 897
 898
 899 void
 900 Kernel::registerCore_sort( Kernel::Environment * env )
 901 {
 902   env->initDefineCoreFunction( new Lang::Core_lexiographicSort( Lang::THE_NAMESPACE_Shapes_Data, "lexiographicSort" ) );
 903   env->initDefineCoreFunction( new Lang::Core_mergeSort( Lang::THE_NAMESPACE_Shapes_Data, "sort" ) );
 904 }
 905