Mercurial > hg > octave-nkf

comparison liboctave/oct-sort.cc @ 8721:e9cb742df9eb

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
imported patch sort3.diff
author Jaroslav Hajek <highegg@gmail.com>
date Wed, 11 Feb 2009 15:25:53 +0100
parents 314be237cd5b
children d5af326a3ede
comparison
equal deleted inserted replaced
8720:dda421a1f1e6 8721:e9cb742df9eb
95 #endif 95 #endif
96 96
97 #include <cassert> 97 #include <cassert>
98 #include <algorithm> 98 #include <algorithm>
99 #include <cstring> 99 #include <cstring>
100 #include <stack>
100 101
101 #include "lo-mappers.h" 102 #include "lo-mappers.h"
102 #include "quit.h" 103 #include "quit.h"
103 #include "oct-sort.h" 104 #include "oct-sort.h"
105 #include "oct-locbuf.h"
104 106
105 template <class T> 107 template <class T>
106 octave_sort<T>::octave_sort (void) : compare (ascending_compare) 108 octave_sort<T>::octave_sort (void) : compare (ascending_compare)
107 { 109 {
108 merge_init (); 110 merge_init ();
109 merge_getmem (1024);
110 } 111 }
111 112
112 template <class T> 113 template <class T>
113 octave_sort<T>::octave_sort (bool (*comp) (T, T)) : compare (comp) 114 octave_sort<T>::octave_sort (bool (*comp) (T, T)) : compare (comp)
114 { 115 {
115 merge_init (); 116 merge_init ();
116 merge_getmem (1024); 117 }
117 } 118
118 119 template <class T>
120 void
121 octave_sort<T>::set_compare (sortmode mode)
122 {
123 if (mode == ASCENDING)
124 compare = ascending_compare;
125 else if (mode == DESCENDING)
126 compare = descending_compare;
127 else
128 compare = 0;
129 }
130
119 template <class T> 131 template <class T>
120 template <class Comp> 132 template <class Comp>
121 void 133 void
122 octave_sort<T>::binarysort (T *data, octave_idx_type nel, 134 octave_sort<T>::binarysort (T *data, octave_idx_type nel,
123 octave_idx_type start, Comp comp) 135 octave_idx_type start, Comp comp)
1506 1518
1507 template <class T> 1519 template <class T>
1508 void 1520 void
1509 octave_sort<T>::sort (T *data, octave_idx_type nel) 1521 octave_sort<T>::sort (T *data, octave_idx_type nel)
1510 { 1522 {
1523 merge_getmem (1024);
1511 #ifdef INLINE_ASCENDING_SORT 1524 #ifdef INLINE_ASCENDING_SORT
1512 if (compare == ascending_compare) 1525 if (compare == ascending_compare)
1513 sort (data, nel, std::less<T> ()); 1526 sort (data, nel, std::less<T> ());
1514 else 1527 else
1515 #endif 1528 #endif
1516 #ifdef INLINE_DESCENDING_SORT 1529 #ifdef INLINE_DESCENDING_SORT
1517 if (compare == descending_compare) 1530 if (compare == descending_compare)
1518 sort (data, nel, std::greater<T> ()); 1531 sort (data, nel, std::greater<T> ());
1519 else 1532 else
1520 #endif 1533 #endif
1521 if (compare) 1534 if (compare)
1522 sort (data, nel, compare); 1535 sort (data, nel, compare);
1523 } 1536 }
1524 1537
1525 template <class T> 1538 template <class T>
1526 void 1539 void
1527 octave_sort<T>::sort (T *data, octave_idx_type *idx, octave_idx_type nel) 1540 octave_sort<T>::sort (T *data, octave_idx_type *idx, octave_idx_type nel)
1528 { 1541 {
1542 merge_getmemi (1024);
1529 #ifdef INLINE_ASCENDING_SORT 1543 #ifdef INLINE_ASCENDING_SORT
1530 if (compare == ascending_compare) 1544 if (compare == ascending_compare)
1531 sort (data, idx, nel, std::less<T> ()); 1545 sort (data, idx, nel, std::less<T> ());
1532 else 1546 else
1533 #endif 1547 #endif
1534 #ifdef INLINE_DESCENDING_SORT 1548 #ifdef INLINE_DESCENDING_SORT
1535 if (compare == descending_compare) 1549 if (compare == descending_compare)
1536 sort (data, idx, nel, std::greater<T> ()); 1550 sort (data, idx, nel, std::greater<T> ());
1537 else 1551 else
1538 #endif 1552 #endif
1539 if (compare) 1553 if (compare)
1540 sort (data, idx, nel, compare); 1554 sort (data, idx, nel, compare);
1541 } 1555 }
1556
1557 template <class T> template <class Comp>
1558 bool
1559 octave_sort<T>::is_sorted (const T *data, octave_idx_type nel, Comp comp)
1560 {
1561 const T *end = data + nel;
1562 if (data != end)
1563 {
1564 const T *next = data;
1565 while (++next != end)
1566 {
1567 if (comp (*next, *data))
1568 break;
1569 data = next;
1570 }
1571 data = next;
1572 }
1573
1574 return data == end;
1575 }
1576
1577 template <class T>
1578 bool
1579 octave_sort<T>::is_sorted (const T *data, octave_idx_type nel)
1580 {
1581 bool retval = false;
1582 #ifdef INLINE_ASCENDING_SORT
1583 if (compare == ascending_compare)
1584 retval = is_sorted (data, nel, std::less<T> ());
1585 else
1586 #endif
1587 #ifdef INLINE_DESCENDING_SORT
1588 if (compare == descending_compare)
1589 retval = is_sorted (data, nel, std::greater<T> ());
1590 else
1591 #endif
1592 if (compare)
1593 retval = is_sorted (data, nel, compare);
1594
1595 return retval;
1596 }
1597
1598 // FIXME: is there really no way to make this local to the following function?
1599 struct sortrows_run_t
1600 {
1601 sortrows_run_t (octave_idx_type c, octave_idx_type o, octave_idx_type n)
1602 : col (c), ofs (o), nel (n) { }
1603 octave_idx_type col, ofs, nel;
1604 };
1605
1606
1607 template <class T> template <class Comp>
1608 void
1609 octave_sort<T>::sort_rows (const T *data, octave_idx_type *idx,
1610 octave_idx_type rows, octave_idx_type cols,
1611 Comp comp)
1612 {
1613 OCTAVE_LOCAL_BUFFER (T, buf, rows);
1614 for (octave_idx_type i = 0; i < rows; i++)
1615 idx[i] = i;
1616
1617 if (cols == 0 || rows <= 1)
1618 return;
1619
1620
1621 // This is a breadth-first traversal.
1622 typedef sortrows_run_t run_t;
1623 std::stack<run_t> runs;
1624
1625 runs.push (run_t (0, 0, rows));
1626
1627 while (! runs.empty ())
1628 {
1629 octave_idx_type col = runs.top ().col;
1630 octave_idx_type ofs = runs.top ().ofs;
1631 octave_idx_type nel = runs.top ().nel;
1632 runs.pop ();
1633 assert (nel > 1);
1634
1635 T *lbuf = buf + ofs;
1636 const T *ldata = data + rows*col;
1637 octave_idx_type *lidx = idx + ofs;
1638
1639 // Gather.
1640 for (octave_idx_type i = 0; i < nel; i++)
1641 lbuf[i] = ldata[lidx[i]];
1642
1643 // Sort.
1644 sort (lbuf, lidx, nel, comp);
1645
1646 // Identify constant runs and schedule subsorts.
1647 if (col < cols-1)
1648 {
1649 octave_idx_type lst = 0;
1650 for (octave_idx_type i = 0; i < nel; i++)
1651 {
1652 if (comp (lbuf[lst], lbuf[i]))
1653 {
1654 if (i > lst + 1)
1655 runs.push (run_t (col+1, lst, i - lst));
1656 lst = i;
1657 }
1658 }
1659 if (nel > lst + 1)
1660 runs.push (run_t (col+1, lst, nel - lst));
1661 }
1662 }
1663 }
1664
1665 template <class T>
1666 void
1667 octave_sort<T>::sort_rows (const T *data, octave_idx_type *idx,
1668 octave_idx_type rows, octave_idx_type cols)
1669 {
1670 #ifdef INLINE_ASCENDING_SORT
1671 if (compare == ascending_compare)
1672 sort_rows (data, idx, rows, cols, std::less<T> ());
1673 else
1674 #endif
1675 #ifdef INLINE_DESCENDING_SORT
1676 if (compare == descending_compare)
1677 sort_rows (data, idx, rows, cols, std::greater<T> ());
1678 else
1679 #endif
1680 if (compare)
1681 sort_rows (data, idx, rows, cols, compare);
1682 }
1683
1684 template <class T> template <class Comp>
1685 bool
1686 octave_sort<T>::is_sorted_rows (const T *data, octave_idx_type rows,
1687 octave_idx_type cols, Comp comp)
1688 {
1689 if (rows <= 1 || cols == 0)
1690 return true;
1691
1692 // This is a breadth-first traversal.
1693 const T *lastrow = data + rows*(cols - 1);
1694 typedef std::pair<const T *, octave_idx_type> run_t;
1695 std::stack<run_t> runs;
1696
1697 bool sorted = true;
1698 runs.push (run_t (data, rows));
1699 while (sorted && ! runs.empty ())
1700 {
1701 const T *lo = runs.top ().first;
1702 octave_idx_type n = runs.top ().second;
1703 runs.pop ();
1704 if (lo < lastrow)
1705 {
1706 // Not the final column.
1707 assert (n > 1);
1708 const T *hi = lo + n, *lst = lo;
1709 for (lo++; lo < hi; lo++)
1710 {
1711 if (comp (*lst, *lo))
1712 {
1713 if (lo > lst + 1)
1714 runs.push (run_t (lst + rows, lo - lst));
1715 lst = lo;
1716 }
1717 else if (comp (*lo, *lst))
1718 break;
1719
1720 }
1721 if (lo == hi)
1722 {
1723 if (lo > lst + 1)
1724 runs.push (run_t (lst + rows, lo - lst));
1725 }
1726 else
1727 {
1728 sorted = false;
1729 break;
1730 }
1731 }
1732 else
1733 // The final column - use fast code.
1734 sorted = is_sorted (lo, n, comp);
1735 }
1736
1737 return sorted;
1738 }
1739
1740 template <class T>
1741 bool
1742 octave_sort<T>::is_sorted_rows (const T *data, octave_idx_type rows,
1743 octave_idx_type cols)
1744 {
1745 bool retval = false;
1746
1747 #ifdef INLINE_ASCENDING_SORT
1748 if (compare == ascending_compare)
1749 retval = is_sorted_rows (data, rows, cols, std::less<T> ());
1750 else
1751 #endif
1752 #ifdef INLINE_DESCENDING_SORT
1753 if (compare == descending_compare)
1754 retval = is_sorted_rows (data, rows, cols, std::greater<T> ());
1755 else
1756 #endif
1757 if (compare)
1758 retval = is_sorted_rows (data, rows, cols, compare);
1759
1760 return retval;
1761 }
1762
1542 1763
1543 template <class T> 1764 template <class T>
1544 bool 1765 bool
1545 octave_sort<T>::ascending_compare (T x, T y) 1766 octave_sort<T>::ascending_compare (T x, T y)
1546 { 1767 {