Using Interfaces for Object Oriented Primitives

// (C) Copyright Chrstopher Diggins 2004 http://www.cdiggins.com 
// Distributed under the Boost Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt.)
//
// Disclaimer: Not a Boost library

namespace ootl
{
  template<typename Elem_T> class ISequence;
  template<typename Elem_T> class IList;
  
  //==========================================================================================
  // iterators
  
  template<typename Elem_T>
  BOOST_IDL_BEGIN1(IIterator)
    BOOST_IDL_FN0(IsAtEnd, Bool)
    BOOST_IDL_FN0(Get, Elem_T&)
    BOOST_IDL_FN0(GotoNext, void)
    BOOST_IDL_FN0(GotoFirst, void)
  BOOST_IDL_END1(IIterator)
    
  template<typename Elem_T>
  BOOST_IDL_BEGIN1(IListIterator)
    BOOST_IDL_EXTENDS(IIterator<Elem_T>)
    BOOST_IDL_FN0(Delete, void)
    BOOST_IDL_FN0(Insert, void)
  BOOST_IDL_END1(IListIterator)

  //==========================================================================================
  // iterator implementations 
  
  template<typename Elem_T>
  struct Iter
  {
    Iter(ISequence<Elem_T> seq) : m(seq) { }    
    Elem_T& Get() { 
      return m.GetAt(this); 
    }
    void GotoNext() { 
      m.MoveToNext(this); 
    }
    void GotoFirst() { 
      m.MoveToFirst(this); 
    }
    Bool IsAtEnd() { 
      return m.IsAtEnd(this); 
    }
    ISequence<Elem_T> m;
    void* mpObject; // typically holds a node
    UInt mnIndex; // used to hold some kind of index 
  }; 
  
  template<typename Elem_T>
  struct ListIter 
  {
    ListIter(IList<Elem_T> list) : m(list) { }
    Elem_T& Get() { 
     return m.GetAt(this); 
    }
    void GotoNext() { 
      m.MoveToNext(this); 
    }
    void GotoFirst() { 
      m.MoveToFirst(this); 
    }
    void Insert() { 
      m.InsertAt(this); 
    }
    void Delete() { 
      m.DeleteAt(this); 
    }
    Bool IsAtEnd() { 
      return m.IsAtEnd(this); 
    }
    IList<Elem_T> m;
    void* mpObject; // typically holds a node
    UInt mnIndex; // used to hold some kind of index 
  };  
  
  //==========================================================================================
  // basic collection interfaces

  template<typename Elem_T>
  BOOST_IDL_BEGIN1(IStack)
    BOOST_IDL_FN1(Push, void, (const Elem_T&, x))
    BOOST_IDL_FN0(Pop, const Elem_T&)
    BOOST_IDL_FN0(Peek, const Elem_T&)
    BOOST_IDL_FN0(IsEmpty, Bool)
  BOOST_IDL_END1(IStack)      
  
  template<typename Elem_T>
  BOOST_IDL_BEGIN1(ISizedStack)    
    BOOST_IDL_EXTENDS(IStack<Elem_T>)    
    BOOST_IDL_FN0(IsFull, Bool)
  BOOST_IDL_END1(ISizedStack)
  
  template<typename Elem_T>
  BOOST_IDL_BEGIN1(IQueue)
    BOOST_IDL_FN1(Push, void, (const Elem_T&, x))
    BOOST_IDL_FN0(Pop, const Elem_T&)
    BOOST_IDL_FN0(Peek, const Elem_T&)
    BOOST_IDL_FN0(IsEmpty, Bool)
  BOOST_IDL_END1(IQueue)    
     
  template<typename Elem_T>
  BOOST_IDL_BEGIN1(ISizedQueue)    
    BOOST_IDL_EXTENDS(IQueue<Elem_T>)    
    BOOST_IDL_FN0(IsFull, Bool)
  BOOST_IDL_END1(ISizedQueue)  
  
