数値を範囲で表すクラス

ワープロソフトの印刷画面で見たことありませんか？こんな風に数値を指定しているのを。

1,5-7,12

こんな風に数値を指定できるクラスを作ってみました。

// 【 number_list.h 】
#ifndef __NUMBER_LIST_H
#define __NUMBER_LIST_H

#include        <vector>
#include        <cassert>

class number_list
{
  public:
    // 扱う値の型
    typedef int value_type;

  private:
    // 値の範囲の開始と終わりを表す。
    typedef std::pair<value_type, value_type> range;

    // 内部データ構造
    typedef std::vector<range> Imp;

  public:
    // イテレータ(参照用)                                               
    class const_iterator
    {
      public:
        // 扱う値の型
        typedef number_list::value_type value_type;

      protected:
        // データ中の位置を表す型
        typedef number_list::Imp::size_type size_type;

      protected:
        const number_list& data_;       // イテレートの対象となるデータ
        value_type value_;              // 現在参照している値
        size_type index_;               // 現在参照している値のデータ位置

      public:
        const_iterator(const number_list&);

        // 最後の値までイテレートが完了したかどうか
        bool is_end() const;

        // 現在の値を参照する
        value_type get() const;

        // 次の値へ移動する
        void next();
    };

    // イテレータ(参照/削除用)
    class iterator : public const_iterator
    {
      public:
        iterator(number_list&);

        // 現在参照している値を削除する。
        void remove();
    };

  private:

    // 検索用の比較
    struct less_value_area
    {
        // 検索対象の値
        number_list::value_type value_;

        less_value_area(number_list::value_type);
        bool operator()(const number_list::range&) const;
    };

  private:
    // 値のリスト（内部構造）
    Imp data_;

  public:
    // 値を追加する(文字列指定)
    void add(const char*);

    // 値を追加する(値指定)
    void add(value_type);

    // 値を追加する(範囲指定)
    void add(value_type, value_type);

    // 値を追加する(イテレータ指定)
    template<typename T>
    void add(T first, T last)
    {
        for ( ; first != last; ++first)
            data_.push_back(range(*first, *first));
        canonicalize();
    }

    // 値を削除する
    bool remove(value_type);

    // 値を全て削除する
    void clear();

    // 値を文字列で取得する
    std::string get_list() const;

    // イテレータを取得する
    const_iterator get_iterator() const;

    // イテレータを取得する
    iterator get_iterator();

    // 値を含んでいるか
    bool is_contain(value_type) const;

    // 値を入れ替える。
    void swap(number_list&);

  private:
    void canonicalize();

    static std::string to_string(const range&);
    
    friend class number_list::const_iterator;
    friend class number_list::iterator;
    friend struct number_list::less_value_area;
};

#endif

// 【 number_list.cpp 】
#include        "number_list.h"
#include        <algorithm>

namespace
{

void skip_space(const char*& str)
{
    for ( ; isspace(*str) ; str++)
        ;
}
int get_value(const char*& str)
{
    skip_space(str);

    char* end;
    int sign = 1;
    if (*str == _T('-')) {
        sign = -1;
        str++;
    }
    if (!isdigit(*str))
        throw std::invalid_argument("");
    
    const long value = sign*strtol(str, &end, 10);
    str = end;

    return value;
}

}

void number_list::add(const char* str)
{
    if (str == NULL)
        throw std::invalid_argument("");

    for (;;) {
        int start = get_value(str);
        skip_space(str);

        switch (*str) {
          case _T('\0'):
            data_.push_back(range(start, start));
            canonicalize();
            return;
          case _T(','):
            data_.push_back(range(start, start));
            str++;
            continue;
          case _T('-'):
            str++;
            break;
          default:
            throw std::invalid_argument("");
        }

        int last = get_value(str);

        if (start > last)
            std::swap(start, last);
        data_.push_back(range(start, last));
        skip_space(str);
    
        switch (*str) {
          case _T('\0'):
            canonicalize();
            return;
          case _T(','):
            str++;
            continue;
          default:
            throw std::invalid_argument("");
        }
    }
}

