class BoostMultiIndex:
  "Pretty Printer for boost::multiindex (Boost.MultiIndex)"
  regex = re.compile('boost::multi_index::multi_index_container<([^,]*),.*>$');
  header_re = re.compile('boost::multi_index::detail::header_holder')
  node_base_re = re.compile('boost::multi_index::detail::index_node_base')
  pod_holder_re = re.compile('boost::multi_index::detail::pod_value_holder')
  index_node_tramp_re = re.compile('boost::multi_index::detail::hashed_index_node_trampoline')
  index_node_impl_re = re.compile('boost::multi_index::detail::hashed_index_node_impl')
  hashed_index_re = re.compile('boost::multi_index::detail::hashed_index')
  ordered_index_re = re.compile('boost::multi_index::detail::ordered_index')
  sequenced_index_re = re.compile('boost::multi_index::detail::sequenced_index')
  sequenced_index_node_impl_re = re.compile('boost::multi_index::detail::sequenced_index_node_impl')
  random_access_re = re.compile('boost::multi_index::detail::random_access_index')

  class HashedIndexIterator:
    def __init__(self, len, hashed_index):
      self.size = len
      self.first_bucket = hashed_index['first_bucket']
      self.bucket_begin = hashed_index['buckets']['spc']['data_']
      self.bucket_size = hashed_index['buckets']['size_']
      self.itr = self.bucket_begin + self.first_bucket
      self.itr = self.itr['next_']
      self.bucket_end = self.bucket_begin + self.bucket_size
  
    def __len__(self):
      return int (self.size)
      
    def __iter__(self):
      return self
      
    def next(self):
      self.itr = self.itr['next_']
      if((self.bucket_begin <= self.itr) and (self.itr <= self.bucket_end)):
        while True:
          self.itr += 1
          if self.itr['next_'] != self.itr:
            break
        self.itr = self.itr['next_']
      return self
    
    def node(self):
      return self.itr

    def index_type(self):
      return "hashed index"
  
  class OrderedIndexIterator:
    def find_left(self, obj):
      for i in obj.type.fields():
        if i.name == "left_":
          return obj['left_']
        else:
          ret = self.find_left(obj.cast(i.type))
          if ret != None:
            return ret

    def __init__(self, len, ordered_index, member):
      self.member = member
      self.ordered_index = ordered_index
      self.size = len
      self.itr = self.find_left(member.dereference())
  
    def __len__(self):
      return int (self.size)
      
    def __iter__(self):
      return self
      
    def next(self):
      if self.itr["right_"] != 0:
          self.itr = self.itr["right_"]
          while self.itr["left_"] != 0:
            self.itr = self.itr["left_"]
      else:
        y = self.itr['parentcolor_'] & ~1
        pointer = self.itr["left_"].type
        y = y.cast(pointer)
        while self.itr == y["right_"]:
          self.itr = y;
          y = y['parentcolor_'] & ~1
          y = y.cast(pointer)
        if self.itr['right_'] != y:
          self.itr = y;
      return self
    
    def node(self):
      return self.itr

    def index_type(self):
      return "ordered index"


  class SequencedIndexIterator:
    def find_next(self, obj):
      for i in obj.type.fields():
        if i.name:
          if BoostMultiIndex.sequenced_index_node_impl_re.match(i.name):
            return obj.cast(i.type)['next_']
          else:
            ret = self.find_next(obj.cast(i.type))
            if ret != None:
              return ret

    def __init__(self, len, ordered_index, member):
      self.member = member
      self.ordered_index = ordered_index
      self.size = len
      #print member.dereference()
      self.itr = self.find_next(member.dereference())
  
    def __len__(self):
      return int (self.size)
      
    def __iter__(self):
      return self
      
    def next(self):
      self.itr = self.itr['next_']
      return self
    
    def node(self):
      return self.itr

    def index_type(self):
      return "sequenced index"
  
  class RandomAccessIndexIterator:
    def __init__(self, len, index):
      self.index = index
      self.size = len
      #print member.dereference()
      self.itr = self.index['ptrs']['spc']['data_'].dereference()
      print self.itr
  
    def __len__(self):
      return int (self.size)
      
    def __iter__(self):
      return self
      
    def next(self):
      up = self.itr['up_'] + 1
      up = up.cast(self.itr['up_'].type)
      self.itr = up.dereference()
      return self
    
    def node(self):
      return self.itr

    def index_type(self):
      return "random access index"
    
  class _iter:
    def __init__(self, itr, membertype, podtype):
      self.itr = itr
      self.membertype = membertype
      self.podtype = podtype
      self.count = 0

    def __iter__(self):
      return self
      
    def next(self):
      if self.count == len(self.itr):
        raise StopIteration
      itr = self.itr
      item = self.itr.node().cast(self.membertype.pointer()).dereference().cast(self.podtype)['space'].cast(self.podtype.template_argument(0))
      result = ('[%d]' % self.count, item)
      self.count += 1
      if self.count != len(self.itr):
        self.itr = self.itr.next()
      return result

    def index_type(self):
      return self.itr.index_type()

    def children(self):
      return self

    def to_string(self):
      return self.itr.index_type()