  template<typename Elem_T>
  BOOST_IDL_BEGIN1(IDeque)
    BOOST_IDL_FN1(PushFront, void, (const Elem_T&, x))
    BOOST_IDL_FN1(PushBack, void, (const Elem_T&, x))
    BOOST_IDL_FN0(PopFront, const Elem_T&)
    BOOST_IDL_FN0(PopBack, const Elem_T&)
    BOOST_IDL_FN0(PeekFront, const Elem_T&)
    BOOST_IDL_FN0(PeekBack, const Elem_T&)
    BOOST_IDL_FN0(IsEmpty, Bool)
  BOOST_IDL_END1(IDeque)    

  template<typename Elem_T>
  BOOST_IDL_BEGIN1(ISizedDeque)    
    BOOST_IDL_EXTENDS(IDeque<Elem_T>)    
    BOOST_IDL_FN0(IsFull, Bool)
  BOOST_IDL_END1(ISizedDeque)
  
  //==========================================================================================
  // sequence interfaces
 
  template<typename Elem_T> 
  BOOST_IDL_BEGIN1(ISequence)
    BOOST_IDL_FN0(GetIter, Iter<Elem_T>)
    BOOST_IDL_FN1(IsAtEnd, Bool, (Iter<Elem_T>*, i))
    BOOST_IDL_FN1(GetAt, Elem_T&, (Iter<Elem_T>*, i))
    BOOST_IDL_FN1(MoveToNext, void, (Iter<Elem_T>*, i))
    BOOST_IDL_FN1(MoveToFirst, void, (Iter<Elem_T>*, i))
  BOOST_IDL_END1(ISequence) 
         
  //==========================================================================================
  // list interfaces 
  
  template<typename Elem_T> 
  BOOST_IDL_BEGIN1(IList)
    BOOST_IDL_FN0(GetListIter, ListIter<Elem_T>)
    BOOST_IDL_FN1(IsAtEnd, Bool, (ListIter<Elem_T>*, i))
    BOOST_IDL_FN1(GetAt, Elem_T&, (ListIter<Elem_T>*, i))
    BOOST_IDL_FN1(MoveToNext, void, (ListIter<Elem_T>*, i))
    BOOST_IDL_FN1(MoveToFirst, void, (ListIter<Elem_T>*, i))
    BOOST_IDL_FN1(DeleteAt, void, (ListIter<Elem_T>*, i))
    BOOST_IDL_FN1(InsertAt, void, (ListIter<Elem_T>*, i)) 
  BOOST_IDL_END1(IList)  
    
  //==========================================================================================
  // array interfaces
  
  template<typename Elem_T>
  BOOST_IDL_BEGIN1(IArray)
    BOOST_IDL_FN1(ElementAt, Elem_T&, (UInt, index))
    BOOST_IDL_FN0(Count, UInt)
  BOOST_IDL_END1(IArray)
 
  template<typename Elem_T>
  BOOST_IDL_BEGIN1(IDynamicArray)
    BOOST_IDL_EXTENDS(IArray<Elem_T>)
    BOOST_IDL_FN1(Resize, void, (UInt, x))
  BOOST_IDL_END1(IDynamicArray)

  //==========================================================================================
  // misc. collection interfaces
  
  BOOST_IDL_BEGIN(IComparableCollection)
    BOOST_IDL_FN2(Swap, void, (UInt, index1), (UInt, index2))
    BOOST_IDL_FN2(Compare, Int, (UInt, index1), (UInt, index2))
    BOOST_IDL_FN0(Count, UInt)
  BOOST_IDL_END(IComparableCollection)
  
  //==========================================================================================
  // array implementations 

  template<typename Elem_T>
  struct Array_impl
  {
    // type identities 
    typedef Array_impl<Elem_T> self;
    // ctors
    Array_impl(const Int& x) : m(x) { };
    Array_impl(const Array_impl& x) : m(x.m) { };
    // IArray implementation
    Elem_T& ElementAt(UInt x) { return m.at(x); }
    UInt Count() { return static_cast<UInt>(m.size()); }
  private:
    std::vector<Elem_T> m; 
  };

  template<typename Elem_T, unsigned int Size_N>
  struct StaticArray_impl
  {
    // type identities 
    typedef StaticArray_impl<Elem_T, Size_N> self;
    // ctors
    StaticArray_impl() { };
    // IArray implementation
    Elem_T& ElementAt(UInt x) { return m[x.ToPrimitive()]; }
    UInt Count() { return Size_N; }
  private:
    Elem_T m[Size_N]; 
  };

