home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / lib270b.zip / emx / include / cpp / list.h < prev    next >
C/C++ Source or Header  |  1995-05-17  |  15KB  |  528 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  */
  15.  
  16. #ifndef LIST_H
  17. #define LIST_H
  18.  
  19. #include <function.h>
  20. #include <algobase.h>
  21. #include <iterator.h>
  22. #include <bool.h>
  23.     
  24. #ifndef Allocator
  25. #define Allocator allocator
  26. #include <defalloc.h>
  27. #endif
  28.  
  29. #ifndef list 
  30. #define list list
  31. #endif
  32.  
  33. template <class T>
  34. class list {
  35. protected:
  36.     typedef Allocator<void>::pointer void_pointer;
  37.     struct list_node;
  38.     friend list_node;
  39.     struct list_node {
  40.     void_pointer next;
  41.     void_pointer prev;
  42.     T data;
  43.     };
  44. #ifndef __GNUG__
  45.     static Allocator<list_node> list_node_allocator;
  46.     static Allocator<T> value_allocator;
  47. #endif
  48. public:      
  49.     typedef T value_type;
  50.     typedef Allocator<T> value_allocator_type;
  51.     typedef Allocator<T>::pointer pointer;
  52.     typedef Allocator<T>::reference reference;
  53.     typedef Allocator<T>::const_reference const_reference;
  54.     typedef Allocator<list_node> list_node_allocator_type;
  55.     typedef Allocator<list_node>::pointer link_type;
  56.     typedef Allocator<list_node>::size_type size_type;
  57.     typedef Allocator<list_node>::difference_type difference_type;
  58. protected:
  59. #ifdef __GNUG__
  60.     link_type get_node() { return new list_node; }
  61.     void put_node(link_type p) { delete p; }
  62. #else
  63.     size_type buffer_size() {
  64.     return list_node_allocator.init_page_size();
  65.     }
  66.     struct list_node_buffer;
  67.     friend list_node_buffer;
  68.     struct list_node_buffer {
  69.     void_pointer next_buffer;
  70.     link_type buffer;
  71.     };
  72. public:
  73.     typedef Allocator<list_node_buffer> buffer_allocator_type;
  74.     typedef Allocator<list_node_buffer>::pointer buffer_pointer;     
  75. protected:
  76.     static Allocator<list_node_buffer> buffer_allocator;
  77.     static buffer_pointer buffer_list;
  78.     static link_type free_list;
  79.     static link_type next_avail;
  80.     static link_type last;
  81.     void add_new_buffer() {
  82.     buffer_pointer tmp = buffer_allocator.allocate((size_type)1);
  83.     tmp->buffer = list_node_allocator.allocate(buffer_size());
  84.     tmp->next_buffer = buffer_list;
  85.     buffer_list = tmp;
  86.     next_avail = buffer_list->buffer;
  87.     last = next_avail + buffer_size();
  88.     }
  89.     static size_type number_of_lists;
  90.     void deallocate_buffers();
  91.     link_type get_node() {
  92.     link_type tmp = free_list;
  93.     return free_list ? (free_list = (link_type)(free_list->next), tmp) 
  94.         : (next_avail == last ? (add_new_buffer(), next_avail++) 
  95.         : next_avail++);
  96.     // ugly code for inlining - avoids multiple returns
  97.     }
  98.     void put_node(link_type p) {
  99.     p->next = free_list;
  100.     free_list = p;
  101.     }
  102. #endif
  103.  
  104.     link_type node;
  105.     size_type length;
  106. public:
  107.     class iterator;
  108.     class const_iterator;
  109.     class iterator : public bidirectional_iterator<T, difference_type> {
  110.     friend class list<T>;
  111.     friend class const_iterator;
  112. //  friend bool operator==(const iterator& x, const iterator& y);
  113.     protected:
  114.     link_type node;
  115.     iterator(link_type x) : node(x) {}
  116.     public:
  117.     iterator() {}
  118.     bool operator==(const iterator& x) const { return node == x.node; }
  119.     reference operator*() const { return (*node).data; }
  120.     iterator& operator++() { 
  121.         node = (link_type)((*node).next);
  122.         return *this;
  123.     }
  124.     iterator operator++(int) { 
  125.         iterator tmp = *this;
  126.         ++*this;
  127.         return tmp;
  128.     }
  129.     iterator& operator--() { 
  130.         node = (link_type)((*node).prev);
  131.         return *this;
  132.     }
  133.     iterator operator--(int) { 
  134.         iterator tmp = *this;
  135.         --*this;
  136.         return tmp;
  137.     }
  138.     };
  139.     class const_iterator : public bidirectional_iterator<T, difference_type> {
  140.     friend class list<T>;
  141.     protected:
  142.     link_type node;
  143.     const_iterator(link_type x) : node(x) {}
  144.     public:     
  145.     const_iterator() {}
  146.     const_iterator(const iterator& x) : node(x.node) {}
  147.     bool operator==(const const_iterator& x) const { return node == x.node; } 
  148.     const_reference operator*() const { return (*node).data; }
  149.     const_iterator& operator++() { 
  150.         node = (link_type)((*node).next);
  151.         return *this;
  152.     }
  153.     const_iterator operator++(int) { 
  154.         const_iterator tmp = *this;
  155.         ++*this;
  156.         return tmp;
  157.     }
  158.     const_iterator& operator--() { 
  159.         node = (link_type)((*node).prev);
  160.         return *this;
  161.     }
  162.     const_iterator operator--(int) { 
  163.         const_iterator tmp = *this;
  164.         --*this;
  165.         return tmp;
  166.     }
  167.     };
  168.     typedef reverse_bidirectional_iterator<const_iterator, value_type,
  169.                                            const_reference, difference_type>
  170.     const_reverse_iterator;
  171.     typedef reverse_bidirectional_iterator<iterator, value_type, reference,
  172.                                            difference_type>
  173.         reverse_iterator; 
  174.     list() : length(0) {
  175. #ifndef __GNUG__
  176.     ++number_of_lists;
  177. #endif
  178.     node = get_node();
  179.     (*node).next = node;
  180.     (*node).prev = node;
  181.     }
  182.     iterator begin() { return (link_type)((*node).next); }
  183.     const_iterator begin() const { return (link_type)((*node).next); }
  184.     iterator end() { return node; }
  185.     const_iterator end() const { return node; }
  186.     reverse_iterator rbegin() { return reverse_iterator(end()); }
  187.     const_reverse_iterator rbegin() const { 
  188.         return const_reverse_iterator(end()); 
  189.     }
  190.     reverse_iterator rend() { return reverse_iterator(begin()); }
  191.     const_reverse_iterator rend() const { 
  192.         return const_reverse_iterator(begin());
  193.     } 
  194.     bool empty() const { return length == 0; }
  195.     size_type size() const { return length; }
  196. #ifndef __GNUG__
  197.     size_type max_size() const { return list_node_allocator.max_size(); }
  198. #endif
  199.     reference front() { return *begin(); }
  200.     const_reference front() const { return *begin(); }
  201.     reference back() { return *(--end()); }
  202.     const_reference back() const { return *(--end()); }
  203.     void swap(list<T>& x) {
  204.     ::swap(node, x.node);
  205.     ::swap(length, x.length);
  206.     }
  207.     iterator insert(iterator position, const T& x) {
  208.     link_type tmp = get_node();
  209. #ifdef __GNUG__
  210.     construct(&(*tmp).data, x);
  211. #else
  212.     construct(value_allocator.address((*tmp).data), x);
  213. #endif
  214.     (*tmp).next = position.node;
  215.     (*tmp).prev = (*position.node).prev;
  216.     (*(link_type((*position.node).prev))).next = tmp;
  217.     (*position.node).prev = tmp;
  218.     ++length;
  219.     return tmp;
  220.     }
  221. #ifdef __GNUG__
  222.     void insert(iterator position, const T* first, const T* last) {
  223.     while (first != last) insert(position, *first++);
  224.     }
  225.     void insert(iterator position, const_iterator first,
  226.         const_iterator last) {
  227.         while (first != last) insert(position, *first++);
  228.     }
  229.     void insert(iterator position, size_type n, const T& x) {
  230.     while (n--) insert(position, x);
  231.     }
  232. #else
  233.     void insert(iterator position, const T* first, const T* last);
  234.     void insert(iterator position, const_iterator first,
  235.         const_iterator last);
  236.     void insert(iterator position, size_type n, const T& x);
  237. #endif
  238.     void push_front(const T& x) { insert(begin(), x); }
  239.     void push_back(const T& x) { insert(end(), x); }
  240.     void erase(iterator position) {
  241.     (*(link_type((*position.node).prev))).next = (*position.node).next;
  242.     (*(link_type((*position.node).next))).prev = (*position.node).prev;
  243. #ifdef __GNUG__
  244.     destroy(&(*position.node).data);
  245. #else
  246.     destroy(value_allocator.address((*position.node).data));
  247. #endif
  248.     put_node(position.node);
  249.     --length;
  250.     }
  251. #ifdef __GNUG__
  252.     void erase(iterator first, iterator last) {
  253.     while (first != last) erase(first++);
  254.     }
  255. #else
  256.     void erase(iterator first, iterator last);
  257. #endif
  258.     void pop_front() { erase(begin()); }
  259.     void pop_back() { 
  260.     iterator tmp = end();
  261.     erase(--tmp);
  262.     }
  263.     list(size_type n, const T& value = T()) : length(0) {
  264. #ifndef __GNUG__
  265.     ++number_of_lists;
  266. #endif
  267.     node = get_node();
  268.     (*node).next = node;
  269.     (*node).prev = node;
  270.     insert(begin(), n, value);
  271.     }
  272.     list(const T* first, const T* last) : length(0) {
  273. #ifndef __GNUG__
  274.     ++number_of_lists;
  275. #endif
  276.     node = get_node();
  277.     (*node).next = node;
  278.     (*node).prev = node;
  279.     insert(begin(), first, last);
  280.     }
  281.     list(const list<T>& x) : length(0) {
  282. #ifndef __GNUG__
  283.     ++number_of_lists;
  284. #endif
  285.     node = get_node();
  286.     (*node).next = node;
  287.     (*node).prev = node;
  288.     insert(begin(), x.begin(), x.end());
  289.     }
  290.     ~list() {
  291.     erase(begin(), end());
  292.     put_node(node);
  293. #ifndef __GNUG__
  294.     if (--number_of_lists == 0) deallocate_buffers();
  295. #endif
  296.     }
  297.     list<T>& operator=(const list<T>& x);
  298. protected:
  299.     void transfer(iterator position, iterator first, iterator last) {
  300.     (*(link_type((*last.node).prev))).next = position.node;
  301.     (*(link_type((*first.node).prev))).next = last.node;
  302.     (*(link_type((*position.node).prev))).next = first.node;  
  303.     link_type tmp = link_type((*position.node).prev);
  304.     (*position.node).prev = (*last.node).prev;
  305.     (*last.node).prev = (*first.node).prev; 
  306.     (*first.node).prev = tmp;
  307.     }
  308. public:
  309.     void splice(iterator position, list<T>& x) {
  310.     if (!x.empty()) {
  311.         transfer(position, x.begin(), x.end());
  312.         length += x.length;
  313.         x.length = 0;
  314.     }
  315.     }
  316.     void splice(iterator position, list<T>& x, iterator i) {
  317.     iterator j = i;
  318.     if (position == i || position == ++j) return;
  319.     transfer(position, i, j);
  320.     ++length;
  321.     --x.length;
  322.     }
  323.     void splice(iterator position, list<T>& x, iterator first, iterator last) {
  324.     if (first != last) {
  325.         if (&x != this) {
  326.         difference_type n = 0;
  327.             distance(first, last, n);
  328.             x.length -= n;
  329.             length += n;
  330.         }
  331.         transfer(position, first, last);
  332.     }
  333.     }
  334.     void remove(const T& value);
  335.     void unique();
  336.     void merge(list<T>& x);
  337.     void reverse();
  338.     void sort();
  339. #ifdef __GNUG__
  340.     friend difference_type* distance_type(const iterator&) {
  341.     return (difference_type*)(0);
  342.     }
  343.     friend T* value_type(const iterator&) {
  344.     return (T*)(0);
  345.     }
  346.     friend bidirectional_iterator_tag iterator_category(iterator) {
  347.     return bidirectional_iterator_tag();
  348.     }
  349. #endif
  350. };
  351.  
  352. #ifndef __GNUG__
  353. template <class T>
  354. list<T>::buffer_pointer list<T>::buffer_list = 0;
  355.  
  356. template <class T>
  357. list<T>::link_type list<T>::free_list = 0;
  358.  
  359. template <class T>
  360. list<T>::link_type list<T>::next_avail = 0;
  361.  
  362. template <class T>
  363. list<T>::link_type list<T>::last = 0;
  364.  
  365. template <class T>
  366. list<T>::size_type list<T>::number_of_lists = 0;
  367.  
  368. template <class T>
  369. list<T>::list_node_allocator_type list<T>::list_node_allocator;
  370.  
  371. template <class T>
  372. list<T>::value_allocator_type list<T>::value_allocator;
  373.  
  374. template <class T>
  375. list<T>::buffer_allocator_type list<T>::buffer_allocator;
  376. #endif
  377.  
  378. /* 
  379.  * currently the following does not work - made into a member function
  380.  
  381. template <class T>
  382. inline bool operator==(const list<T>::iterator& x, const list<T>::iterator& y) { 
  383.     return x.node == y.node; 
  384. }
  385. */
  386.  
  387. template <class T>
  388. inline bool operator==(const list<T>& x, const list<T>& y) {
  389.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  390. }
  391.  
  392. template <class T>
  393. inline bool operator<(const list<T>& x, const list<T>& y) {
  394.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  395. }
  396.  
  397. #ifndef __GNUG__
  398. template <class T>
  399. void list<T>::deallocate_buffers() {
  400.     while (buffer_list) {
  401.     buffer_pointer tmp = buffer_list;
  402.     buffer_list = (buffer_pointer)(buffer_list->next_buffer);
  403.     list_node_allocator.deallocate(tmp->buffer);
  404.     buffer_allocator.deallocate(tmp);
  405.     }
  406.     free_list = 0;
  407.     next_avail = 0;
  408.     last = 0;
  409. }
  410. #endif
  411.  
  412. #ifndef __GNUG__
  413. template <class T>
  414. void list<T>::insert(iterator position, const T* first, const T* last) {
  415.     while (first != last) insert(position, *first++);
  416. }
  417.      
  418. template <class T>
  419. void list<T>::insert(iterator position, const_iterator first,
  420.              const_iterator last) {
  421.     while (first != last) insert(position, *first++);
  422. }
  423.  
  424. template <class T>
  425. void list<T>::insert(iterator position, size_type n, const T& x) {
  426.     while (n--) insert(position, x);
  427. }
  428.  
  429. template <class T>
  430. void list<T>::erase(iterator first, iterator last) {
  431.     while (first != last) erase(first++);
  432. }
  433. #endif
  434.  
  435. template <class T>
  436. list<T>& list<T>::operator=(const list<T>& x) {
  437.     if (this != &x) {
  438.     iterator first1 = begin();
  439.     iterator last1 = end();
  440.     const_iterator first2 = x.begin();
  441.     const_iterator last2 = x.end();
  442.     while (first1 != last1 && first2 != last2) *first1++ = *first2++;
  443.     if (first2 == last2)
  444.         erase(first1, last1);
  445.     else
  446.         insert(last1, first2, last2);
  447.     }
  448.     return *this;
  449. }
  450.  
  451. template <class T>
  452. void list<T>::remove(const T& value) {
  453.     iterator first = begin();
  454.     iterator last = end();
  455.     while (first != last) {
  456.     iterator next = first;
  457.     ++next;
  458.     if (*first == value) erase(first);
  459.     first = next;
  460.     }
  461. }
  462.  
  463. template <class T>
  464. void list<T>::unique() {
  465.     iterator first = begin();
  466.     iterator last = end();
  467.     if (first == last) return;
  468.     iterator next = first;
  469.     while (++next != last) {
  470.     if (*first == *next)
  471.         erase(next);
  472.     else
  473.         first = next;
  474.     next = first;
  475.     }
  476. }
  477.  
  478. template <class T>
  479. void list<T>::merge(list<T>& x) {
  480.     iterator first1 = begin();
  481.     iterator last1 = end();
  482.     iterator first2 = x.begin();
  483.     iterator last2 = x.end();
  484.     while (first1 != last1 && first2 != last2)
  485.     if (*first2 < *first1) {
  486.         iterator next = first2;
  487.         transfer(first1, first2, ++next);
  488.         first2 = next;
  489.     } else
  490.         ++first1;
  491.     if (first2 != last2) transfer(last1, first2, last2);
  492.     length += x.length;
  493.     x.length= 0;
  494. }
  495.  
  496. template <class T>
  497. void list<T>::reverse() {
  498.     if (size() < 2) return;
  499.     for (iterator first = ++begin(); first != end();) {
  500.     iterator old = first++;
  501.     transfer(begin(), old, first);
  502.     }
  503. }    
  504.  
  505. template <class T>
  506. void list<T>::sort() {
  507.     if (size() < 2) return;
  508.     list<T> carry;
  509.     list<T> counter[64];
  510.     int fill = 0;
  511.     while (!empty()) {
  512.     carry.splice(carry.begin(), *this, begin());
  513.     int i = 0;
  514.     while(i < fill && !counter[i].empty()) {
  515.         counter[i].merge(carry);
  516.         carry.swap(counter[i++]);
  517.     }
  518.     carry.swap(counter[i]);         
  519.     if (i == fill) ++fill;
  520.     } 
  521.     while(fill--) merge(counter[fill]);
  522. }
  523.  
  524. #undef Allocator
  525. #undef list
  526.  
  527. #endif
  528.