/home/elb/work/cs590n/mace/mace/lib/mmultimap.h

Go to the documentation of this file.

/* 
 * mmultimap.h : part of the Mace toolkit for building distributed systems
 * 
 * Copyright (c) 2007, Charles Killian, Dejan Kostic, Ryan Braud, James W. Anderson, John Fisher-Ogden, Calvin Hubble, Duy Nguyen, Justin Burke, David Oppenheimer, Amin Vahdat, Adolfo Rodriguez, Sooraj Bhat
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 *    * Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *    * Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in
 *      the documentation and/or other materials provided with the
 *      distribution.
 *    * Neither the names of Duke University nor The University of
 *      California, San Diego, nor the names of the authors or contributors
 *      may be used to endorse or promote products derived from
 *      this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
 * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * 
 * ----END-OF-LEGAL-STUFF---- */
#include <map>
#include "mdeque.h"
#include "mpair.h"
#include "CollectionSerializers.h"
#include "RandomUtil.h"
#include "mace_constants.h"
#include "StrUtil.h"

#ifndef _MACE_MULTIMAP_H
#define _MACE_MULTIMAP_H

namespace mace {



  template<class Key, class Data, class Serial = SerializeMap<Key, Data>, class Compare = std::less<Key>, class Alloc = std::allocator<std::pair<const Key, Data> > >
class multimap : public std::multimap<Key, Data, Compare, Alloc>, public virtual Serial, public PrintPrintable {

  BOOST_CLASS_REQUIRE2(Serial, Serializer, boost, ConvertibleConcept);

public:
  typedef typename std::multimap<Key, Data, Compare, Alloc> baseType;
  typedef typename baseType::iterator iterator;
  typedef typename baseType::const_iterator const_iterator;
  typedef typename baseType::size_type size_type;
  typedef typename baseType::key_compare key_compare;

  multimap() : baseType() {
  }

  multimap(const key_compare& comp) : baseType(comp) {
  }

  virtual ~multimap() { }

  void clear() {
    baseType::clear();
  }
  
  size_t size() const {
    return baseType::size();
  }
  
  bool containsKey(const Key& k) const {
    return find(k) != this->end();
  } // containsKey

  deque<Data> get(const Key& k) const {
    deque<Data> l;
    for (const_iterator i = find(k); i != this->end() && i->first == k; i++) {
      l.push_back(i->second);
    }
    return l;
  } // get
  
  const_iterator random() const {
    if(this->size()==0) { return this->end(); }
    int rand = RandomUtil::randInt(this->size());
    const_iterator i;
    int position;
    for(i = this->begin(), position=0; i != this->end() && position < rand; i++, position++);
    return i;
  }

  const std::string& getTypeName() const {
    const char* types[] = { "Key", "Data", "Compare", "Alloc", 0 };
    static const StrUtilNamespace::StdStringList myTypes = StrUtilNamespace::getTypeFromTemplate(__PRETTY_FUNCTION__, types);
    static string ret = myTypes[0]+"->"+myTypes[1];
    return ret;
  }

  void print(std::ostream& out) const {
    if(mace::PRINT_TYPE_NAMES) {
      out << "mace::MultiMap<" << getTypeName() << ">";
    }
    mace::printMap(out, this->begin(), this->end());
  }
  void printState(std::ostream& out) const {
    if(mace::PRINT_TYPE_NAMES) {
      out << "mace::MultiMap<" << getTypeName() << ">";
    }
    mace::printMapState(out, this->begin(), this->end());
  }

  private:
  class v_const_iterator : public _SerializeMap<Key, Data>::const_iterator {
    private:
      const_iterator i;
      const_iterator end;

    public:
      bool isValid() {
        return i != end;
      }
      void next() {
        ASSERT(i != end);
        i++;
      }
      const Key& getKey() {
        return i->first;
      }
      const Data& getValue() {
        return i->second;
      }

      v_const_iterator(const_iterator beg, const_iterator end) : i(beg), end(end) {}
      ~v_const_iterator() {}
  };

  protected:
    typename _SerializeMap<Key, Data>::const_iterator* getIterator() const {
      return new v_const_iterator(this->begin(), this->end());
    }
    Data& insertKey(const Key& k) {
      iterator i = insert(std::pair<Key, Data>(k, Data()));
      return i->second;
    }

};

}
#endif // _MACE_MULTIMAP_H

---