  template<typename Array_T, typename Elem_T>
  struct Array_contract : public Array_T 
  {
    // type identities 
    typedef Array_T inherited;
    // constructor
    Array_contract() { };
    template<typename Arg_T> Array_contract(const Arg_T& x) : inherited(X) { };
    // contract verification
    Elem_T& ElementAt(UInt x) { PRE(x < Count()); return inherited::ElementAt(x); }    
  };
  
  template<typename Array_T, typename Elem_T>
  struct Array_ext : public Array_T
  {
    // type identities
    typedef Array_ext<Array_T, Elem_T> self;
    typedef Array_T inherited;
    // constructor
    template<typename Arg_T> Array_ext(const Arg_T& x) : inherited(X) { };
    Array_ext() { }
    // ISequence implementation
    Iter<Elem_T> GetIter() { Iter<Elem_T> i(self); return i; }    
    Bool IsAtEnd(Iter<Elem_T>* x) { return x->mnIndex == Count(); }
    void MoveToNext(Iter<Elem_T>* x) { x->mnIndex++; }
    void MoveToFirst(Iter<Elem_T>* x) { x->mnIndex = 0; }
    // operators
    Elem_T& operator[](UInt x) { return inherited::ElementAt(x); }
  };
        
  template<typename Array_T, typename Elem_T>
  struct Array_wrapper 
  {
    #ifdef APPLY_CONTRACTS
      typedef Array_ext<Array_contract<Array_T, Elem_T>, Elem_T> type;
    #else
      typedef Array_ext<Array_T, Elem_T> type;
    #endif
  };
  
  template<typename Elem_T>
  struct Array : public Array_wrapper<Array_impl<Elem_T>, Elem_T>::type
  {
    typedef typename Array_wrapper<Array_impl<Elem_T>, Elem_T>::type inherited; 
    template<typename Arg_T> Array(const Arg_T& x) : inherited(x) { }
  }; 
  
  template<typename Elem_T, unsigned int Size_N>
  struct StaticArray : public Array_wrapper<StaticArray_impl<Elem_T, Size_N>, Elem_T>::type
  {
    typedef typename Array_wrapper<StaticArray_impl<Elem_T, Size_N>, Elem_T>::type inherited; 
    StaticArray() { }
  }; 
  
  //==========================================================================================
  // list implementations 
  
  template<typename Elem_T>
  struct ListNode 
  {
    ListNode(const Elem_T& x) : mData(x), mpNext(NULL) { }
    ListNode() : mpNext(NULL) { }
    Elem_T mData;
    ListNode<Elem_T>* mpNext;
  }; 
  
  template<typename Elem_T> 
  struct List_impl 
  {
    // ctor
    List_impl() { 
    }
    // dtor
    ~List_impl() {
      ListNode<Elem_T>* pCur = mHead.mpNext;
      while (pCur != NULL) {
        ListNode<Elem_T>* pTmp = pCur->mpNext;
        delete pCur;
        pCur = pTmp;
      }
    }
    // IList implementation
    ListIter<Elem_T> GetListIter() { 
      ListIter<Elem_T> ret(*this); 
      ret.mpObject = &mHead;
      return ret;
    }    
    ListNode<Elem_T>* IterToNode(ListIter<Elem_T>* iter) {
      return static_cast<ListNode<Elem_T>*>(iter->mpObject);
    }
    Bool IsAtEnd(ListIter<Elem_T>* iter) { 
      return IterToNode(iter)->mpNext == NULL; 
    }
    void MoveToNext(ListIter<Elem_T>* iter) { 
      iter->mpObject = IterToNode(iter)->mpNext; 
    }
    void MoveToFirst(ListIter<Elem_T>* iter) { 
      iter->mpObject = &mHead;
    }    
    void InsertAt(ListIter<Elem_T>* iter) {  
      ListNode<Elem_T>* pTmp = IterToNode(iter)->mpNext; 
      IterToNode(iter)->mpNext = new ListNode<Elem_T>(); 
      IterToNode(iter)->mpNext->mpNext = pTmp;
    }
    void DeleteAt(ListIter<Elem_T>* iter) { 
      ListNode<Elem_T>* pTmp = IterToNode(iter)->mpNext; 
      ListNode<Elem_T>* pNext = pTmp->mpNext; 
      delete pTmp; 
      IterToNode(iter)->mpNext = pNext;
    }
    Elem_T& GetAt(ListIter<Elem_T>* iter) {
      return IterToNode(iter)->mpNext->mData;
    }
  private:
    ListNode<Elem_T> mHead;
  };
    
