advanced search

We Recommend

C++ The Core Language C++ The Core Language
C++: The Core Language is for C programmers transitioning to C++. It's designed to get readers up to speed quickly by covering an essential subset of the language. The subset consists of features without which it's just not C++, and a handful of others that make it a reasonably useful language.

Posted By

kodeape on 12/01/06


Tagged


Versions (?)


Who likes this?

2 people have marked this snippet as a favorite

hkmd
copyleft


Epic Delusions Multimedia API: Base List Template Class [LGPL]...

Published in: C++ 

Plain TextExpand 
  1. /*
  2.     Epic Delusions Multimedia API v0.5
  3.     Cross platform libraries and utilities for multimedia software
  4.     Copyright (C) 1993-2006  Orlando Llanes aka KodeApe
  5.  
  6.     This library is free software; you can redistribute it and/or
  7.     modify it under the terms of the GNU Lesser General Public
  8.     License as published by the Free Software Foundation; either
  9.     version 2.1 of the License, or (at your option) any later version.
  10.  
  11.     This library is distributed in the hope that it will be useful,
  12.     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13.     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14.     Lesser General Public License for more details.
  15.  
  16.     You should have received a copy of the GNU Lesser General Public
  17.     License along with this library; if not, write to the Free Software
  18.     Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  19.  
  20.     E-Mail: "Orlando Llanes" <ollanes@pobox.com>
  21. */
  22. #ifndef edlist_h
  23. #define edlist_h
  24.  
  25.   #include "eddef.h"
  26.   #include "edio.h"
  27.  
  28. /*
  29.  * Base key list object
  30.  */
  31.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy = 16>
  32.   class TEDKeyList
  33.   {
  34.     public:
  35.       TEDKeyList();
  36.       TEDKeyList( edu32 p_nItems );
  37.       virtual ~TEDKeyList();
  38.  
  39.       bool Create( edu32 p_nItems = t_nGrowBy );
  40.       void Destroy();
  41.  
  42.       virtual bool Sort();
  43.  
  44.       edu32 ItemCount();
  45.  
  46.       edu32 FindItem( const TEDKeyID p_Key );
  47.  
  48.       bool GetItem( edu32 p_Index, TEDKeyItem& p_ResItem );
  49.       bool SetItem( edu32 p_Index, TEDKeyItem& p_ResItem );
  50.  
  51.       bool Remove( const TEDKeyID p_Key );
  52.       bool RemoveItem( edu32 p_Index );
  53.  
  54.     protected:
  55.       bool Add( const TEDKeyItem& p_Item );
  56.  
  57.       virtual int Compare( const TEDKeyItem& p_Left,
  58.         const TEDKeyID p_Key );
  59.       virtual int Compare( const TEDKeyItem& p_Left,
  60.         const TEDKeyItem& p_Right );
  61.  
  62.       bool InsertItem( edu32 p_Index );
  63.       bool DeleteItem( edu32 p_Index );
  64.       bool SwapItem( edu32 p_Left, edu32 p_Right );
  65.  
  66.       bool GrowList();
  67.       bool ShrinkList();
  68.  
  69.     protected:
  70.       TEDKeyItem* m_List;
  71.       edu32       m_nItems;
  72.       edu32       m_MaxItems;
  73.   };
  74.  
  75.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy>
  76.   TEDKeyList<TEDKeyItem, TEDKeyID>::TEDKeyList():
  77.     m_List(NULL),
  78.     m_nItems(0),
  79.     m_MaxItems(0)
  80.   {
  81.   }
  82.  
  83.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy>
  84.   TEDKeyList<TEDKeyItem, TEDKeyID>::TEDKeyList( edu32 p_nItems ):
  85.     m_List(NULL),
  86.     m_nItems(0),
  87.     m_MaxItems(0)
  88.   {
  89.       Create( p_nItems );
  90.   }
  91.  
  92.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy>
  93.   TEDKeyList<TEDKeyItem, TEDKeyID>::~TEDKeyList()
  94.   {
  95.     Destroy();
  96.   }
  97.  
  98.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy>
  99.   bool TEDKeyList<TEDKeyItem, TEDKeyID>::Create( edu32 p_nItems )
  100.   {
  101.     Destroy();
  102.  
  103.     if( p_nItems == 0 )
  104.       p_nItems = t_nGrowBy;
  105.  
  106.     m_List = new TEDKeyItem[p_nItems];
  107.     if( m_List == NULL )
  108.       return false;
  109.  
  110.     m_nItems   = 0;
  111.     m_MaxItems = p_nItems;
  112.  
  113.     return true;
  114.   }
  115.  
  116.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy>
  117.   void TEDKeyList<TEDKeyItem, TEDKeyID>::Destroy()
  118.   {
  119.     if( m_List )
  120.       delete[] m_List;
  121.     m_List = NULL;
  122.  
  123.     m_nItems   = 0;
  124.     m_MaxItems = 0;
  125.   }
  126.  
  127.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy>
  128.   bool TEDKeyList<TEDKeyItem, TEDKeyID>::Sort()
  129.   {
  130.     return false;
  131.   }
  132.  
  133.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy>
  134.   edu32 TEDKeyList<TEDKeyItem, TEDKeyID>::ItemCount()
  135.   {
  136.     if( m_nItems <= m_MaxItems )
  137.       return m_nItems;
  138.  
  139.     return ED_INVALID;
  140.   }
  141.  
  142.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy>
  143.   edu32 TEDKeyList<TEDKeyItem, TEDKeyID>::FindItem( const TEDKeyID p_Key )
  144.   {
  145.     edu32         l_Left  = 0;
  146.     edu32         l_Mid   = m_nItems >> 1;
  147.     edu32         l_Right = m_nItems;
  148.     int           l_Code;
  149.  
  150.     if( m_List == NULL )
  151.       return ED_INVALID;
  152.  
  153.     if( m_nItems == 0 )
  154.       return ED_INVALID;
  155.  
  156.     while( l_Left < l_Right )
  157.     {
  158.       l_Code = Compare(m_List[l_Mid], p_Key);
  159.  
  160.       if( l_Code == 0 )
  161.         return l_Mid;
  162.  
  163.       if( l_Code < 0 )
  164.         l_Left = l_Mid + 1;
  165.       else
  166.         l_Right = l_Mid;
  167.  
  168.       l_Mid = (l_Left + l_Right) >> 1;
  169.     }
  170.  
  171.     return ED_INVALID;
  172.   }
  173.  
  174.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy>
  175.   bool TEDKeyList<TEDKeyItem, TEDKeyID>::GetItem( edu32 p_Index, TEDKeyItem& p_ResItem )
  176.   {
  177.     if( (p_Index >= m_nItems) || (&p_ResItem == NULL) )
  178.       return false;
  179.  
  180.     p_ResItem = m_List[p_Index];
  181.  
  182.     return true;
  183.   }
  184.  
  185.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy>
  186.   bool TEDKeyList<TEDKeyItem, TEDKeyID>::SetItem( edu32 p_Index, TEDKeyItem& p_ResItem )
  187.   {
  188.     if( (p_Index >= m_nItems) || (&p_ResItem == NULL) )
  189.       return false;
  190.  
  191.     m_List[p_Index] = p_ResItem;
  192.  
  193.     return true;
  194.   }
  195.  
  196.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy>
  197.   bool TEDKeyList<TEDKeyItem, TEDKeyID>::Remove( const TEDKeyID p_Key )
  198.   {
  199.     edu32 l_Index;
  200.  
  201.     l_Index = FindItem(p_Key);
  202.     if( !DeleteItem(l_Index) )
  203.       return false;
  204.  
  205.     if( m_nItems )
  206.       m_nItems--;
  207.  
  208.     return ShrinkList();
  209.   }
  210.  
  211.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy>
  212.   bool TEDKeyList<TEDKeyItem, TEDKeyID>::RemoveItem( edu32 p_Index )
  213.   {
  214.     if( !DeleteItem(p_Index) )
  215.       return false;
  216.  
  217.     if( m_nItems )
  218.       m_nItems--;
  219.  
  220.     return ShrinkList();
  221.   }
  222.  
  223.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy>
  224.   bool TEDKeyList<TEDKeyItem, TEDKeyID>::Add( const TEDKeyItem& p_Item )
  225.   {
  226.     edu32 l_Left;
  227.     edu32 l_Mid = 0;
  228.     edu32 l_Right;
  229.     int   l_Code;
  230.  
  231.     if( !GrowList() )
  232.       return false;
  233.  
  234.     if( m_nItems == 0 )
  235.       goto Add_SkipSearch;
  236.  
  237.     // Special case last item, no duplicates allowed
  238.     l_Code = Compare(m_List[m_nItems - 1], p_Item);
  239.     if( l_Code == 0 )
  240.       return false;
  241.  
  242.     // If insert position is at end, skip search
  243.     if( l_Code < 0 )
  244.     {
  245.       l_Mid = m_nItems;
  246.       goto Add_SkipSearch;
  247.     }
  248.  
  249.     l_Left  = 0;
  250.     l_Right = m_nItems;
  251.     l_Mid   = (l_Left + l_Right) >> 1;
  252.  
  253.     while( l_Left < l_Right )
  254.     {
  255.       // No duplicates allowed
  256.       l_Code = Compare(m_List[l_Mid], p_Item);
  257.       if( l_Code == 0 )
  258.         return false;
  259.  
  260.       if( l_Code < 0 )
  261.         l_Left = l_Mid + 1;
  262.       else
  263.         l_Right = l_Mid;
  264.  
  265.       l_Mid = (l_Left + l_Right) >> 1;
  266.     }
  267.  
  268.     if( !InsertItem(l_Mid) )
  269.       return false;
  270.  
  271.    Add_SkipSearch:
  272.     m_List[l_Mid] = p_Item;
  273.  
  274.     m_nItems++;
  275.  
  276.     return true;
  277.   }
  278.  
  279.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy>
  280.   int TEDKeyList<TEDKeyItem, TEDKeyID>::Compare( const TEDKeyItem& p_Left,
  281.     const TEDKeyID p_Key )
  282.   {
  283.     return -1;
  284.   }
  285.  
  286.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy>
  287.   int TEDKeyList<TEDKeyItem, TEDKeyID>::Compare( const TEDKeyItem& p_Left,
  288.     const TEDKeyItem& p_Right )
  289.   {
  290.     return -1;
  291.   }
  292.  
  293.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy>
  294.   bool TEDKeyList<TEDKeyItem, TEDKeyID>::InsertItem( edu32 p_Index )
  295.   {
  296.     if( p_Index >= m_nItems )
  297.       return false;
  298.  
  299.     memmove( &m_List[p_Index + 1], &m_List[p_Index],
  300.       (m_nItems - p_Index) * sizeof(TEDKeyItem) );
  301.  
  302.     return true;
  303.   }
  304.  
  305.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy>
  306.   bool TEDKeyList<TEDKeyItem, TEDKeyID>::DeleteItem( edu32 p_Index )
  307.   {
  308.     if( p_Index > m_nItems )
  309.       return false;
  310.  
  311.     memmove( &m_List[p_Index], &m_List[p_Index + 1],
  312.       (m_nItems - p_Index) * sizeof(TEDKeyItem) );
  313.  
  314.     return true;
  315.   }
  316.  
  317.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy>
  318.   bool TEDKeyList<TEDKeyItem, TEDKeyID>::SwapItem( edu32 p_Left, edu32 p_Right )
  319.   {
  320.     TEDKeyItem l_Tmp;
  321.  
  322.     if( m_List == NULL )
  323.       return false;
  324.  
  325.     if( (p_Left >= m_nItems) || (p_Right >= m_nItems) )
  326.       return false;
  327.  
  328.     l_Tmp = m_List[p_Left];
  329.     m_List[p_Left] = m_List[p_Right];
  330.     m_List[p_Right] = l_Tmp;
  331.  
  332.     return true;
  333.   }
  334.  
  335.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy>
  336.   bool TEDKeyList<TEDKeyItem, TEDKeyID>::GrowList()
  337.   {
  338.     TEDKeyItem* l_List;
  339.     edu32       l_MaxItems;
  340.  
  341.     if( m_MaxItems < m_nItems )
  342.       return false;
  343.  
  344.     if( m_nItems == m_MaxItems )
  345.     {
  346.       l_MaxItems = m_nItems + t_nGrowBy;
  347.  
  348.       l_List = new TEDKeyItem[l_MaxItems];
  349.       if( l_List == NULL )
  350.         return false;
  351.  
  352.       if( m_List )
  353.       {
  354.         memcpy( l_List, m_List, m_nItems * sizeof(TEDKeyItem) );
  355.  
  356.         delete[] m_List;
  357.       }
  358.  
  359.       m_List     = l_List;
  360.       m_MaxItems = l_MaxItems;
  361.     }
  362.  
  363.     return true;
  364.   }
  365.  
  366.   template <typename TEDKeyItem, typename TEDKeyID, int t_nGrowBy>
  367.   bool TEDKeyList<TEDKeyItem, TEDKeyID>::ShrinkList()
  368.   {
  369.     TEDKeyItem* l_List;
  370.     edu32       l_MaxItems;
  371.  
  372.     if( m_MaxItems < m_nItems )
  373.       return false;
  374.  
  375.     if( (m_MaxItems - m_nItems) > t_nGrowBy )
  376.     {
  377.       l_MaxItems = m_MaxItems - t_nGrowBy;
  378.  
  379.       l_List = new TEDKeyItem[l_MaxItems];
  380.       if( l_List == NULL )
  381.         return false;
  382.  
  383.       if( m_List )
  384.       {
  385.         memcpy( l_List, m_List, m_nItems * sizeof(TEDKeyItem) );
  386.  
  387.         delete[] m_List;
  388.       }
  389.  
  390.       m_List     = l_List;
  391.       m_MaxItems = l_MaxItems;
  392.     }
  393.  
  394.     return true;
  395.   }
  396.  
  397. #endif

Report this snippet 

You need to login to post a comment.