void number_list::add(value_type value)
{
    data_.push_back(range(value, value));
    canonicalize();
}

void number_list::add(value_type v1, value_type v2)
{
    if (v1 > v2)
        std::swap(v1, v2);

    data_.push_back(range(v1, v2));
    canonicalize();
}

bool number_list::remove(value_type value)
{
    Imp::iterator it = std::find_if(data_.begin(),
                                    data_.end(),
                                    less_value_area(value));

    if (it == data_.end())
        return false;

    if (it->first == it->second) {
        // 単一の値の場合
        if (it->first != value)
            return false;
        data_.erase(it);
    } else if (it->first == value) {
        // 連続する値の先頭
        assert(value < it->second);
        it->first++;
        assert(it->first <= it->second);
    } else if (it->second == value) {
        // 連続する値の末尾
        assert(value > it->first);
        it->second--;
        assert(it->first <= it->second);
    } else if (value > it->first) {
        assert(value > it->first && value < it->second);

        range new_value(it->first, value - 1);
        it->first = value + 1;

        assert(new_value.first <= new_value.second);
        assert(it->first <= it->second);
        assert(it->first - new_value.second > 1);

        data_.insert(it, new_value);
    } else {
        return false;
    }
    return true;
}

void number_list::clear()
{
    data_.clear();
}

std::string number_list::get_list() const
{
    if (data_.empty())
        return std::string();

    Imp::const_iterator it = data_.begin();
    std::string str = to_string(*it);
    for (++it; it != data_.end(); ++it) {
        str += ',';
        str +=  to_string(*it);
    }
    
    return str;
}

number_list::const_iterator number_list::get_iterator() const
{
    return const_iterator(*this);
}

number_list::iterator number_list::get_iterator()
{
    return iterator(*this);
}

bool number_list::is_contain(value_type value) const
{
    Imp::const_iterator it = std::find_if(data_.begin(),
                                          data_.end(),
                                          less_value_area(value));

    if (it == data_.end())
        return false;
    return value >= it->first;
}


void number_list::swap(number_list& other)
{
    data_.swap(other.data_);
}

std::string number_list::to_string(const range& value)
{
    char buff[100];
    if (value.first == value.second)
        sprintf(buff, "%d", value.first);
    else
        sprintf(buff, "%d-%d", value.first, value.second);

    return std::string(buff);
}

void number_list::canonicalize()
{
    std::sort(data_.begin(), data_.end());

    Imp::size_type i = 0;
    while (i < data_.size() - 1) {
        assert(data_[i].first <= data_[i + 1].second);

        if (data_[i].first == data_[i + 1].first) {
            if (data_[i].second >= data_[i + 1].second)
                // data_[i] ⊇ data_[i + 1]
                data_.erase(data_.begin() + (i + 1));
            else
                // data_[i] ⊂ data_[i + 1]
                data_.erase(data_.begin() + i);
        } else {
            assert(data_[i].first < data_[i + 1].first);
            if (data_[i].second >= data_[i + 1].first - 1) {
                // data_[i] ∩ data_[i + 1] ≠ φ
                // (隣接の場合も含む)
                if (data_[i].second < data_[i + 1].second) {
                    // 連結
                    data_[i].second = data_[i + 1].second;
                } else {
                    // data_[i] ⊇ data_[i + 1]
                }
                data_.erase(data_.begin() + (i + 1));
            } else {
                // data_[i] ∩ data_[i + 1] ＝ φ
                i++;
            }
        }
    }
}

number_list::const_iterator::const_iterator(const number_list& data) :
        data_(data), index_(0)
{
    if (!data_.data_.empty())
        value_ = data_.data_[0].first;
}

bool number_list::const_iterator::is_end() const
{
    return index_ >= data_.data_.size();
}

number_list::value_type number_list::const_iterator::get() const
{
    assert(!is_end());
    return value_;
}

