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