Radegast/Core/Types/ListBoxCustomSort.cs

   1 //
   2 // Radegast Metaverse Client
   3 // Copyright (c) 2009-2014, Radegast Development Team
   4 // All rights reserved.
   5 //
   6 // Redistribution and use in source and binary forms, with or without
   7 // modification, are permitted provided that the following conditions are met:
   8 //
   9 //     * Redistributions of source code must retain the above copyright notice,
  10 //       this list of conditions and the following disclaimer.
  11 //     * Redistributions in binary form must reproduce the above copyright
  12 //       notice, this list of conditions and the following disclaimer in the
  13 //       documentation and/or other materials provided with the distribution.
  14 //     * Neither the name of the application "Radegast", nor the names of its
  15 //       contributors may be used to endorse or promote products derived from
  16 //       this software without specific prior written permission.
  17 //
  18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  19 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  21 // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  22 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  23 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  24 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  25 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  26 // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  27 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28 //
  29 // $Id: ListBoxCustomSort.cs 300 2009-10-05 09:29:46Z latifer@gmail.com $
  30 //
  31 using System;
  32 using System.Collections.Generic;
  33 using System.Windows.Forms;
  34
  35 namespace Radegast
  36 {
  37     public class ListBoxCustomSort : ListBox
  38     {
  39         public ListBoxCustomSort()
  40             : base()
  41         {
  42         }
  43
  44         public void PerformSort()
  45         {
  46             QuickSort(0, Items.Count - 1);
  47         }
  48
  49         private void QuickSort(int left, int right)
  50         {
  51             if (right > left)
  52             {
  53                 int pivotIndex = left;
  54                 int pivotNewIndex = QuickSortPartition(left, right, pivotIndex);
  55
  56                 QuickSort(left, pivotNewIndex - 1);
  57                 QuickSort(pivotNewIndex + 1, right);
  58             }
  59         }
  60
  61         private int QuickSortPartition(int left, int right, int pivot)
  62         {
  63             var pivotValue = (IComparable)Items[pivot];
  64             Swap(pivot, right);
  65
  66             int storeIndex = left;
  67             for (int i = left; i < right; ++i)
  68             {
  69                 if (pivotValue.CompareTo(Items[i]) >= 0)
  70                 {
  71                     Swap(i, storeIndex);
  72                     ++storeIndex;
  73                 }
  74             }
  75
  76             Swap(storeIndex, right);
  77             return storeIndex;
  78         }
  79
  80         private void Swap(int left, int right)
  81         {
  82             var temp = Items[left];
  83             Items[left] = Items[right];
  84             Items[right] = temp;
  85         }
  86     }
  87 }