Static Queue 테스트

앞서 만든 static queue가 잘 동작하는지 몇 가지 테스트를 해 보았다. 먼저, 아래와 같이 queue에 저장할 간단한 데이터 구조를 만들었다.

struct DataItem
{
    DataItem(int key = 0, double value = 0) : m_key(key), m_value(value) {};
    void print() const
    {
        std::cout << "key=" << m_key << ", value=" << m_value << std::endl;
    }
private:
    int m_key;
    double m_value;
};

typedef StaticQueue<DataItem> StaticDataQueue;

그리고, 최대 용량 10개 짜리 dataQue를 만들어서 enqueue와 dequeue 테스트...

//
    StaticDataQueue dataQue(10);
    for(size_t i = 0; i < 100; ++i) {
#if __cplusplus >= 201103L
        dataQue.enqueue(DataItem(i, 0.1 * i)); // call move semantics(-std=c++11)
#else
        dataQue.enqueue(DataItem(i, 10 * i)); // call copy semantics
        //dataQue.enqueue(new DataItem(i, 10 * i)); // OK~!
#endif
        if(i >= dataQue.capacity() - 1 && !dataQue.isEmpty()) {
            DataItem dq_item = dataQue.dequeue();
            std::cout << "Dequeue: ";
            dq_item.print();
        }
    }
    dataQue.print();

Constructor와 Operator 테스트...

//
    dataQue[3] = DataItem(3, 333);

    StaticDataQueue qtmp1(dataQue), qtmp2(100);
    std::cout << "\n<< qtmp1 >>\n";
    qtmp1.print();
    std::cout << "\n<< qtmp2 >>\n";
    qtmp2.print();
 
    qtmp2 = qtmp1;
    std::cout << "\n<< qtmp2 >>\n";
    qtmp2.print();

#if __cplusplus >= 201103L
    StaticDataQueue qtmp3(std::move(qtmp2));
    std::cout << "\n<< qtmp2 >>\n";
    qtmp2.print();
    std::cout << "\n<< qtmp3 >>\n";
    qtmp3.print();
#endif

그럭저럭 잘 동작한다. 위에서 dataQue[3]와 같이 컨테이너의 데이터를 수정하는 것도 바람직하지는 않지만 가능하다. 여기선 단지 index operator를 테스트한 것이다. 메모리 누수도 없고~!

Static Queue

늙어도 심심삼아 코딩 할 수 있도록 소시적 배운 C++의 기억을 회복할 겸  C++ STL deque을 써서 static queue를 만들어 보았다. 임의의 data structure에 대한 pointer 들을 저장하되 정해진 용량까지만 저장한다. Queue size는 가변적이다. enqueue를 시작하면 정해진 용량까지만 채워지고 그 용량을 넘어서면 과거 데이터부터 자동 삭제된다. 또, dequeue할 때마다 size는 하나씩 감소한다. 즉, size는 0 ~ capacity 내에서 유동적이다.

실제 이 static queue를 써먹을 것인지는 중요하지 않다. 여기서는 C++ Class Constructor 기본 개념과 pointer에 대해 빨리 적응하고, 덤으로 C++11에 추가된 move constructor 등에 대해서도 알아 보는데 의의가 있다.

#include <iostream>
#include <deque>

template<typename _Tp>
class StaticQueue
{
public:
    typedef typename std::deque<_Tp*> _Tp_Data;
    typedef typename _Tp_Data::iterator iterator;
    typedef typename _Tp_Data::const_iterator const_iterator;

    // default constructor
    explicit StaticQueue(size_t capa=100) :
        m_size(0), m_capacity(capa)
    {
        m_dequeue_item = new _Tp;
        m_data = new _Tp_Data;
    }

    // destructor
    ~StaticQueue() { destroy(); }

    // copy constructor
    StaticQueue(const StaticQueue& rhs) { copyFrom(rhs); }