  template<typename List_T, typename Elem_T>
  struct List_contract : public List_T
  {
    // type identities
    typedef List_contract<List_T, Elem_T> self;
    typedef List_T inherited;
    // ctor
    List_contract() { }
    // IList contract verification
    void MoveToNext(ListIter<Elem_T>* iter) { 
      PRE(!iter->IsAtEnd()); 
      inherited::MoveToNext(iter); 
    }
    void InsertAt(ListIter<Elem_T>* iter) { 
      PRE(!iter->IsAtEnd()); 
      inherited::InsertAt(iter); 
    }      
    void DeleteAt(ListIter<Elem_T>* iter) { 
      PRE(!iter->IsAtEnd()); 
      inherited::DeleteAt(iter); 
    }
    Elem_T& GetAt(ListIter<Elem_T>* iter) { 
      PRE(!iter->IsAtEnd()); 
      return inherited::GetAt(iter); 
    }
    void MoveToNext(Iter<Elem_T>* iter) { 
      PRE(!iter->IsAtEnd()); 
      inherited::MoveToNext(iter); 
    } 
    Elem_T& GetAt(Iter<Elem_T>* iter) { 
      PRE(!iter->IsAtEnd()); 
      return inherited::GetAt(iter, x); 
    }
  };

  template<typename List_T, typename Elem_T>
  struct List_ext : public List_T
  {
    // type identities
    typedef List_ext<List_T, Elem_T> self;
    typedef List_T inherited;
    // ctor
    List_ext() { }
    // IStack implementation 
    const Elem_T& Peek() { 
      return GetHead(); 
    }
    const Elem_T& Pop() { 
      const Elem_T& ret = Peek(); 
      DeleteHead(); 
      return ret; 
    }
    void PushFront(const Elem_T& x) { 
      GetListIter().Insert(x) 
    }
    Bool IsEmpty() { 
      return GetListIter().IsAtEnd(); 
    }
    // Useful functions 
    Elem_T& GetHead() { 
      return GetListIter().Get(); 
    } 
    void DeleteHead() { 
      GetListIter().Delete(); 
    }
    void InsertHead() { 
      GetListIter().Insert(); 
    }  
    void InsertHead(const Elem_T& x) { 
      GetListIter().Insert(); 
      GetHead() = x;
    }  
  };
  
  template<typename List_T, typename Elem_T>
  struct List_wrapper 
  {
    #ifdef APPLY_CONTRACTS
      typedef List_ext<List_contract<List_T, Elem_T>, Elem_T> type;
    #else
      typedef List_ext<List_T, Elem_T> type;
    #endif
  };
  
  template<typename Elem_T>
  struct List : public List_wrapper<List_impl<Elem_T>, Elem_T>::type
  {
    typedef typename List_wrapper<List_impl<Elem_T>, Elem_T>::type inherited; 
    template<typename Arg_T> List(const Arg_T& x) : inherited(x) { }
    // ctor
    List() { }
  }; 

  //==========================================================================================
  // queue implementations 

  template<typename Elem_T>
  struct Queue_impl 
  {
    Queue_impl() { }
    // IQueue implementation 
    const Elem_T& Peek() { return m.back(); }
    const Elem_T& Pop() { const Elem_T& ret = Peek(); m.pop_back(); return ret; }
    void Push(const Elem_T& x) { m.push_front(x); }
    Bool IsEmpty() { return m.empty(); }
  private: 
    std::deque<Elem_T> m;
  };
  
  template<typename Queue_T, typename Elem_T>
  struct Queue_contract : public Queue_T 
  {
    // type identities 
    typedef Queue_T inherited;
    // constructor
    Queue_contract() { }
    template<typename Arg_T> Queue_contract(const Arg_T& x) : inherited(X) { };
    // contract verification
    const Elem_T& Pop() { PRE(!IsEmpty()); return inherited::Pop(); }
    const Elem_T& Peek() { PRE(!IsEmpty()); return inherited::Peek(); }
  };  
  