void number_list::const_iterator::next()
{
    if (is_end())
        return;
            
    if (value_ >= data_.data_[index_].second) {
        index_ ++;
        if (index_ < data_.data_.size())
            value_ = data_.data_[index_].first;
    } else {
        value_ = value_ + 1;
    }

    assert(index_ >= data_.data_.size() ||
           (value_ >= data_.data_[index_].first &&
            value_ <= data_.data_[index_].second));
}

number_list::iterator::iterator(number_list& data) :
        const_iterator(data)
{
}

void number_list::iterator::remove()
{
    if (is_end())
        return;

    const_cast<number_list&>(data_).remove(value_);
    if (!is_end()) {
        if (value_ > data_.data_[index_].first)
            index_++;
        value_ = data_.data_[index_].first;
    }
}

number_list::less_value_area::less_value_area(number_list::value_type value) :
        value_(value)
{
}

bool number_list::less_value_area::operator()(const number_list::range& target) const
{
    return value_ <= target.second;
}

---

使い方のサンプル。

number_list numbers;
numbers.add("1,5-7,12");

number_list::const_iterator it = numbers.get_iterator();
while (!it.is_end()) {
    std::cout << it.get() << "\n";
}

サンプルの出力

1
5
6
7
12

---

上のコードは、元々 Visual Basic .NET で書いたのを C++ で書き直したのですが、C++ なら、こう↓した方が便利だったことに、後から気づきました。

// 【 number_list.h 】
#ifndef __NUMBER_LIST_H
#define __NUMBER_LIST_H

#include        <set>

class number_list : public std::set<int>
{
  public:
    // 扱う値の型
    typedef int value_type;

  public:
    // 値を追加する(文字列指定)
    void add(const char*);

    // 値を文字列で取得する
    std::string get_list() const;
};

#endif

// 【 number_list.cpp 】
#include        "numbers_list.h"
#include        "value_iterator.h"
#include        <sstream>

namespace
{

void skip_space(const char*& str)
{
    for ( ; isspace(*str) ; str++)
        ;
}
int get_value(const char*& str)
{
    skip_space(str);

    char* end;
    int sign = 1;
    if (*str == _T('-')) {
        sign = -1;
        str++;
    }
    if (!isdigit(*str))
        throw std::invalid_argument("");
    
    const long value = sign*strtol(str, &end, 10);
    str = end;

    return value;
}

void append(std::stringstream& out, int start, int end)
{
    if (!out.str().empty())
        out << ',';
    if (start == end) {
        out << start;
    } else {
        out << start << '-' << end;
    }
}

}

void number_list::add(const char* str)
{
    if (str == NULL)
        throw std::invalid_argument("");

    for (;;) {
        int start = get_value(str);
        skip_space(str);

        switch (*str) {
          case _T('\0'):
            insert(start);
            return;
          case _T(','):
            insert(start);
            str++;
            continue;
          case _T('-'):
            str++;
            break;
          default:
            throw std::invalid_argument("");
        }

        int last = get_value(str);

        if (start > last)
            std::swap(start, last);

        insert(value_iterator<value_type,1>(start),
               value_iterator<value_type,1>(last + 1));
        skip_space(str);
    
        switch (*str) {
          case _T('\0'):
            return;
          case _T(','):
            str++;
            continue;
          default:
            throw std::invalid_argument("");
        }
    }
}

std::string number_list::get_list() const
{
    if (empty())
        return std::string();

    std::stringstream out;

    const_iterator it = begin();
    value_type first = *(it++);
    value_type last = first;
    
    while (it != end()) {
        value_type v = *(it++);
        if (v == last + 1) {
            last = v;
        } else {
            append(out, first, last);
            first = last = v;
        }
    }
    append(out, first, last);
    
    return out.str();
}

ちなみ、前回作った「数値のイテレータ化クラス（value_iterator）」をちゃっかり有効利用してたりします。

で、
何が便利かって、イテレータがC++標準の形式になるので（std::setのイテレータなので）、STLにある諸々の関数の恩恵が受けられます。

"1-100000000"とかを扱うのなら、最初の方が良さげですが。

今日の一冊
	雪月花の数学 作者: 桜井 進 出版社/メーカー: 祥伝社 発売日: 2006/07 メディア: 単行本

タグ：C++