    // copy assignment operator
    StaticQueue& operator=(const StaticQueue& rhs)
    {
        if(this!=&rhs) {
            destroy();
            copyFrom(rhs);
        }
        return *this;
    }

#if __cplusplus >= 201103L
    // move constructor: -std=c++11
    StaticQueue(StaticQueue&& rhs) { moveFrom(rhs); }

    // move assignment operator: -std=c++11
    StaticQueue& operator=(StaticQueue&& rhs)
    {
        if(this!=&rhs) {
            destroy();
            moveFrom(rhs);
        }
        return *this;
    }
#endif
   
    // index operator
    const _Tp& operator[](size_t index) const { return *m_data->at(index); }
    _Tp& operator[](size_t index) { return *m_data->at(index); }

    // getters
    size_t size() const { return m_size; }
    size_t capacity() const { return m_capacity; }
    _Tp_Data* data() const { return m_data; }

    // setters
    void setCapacity(size_t size) { m_capacity = size; }

    void enqueue(const _Tp& item);
    void enqueue(_Tp* item);
#if __cplusplus >= 201103L
    // rvalue reference parameter: -std=c++11
    void enqueue(_Tp&& item);
#endif
    const _Tp& dequeue();
    bool isEmpty() const { return !m_size; }

    void print() const;

private:
    void popFront();
    void copyFrom(const StaticQueue& rhs);
    void moveFrom(StaticQueue& rhs);
    void destroy();

    size_t m_size;       // Current queue size
    size_t m_capacity;   // Maximum queue size
    _Tp* m_dequeue_item; // Storage for a dequeued item
    _Tp_Data* m_data;    // Queue container for storing FIFO data
};


template<typename _Tp>
inline void StaticQueue<_Tp>::enqueue(const _Tp& item)
{
    m_data->push_back(new _Tp(item));

    if(++m_size > m_capacity) {
        popFront();
        m_size = m_capacity;
    }
}

template<typename _Tp>
inline void StaticQueue<_Tp>::enqueue(_Tp* item)
{
    m_data->push_back(item);

    if(++m_size > m_capacity) {
        popFront();
        m_size = m_capacity;
    }
}

#if __cplusplus >= 201103L
template<typename _Tp>
inline void StaticQueue<_Tp>::enqueue(_Tp&& item)
{
    m_data->push_back(new _Tp(item));

    if(++m_size > m_capacity) {
        popFront();
        m_size = m_capacity;
    }
}
#endif

template<typename _Tp>
inline const _Tp& StaticQueue<_Tp>::dequeue()
{
    // What if undeflow condition(m_size==0)?
    if(m_size) {
        *m_dequeue_item = *m_data->front();
        popFront();
        --m_size;
    }

    return *m_dequeue_item;
}

template<typename _Tp>
inline void StaticQueue<_Tp>::print() const
{
    std::cout << "\nQueue size/capacity: " << size() << "/" << capacity() << std::endl;

    if(!isEmpty()) {
        int c = 0;
        for(const_iterator i=m_data->begin(); i != m_data->end(); ++i) {
            std::cout << c++ << ": ";
            (*i)->print();
        }
    }
}

template<typename _Tp>
inline void StaticQueue<_Tp>::popFront()
{
    delete m_data->front();
    m_data->pop_front();
}

template<typename _Tp>
inline void StaticQueue<_Tp>::copyFrom(const StaticQueue<_Tp>& rhs)
{
    m_size = rhs.m_size;
    m_capacity = rhs.m_capacity;

    m_dequeue_item = new _Tp(*rhs.m_dequeue_item);

    m_data = new _Tp_Data;
    for(size_t i=0; i < rhs.m_size; ++i) {
        _Tp* item = new _Tp(rhs[i]);
        m_data->push_back(item);
    }
}

template<typename _Tp>
inline void StaticQueue<_Tp>::moveFrom(StaticQueue<_Tp>& rhs)
{
    m_size = rhs.m_size;
    m_capacity = rhs.m_capacity;
    m_dequeue_item = rhs.m_dequeue_item;
    m_data = rhs.m_data;

    rhs.m_size = 0;
    rhs.m_capacity = 0;
    rhs.m_dequeue_item = 0;
    rhs.m_data = 0;        
}