  template<typename Queue_T, typename Elem_T>
  struct Queue_ext : public Queue_T
  {
    Queue_ext() { }
    void Clear() { 
      while (!IsEmpty()) 
        Pop(); 
    }
    void ReverseQueue() {
      Stack<Elem_T> tmp; 
      while (!IsEmpty()) 
        tmp.Push(Pop()); 
      while (!tmp.IsEmpty()) 
        Push(tmp.Pop());
    }
    void MultiPush(const Elem_T& x, UInt cnt) {
      for (UInt i=0; i < cnt; i++) {
        Push(x);
      }
    }
    void MultiPop(UInt cnt) {
      for (UInt i=0; (i < cnt) && !IsEmpty(); i++) {
        Pop();
      }
    }
  }; 
  
  template<typename Queue_T, typename Elem_T>
  struct Queue_wrapper 
  {
    #ifdef APPLY_CONTRACTS
      typedef Queue_ext<Queue_contract<Queue_T, Elem_T>, Elem_T> type;
    #else
      typedef Queue_ext<Queue_T, Elem_T> type;
    #endif
  };
  
  template<typename Elem_T>
  struct Queue : public Queue_wrapper<Queue_impl<Elem_T>, Elem_T>::type
  {
    typedef typename Queue_wrapper<Queue_impl<Elem_T>, Elem_T>::type inherited; 
    template<typename Arg_T> Queue(const Arg_T& x) : inherited(x) { }
    Queue() { }
  }; 

  //==========================================================================================
  // stack implementations   
  
  template<typename Elem_T>
  struct Stack_impl 
  {
    Stack_impl() { }
    // IStack implementation 
    const Elem_T& Peek() { return m.top(); }
    const Elem_T& Pop() { const Elem_T& ret = m.top(); m.pop(); return ret; }
    void Push(const Elem_T& x) { m.push(x); }
    Bool IsEmpty() { return m.empty(); }
  private: 
    std::stack<Elem_T> m;
  };
  
  /*
  template<typename Elem_T>
  struct Stack_impl
  {
    // size of buffers in linked list
    const static int BLOCK_SIZE = 1000;
    Stack_impl() { 
      assert(IsEmpty());
    }
    // IStack implementation 
    const Elem_T& Peek() { 
      assert(!IsEmpty());
      assert(mnIndex > 0);
      return mList.GetHead()[mnIndex - 1]; 
    }
    const Elem_T& Pop() { 
      const Elem_T& ret = Peek();
      --mnIndex;
      if (mnIndex == UInt(0)) { 
        mnIndex = BLOCK_SIZE;
        mList.DeleteHead();
      }
      return ret;
    }
    void Push(const Elem_T& x) {       
      if ((mnIndex == BLOCK_SIZE) || IsEmpty()) {
        mList.InsertHead();
        mnIndex = 0;
      }
      mList.GetHead()[mnIndex] = x;
      mnIndex++;
    }
    Bool IsEmpty() { 
      return mList.IsEmpty(); 
    }
  private:
    List<StaticArray<Elem_T, BLOCK_SIZE> > mList;
    UInt mnIndex;       
  };
  */
  
  template<typename Stack_T, typename Elem_T>
  struct Stack_contract : public Stack_T 
  {
    // type identities 
    typedef Stack_T inherited;
    // constructor
    Stack_contract() { }
    template<typename Arg_T> Stack_contract(const Arg_T& x) : inherited(X) { };
    // contract verification
    const Elem_T& Pop() { PRE(!IsEmpty()); return inherited::Pop(); }
    const Elem_T& Peek() { PRE(!IsEmpty()); return inherited::Peek(); }
  };  
  
