Wednesday, January 30, 2013

Scheme: Չփոփոխվող բինար ծառերի մասին

Շարունակելով իմ նախորդ գրառման բինար որոնման ծառերի թեման, ուզում եմ նույն այդ օրինակով ցույց տալ, թե ինչպես կարելի է ծրագրեր գրել օգտագործելով միայն չփոփոխվող (immutable) տվյալների կառուցվածքներ։ Այս անգամ բինար որոնման ծառերի վարքը ծրագրավորել եմ Scheme լեզվով (այն Lisp ընտանիքի թերևս ամենահայտնի ներկայացուցիչն է)։ Ծառը ներկայացված է ցուցակի տեսքով, որի առաջին տարրը արմատի արժեքն է, երկրորդը՝ ձախ ենթածառն է, իսկ երրորդը՝ աջ ենթածառը։ Տերևներն իրենց աջ ու ձախ ենթածառերի փոխարեն պարունակում են #f արժեքը։ Օրինակ, 23 արժեքով տերևը ներկայանում է (23 #f #f) ցուցակով։ Իսկ ստորև բերված նկարում պատկերված ծառը․
        10
       /  \
      6    20
     / \    \
    4   8    28
            /  \
          23    30
            \
             26
ցուցակային ներկայացմամբ կունենա ահա այսպիսի տեսք․
(10 (6 (4 #f #f) (8 #f #f)) (20 #f (28 (23 #f (26 #f #f)) (30 #f #f))))
(Իհարկե կարելի է տերևները ներկայացնել կա՛մ ատոմներով, կա՛մ մեկ տարր պարունակող ցուցակներով։ Բայց ես ընտրել եմ այս ներկայացումը։)

Նախ ծառում արժեք ավելացնելու օրինակով ցույց տամ փոփոխվող (mutable) և չփոփոխվող (immutable) ծրագրավորելու տարբերությունները։ Ենթադրենք C լեզվով որպես բինար որոնման ծառի հանգույց սահմանված է _node ստրուկտուրան, իր _new_node կոնստրուկտորով.
typedef struct _node {
  int data;
  struct _node* left;
  struct _node* right;
} node;
node* _new_node( int value, node* l, node* r )
{
  node* result = (node*)malloc(sizeof(node));
  result->data = value;
  result->left = l;
  result->right = r;
  return result;
}
Այս տիպի հանգույցներով ծառում արժեք ավելացնելու համար սահմանված է _add_value ռեկուրսիվ ֆունկցիան, որն արգումենտում ստանում է ծառի արմատի ցուցիչի ցուցիչը և ավելացվող արժեքը:
void _add_value( node** tree, int value )
{
  if( *tree == NULL )
    *tree = _new_node( value, NULL, NULL );
  if( value < (*tree)->data )
    _add_value( &((*tree)->left), value );
  if( value > (*tree)->data )
    _add_value( &((*tree)->right), value );
}
Այս ֆունկցիայի համար ծառը փոփոխվող օբյեկտ է։ Այն դեպքում, երբ *tree ցուցիչի արժեքը NULL է, ստեղծվում է նոր հանգույց, և այդ նոր հանգույցի ցուցչիը վերագրվում է *tree ցուցիչին։ Քանի որ tree փոփոխականը ֆունկցիայի արգումենտում հայտարարված է struct _node** tree տեսքով, ապա փոփոխությունը կատարվում է հենց ծառի մեջ։

Չփոփոխվող տվյալներով տարբերակում նոր ստեղծված հանգույցն ավելացվում է ոչ թե ծառի մեջ, այլ տրոհվում է ծառը, ավելացվում է հանգույցը պետք եղած տեղում, ապա ստեղծվում է նոր ծառ։
node* _add_value_i( node* tree, int value )
{
  // եթե ծառը դատարկ է, ապա ստեղծել ու վերադարձնել նոր հանգույց
  if( tree == NULL )
    return _new_node( value, NULL, NULL );

  // տրոհել ծառը արմատի արժեքի, ձախ ու աջ ենթածառերի
  int d = tree->data;
  node* l = tree->left;
  node* r = tree->right;
  // ազատել հանգույցի զբաղեցրած հիշողությունը
  free(tree);
  
  // եթե տրված արժեքը փոքր է արմատի արժեքից, ապա 
  // ապա այն ավելացնել ձախ ենթածառում
  if( value < d )
    l = _add_value_i( l, value );
  // եթե տրված արժեքը մեծ է արմատի արժեքից, ապա 
  // ապա այն ավելացնել աջ ենթածառում
  else if( value > d )
    r = _add_value_i( r, value );
  // ստեղծել նոր արմատ ու վերադարձնել նրա ցուցիչը
  return _new_node( d, l, r );
}
(Պարզ է, որ եթե տրված արժեքը հավասար է արմատի արժեքին, ապա հանգույցը քանդելու կարիք չկա, այլ պետք է այն նույնությամբ վերադարձնել։)

Ծառում արժեք ավելացնող add-value պրոցեդուրայի սահմանումը Scheme լեզվով բերված է ստորև։ Այն համարյա նույնությամբ կրկնում է C լեզվով գրված տարբերակը։
(define add-value
  (lambda (tree val)
    (if tree
        (let ([d (car tree)] [l (cadr tree)] [r (caddr tree)])
          (cond
             [(< val d) (list d (add-value l val) r)]
             [(> val d) (list d l (add-value r val))]
             [else (list d l r)]))
        (list val #f #f))))
Քանի որ Scheme լեզվում ներդրված է աղբի հավաքման մեխանիզմը, այս պրոցեդուրայում կարիք չկա C լեզվի free() ֆունկցիային համարժեք գործողություններ կատարելու։
Ֆունկցիաների սահմանման համար Scheme լեզվում նախաատեսված է նաև (define (function-mane arguments) ...) գրելաձևը։ Բայց ինձ ավելի է դուր գալիս lambda արտահայտությամբ սահմանված (define function-name (lambda (arguments) ...) տարբերակը։ Հաջորդ բոլոր ֆունկցիաները սահմանելիս նույնպես օգտագործել եմ այս վերջին գրելաձևը։
Նաև սահմանեմ մի պրոցեդուրա, որը ծառի մեջ ավելացնում է ոչ միայն մեկ տրված արժեքը, այլ արժեքների ցուցակը։ Սա հնարավորություն կտա հեշտ ու ակնառու եղանակով կառուցել մեծ ծառեր։
(define add-to-tree
  (lambda (tree values)
    (if (empty? values)
        tree
        (add-to-tree (add-value tree (car values)) 
                     (cdr values)))))
Օրինակ, վերևի նկարում պատկերված ծառը կարելի է սահմանել (և սահմանածում համոզվելու համար արտածել) հետևյալ արտահայտություններով.
(define *tr* (add-to-tree #f '(10 6 20 4 8 28 23 30 26)))
(displayln *tr*)
Ծառից որևէ տրված արժեքը պարունակող հանգույցը հեռացնելու համար նույնպես կիրառված է նույն մոտեցումը՝ տրոհվում է ծառը, ապա հետ է հավաքվում, բայց արդեն առանց հեռացվող արժեքի։ Այն դեպքում, երբ ծառը դատարկ չէ, արմատը տրոհվում է d, l և r բաղադրիչների։ Երբ որոնվող արժեքը հավասար է d-ին, դիտարկվում են հետևյալ դեպքերը.
  1. Եթե \(r=\varnothing \;\wedge\; l=\varnothing\), ապա վերադարձվում է #f։
  2. Եթե \(r=\varnothing \;\vee\; l=\varnothing\), ապա վերադարձվում է համապատասխանաբար ձախ կամ աջ ենթածառը։
  3. Եթե \(r\ne\varnothing \;\wedge\; l\ne\varnothing\), ապա հեռացվում է աջ ենթածառի ամենափոքր արժեքը պարունակող հանգույցը, իսկ նրա արժեքը գրվում է արմատի արժեքի փոխարեն։
(define remove-value
  (lambda (tree val)
    (if tree
      (let ([d (car tree)] [l (cadr tree)] [r (caddr tree)])
        (cond
          [(< val d)
           (list d (remove-value l val) r)]
          [(> val d)
           (list d l (remove-value r val))]
          [else
           (cond
             [(and (not l) (not r)) #f]
             [(and l (not r)) l]
             [(and (not l) r) r]
             [else
              (let* ([h (minimum-value r)]
                     [t (remove-value r h)])
                (list h l t))])]))
      #f)))
minimum-value պրոցեդուրան, որ օգտագործված է remove-value պրոցեդուրայում, վերադարձնում է իրեն տրված ծառի ամենափոքր արժեքը, կամ, այլ կերպ ասած, ծառի ամենաձախ հանգույցի արժեքը։
(define minimum-value 
  (lambda (tree)
    (let ([l (cadr tree)])
      (if (not l)
          (car tree)
          (minimum-value l)))))

* * *
ՈՒ, պարզապես հետաքրքրության համար սահմանեմ նաև ծառի հետ կատարվող մի քանի գործողություններ։ Առաջինը թող լինի մի պրոցեդուրա, որ պարզում է տրված արժեքի առկայությունը ծառում։
(define contains-value 
  (lambda (tree val)
    (if tree
        (let ([d (car tree)])
          (cond 
            [(= val d) #t]
            [(< val d) (contains-value (cadr tree) val)]
            [(> val d) (contains-value (caddr tree) val)]))
        #f)))
Իսկ inorder-traverse պրոցեդուրան կատարում է ծառի ձախ-արմատ-աջ անցում՝ արմատի արժեքի վրա կիրառելով տրված պրոցեդուրան։
(define inorder-traverse 
  (lambda (tree func)
    (when tree
      (inorder-traverse (cadr tree) func)
      (func (car tree))
      (inorder-traverse (caddr tree) func))))
inorder-modify պրոցեդուրան տրված ծառից կառուցում ու վերադարձնում է մի նոր ծառ, որի հանգույցների արժեքները ձևափոխվել են ըստ տրված գործողության։
(define inorder-modify
  (lambda (tree func)
    (if tree
        (let* ([l (inorder-modify (cadr tree) func)]
               [d (func (car tree))]
               [r (inorder-modify (caddr tree) func)])
          (list d l r))
        #f)))
Այս պրոցեդուրայի աշխատանքի արդյունքը ցուցադրելու համար, օրինակ, տրված ծառից կառուցենք և արտածենք մի նոր ծառ, որի հանգույցների \(x\) արքժեքները փոխարինված են \((x\; \sqrt{x})\) տեսքի զույգերով։
(define *tr* (add-to-tree #f '(10 6 20 4 8 28 23 30 26)))
(displayln *tr*)
(displayln (inorder-modify *tr* (lambda (e) (list e (sqrt e)))))
Ահա նաև արդյունքը.
(10 (6 (4 #f #f) (8 #f #f)) (20 #f (28 (23 #f (26 #f #f)) (30 #f #f))))
((10 3.1622776601683795) ((6 2.449489742783178) ((4 2) #f #f) ((8 2.8284271247461903) #f #f)) ((20 4.47213595499958) #f ((28 5.291502622129181) ((23 4.795831523312719) #f ((26 5.0990195135927845) #f #f)) ((30 5.477225575051661) #f #f))))

Thursday, January 24, 2013

C++11: Բինար որոնման ծառեր

Այս գրառման մեջ ես ներկայացնում եմ բինար որոնման ծառի (binary search tree, BST) դասի ծրագրավորումը C++11 լեզվով։ Բինար որոնման ծառերն առանձնանում են նրանով, ամեն մի հանգույցի պարունակած արժեքը ավելի մեծ է քան նրա ձախ ենթածառի արժեքները և ավելի փոքր է, քան նրա աջ ենթածառի արժեքները։

Քանի որ բինար ծառի ամեն մի հանգույցը կարող է ունենալ առավելագույնը երկու ենթածառ, հանգույցը ներկայացնող շաբլոնային դասը կարելի է ներկայացնել հետևյալ տեսքով.
template<typename T>
class Node {
public:
  T data;
  Node* cleft;
  Node* cright;

public:
  Node( const T& val )
    : data(val), cleft(nullptr), cright(nullptr)
  {}
};
data դաշտը նախատեսված է հանգույցի տվյալների համար, cleft դաշտը ձախ ենթածառի ցուցիչն է, cright դաշտը՝ աջ ենթածառինը։ Հարմարության համար սահմանված է նաև կոնստրուկտոր, որը տրված արժեքը վերագրում է data փոփոխականին, իսկ աջ ու ձախ ենթածառերիո ցուցիչներին վերագրում է զրոյական ցուցիչի nullptr հաստատունը։

Ծառի մոդելը նույնպես ծրագրավորված է շաբլոնային դասի տեսքով։ Որպես ինտերֆեյսային մեթոդներ նախատեսել եմ հետևյալները.
  • Կոնստրուկտորներ, որոնցից մեկը ստեղծում է դատարկ ծառ, իսկ մյուսը ծառն արժեքավորում է արժեքավորող ցուցակով (initializer list) trva] արժեքներով։
  • Add մեթոդը տրված արժեքն ավելացնում է ծառի մեջ՝ ըստ այն պայմանի, որ ամեն մի հանգույցի ձախ ենթածառի բոլոր արժեքները պիտի լինեն ավելի փոքր, իսկ աջ ենթածառինն՝ ավելի մեծ, քան դիտարկվող հանգույցինն է։
  • Contains մեթոդը դրական պատասխան է տալիս, եթե ծառը պարունակում է տրված արժեքը։
  • Remove մեթոդը ծառից հեռացնում է տրված արժեքով հանգույցը՝ պահպանելով բինար ծառի վերը նշված հատկությունը։
  • Preorder, Inorder և Postorder մեթոդները անցնում են ծառի բոլոր հանգույցներով՝ կիրառելով համապատասխանաբար գագաթ-ձախ-աջ, ձախ-գագաթ-աջ և ձախ-աջ-գագաթ եղանակները։ Այս մեթոդներն արգումենտում ստանում են ֆունկցիա, որը կիրառվում է բոլոր հանգույցների data դաշտի նկատմամբ։
Բինար ծառը ներկայացված է իր արմատը ցույց տվող root ցուցիչով։ Դատարկ ծառի դեպքում այս ցուցիչն ունի nullptr արժեքը։ (Node դասը կարող է հայտարարվել նաև Tree դասի ներսում։)
template<typename T>
class Tree {
protected:
  Node<T>* root;
Կոնստրուկտորներից առաջինը արմատի ցուցիչին վերագրում է զրոյական արժեք։
public:
  Tree()
    : root(nullptr)
  {}
Երկրորդ կոնստրուկտորը արգումենտում սպասում է արժեքավորող ցուցակ և այդ ցուցակի տարրերը հերթականությամբ ավելացնում է ծառի մեջ։
  Tree( std::initializer_list<T> els )
    : Tree()
  {
    for( auto e : els )
      Add( e );
  }
Add, Contains, Remove, Preorder, Inorder, Postorder արտաքին (public) մեթոդներն իրականում թաղանթներ (wrapper) են addValue, search, traverse և removeNode ներքին (private) մեթոդների համար։
  // ծառում ավելացնում է val նոր արժեքը
  void Add( const T& val )
  { addValue( val, root ); }

  // ստուգում է val արժեքի առկայությունը ծառում
  bool Contains( const T& val )
  { return nullptr != search( val, root ); }
  
  // ծառից հեռացնում է val արժեքը
  void Remove( const T& val )
  { removeNode( val, root ); }

  // ծառի հանգույցներն անցնում է գագաթ-ձախ-աջ եղանակով և 
  // հանգույցի արժեքի նկատմամբ կիրառում է operation ֆունկցիան
  void Preorder( std::function<void(T)> operation )
  { traverse( root, T_Preorder, operation ); }
  
  // ծառի հանգույցներն անցնում է ձախ-գագաթ-աջ եղանակով և 
  void Inorder( std::function<void(T)> operation )
  { traverse( root, T_Inorder, operation ); }
  
  // ծառի հանգույցներն անցնում է ձախ-աջ-գագաթ եղանակով և 
  void Postorder( std::function<void(T)> operation )
  { traverse( root, T_Postorder, operation ); }
Վերջին երեք մեթոդներում T_Preorder, T_Inorder և T_Postorder իդենտիֆիկատորները սահմանված են հետևյալ կերպ.
protected:
  enum Order { T_Preorder, T_Inorder, T_Postorder };
Հիմա տեսնենք, թե իրականում ինչպես են կատարվում բինար ծառերին յուրահատուկ գործողությունները։ Եվ, քանի որ ծառն ինքնին ռեկուրսիվ կառուցվածք է, բոլոր գործողություններն իրականացված են ռեկուրսիվ տեսքով (չնայած ոչինչ չէր խանգարում դրանք իրականացնել առանց ռեկուրսիայի)։

Սկսեմ արժեքի ավելացման գործողությունից։ addValue մեթոդը ստանում է ավելացվող արժեքը և այն ծառի արմատի հղումը, որի մեջ պետք է ավելացնել նոր հանգույց՝ տրված արժեքով։ Դիտարկվում են երեք դեպքեր. i. եթե տրված արմատը դատարկ է, ապա ստեղծվում է նոր հանգույց և կապվում է այդ արմատին, ii. եթե տրված արժեքը փոքր է տրված արմատի արժեքից, ապա արժեքն ավելացվում է ձախ ենթածառում, iii. եթե տրված արժեքը մեծ է արմատի արժեքից, ապա այն ավելացվում է աջ ենթածառում։ Քանի որ ծառը կրկնվող արժեքներ չի կարող պարունակել, տրված արժեքի ու տրված արմատի արժեքների հավասարության դեպքը պարզապես չի դիտարկվում։
  void addValue( const T& val, Node<T>*& tree )
  {
    if( tree == nullptr )           // i
      tree = new Node<T>(val);
    else if( val < tree->data )     // ii
      addValue( val, tree->cleft );
    else if( val > tree->data )     // iii
      addValue( val, tree->cright );
  }
Հաջորդ պարզ գործողությունը ծառում տրված արժեքը պարունակող հանգույցի որոնումն է։ search մեթոդը ստանում է որոնվող արժեքը և այն արմատը, որից պետք է սկսել որոնումը և վերադարձնում է կա՛մ nullptr, եթե հանգույցի չի գտնվել, կա՛մ գտնված հանգույցի ցուցիչը։ Այս մեթոդի վերնագրի տարօրինակ գրառումը նույնպես C++11 ստանդարտի նորամությություններից է։ decltype(root) արտահայտությունն ասում է, որ մեթոդի վերադարձրած արժեքն ու նրա երկրորդ tree արգումենտը պետք է ունենան նոււյն տիպը, ինչ տիպ տրված է ծառի root արմատին։ Այս մեթոդում առանձնացված է այն դեպքը երբ տրված արմատը զրոյական է. վերդարձվում է nullptr։ i. Եթե տրված արժեքը հավասար է արմատի արժեքին, ապա արմատը ներկայացնող հանգույցը հենց որոնվող հանգույցն է։ ii. եթե val-ը փոքր է արմատի արժեքից, ապա որոնումը շարունակել ձախ ենթածառում, iii. հակառակ դեպքում որոնումը շարունակել աջ ենթածառում։
  decltype(root) search( const T& val, decltype(root) tree )
  {
    if( tree == nullptr )
      return nullptr;
    if( val == tree->data )
      return tree;
    if( val < tree->data )
      return search( val, tree->cleft );
    return search( val, tree->cright );
  }
Բնականաբար decltype(root) արտահայտության օգտագործումն ամենևին էլ պարտադիր չէր այս պարագայում։ Ես այն օգտագործել եմ միայն ցուցադրման նպատակով։ Կարելի է պարզապես բացահայտ գրել Node<T>*, որը հենց հանգույցի ցուցիչի տիպն է։
Համեմատաբար ավելի բարդ է ծառից տրված արժեքը պարունակող հանգույցը հեռացնելու գործողությունը։ Այս գործողությունը պետք է կատարել այնպես, որ բինար որոնման ծառը շարունակի պահպանել իր հատկությունները։ removeNode մեթոդը նույնպես ունի ռեկուրսիվ կառուցվածք, որտեղ նորից առանձնացված է տրված արմատի դատարկ լինելու դեպքը։ (Ավելի ճիշտ ասած, սա որոնող-հեռացնող մեթոդ է։) Այն դեպքում, երբ որոնումը կանգ է առել տրված արժեքը պարունակող հանգույցի վրա, դիտարկվում են քայլերի չորս տարբերակներ.
  • Երբ հանգույցը ենթածառեր չունի՝ տերև է: Այս դեպքում ազատվում է հանգույցի զբաղեցրած հիշողությունը և նրա հասցեն զրոյացվում է։
  • Երբ հանգույցն ունի միայն ձախ ենթածառ։ Այս դեպքում հանգույցը հեռացվում է և նրա հասցեին վերագրվում է ձախ ենթածառի հասցեն։
  • Համանման գործողություններ են կատարվում նաև այն դեպքում, երբ հանգույցն ունի միայն աջ ենթածառ։
  • Երբ առկա են հանգույցի և՛ ձախ, և՛ աջ ենթածառերը։ Այս դեպքում, որպեսզի պահպանվի բինար որոնման ծառի հատկությունները, հեռացվող հանգույցը պետք է փոխարինել կա՛մ ձախ ենթածառի ամենամեծ արժեքով, կա՛մ աջ ենթածառի ամենափոքր արժեքով։
  void removeNode( const T& val, decltype(root)& tree )
  {
    // ծառը դատարկ է
    if( tree == nullptr )
      return;
    // հեռացնել ձախ ենթածառից
    if( val < tree->data )
      removeNode( val, tree->cleft );
    // հեռացնել աջ ենթածառից
    else if( val > tree->data )
      removeNode( val, tree->cright );
    else {
      bool L(tree->cleft != nullptr);
      bool R(tree->cright != nullptr);
      if( !L && !R ) {
        // տերև է
        delete tree;
        tree = nullptr;
      }
      else if( L && !R ) {
        // միայն ձախ ենթածառն է
        auto temp(tree);
        tree = tree->cleft;
        delete temp;
      }
      else if( !L && R ) {
        // միայն աջ ենթածառն է
        auto temp(tree);
        tree = tree->cright;
        delete temp;
      }
      else /* if( L && R ) */ {
        // առկա են ձախ և աջ ենթածառերը
        auto temp(tree->cright);
        // որոնել աջ ենթածառի ամենաձախ հանգույցը
        while( temp->cleft != nullptr )
          temp = temp->cleft;
        // նրա արժեքը արտագրել "հեռացվող" հանգույցում
        tree->data = temp->data;
        // բայց հեռացնել աջ ենթածառի ամենաձախ հանգույցը
        removeNode( temp->data, tree->cright );
      }
    }
  }
Ծառի բոլոր հանգույցներով անցնելու այն երեք ստարատեգիաները, որոնք արտահայտված են Preorder, Inorder և Postorder արտաքին մեթոդներով, օգտագործում են միակ traverse ներքին մեթոդը։ Այստեղ ord արգումենտի արժեքով որոշվում է թե երբ պետք է գործողությունը կիրառել գագաթի արժեքի նկատմամբ։
  void traverse( decltype(root) tree, Order ord, std::function<void(T)> operation )
  {
    // ծառը դատարկ է
    if( tree == nullptr )
      return;
    // գագաթ-ձախ-աջ
    if( T_Preorder == ord )
      operation(tree->data);
    // անցում ձախ ենթածառով
    traverse(tree->cleft, ord, operation);
    // ձախ-գագաթ-աջ
    if( T_Inorder == ord )
      operation(tree->data);
    // անցում աջ ենթածառով
    traverse(tree->cright, ord, operation);
    // ձախ-աջ-գագաթ
    if( T_Postorder == ord )
      operation(tree->data);
  }
};

* * *
Ծառը ներկայացնող դասն արդեն պատրաստ է։ Այժմ կառուցենք ստորև բերված նկարում պատկերված բինար որոնման ծառը.
Տրված արժեքներով ծառ կառուցելու համար օգտագործենք արժեքավորող ցուցակը։
Tree<int> tr { 10, 6, 20, 4, 8, 16, 22, 7, 13, 17, 15 };
Ծառի պարունակությունը preorder, inorder և postorder անցումներով արտածելու համար սահմապենք printer ֆունկցիան և այն փոխանցենք Preorder, Inorder և Postorder արտքին մեթոդներին։
auto printer = [](int e) { printf("%d ", e); };

printf(" Preorder: ");
tr.Preorder( printer );
printf("\n");
  
printf("  Inorder: ");
tr.Inorder( printer );
printf("\n");
  
printf("Postorder: ");
tr.Postorder( printer );
printf("\n");
Կատարումից հետո կստանանք.
 Preorder: 10 6 4 8 7 20 16 13 15 17 22 
  Inorder: 4 6 7 8 10 13 15 16 17 20 22 
Postorder: 4 7 8 6 15 13 17 16 22 20 10 
Եթե հեռացնենք 13 արժեքը և ծառի պարունակությունն արտածենք ձախ-գագաթ-աջ կարգով, այնուհետև հեռանցնենք 10 արժեքը ու նորից արտածենք գագաթ-ձախ-աջ կարգով.
tr.Remove(13);
printf("  Inorder: ");
tr.Inorder( printer );
printf("\n");

printf(" Preorder: ");
tr.Preorder( printer );
printf("\n");
ապա կստանանք.
  Inorder: 4 6 7 8 10 15 16 17 20 22 
 Preorder: 15 6 4 8 7 20 16 17 22 
Այժմ, ենթադրենք պահանջվում է ծառի հանգույցները հավաքել std::vector<int> օբյեկտի մեջ, օրինակ, postorder կարգով։ Սահմանենք vec վեկտորը և մի լյամբդա արտահայտությունը, որը "բռնում" (capture) vec օբյեկտը որպես հղում և նրա մեջ է ավելացնում իր արգումենտում տրված արժեքը։
std::vector<int> vec;
tr.Postorder( [&vec](int e) { vec.push_back(e); });
Իսկ, օրինակ, ծառի արժեքների թվաբանական միջինը կարելի է հաշվել հետևյալ կերպ.
int summ(0), count(0);
tr.Inorder( [&summ,&count](int e) { summ += e; ++count; });
printf( "Sum = %f\n", 1.0 * summ / count );

Sunday, January 20, 2013

Common Lisp: Պարզ ու կատարյալ թվերի մասին

«N թիվը կոչվում է պարզ, եթե այն բացի մեկից և իրենից այլ բաժանարարներ չունի։» Եթե թվի պարզությունը որոշող ֆունկցիան գրենք ըստ այս սահմանման, ապա պետք է որ ստանանք մոտավորապես հետևյալը․
(defun is-prime-a (num)
  (loop for k from 2 to (1- num)
        never (zerop (mod num k))))
Սա իմպերատիվ լուծում է, որտեղ ցիկլի կազմակերպմամբ բացահայտորեն նկարագրված է, թե ինչ գործողություններ պետք է անել թվի պարզությունը ստուգելու համար։ (Այս ալգորիթմի քայլերի քանակը կարելի է կրճատել, եթե ցիկլի հաշվիչի վերին սահմանը փոխարինենք (ceiling (sqrt num)) արտահայտությամբ։ Բայց սա ոճական առումով ոչ մի լավացում չի տալիս։)

Փորձենք տալ պարզ թվի մեկ այլ սահմանում՝ հիմնված առաջինի վրա․ «N թիվը կոչվում է պարզ, եթե այն ունի միայն երկու բաժանարար։» Բայց այս սահմանումը պահանջում է, որ ստուգվեն 1..N միջակայքի մոլոր թվերը։ Այս անգամ էլ միջակայքի վերին սահմանը փոխարինելով (ceiling (sqrt N)) թվով, կստանանք մի նոր սահմանում։ «N թիվը կոչվում է պարզ, եթե այն 1..(sqrt N) միջակայքում ունի միայն մեկ բաժանարար։» (Բնականաբար այդ բաժանարարը 1 թին է։)

Այս վերջին սահմանումը բառացիորեն ծրագրավորելու դեպքում կունենանք հետևյալ ֆունկցիոնալ լուծումը․
(defun is-prime-b (num)
  (= 1 (list-length
 (remove-if 
  #'(lambda (e)
      (/= 0 (mod num e)))
  (loop for i from 1 to (ceiling (sqrt num))
        collect i)))))
Այս ֆունկցիան, չնայած որ կառուցվածքով բավականին հետաքրքիր է, արտաքնապես այնքան էլ գրավիչ չէ։ Փորձենք այն տրոհել ավելի պարզ ֆունկցիաների։

Վերջին սահմանումը հուշում է երեք գործողություն․ ա) 1..(sqrt N) միջակայքի ամբողջ թվերի ցուցակի կառուցում, բ) այդ ցուցակից N թվի բաժանարարների ֆիլտրում, գ) ֆիլտրված ցուցակի երկարության համեմատում 1 թվի հետ։

[a..b] միջակայքը, որտեղ a>b, կարող ենք կառուցել և՛ ռեկուրսիվ, և՛ իտերատիվ եղանակներով։ Ռեկուրսիվ տարբերակն ահա այսպիսինն է․
(defun range (lower upper &optional (delta 1))
  (if (> lower upper)
      '()
      (cons lower (range (+ lower delta) upper))))
Իտերատիվ տարբերակը էլ ավելի պարզ կառուցվածք ունի․
(defun range (lower upper &optional (delta 1))
  (loop for i from lower to upper by delta
        collect i))
Միջակայքը կազմող թվերի ցուցակը ֆիլտրելու և միայն տրված թվի բաժանարաները թողնելու համար սահմանենք divisors ֆունկցիան։ Ֆիլտրելու համար օգտագործված է Common Lisp լեզվի remove-if ֆունկցիան, որը տրված ցուցակից հեռացնում է տրված պրեդիկատին բավարարող տարրերը։
(defun divisors-a (num)
  (remove-if #'(lambda (e) (/= 0 (mod num e)))
             (range 1 (ceiling (sqrt num)))))
Եվ վերջապես, is-prime պրեդիկատը բաժանարարների ցուցակի երկարությունը համեմատում է 1-ի հետ։
(defun is-prime (num)
  (= 1 (list-length (divisors-a num))))

* * *
«N թիվը կոչվում է կատարյալ, եթե այն հավասար է իր բաժանարարների (բացի իրենից) գումարին։» Եթե թվի պարզ լինելը ստուգելու համար բաժանարարները որոնում էինք 1..(sqrt N) միջակայքում, ապա այս դեպքում պետք է ընտրել 1..N/2 միջակայքը։ Սահմանենք մի նոր divisors ֆունկցիա․
(defun divisors (num)
  (remove-if #'(lambda (e) (/= 0 (mod num e)))
             (range 1 (ceiling num 2))))
Թվի կատարյալ լինելն էլ ստուգելու համար սահմանենք is-perfect ֆունկցիան, որը գումարում է ընտրված բաժանարարները և ամեմատում թվի հետ։
(defun is-perfect (num)
  (= num (apply #'+ (divisors num))))
Այն դեպքում, երբ պետք է որոնել տրված M թվին չգերազանցող բոլոր կատարյալ թվերի ցուցակը, կարող ենք սահմանել perfects-in-range ֆունկցիան։
(defun perfects-in-range (upper)
  (remove-if (complement #'is-perfect) (range 2 upper)))

Thursday, January 17, 2013

Tcl ցուցակների հետ աշխատանքը

Ցուցակները Tcl լեզվում կառուցվում են list պրոցեդուրայով։ Այն ստանում է արգումենտների ցուցակ, հաշվարկում է դրանք և արդյունքներից կառուցվում է նոր ցուցակ։ Օրինակ,
set a [list [expr 1 + 2] 7 [expr 34 * 2]]
պրոցեդուրայի կատարումը a փոփոխականին կվերագրի {3 7 68} ցուցակը։ Հաստատուններից ցուցակ կարելի է կառուցել դրանք պարզապես թվարկելով "{" և "}" փախագծերի միջև։ Օրինակ,
set b {1 2 3 4 5}
Ցուցակի ամեն մի տարրն իր հերթին կարող է լինել ցուցակ։ Այդպիսին է օրինակ {a b c {3 4} d {5 6}} ցուցակը, որի տարրերից երկուսը ցուցակներ են։

Որևէ տողից կարելի է ցուցակ ստանալ, այն կտրտելով տրված բաժանիչով։ Օրինակ, եթե տրված է "a,b,c,d" տողը, ապա նրանից {a b c d} ցուցակը կարող ենք ստանալ ահա այսպես.
set c [split "a,b,c,d" ,]
Իսկ եթե տողում բաժանիչները մի քանիսն են, օրինակ ինչպես "a,b:c;d" տողում, ապա նույն {a b c d} ցուցակը կարելի է ստանալ split պրոցեդուրայի երկրորդ արգումենտում տալով բոլոր բաժանիչները.
set c [split "a,b,c,d" ",:;"]
split պրոցեդուրայի հակառակ գործողությունն է կատարում join պրոցեդուրան, որը տրված ցուցակի տարրերը տարրերը միացնում է իրար և ստանում տող՝ տարրի միջև ավելացնելով տրված տողը։ Օրինակ, {1 2 3 4} ցուցակից "1 + 2 + 3 + 4" տողը ստանալու համար կարող ենք գրել
set d [join {1 2 3 4} { + }]
Մի քանի ցուցակներ իրար կցելու և նոր ցուցակ ստանալու համար է նախատեսված concat պրոցեդուրան։ Օրինակ, {6 7 8 9}, {g h i j} և {"a 1" "b 2" "c 3"} ցուցակներից մի նոր ցուցակ կարող ենք ստանալ՝ կատարելով հետևյալ հրամանը.
set e [concat {6 7 8 9} {g h i j} {"a 1" "b 2" "c 3"}]
կատարման արդյունքում կստացվի {6 7 8 9 g h i j "a 1" "b 2" "c 3"} ցուցակը։

Ցուցակ կարելի է կազմել նաև տրված տարրը lrepeat պրոցեդուրայի օգնությամբ տրված քանակով կրկնելով։ Օրինակ, եթե ուզում ենք կառուցել տաս z տառերից բաղկացած ցուցակ, ապա պետք է գրել.
set u [lrepeat 10 z]
Տրված ցուցակի պոչից նոր տարր կցելու համար lappend պրոցեդուրայի առաջին արդումենտում պետք է տալ այն ցուցակը, որին ուզում ենք կցել տարրերը, իսկ հաջորդ արգումենտներով՝ կցվող տարրերը։ Օրինակ,
set a [list 1 2 3]
lappend a 4 5 6
Առաջին տողը կատարվելիս a փոփոխականի վերագրվում է {1 2 3} ցուցակը։ Հաջորդ տողը կատարելիս արդեն a-ն փոխվում է՝ ստանալով {1 2 3 4 5 6} արժեքը։ lappend պրոցեդուրան փոխում է իր առաջին արգումենտում տրված ցուցակը, բայց նաև վերադարձնում է նոր ստեղծված ցուցակը։

Ցուցակի տարրերի միջև նոր տարրեր խցկելու համար պետք է օգտագործել linsert պրոցեդուրան։ Նրա առաջին արգումենտը ցուցակն է, որում պետք է խցկել նոր տարրեր, երկրորդը ինդեքս է՝ այն տարրի ինդեքսը, որից առաջ պետք է խցկել տարրերը, հաջորդ արգումենտներով արդեն տրվում են ավելացվող տարրերը։ Օրինակ, եթե {1 2 3} ցուցակի սկզբից 8 և 9 տարրերն ավելացնելու համար ինդեքսը պետք է տալ զրո.
linsert {1 2 3} 0 8 9
Այս հրամանը կվերադարձնի {8 9 1 2 3} ցուցակը։ Իսկ {1 8 9 2 3} ցուցակը ստանալու համար պետք է գրել հետևյալը.
linsert {1 2 3} 1 8 9
Ցուցակի վերջից տարրերն ավելացնելու համար (մոտավորապես այնպես, ինչպես անում է lappend պրոցեդուրան) ինդեքսի փոխարեն պետք է տալ end բառը.
linsert {1 2 3} end 8 9
Ցուցակի տարրերը հեռացնելու կամ այլ տարրերով փոխարինելու համար է նախատեսված lreplace պրոցեդուրան։ Այն առաջին արգումենտում ստանում է ցուցակը, որի տարրերը պետք է փոխարինել, երկրորդ և երրորդ արգումենտով ստանում է փոխարինվող տարրերի միջակայքի ինդեքսները, իսկ հաջորդ արգումենտներով ստանում է այն տարրերը, որոնք պետք է տեղադրվեն հեռացվածների փոխարեն։ Օրինակ, {1 2 3 4 5 6 7} ցուցակից {1 2 a b c d 6 7} ցուցակը ստանալու համար պետք է գրել.
lreplace {1 2 3 4 5 6 7} 2 4 a b c d
Նույն այդ ցուցակի վերջին երկու տարրերը հեռացնելու համար էլ պետք է գրել.
lreplace {1 2 3 4 5 6 7} end-2 end
Ցուցակի տարրերից որևէ մեկի արժեքը մեկ այլ արժեքով փոխարինելու համար պետք է lset պրոցեդուրային տալ ցուցակը ներկայացնող փոփոխականի անունը, տարրի ինդեքսը և նոր արժեքը։ Օրինակ, եթե a փոփոխականին վերագրված է {1.2 3.4 5.6 7.8 9.0} ցուցակը, և ուզում ենք 7.8 արժեքը փոխարինել 8.7 արժեքով, ապա կարող ենք գրել.
set a {1.2 3.4 5.6 7.8 9.0}
lset a 3 8.7
lset պրոցեդուրայով կարելի է փոփոխել նաև ներդրված ցուցակների տարրերը։ Այս դեպքում ինդեքսի փոխարեն պետք է տալ ինդեքսների ցուցակ։ Օրինակ, եթե b փոփոխականին վերագրված է {{x0 1.2} {x1 3.4} {x2 5.6} {x3 7.8} {x4 9.0}} ցուցակը, և մեզ պետք է 5.6 արժեքը փոխարինել 0.0 արժեքով, ապա կարող ենք գրել.
set b {{x0 1.2} {x1 3.4} {x2 5.6} {x3 7.8} {x4 9.0}}
lset b {2 1} 0.0
Եթե պետք է ստանալ ցուցակի տրված ինդեքսով տարրը, ապա lindex պրոցեդուրային պետք է տալ ցուցակը և պահանջվող տարրի ինդեքսը։ (Եթե որևէ ինդեքս տրված չէ, ապա այս պրոցեդուրան վերադարձնում է ամբողջ ցուցակը։) Օրինակ, հետևյալ արտահայտությունը k փոփոխականին վերագրում է {x1 3.4}.
# set b {{x0 1.2} {x1 3.4} {x2 5.6} {x3 7.8} {x4 9.0}}
set k [lindex $b 1]
Եթե հարկավոր է k փոփոխականին վերագրել 3.4 արժեքը, ապա ինդեքսի փոխարեն պետք է տալ ինդեքսների ցուցակ (ինչպես lset պրոցեդուրայի դեպքում).
set k [lindex $b {1 1}]
Մի տարրի փոխարեն ցուցակի տարրերի տրված ինդեքստներով սահմանափակված հատվածը կարելի է ստանալ lrange պրոցեդուրայով։ Այն ստանում է ցուցակը, պահանջվող հատվածի սկզբի և վերջի ինդեքսները. ընդ որում, վերջին ինդեքսով որոշվող տարրը արդյուքի մեջ չի ներառվում։ Օրինակ, {a b c d e f g h} ցուցակից def բառը ստանալու համար պետք է գրել.
join [lrange {a b c d e f g h} 3 5] {}
Ցուցակում տրված շաբլոնին համապատասխանող տարրի առկայությունը որոշելու համար է նախատեսված lsearch պրոցեդուրան։ Սա վերադարձնում է որոնվող տարրի ինդեքսը, կամ -1 արժեքը՝ եթե որոնումն անհաջող է ավարտվել։ Օրինակ, ենթադրենք, թե a փոփոխականին վերագրված է {1.2 3.4 5.6 7.8 3.4 9.0} ցուցակը։ 7.8 արժեքով տարրի ինդեքսը որոշելու համար պետք է գրել.
set k [lsearch -real $a 7.8]
որտեղ -real բանալին ցույց է տալիս, որ որոնման ժամանակ արժեքները համեմատվելու են որպես իրական թվեր։ Ցուցակը 3.4 արժեքը պարունակում է երկու անգամ և այդ երկու տարրերի ինդեքսները որոշելու համար lsearch պրոցեդուրայի կանչի ժամանակ պետք է տալ -all բանալին, և այս դեպքում կստանանք ինդեքսների ցուցակ։
set k [lsearch -real -all $a 3.4]
Այժմ ենթադրենք, թե b փոփոխականի հետ կապված է {c7 b4 a0 B6 a2 c8 a1 b3 B5} ցուցակը, և ուզում ենք ստանալ այն տարրերը, որոնց սկսվում են a տառով։
puts [lsearch -ascii -all -inline -regexp $b {^a}]
Այս արտահայտության մեջ -ascii բանալին նշում է, որ ցուցակի տարրերը տողեր են, -inline բանալին ցույց է տալիս, որ պետք է վերադարձնել ոչ թե տառերը, այլ գտնված տարրերը։ -regexp բանալին ասում է, որ որոնման ժամանակ տարրերը պետք է համապատասխանեմ տրված կանոնավոր արտահայտությանը, իսկ {^a} արտահայտությունը ճանաչում է բոլոր այն տարրերը, որոնց առաջին տարրը a է։ Եթե հարկավոր է, որ որոնում կատարելիս անտեսվեն մեծատառերի ու փոքրատառերի տարբերությունները, ապա պետք է գրել նաև -nocase բանալին։

Ցուցակները կարդավորելու (sort) համար է lsort պրոցեդուրան: Օրինակ, նախորդ b ցուցակը այբբենական եղանակով կարգավորելու համար պետք է գրել.
puts [lsort -nocase -ascii $b]
Նույն ցուցակը հակառակ կարգով կարգավորելու համար հրամանին պետք է ավելացնել -decreasing բանալին։ Եթե հարկավոր է կարգավորման ժամանակ ցուցակից հեռացնել կրկնությունները, ապա պետք է տալ նաև -unique բանալին։

Ցուցակը շրջելու համար պետք է օգտագործել lreverse պրոցեդուրան: Այն ստանում է ցուցակը և վերադարձնում է մեկ այլ ցուցակ, որում նախնականի տարրերն են՝ թվարկված հակառակ հաջորդականությամբ։ llength պրոցեդուրան պարզապես վերադարձնում է տրված ցուցակի տարրերի քանակը։

Sunday, January 13, 2013

Եզակի անձնանունների մասին

Նախագահական ընտրությունների հետ կապված ՀՀ ոստիկանության կայքում տեղադրվել են Հայաստանի բոլոր ընտրատեղամասերի ընտրողների ցուցակները` ըստ ընտրատարածքների։ Ես աչքի էի անցկացնում իմ ընտրատեղամասի ցուցակները և հանդիպեցի բավականին շատ հազվադեպ հանդիպող անձնանունների։ Միանգամից ցանկություն առաջացավ տեսնել, թե է՛լ ինչպիսի եզակի անուններ կան, օրինակ այն ընտրատարածքում, որում ես գրանցված եմ։ Այս գրառման մեջ կներկայացնեմ, թե ինչպես «լուծեցի» այդ խնդիրը։

Նշված էջում ամեն մի ընտրատարածքի համար նախատեսված է համարակալված պանակ, որի մեջ առանձին Microsoft Excel ֆայլերով տրված են ընտրատեղամասերի ընտրողների ցուցակները։ (Օրինակ, ես գրանցված եմ 39-րդ ընտրատարածքի 18-րդ ընտրատեղամասում։ Հետևաբար իմ տվյալները պետք է որոնեմ 39 համարով պանակի 39_18.xls ֆայլում։) Նախ, իմ աշխատանքային պանակում ստեղծեցի uniquenames անունով մի պանակ և այն դարձրեցի ընթացիկ։
mkdir uniquenames
cd uniquenames
Այնուհետև wget ծրագրով համակարգիչ բեռնեցի 39-րդ պանակի բոլոր ֆայլերը․
wget -r -np -A '*.xls' http://www.police.am/yntrutyunner/39/
Այս հրամանի կատարումից հետո uniquenames պանակում ստեղվեց բեռնված պանակների հիերարխիա՝ www.police.am/yntrutyunner/39/ ճանապարհով։ Հարմարության համար բոլոր xls ֆայլերը պատճենեցի ընթացիկ պանակի մեջ․
cp www.police.am/yntrutyunner/39/*.xls .
Excel ֆայլերի հետ աշխատելու ոչ մի ցանկություն չունեմ, հետևաբար դրանք պետք է փոխարինել մի որևէ պարզ ֆորմատի։ Ես ընտրեցի ստորակետով բաժանված դաշտերով (csv) ֆորմատը։ Իսկ քանի որ ֆայլերում ինֆորմացիան գրված է ArmSCII-8 կոդավորմամբ, նաև պետք է ձևափոխություն կատարել Utf-8 կոդավորման։ Իմ Ubuntu 12.04 համակարգում տեղադրված է LibreOffice 3.5 փաթեթը, որի Calc ծրագիրը կարողանում է բացել Microsoft Excel ֆայլերը։ Բայց քանի որ ֆայլերը շատ են, ձևափոխությունը ավելի հարմար է անել հրամանային տողից։ Պանակի բոլոր Excel ֆայլը csv ֆայլերի փոխարինելու համար պետք է գրել հետևյալ հրամանը․
libreoffice --nologo --calc --convert-to csv *.xls
Ստեղծվում են *.csv ընդլայնումով ֆայլեր, որոնց պարունակությունը ArmSCII-8 կոդավորմամբ է։ Դրանք Utf-8 կոդավորման ձևափոխելու համար կարելի է օգտագործել iconv ծրագիրը: Հետևյալ հրամանը գտնում է պանակի բոլոր csv ֆայլերը և ամեն մեկի համար ստեղծում է նրա Utf-8 կոդավորմամբ տարբերակը՝ *.txt ընդլայնմամբ։
find . -name '*.csv' -exec iconv -f ArmSCII-8 -t Utf-8 {} -o {}.txt \;
Այս դրությամբ արդեն ունեմ Utf-8 կոդավորմամբ տեքստային ֆայլեր, որոնց ամեն մի տողում գրված է մի ընտրողի մասին ինֆորմացիա։ Ֆայլերի սկզբում մնացել է Excel աղյուսակի սյունակի վերնագրերը, բայց քանի որ ընտրողների տվյալները համարակալված են, մշակելիս ես կդիտարկեմ միայն թվանշանով սկսվող տողերը։

Այս տիպի խնդիրների լուծման համար ամենահարմար գործիքը AWK ծրագրավորման լեզուն է: Իմ համակարգում տեղադրված է այդ լեզվի gawk (GNU Awk) իրականացումը։ Ահա մի կարճ սկրիպտ, որը բոլոր ֆայլերից հարդում է մարդկանց անունները, հաշվում է ամեն մի անունի հանդիպելու քանակը և արտածում է այն անունները, որոնք հանդիպել են միայն մեկ անգամ։
BEGIN { FS = "," }

/^[0-9]/ { names[$3]++ }

END {
  uniques = ""
  for(e in names)
    if( names[e] == 1 )
      uniques = uniques e " "
  print uniques
}
Հրամանային տողից այս ծրագիրն աշխատեցնելու համար (այն պահպանել եմ uniquenames.awk անունով ֆայլում) պետք է գրել․
gawk -f uniquenames.awk *.txt
Որն անունները տերմինալին կարտածի բացատանիշերով անջատված ու չկարգավորված տեսքով։ Մեկ այլ հրամանով կարելի է անունները կարգավորել ու արտածել մեկ սյունակով (կամ ուղարկել sorted-names.txt ֆայլի մեջ)։
gawk -f uniquenames.awk *.txt | tr " " "\n" | sort > sorted-names.txt
Եվ վերջում հեռացնեմ բոլոր ժամանակավոր ֆայլերը․
rm *.xls *.csv *.csv.txt

* * *
Անպայման առաջարկում եմ լսել Հովհաննես Շիրազի «Հայոց անունները» պոեմը։

Wednesday, January 9, 2013

C++11: Կապակցված ցուցակներ (II)

Ժամանակ առ ժամանակ ինձ մոտ ցանկություն է առաջանում ծանոթանալ C++ լեզվի C++11 ստանդարտի հնարավորություններին։ Այս գրառման մեջ ես երկկապակցված ցուցակի (doubly linked list) իրականացման օրինակով փորձում եմ ծանոթանալ լեզվի այնպիսի նորամուծություններին, ինչպիսիք են զրոյական ցուցիչի nullptr արժեքը, տիպի դուրսբերման auto եղանակը, արժեքավորող ցուցակով կոնստրուկտորները, մի կոնստրուկտորում մեկ այլ կոնստրուկտորի օգտագործումը, և այլն։

* * *
Մինչև ցուցակը նկարագրելը ներկայացնեմ նրա մեկ հանգույցը մոդելավորող Item դասը։ Այն շաբլոնային դաս է, data, prev և next դաշտերով, որոնցից առաջինը նախատեսված է հանգույցում պահվող ինֆորմացիայի համար, երկրորդն ու երրորդն էլ համապատասխանաբար նախորդ ու հաջորդ հանգույցներին կապելու համար։
template<typename T>
class Item {
public:
  T data;
  Item* prev;
  Item* next;
    
public:
  Item( const T& val, Item* pr, Item* nx )
    : data(val), prev(pr), next(nx)
  {}
  Item( const T& val )
    : Item(val, nullptr, nullptr)
  {}
  inline void Print() const
  { std::cout << data << (next != nullptr ? ", " : ""); }
};
Առաջին կոնստրուկտորը երեք դաշտերն էլ արժեքավորում է տրված արժեքներով։ Երկրորդ կոնստրուկտորը կառուցում է տրված ինֆորմացիայով հանգույց, որի prev և next ցուցիչները զրոյական են։ Այս կոնստրուկտորում արդեն երևում են C++11 ստանդարտի երկու նորամուծություններ։ 1. Մի կոնստրուկտորում կարելի է օգտագործել մեկ այլ կոնստրուկտոր՝ կիրառելով այն դաշտերի արժեքավորման ցուցակում։ 2. Զրոյական ցուցիչների համար նախատեսված է nullptr հաստատունը (այն ծառայողական բառ է)։

Print մեթոդը ստանդարտ արտածման հոսքի վրա արտածում է հանգույցի data դաշտի պարունակությունը։ Եթե հանգույցի next ցուցիչը հավասար է nullptr-ի, ապա համարվում է, որ այդ հանգույցը ցուցակի վերջին հանգույցն է և այլևս ոչինչ չի արտածվում։ Եթե next ցուցիչը տարբեր է nullptr-ից, ապա արտածվում է նաև ստորակետ՝ ենթադրելով, որ հաջորդելու են այլ հանգույցների արտածումներ։

* * *
Ցուցակը մոդելավորող List շաբլոնային դասն ունի երեք դաշտ. head - ցուցիչ է առաջին հանգույցին, tail - ցուցիչ է վերջին հանգույցին, count - հանգույցների քանակն է։
template<typename T>
class List {
private:
  Item<T>* head;
  Item<T>* tail;
  unsigned int count;
Կոնստրուկտորներից առաջինը ստեղծում է դատարկ ցուցակ՝ առաջին ու վերջին հանգույցների ցրույական ցուցիչներով և տարրերի քանակի զրոյական հաշվիչով։
public:
  List()
    : head(nullptr), tail(nullptr), count(0)
  {}
Երկրորդ կոնստրուկտորը ցուցակը կառուցում է տրված արժեքավորող ցուցակի (initializer list) տարրերից: Օրինակ, եթե պետք է սահմանել մի ցուցակ 1, 2, 3 սկզբնական տարրերով, ապա կարող ենք գրել "List<int> ex0 = {1, 2, 3};": Ահա այս դեպքում է աշխատում հենց ստորև բերված կոնստրուկտորը։ (initializer_list կոնտեյները հայտարարված է ստանդարտ գրադարանի initializer_list ֆայլում։)
  List( std::initializer_list<T> vals )
    : List()
  {
    for( auto v : vals )
      PushBack( v );
  }
Նորամուծություն է նաև ցիկլի կազմակերպման for կառուցվածքի տեսքը։ Այս տեսքով v փոփոխականն անցնում է vars կոնտեյների տարրերով։ auto ծառայողական բառը ցույց է տալիս, որ կոմպիլյատորը v փոփոխականի տիպը ավտոմատ որոշելու է կոմպիլյացիայի ժամանակ։ Եթե գրեինք C++98 ոճով, ապա այս ցիկլը կունենար մոտավորապես հետևյալ տեսքը.
for( std::initalizer_list<T>::iterator v = vals.begin(); v != vals.end(); ++v )
  PushBack( *v );
Front և Back մեթոդները համապատասխանաբար վերադարձնում են ցուցակի առաջին ու վերջին հանգույցների ցուցիչները։ Count մեթոդը վերադարձնում է տարրերի քանակը։ IsEmpty մեթոդը պարզում է ցուցակի դատարկ լինելը։ (Այս ֆունկցիաների իրականացման մեջ որևէ հետաքրքիր բան չկա։)
  Item<T>* Front() const 
  { return head; }
  
  Item<T>* Back() const 
  { return tail; }
  
  unsigned int Count() const
  { return count; }

  bool IsEmpty() const
  { return head == nullptr && tail == nullptr; }
Print մեթոդը ստանդարտ արտածման հոսքին արտածում է ցուցակի տարրերի արժեքները՝ ստորակետերով անջատված։ Ցուցակի ամբողջ պարունակությունն արտածվում է "[" և "]" նիշերի մեջ։ Մեթոդի իրականացումը մի պարզ ցիկլ է, որը, թեևս, բացատրության կարիք չունի։
  void Print() const
  {
    std::cout << "[";
    for( auto p(head); p != nullptr; p = p->next )
      p->Print();
    std::cout << "]";
  } 

* * *
Ցուցակում տարրեր ավելացվում են չորս մեթոդների օգնությամբ։ Դրանք են.
  • PushFront(v) - ցուցակի սկզբից ավելացնում է տրված v արժեքով հանգույց,
  • InsertBefore(v, n) - ցուցակի n հանգույցից առաջ ավելացնում է v արժեքով հանգույց,
  • PushBack(v) - ցուցակի վերջից ավելացնում է տրված v արժեքով հանգույց,
  • InsertAfter(v, n) - ցուցակի n հանգույցից հետո ավելացնում է v արժեքով հանգույց։

Եթե ցուցակը դատարկ է, ապա PushFront մեթոդը ստեղծում է նոր հանգույց, head և tail ցուցյիչները կապում է նրան, իսկ հանգույցների հաշվիչին վերագրում է 1։ Եթե ցուցակը դատարկ չէ, ապա նոր հանգույցն ավելացվում է InsertBefore մեթոդով։
  void PushFront( const T& val )
  {
    if( IsEmpty() ) {
      head = new Item<T>(val);
      tail = head;
      count = 1;
    }
    else
      InsertBefore( val, head );
  }
InsertBefore մեթոդը արգումենտում ստանում է val արժեքը և node ցուցիչը։ Ապա ստեղծվում է նոր հանգույց՝ val արժեքով, որի prev ցուցիչին վերագրված է node->prev ցուցիչը, իսկ next ցուցիչին՝ node ցուցիչը։ Հաջորդ քայլում նոր ստեղծված temp հանգույցին հաջորդող և նախորդող հանգույցները կապվում են temp-ի հետ։ Եվ վերջապես, ստուգվում է, որ եթե հոր հանգույցն ավելացվել է head-ից առաջ, ապա head տեղաշարժվում է նոր հանգույցի վրա։
  void InsertBefore( const T& val, Item<T>* node )
  {
    auto temp = new Item<T>(val, node->prev, node); // 1
    temp->next->prev = temp; // 2
    if( temp->prev != nullptr )
      temp->prev->next = temp; // 3
    ++count;
    if( node == head )
      head = temp;
  }
PushBack մեթոդը, որ պետք է արժեք ավելացնի ցուցակի պոչից, օգտագործում է տրված հանգույցից հետո նոր հանգույց խցկող InsertAfter մեթոդը։
  void PushBack( const T& val )
  {
    if( IsEmpty() )
      PushFront( val );
    else
      InsertAfter( val, tail );
  }
Իսկ InsertAfter մեթոդն իր հերթին օգտագործում է InsertBefore մեթոդը՝ նոր հանգույցն ավելացնելով ոչ թե տրված հանգույցից առաջ, այլ նրանից հետո, ապա փոխարինելով data դաշտի արժեքները։
  void InsertAfter( const T& val, Item<T>* node )
  {
    InsertBefore( node->data, node );
    node->data = val;
  }

* * *
Մեթոդների հաջորդ խումբը նախատեսված է ցուցակից հանգույցներ հեռացնելու համար։ Դրանք են.
  • Remove(n) - ցուցակից հեռացնում է տրված n հանգույցը,
  • PopFront - հեռացնում է ցուցակի առաջին հանգույցը և վերադարձնում է նրա data դաշտի արժեքը,
  • PopBack - հեռացնում է ցուցակի վերջին հանգույցը՝ նույնպես վերադարձնելով նրա data դաշտի արժեքը,

Remove մեթոդի սկզբում նախ ստուգվում է, որ տրված հանգույցի ցուցիչը զրոյական չլինի և ցուցակը դատարկ չլինի։ Երկու դեպքերում էլ գեներացվում է սխալ՝ runtime_error՝ համապատասխան հաղորդագրությամբ։ Այս բացառության դասը նունպես ավելացված է C++11 ստանդարտում և, ի թիվս այլ նոր բացառությունների դասերի, սահմանված է ստանդարտ գրադարանի stdexcept ֆայլում։
  Այնուհետև, եթե հեռացվող հանգույցն ունի հաջորդող հանգույց, ապա դրա prev ցուցիչին վերագրվում է հեռացվող հանգույցի prev ցուցիչի արժեքը։ Համապատասխան գործողությունը կատարվում է նաև հեռացվողին նախորդող հանգույցի հետ։
  Եթե հեռացվող հանգույցը ցուցակի առաջին կամ վերջին հանգույցն է, ապա համապատասխան ձևով վերահաշվարկվում են նաև head և tail ցուցիչները։
Իսկ վերջում համակարգին է վերադարձվում հեռացվող հանգույցի զբաղեցրած հիշողությունն ու մեկով նվազեցվում է հանգույցների քանակի հաշվիչի արժեքը։
  void Remove( Item<T>* node )
  {
    if( node == nullptr )
      throw new std::runtime_error("Null node.");
    if( IsEmpty() )
      throw new std::runtime_error("Empty list.");
    
    if( node->next != nullptr )
      node->next->prev = node->prev;

    if( node->prev != nullptr )
      node->prev->next = node->next;

    if( node == head )
      head = head->next;
    if( node == tail )
      tail = tail->prev;

    delete node;
    --count;
  }
PopFront և PopBack մեթոդները պարզապես օգտագործում են Remove մեթոդը՝ նախապես պահելով և վերադարձնելով առաջին կամ վերջին հանգույցի պարունակած արժեքը։
  T PopFront()
  {
    auto res(head->data);
    Remove(head);
    return res;
  }
  
  T PopBack()
  {
    auto res(tail->data);
    Remove(tail);
    return res;
  }

* * *
Ցուցակում որոնում կատարելու համար ես նախատեսել եմ երկու մեթոդներ. FindIf, որը վերադարձնում է տրված պրեդիկատին բավարարող առաջին հանգույցի ցուցիչը, և Find, որը վերադարձնում է տրված արժեքը պարունակող առաջին հանգույցի ցուցիչը։

Պրեդիկատը FindIf մեթոդին փոխանցվում է որպես ստանդարտ գրադարանի function օբյեկտ։ Այս function դասը նույնպես ներմուծված է նոր ստանդարտում և սահմանված է functional ֆայլում։
  Item<T>* FindIf( std::function<bool(T)> pred ) const 
  {
    for( auto p(head); p != nullptr; p = p->next )
      if( pred(p->data) )
        return p;
    return nullptr;
  }
Find մեթոդն օգտագործում է FindIf-ը՝ տրված արժեքով հանգույցը գտնելու համար։ Այս մեթոդում ստեղծվում է մի լյամբդա ֆունկցիա (արտահայտություն), որպես որոնման պրեդիկատ, որը "բռնելով" val փոփոխականը, այն համեմատում է իր արգումենտում տրված արժեքի հետ։
  Item<T>* Find( const T& val ) const
  {
    return FindIf( [&val](T v)->bool { return val == v; } );
  }
Եվ վերջին մեթոդը։ Map մեթոդը արգումենտում ստանում է ցուցակի արժեքը ձևափոխող ֆունկցիա և ներադարձնում է ձևափոխված արժեքներից կառուցած նոր ցուցակի ցուցիչը։
  List<T>* Map( std::function<T(T)> func ) const
  {
    auto result = new List<T>();
    for( auto p(head); p != nullptr; p = p->next )
      result->PushBack( func(p->data) );
    return result;
  }
Օրինակ, այս Map մեթոդով կարելի է ամբողջ թվեր պարունակող ցուցակից կառուցել նույն այդ թվերի քառակուսիները պարունակող ցուցակ։ Ահա այսպես.
  auto ex0 = new List<int>({1, 2, 3, 4});
  List<int>* ex1 = ex0->Map( [](int e)->int { return e * e; } );
  ex1->Print();

* * *
List դասի դեստրուկտորը Remove մեթոդի օգնությամբ հեռացնում է բոլոր հանգույցները։
  ~List()
  {
    while( !IsEmpty() )
      Remove( head );
  }
};