template<typename _Tp>
inline void StaticQueue<_Tp>::destroy()
{
    if(m_dequeue_item) delete m_dequeue_item;
    m_dequeue_item = 0;

    if(!isEmpty()) {
        for(iterator i=m_data->begin(); i != m_data->end();) {
            delete *i;
            i = m_data->erase(i);
        }
    }

    if(m_data) delete m_data;
    m_data = 0;
}

참고 사항

구글 blogger에 소스 코드 삽입시 Syntax Highlighter를 사용하는 방법은 아래의 사이트 참조.
http://oneqonea.blogspot.kr/2012/04/how-do-i-add-syntax-highlighting-to-my.html

우연과 과학

우연

무념무상이었는데 뜬금없이 빌 브라이슨의 "거의 모든 것의 역사"에서 태양계 모든 행성 들의 궤도를 책 한 페이지에 그림으로 표현하기 어렵다는 대목이 떠올랐다. 행성간 거리가 엄청나게 멀리 떨어져 있기 때문에 당연한 것이다.

그런데, 뜬금없다는 것은 공돌이의 직감으로 행성 들의 거리 간에 일정한 관계가 있을지도 모른다는 생각이 들었기 때문이다. 태양으로부터 각 행성까지의 거리를 log 함수로 표현하면 직선이 되지 않을까하는 생각이 들었다.

Wikipedia를 뒤져서 수성에서 해왕성까지 행성들의 거리를 찾아서 LibreOffice Calc에 기록하고 line chart로 ln(거리)를 그려 보았다. 앗, 정말 거의 직선이다. 그런데, 수성 ~ 화성, 목성 ~ 해왕성, 두 개의 기울기가 다른 직선이 그려졌다. 가만히 생각해 보니 화성과 목성 사이에 소행성대(asteroid belt)가 있지 않은가? 그걸 집어 넣으면 수성 ~ 해왕성까지 거의 하나의 직선이 될 수 있었다. Linear regression까지는 귀찮아서 눈 대중으로 chart에서 소행성대 거리의 ln 값을 대충 넣어서 거리를 역산한 후 소행성까지의 거리를 대략 구해 보았다. 또, 직선을 연장해서 명왕성(Kuiper belt)까지의 거리도 대충 계산하였다. 혹시 발견되지 않은 Nibiru 행성 X가 있다면 그 위치도 대략 알 수 있을 것이다. 아래 화면에서 녹색 부분은 눈대중으로 계산한  거리이다.

이제 위에서 얻은 거리 값들을 Wikipedia에서 찾은 값들과 비교해 보기로 하였다. 소행성대와 명왕성까지의 거리가 대충 잘 들어 맞는다. 소행성대는 2.2~3.3AU(1AU는 지구와 태양간 거리)이고 명왕성은 50AU 정도란다.

티티우스-보데의 법칙

헐~! Wikipidia에서 소행성대 거리를 찾아 보다가 위의 발견이 티티우스-보데의 법칙을 재발견한 것이라는 것을 알았다. 소행성대의 세레스도 조물주가 우주를 건축했다면 화성과 목성 사이에 무엇인가가 있어야 한다는 티티우스-보데의 법칙으로부터 발견한 것이었다는...!!!

이제 100AU 근처에서 Nibiru가 발견되길~!!!

과학이라는 것

사실 호기심과 끈기만 있으면 누구나 과학자가 될 수 있다. 다만, 옛날과는 달리 새롭게 발견할 꺼리가 많이 줄어 든 것도 사실이다. 그래도 인간은 모르는게 많기 때문에 새로운 세대들이 실망할 필요는 없을 것이다.

내가 천문학자였다면 왜 행성들이 저렇게 질서 정연한 거리를 두고 태양계에 배치될 수 밖에 없는지에 대해 파고들었겠으나 지금은 언젠가 뜬끔없이 영감이 떠오르기를 바랄 뿐이다.