  template<typename Stack_T, typename Elem_T>
  struct Stack_ext : public Stack_T
  {
    Stack_ext() { }
    void Clear() { 
      while (!IsEmpty()) 
        Pop(); 
    }
    void SetLast(const Elem_T& x) { 
      Pop(); 
      Push(x); 
    } 
    void ReverseStack() {
      Queue<Elem_T> tmp; 
      while (!IsEmpty()) 
        tmp.Push(Pop()); 
      while (!tmp.IsEmpty()) 
        Push(tmp.Pop()); 
    }
    void MultiPush(const Elem_T& x, UInt cnt) {
      for (UInt i=0; i < cnt; i++) {
        Push(x);
      }
    }
    void MultiPop(UInt cnt) {
      for (UInt i=0; (i < cnt) && !IsEmpty(); i++) {
        Pop();
      }
    }
  }; 
  
  template<typename Stack_T, typename Elem_T>
  struct Stack_wrapper 
  {
    #ifdef APPLY_CONTRACTS
      typedef Stack_ext<Stack_contract<Stack_T, Elem_T>, Elem_T> type;
    #else
      typedef Stack_ext<Stack_T, Elem_T> type;
    #endif
  };
  
  template<typename Elem_T>
  struct Stack : public Stack_wrapper<Stack_impl<Elem_T>, Elem_T>::type
  {
    typedef typename Stack_wrapper<Stack_impl<Elem_T>, Elem_T>::type inherited; 
    template<typename Arg_T> Stack(const Arg_T& x) : inherited(x) { }
    Stack() { }
  }; 

  //==========================================================================================
  // deque implementations 
  
  template<typename Elem_T>
  struct Deque_impl 
  {
    Deque_impl() { }
    // IDeque implementation 
    const Elem_T& PeekFront() { return m.front(); }
    const Elem_T& PopFront() { const Elem_T& ret = PeekFront(); m.pop_front(); return ret; }
    void PushFront(const Elem_T& x) { m.push_front(x); }
    const Elem_T& PeekBack() { return m.back(); }
    const Elem_T& PopBack() { const Elem_T& ret = PeekBack(); m.pop_back(); return ret; }
    void PushBack(const Elem_T& x) { m.push_back(x); }
    Bool IsEmpty() { return m.empty(); }
  private: 
    std::deque<Elem_T> m;
  };
  
  template<typename Deque_T, typename Elem_T>
  struct Deque_contract : public Deque_T 
  {
    // type identities 
    typedef Deque_T inherited;
    // constructor
    Deque_contract() { }
    template<typename Arg_T> Deque_contract(const Arg_T& x) : inherited(X) { };
    // contract verification
    const Elem_T& PopFront() { PRE(!IsEmpty()); return inherited::PopFront(); }
    const Elem_T& PeekFront() { PRE(!IsEmpty()); return inherited::PeekFront(); }
    const Elem_T& PopBack() { PRE(!IsEmpty()); return inherited::PopBack(); }
    const Elem_T& PeekBack() { PRE(!IsEmpty()); return inherited::PeekBack(); }
  };  
  
  template<typename Deque_T, typename Elem_T>
  struct Deque_ext : public Deque_T
  {
    Deque_ext() { }
    void Clear() { 
      while (!IsEmpty()) 
        PopBack(); 
    }
    void MultiPushFront(const Elem_T& x, UInt cnt) {
      for (UInt i=0; i < cnt; i++) {
        PushFront(x);
      }
    }
    void MultiPushBack(const Elem_T& x, UInt cnt) {
      for (UInt i=0; i < cnt; i++) {
        PushFront(x);
      }
    }
    void MultiPop(UInt cnt) {
      for (UInt i=0; (i < cnt) && !IsEmpty(); i++) {
        Pop();
      }
    }
  }; 
  
  template<typename Deque_T, typename Elem_T>
  struct Deque_wrapper 
  {
    #ifdef APPLY_CONTRACTS
      typedef Deque_ext<Deque_contract<Deque_T, Elem_T>, Elem_T> type;
    #else
      typedef Deque_ext<Deque_T, Elem_T> type;
    #endif
  };
  
  template<typename Elem_T>
  struct Deque : public Deque_wrapper<Deque_impl<Elem_T>, Elem_T>::type
  {
    typedef typename Deque_wrapper<Deque_impl<Elem_T>, Elem_T>::type inherited; 
    template<typename Arg_T> Deque(const Arg_T& x) : inherited(x) { }
    Deque() { }
  };   
}